Small World Detection?

Aug 23, 2013 at 6:18 PM
I'm guessing there's nothing inherent in your software to determine if a network is a small-world or not, but do you know of any reliable ways to figure this out? Certain metrics I could combine or create a formula for, etc.? Ideally, I'd want to know the proportion of networks from a sample that are generally small-world, scale-free, and random.

Any suggestions or points in the right direction would be appreciated!
Aug 31, 2013 at 5:19 PM
You are correct, NodeXL does not (yet) have a feature to measure the "small worlds" quality of a network.

I asked one of our project contributors, Dr. Cody Dunne, for a suggestion and he wrote me back with:
What about the characteristic path length (L) and clustering coefficient (C) measures from the Watts and Strogatz paper, versus the L and C of a random network? In Table 1, they define small-world phenomenon to be:

    L >= L_random AND C >> C_random

It seems like some sort of metric could be built from those measures.

Here is the paper reference:
   Watts, D. J. & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature, 1998, 393, 440-442. DOI:10.1038/30918

Hope that helps.

Sep 4, 2013 at 2:18 PM
Thanks so much, Marc!

I'd come across this paper before, but for whatever reason, I decided to disregard it.

If you have a few moments to look it over, I'd love some input on my analysis plan:

So I ended up with 43 networks of different Twitter hashtags. My goal was to identify some common structural elements, but what I found instead (which I identified visually based on the network's appearance) were three "types" of networks: more centralized, more clustered, and hybrids having elements of each. Obviously the largest group was the hybrid group.

Then I did a number of tests of difference of means to make sure that the groups were significantly different across a number of the usual network metrics. I also tested the difference of means of the average proportion of certain triad types that imply certain structures. From here, I plan to take a look at the hashtags themselves to see if there is some qualitative difference between which types of hashtags develop which types of networks.

As for the small-world problem, since I'm looking at three groups, do you think it would be sufficient to take the average node and edge count for each group, generate a number of random graphs based on those, and compare each group's average shortest path length and clustering coefficient to the randomly generated networks'? The end result would theoretically be to determine which GROUPS rather than individual networks are most representative of the small-world phenomenon.

Any input is appreciated. :)