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

Sparse is well defined, but only in terms of networks whose size varies.  A
network is sparse if the mean degree of a node increases slower than
linearly with the number of nodes.  Thus it may be straightforward to
demonstrate that, for instance, a friendship network is sparse, if the
average number of friends a person has does not double when the population
doubles.  For other networks there's no rigorous way to demonstrate
sparseness because you have only one snapshot of the network, so you cannot
gauge the effect of changing size.

As Brian Keegan points out, short path length usually means scaling as the
log of the network size or slower, but again this can only be established
for networks that actually have varying size.

High clustering (also called transitivity) is somewhat more difficult.  In
the influential 1998 paper by Watts and Strogatz, Nature 393, 440-442
(1998) they defined a network as having high clustering if its clustering
is high compared to the corresponding random graph -- i.e., a network with
the same number of nodes and edges, but with edges placed completely at
random.  However, it turns out that this is not always a good comparison,
because the random graph has unusually low clustering.  If you compare,
say, a graph representation of the Internet against the corresponding
random graph, you find that its clustering is "high" in this sense.
However, if you compare the same Internet against a random graph in which
the degrees of vertices have been fixed to be the same as those for the
Internet (called the "configuration model" by mathematicians), then you
find its clustering is much *lower* than the random graph.  Many people
would say that the random graph with correct degrees is a better model to
compare against than the original random graph, and hence that the Internet
should be considered as having low clustering, not high.  This, however, is
still an open point of discussion, and hence for the moment there is no
accepted standard against which one should compare levels of clustering.

Mark Newman

On 05/28/2010 10:11 AM, Jordi Comas wrote:
> Hello friends-
> When I explain a SWN to new students, I say “relatively large,
> relatively sparse network with local clustering and surprisingly low
> average path length.”
> I have been wondering if any more math-oriented people have defined
> large, sparse, and clustered in precise terms. To me, intuitively, a
> small and/or dense network may look like SWN, but it is uninteresting.
> Of course they are cohesive!
> Any thoughts or references?
> Thanks-
> Jordi
> Jordi Comas
> Assistant Professor
> School of Management
> Bucknell University

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.