Social Network Generation

From InfoVis:Wiki
Jump to navigation Jump to search

Issues on Social Network Generation for Evaluating Visualizations

Watts and Strogatz first described in (Watts, D. J. and S. H. Strogatz (1998). "Collective dynamics of 'small-world' networks." Nature 393: 440 - 442) the concept of small-world networks. They formalized these networks as graphs with three properties: power-law degree distribution, high clustering coefficient and small average shortest path. In the same paper they propose a basic model fitting these properties consisting in a grid (fixed local neighborhood) with additional links simulating some unexpected relations support to the six degrees of separation discovered by Milgram (Milgram, S. (1967). "The small world problem." Psychology Today: 60-67). Barabási and Albert proposed an incremental model to improve it (Barabási, A.-L. and R. Albert (1999). "Emergence of Scaling in Random Networks." Science 286(5439): 509 - 512. ). Since Watts and Strogatz’ model, several have been proposed each generating networks with one or two of the described properties (power-law) but none combine the three of them.

Here are some results of available generators present in the JUNG package.

Small-World Generator

WattsBetaSmallWorldGenerator

Parameters: numNodes (the number of nodes in the ring lattice), beta (the probability of an edge being rewired randomly; the proportion of randomly rewired edges in a graph) and degree( the number of edges connected to each vertex; the local neighborhood size). Degree must be even.

Parameters and Resulting Graph characteristics
graphs W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12
numNodes 47 47 47 47 47 47 47 47 47 47 47 94
beta 0.1 0.3 0.5 0.7 0.9 0.3 0.3 0.3 0.3 0.7 0.1 0.1
degree 6 6 6 6 6 2 4 8 10 4 8 8
numNodes 47 47 47 47 47 47 47 47 47 47 47 94
numEdges 282 282 282 282 282 94 188 376 470 188 376 752
components 1 1 1 1 1 2 1 1 1 1 1 1
density 0.36 0.36 0.36 0.36 0.36 0.21 0.29 0.41 0.46 0.29 0.41 0.29
clusteringCoefficient 0.51 0.25 0.15 0.09 0.12 0.23 0.25 0.32 0.38 0.07 0.53 0.52
diameter 6 4 4 4 4 - 6 4 3 5 5 6
averageShortestDistance 2.97 2.4 2.32 2.3 2.29 - 3.24 2.15 1.98 2.83 2.56 3.15
minDegree 5 4 4 3 4 1 2 5 8 2 7 6
maxDegree 8 9 9 9 9 4 6 10 13 8 10 10

GraphMl files and Pictures

W1 SmallWorld_47_0.1_6 W2 SmallWorld_47_0.3_6 W3 SmallWorld_47_0.5_6