***** To join INSNA, visit http://www.insna.org *****

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

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,

-Carter

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