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