Print

Print


*****  To join INSNA, visit http://www.insna.org  *****

On 16 Jan 2006, at 9:28, Moses Boudourides wrote:

> *****  To join INSNA, visit http://www.insna.org  *****
>
> Juno, what you're asking essentially is the following: given n  
> nodes, find
> the number of all regular graphs with diameter 2. Of course, the  
> complete
> graph is one of these graphs but I guess you want to exclude it,  
> right?

Actually, he wants the number of _minimal_ regular graphs on n  
vertices with diameter 2 (which would exclude the complete graph for  
n > 2).

> I'm not sure if this (as a combinatorical problem) is solvable but  
> I'll
> give a try to it (when I find time) and in case I reach to a  
> formula I'll
> send it to you.

I'm not sure there's a _closed form_ solution, although there's  
always a painful brute-force solution for a given value of n:  
generate all possible 2^(n^2) graphs and check each one, and then  
cross-check the results to remove isomorphic copies.  :)  (Okay,  
technically it would be 2^((n)(n-1)/2), but close enough.)  You  
actually might want to try doing this for a few (small!) values of n  
to see if you can spot a pattern.

More usefully, this sort of question is very common in the graph  
theory literature; that's probably the best place to look for answers.

> Formulating this problem in terms of sociomatrices, it becomes: How  
> many
> symmetric nxn matrices with entries 0 or 1 exist in such a way  
> every row
> (or column) has the same number (sum) of 1s, which are either isolated
> (having 0 to their right and left) or there are at most two  
> consecutive 1s
> (surrounded by 0s).

I'm not sure this formulation is correct, for three reasons:
(1) I don't see why it should matter whether any two 1s are in  
adjacent rows/columns, since the ordering of the vertices is  
presumably arbitrary.
(2) I don't see how these conditions guarantee that the diameter is  
<= 2.  (One easy way to do this is to square the adjacency matrix A,  
and check to make sure that A_ij + (A^2)_ij > 0 for all i, j such  
that i != j.)
(3) How do these conditions guarantee that the resultant graph is  
minimal?

I'd be happy to find that it's simply the case that my graph theory  
is rusty, of course...

A final question for Juno: what is the difference metric that you're  
using?

Good luck--

Joshua O'Madadhain

>
> Incidentally in your example (n = 6) there is a third graph that  
> you need
> to consider and this is the following
>
> n 1 2 3 4 5 6
> 1   1     1 1
> 2 1   1 1
> 3   1   1   1
> 4   1 1   1
> 5 1     1   1
> 6 1   1   1
>
> --Moses
>
>
> On Mon, 16 Jan 2006, Juno Blaauw wrote:
>
>> *****  To join INSNA, visit http://www.insna.org  *****
>>
>> Hello SOCNETTERS,
>>
>> My name is Juno Blaauw and I am a political research student at the
>> University of Amsterdam. I am writing this e-mail on behalf of  
>> Meindert
>> Fennema, Jean Tillie and myself.
>>
>> Meindert Fennema and Jean Tillie are studying ethnic civic  
>> communities.
>> Lately they have been interested (among other things) in  
>> introducing a
>> normative definition of a civic community and in measuring the  
>> difference
>> between a given empirical civic community and this normative  
>> definition. I
>> have been working with them on this (thesis). We have been able to  
>> formulate
>> a, in our eyes, satisfactory definition of a normative civic  
>> community,
>> which we have called an 'old boys civic community', and a measure  
>> for the
>> above mentioned difference. The only problem is that our normative
>> definition does not lead to one unique social network. In other  
>> words: on a
>> given number of nodes many social networks qualify as old boys civic
>> communities.
>>
>> Before getting to the specific question we would like to ask you all,
>> I willfirst give you our definitions. First of all our definition  
>> of a
>> civic
>> community: "a civic community [...] consists of many voluntary  
>> associations
>> that are related to each other by way of overlapping membership and
>> interlocking directorates' (Fennema, 2004, p. 433.)" The voluntary
>> associations are formal organisations and the interlocking  
>> directorates are
>> people that are board members of two of these organisations. Thus,  
>> a civic
>> community can be defined as the set of formal organisations and  
>> the ties, in
>> the form of interlocking directorates, between them. A civic  
>> community that is
>> defined like this can be depicted as a graph were the nodes
>> representorganisations and the lines interlocking directorates.
>>
>> Secondly, our definition of an old boys civic community: A civic  
>> community
>> is an old boys civic community if and only if (a) any two  
>> organisations are
>> either directly linked by an interlocking directorate or have a  
>> maximum of
>> two interlocking directorates between them and (b) each of the
>> civiccommunity's organisations is adjacent to the same number of
>> otherorganisations.
>>
>> Now, the question we would like to ask all of you is this: how can  
>> we find
>> out how many and which old boys civic communities there are on a
>> givennumber of nodes? Note that we are only interested in minimal old
>> boys civic
>> communities, that is in old boys civic communities with a minimal  
>> number of
>> interlocking directorates (ties).
>>
>> To illustrate our problem: Here are two minimal old boys civic  
>> communities
>> on six nodes. Are these the only two? If so, how can we proof  
>> that? If not,
>> how can we find the other ones?
>>
>> n 1 2 3 4 5 6
>> 1   1   1   1
>> 2 1   1   1
>> 3   1   1   1
>> 4 1   1   1
>> 5   1   1   1
>> 6 1   1   1
>>
>> and
>>
>> n 1 2 3 4 5 6
>> 1   1 1     1
>> 2 1   1   1
>> 3 1 1   1
>> 4     1   1 1
>> 5   1   1   1
>> 6 1     1 1
>>
>> We have no idea whether or not this is actually an easy problem  
>> that has
>> already been solved by somebody else. We are just hoping that you  
>> can inform
>> us of anything you seem fit, given what we have told you so far.
>>
>>  Please let me know if you need any additional information. Thank  
>> you in
>> advance!

jmadden@ics.uci.edu...Obscurium Per Obscurius...www.ics.uci.edu/~jmadden
Joshua O'Madadhain: Information Scientist, Musician, and Philosopher- 
At-Tall
   It's that moment of dawning comprehension that I live for--Bill  
Watterson
   My opinions are too rational and insightful to be those of any  
organization.

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.