Back to Journal Cover Page


CURRENT RESEARCH IN SOCIAL PSYCHOLOGY


CURRENT RESEARCH IN SOCIAL PSYCHOLOGY

Volume 1, Number 5

Submitted March 5, 1996
Resubmitted March 29, 1996
Accepted April 3, 1996
Publication Date: April 26, 1996

AN ALGORITHM TO GENERATE CONNECTED GRAPHS*

      John Skvoretz
      University of South Carolina

ABSTRACT

   Connected graphs hold special interest for network exchange 
researchers because all experimentally-studied networks are connected 
graphs. Competing theoretical proposals differ in the predictions they 
make for some sets of connected graphs, but not for other sets. Yet 
researchers do not have at their disposal any catalogue of connected 
graphs for even relatively small-sized groups. In this article, I 
review the theoretical basis for an algorithm that generates all 
connected graphs of a particular size and provide a pseudo-code version 
of the algorithm itself. I then address some considerations regarding 
its use in the network exchange field.

                             [page 43] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 44]

INTRODUCTION

   All of the exchange networks studied experimentally in the field of 
network exchange research are connected graphs, wherein the nodes are 
positions and the lines are exchange relations (i.e., relations in 
which agreement on the terms of exchange produces mutual benefit). 
Further, all positions are connected to one another either directly or 
indirectly. This connectedness of the set of positions is essential 
since the very nature of network exchange research focuses on how 
indirect connections affect the relative power of actors who are 
directly connected to one another. The graphs vary in size, with six 
positions being the largest for which published data exist (Skvoretz 
and Willer 1993).

   Network exchange research presently harbors several contending 
theories of power distribution. Evaluating these theories involves many 
considerations, including parsimony in the assumptive base, breadth of 
coverage, predictive precision, and embeddedness in accepted 
explanatory frameworks (e.g., rational choice theory). One important 
consideration is empirical accuracy: does one proposal make more 
accurate predictions than the others? For many graphs, the contenders 
make very similar predictions and so they cannot be used to assess 
accuracy. Rather, research must use those graphs (if any) for which the 
alternatives make different predictions. Currently, discovery of such 
candidates is a hit-or-miss proposition as there exists no accessible 
catalogue of connected graphs with which to systematically search for 
"critical" networks.

   In addition to the evaluation of empirical accuracy, a catalogue of 
connected graphs could aid in the development of particular approaches, 
as can be exemplified by Lovaglia, Skvoretz, Markovsky, and Willer 
(1995). These authors use a series of "thought experiments" to refine 
the Graph Power Index (GPI) approach first proposed by Markovsky, 
Willer, and Patton (1988): Refinements are proposed to solve 
problematic networks and then evaluated by inspecting the predictions 
offered for other networks of similar size or configuration. Only those 
refinements that offer sensible predictions are retained for 
empirically-based evaluation. Hence, a catalogue of connected graphs is 
needed grist for the "thought experiment" mill.

                             [page 44] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 45]

ALGORITHMS FOR GENERATING GRAPHS

   The problem of generating all connected graphs for a set p of points 
is a combinatorial problem. One procedure for generating combinatorial 
configurations of a certain type is called the "classical method" by 
Read (1978). In this procedure, there are two lists: one of old 
configurations and one of new configurations. Potential candidates for 
the new list are created by performing an operation on an old 
configuration, e.g., adding a node and an edge to one of the points in 
the old configuration. The candidate is added to the new list only if 
it is not already present. Doing this, however, requires checking the 
candidate against each of the items already present on the new list, a 
time-consuming process insofar as there are usually many isomorphic 
versions of any item on the new list, and each of these versions must 
be detected and discarded. For instance, the three networks in Figure 1 
are isomorphic (i.e., they exhibit the same structure). Therefore, on 
any list of connected graphs of size 4, only one of them can appear. As 
the size of the graph and the number of edges grow, the combinatorial 
possibilities explode.

        A - B        B - C        A - C
         \ /          \ /          \ /
          C            A            B
          |            |            |
          D            D            D

      Figure 1.  Three isomorphic graphs.

   Read (1978) proposes a general algorithm that does not require 
looking back over the new list to detect and discard duplicates. In 
this procedure, as each candidate is produced it can be immediately 
tested for inclusion on the new list by simply inspecting the 
configuration itself. Hence, Read titles his paper "Every One a Winner" 
because the candidate is added to the new list only if it is a winner. 
A principle advantage of this algorithm is that the list of new 
elements can be stored externally since searches of it are never 
required.

   Read's "orderly" algorithm may be described as follows. We must 
first specify which of all possible isomorphic configurations will 
represent its class in the list of configurations. This particular 
configuration is called the "canonical configuration." The center graph 
in Figure 1 is the canonical configuration for its isomorphism class. 
Canonicity is defined by representing the upper right triangle of the 
network's adjacency matrix as a binary integer, concatenating the first 
row of this triangle to the second, both to the third, and so on. The 
canonical configuration for the class is the one that produces the 
largest binary integer or code. The codes for the networks in Figure 1 
are 110101, 111100, and 110110, the second one being the largest.

                             [page 45] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 46]

   Second, we must specify an ordering of the list of canonical 
configurations. The binary integers corresponding to each canonical 
configuration form a logical basis for ordering the list. In fact, we 
arrange the list in descending order by these integers.

   Finally, we must define an augmenting operation by which one element 
from an old list can produce an ordered sequence of potential elements 
on a new list in the order they would appear on the new list if they 
were found to be acceptable candidates. The operation we use takes the 
binary code of a canonical configuration of p nodes and q edges and 
produces potential candidates for the list of p nodes and q+1 edges as 
follows. The binary code of the input configuration is scanned from 
right to left to find the rightmost non-zero element. If the code is 
111100, this is the fourth element. Then the candidate configurations 
are created by changing in turn each of the trailing 0's to 1, 
proceeding from left to right. Thus, from 111100 we obtain two 
candidates, 111110 and 111101.

   The algorithm involves processing an old list of canonical 
configurations, taking each element in turn, and creating potential 
candidates for the new list. For each candidate, the algorithm must 
discover if it is a canonical configuration by inspecting permutations 
of rows and columns in the underlying adjacency matrix for an 
equivalent configuration with a larger code value. If this value ever 
equals or exceeds the code value of the last configuration added to the 
new list, the candidate is not a canonical configuration and processing 
can move on to the next candidate. If the configuration is canonical 
and its code value is less than the new list minimum, it is a "winner," 
allowing it to be added directly to the new list and the new list 
minimum to be updated.

   The program that actually generates all connected graphs of a given 
size is presented in pseudo-code form in Table 1. Note that it 
generates all graphs whether connected or not and then retains only 
those that are connected. The algorithm is not effective if its 
operation is confined to just connected graphs. There are connected 
graphs with q+1 edges whose code number is greater than other connected 
graphs with q+1 edges but whose production from the ordered list of 
canonical connected graphs with q edges will occur after the production 
of those graphs with lower code numbers. Consequently, they will never 
be added to the new list. However, they will be produced before these 
other graphs if the augmentation operation applies over all graphs, 
connected or not.

                             [page 46] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 47]

input nodes
initialize file "g00" 
        with bit-string of 0's {length =[nodes(nodes-1)]/2}
for edges = 0 to [nodes(nodes-1)]/2 - 1
  open file "g{nodes}{edges}" for input as #1
  open file "g{nodes}{edges+1}" for output as #2
  open file "g{nodes}{edges+1}c" for output as #3
  initialize current minimum code value
  while not end-of-file #1
    read string from #1
    find rightmost non-zero element of string
    for each trailing zero
      change to 1 and create new adjacency matrix
      for each permutation of rows and columns 
        compare binary number of permuted adjacency matrix with current
                minimum and if greater, try next trailing zero
        compare binary number of permuted adjacency matrix with current
                maximum and if greater, save as new maximum
    set current minimum =3D maximum
    write maximum to #2
    if connected, write maximum to #3
  wend
close #1, #2, #3
end

Table 1: Pseudo-code for an orderly algorithm 
         to generate connected graphs

    Even though the orderly algorithm is relatively more efficient than 
the "classical" approach, it still becomes time consuming as the number 
of nodes increases. On a 90mhz Pentium it will take about 2 hours to 
generate all the connected graphs over 7 nodes, where one finds 853 
non-isomorphic connected graphs. Over 8 nodes, there are 11,118 
connected graphs. Consequently, generating the catalogue of these 
graphs takes literally days of CPU time. Thus, it is unreasonable for 
each researcher to generate his or her own catalogue of connected 
graphs. Instead, the catalogue, once generated, should be made widely 
accessible. Consequently, I supply an Appendix which catalogues all 
connected graphs from size 2 to size 7 and can supply upon request the 
catalogue of size 8 connected graphs. A Sun SparcStation is currently 
at work (on a part-time basis since December) generating all size 9 
connected graphs.

                             [page 47] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 48]

CONCLUSION

   In addition to advancing theoretical inquiry, the catalogue of 
connected graphs can standardize nomenclature for experimental 
networks. For instance, the graph in Figure 2 is called "KITE" in the 
work of Markovsky, Skvoretz, Willer and colleagues (Markovsky, 
Skvoretz, Willer, Lovaglia, and Erger 1993; Skvoretz and Willer 1993) 
and "HOURGLASS" in the work of Bienenstock and Bonacich (1993). The 
catalogue provides a canonical name for this graph: namely, the number 
of nodes, followed by the number of edges, followed by its location in 
the canonical ordering. Thus the graph in Figure 2 has the canonical 
name "p5e6.2" because it is the second graph in the canonical listing 
of all connected graphs with 5 nodes or points and 6 edges.

                    B - C
                     \ /
                      A
                     / \
                    D - E

      Figure 2: The connected graph p5e6.2


   The catalogue also provides a canonical way of labeling the nodes of 
an entry. One simply assigns letters to nodes in alphabetical order and 
then builds the adjacency matrix as specified by the bit string, thus 
standardizing how graphs are drawn for research reports.

   Both uses of the catalogue become more salient as the size of the 
networks investigated becomes larger. Investigators from different 
approaches can more easily communicate with one another over 
problematic graphs since, in switching to a standardized naming system, 
we avoid "pet" names that reflect accidental circumstances surrounding 
an approach's discovery. 

  Thus, the actual use of the catalogue appears to depend on (a) 
maintaining theoretical heterogeneity in exchange network research, (b) 
extending empirical and theoretical investigation to relatively large 
networks (say, 7, 8 and 9 node networks) and (c) making accessible an 
organized catalogue of connected graphs.

  The track record of the network exchange research field over the last 
10 years suggests condition (a) will hold for the foreseeable future. 
The present paper guarantees the satisfaction of condition (c). And the 
internal dynamic of theoretical development via conjecture and 
refutation pushes the explanatory envelope in the direction consistent 
with condition (b). Only empirical extension may lag for the usual 
budgetary reasons.

                             [page 48] 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                             [page 49]

ENDNOTE

*Reviewers provided helpful comments and suggestions. Address 
correspondence to: skvoretz-john@sc.edu

REFERENCES

Bienenstock, E.J. and P. Bonacich. 1993. "Game-Theory Models for 
Exchange Networks: Experimental Results." Sociological Perspectives 36: 
117-35.

Lovaglia, M., J. Skvoretz, B. Markovsky, and D. Willer. 1995. 
"Assessing Fundamental Power Differences in Exchange Networks: 
Iterative GPI." Current Research in Social Psychology 1(2): 8-15, 
http://www.uiowa.edu/~grpproc.

Markovsky, B., J. Skvoretz, D. Willer, M. Lovaglia and J. Erger. 1993. 
"The Seeds of Weak Power: An Extension of Network Exchange Theory." 
American Sociological Review 58: 197-209.

Markovsky, B., D. Willer, and T. Patton. 1988. "Power Relations in 
Exchange Networks." American Sociological Review 53: 220-36.

Read, R.C. 1978. "Every One a Winner or How to Avoid Isomorphism Search 
When Cataloguing Combinatorial Configurations." Annals of Discrete 
Mathematics 2: 107-120.

Skvoretz, J. and D. Willer. 1993. "Exclusion and Power: A Test of Four 
Theories of Power in Exchange Networks." American Sociological Review 
58: 801-18.

AUTHOR BIOGRAPHY

John Skvoretz is a Carolina Distinguished Professor of Sociology at the 
University of South Carolina. Current research projects concern formal 
models of social networks, status and participation in discussion 
groups, power in exchange networks, and theoretical studies of action 
structures. He is the editor of Connections, the bulletin of the 
International Network for Social Network Analysis and an Associate 
Editor of the Journal of Mathematical Sociology.

Appendix

Back to Journal Cover Page