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

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

And don't forget that, as Mark Newman himself says in the forementioned survey (in the sentence preceding the one quoted by Brian), plain random graphs also have logarithmic (thus very short) average path lenghs.

When you say, 'om my, what a small world, dear!', it's more because you unexpectedly see Tom at Harry's party (thus because of a high clustering coefficient) than because Dick is at six handshakes from you (which you probably won't ever know let alone care about).
If everybody is supposedly at six handshakes from each other, then by definition six handshakes is a very long distance (if the distance were to express the likelyhood of anything in common).

But maybe that was not the question... :)

_
Liafa, University Paris-Diderot                           http://liafa.fr/~prieur/
[user experience research, social networks, (large) graph algorithms]

Le 28 mai 2010 à 17:20, Mark Newman a écrit :

> *****  To join INSNA, visit http://www.insna.org  *****
>
> 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 (http://www.insna.org). To unsubscribe, send