Print

Print


*****  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? 
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.

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).

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!
> 
> Juno Blaauw.
> 
> _____________________________________________________________________
> 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.
> 

_____________________________________________________________________
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.