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