*****  To join INSNA, visit  *****

Guy Hagen wrote:

> However, I am thinking it might be useful to be able to describe  global 
> measures for such things.  Perhaps, cliquishness= the  percentage of 
> network actors that belong to identified cliquesets?   global 
> equivalency = the percentage of network actors that belong to  
> identified structural/regular/eigenvector equivalent sets?
> I'll be interested in everybody's thoughts and/or citations.

There are a number of tools in the literature which can be deployed in 
service of these questions.  With respect to the former, the simplest 
measure is likely the density of triangles (i.e., the fraction of triads 
which are complete); the mean of the co-clique membership matrix (the 
adjacency matrix whose i,j entry is the number of cliques to which both 
i and j belong) is another.  One can come up with numerous variants of 
these sorts of measures, and the best one(s) to deploy will obviously 
depend on the specifics of the problem under study.

With respect to the second question, what you call the "equivalency" of 
a network is closely related to the algorithmic complexity of the 
associated graph.  Intuitively, graphs which can be reduced to small 
blockmodels can be regenerated using a relatively small amount of 
information, and are hence "simple."  One stab at this idea can be found 
in a paper of mine (see below), which applied a Lempel-Ziv based index 
to network data from a number of sources.  Everett's role complexity 
index is another variation on this theme, as it effectively measures the 
extent to which positions within a graph are distinct under permutation. 
  (Specifically, the role complexity index is 1-|Aut G|/|Perm G|, where 
Aut G and Perm G are the automorphism and permutation groups on G, 
respectively.)  This, in turn, is closely related to Mowshowitz's orbit 
information index, which is the entropy of a random draw from the set of 
orbits (automorphic equivalence classes) on G.  A discussion/comparison 
of these and several other measures can be found in the JMS paper listed 

Butts, C.T.  2000.  "An Axiomatic Approach to Network Complexity." 
Journal of Mathematical Sociology, 24(4), 273-301.

Butts, C.T. 2001. "The Complexity of Social Networks: Theoretical and 
Empirical Findings." Social Networks, 23(1), 31-71.

Everett, M.C.  1985.  "Role Similarity and Complexity in Social 
Networks."  Social Networks, 7, 353-359.

Mowshowitz, A.  1968.  "Entropy and the Complexity of Graphs I: An Index 
of the Relative Complexity of a Graph."  Bulletin of Mathematical 
Biophysics, 30, 175-204.

Hope that helps,


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