Social Network Generation: Difference between revisions
| Line 16: | Line 16: | ||
|+ Parameters and Resulting Graph characteristics | |+ Parameters and Resulting Graph characteristics | ||
|- | |- | ||
| graphs || | | graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11||W12 | ||
|- | |- style="background:lightgrey;" | ||
|'''numNodes'''||47||47||47||47||47||47||47||47||47||47||47||94 | |'''numNodes'''||47||47||47||47||47||47||47||47||47||47||47||'''94''' | ||
|- | |- style="background:lightgrey;" | ||
|'''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 | |'''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 | ||
|- | |- style="background:lightgrey;" | ||
|'''degree'''||6||6||6||6||6||2||4||8||10||4||8||8 | |'''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 | |numNodes||47||47||47||47||47||47||47||47||47||47||47||94 | ||
| Line 29: | Line 29: | ||
|- | |- | ||
|components||1||1||1||1||1||2||1||1||1||1||1||1 | |components||1||1||1||1||1||2||1||1||1||1||1||1 | ||
|- | |- style="background:#FFFFCC" | ||
|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 | |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''' | ||
|- | |-style="background:#FFFFCC" | ||
|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 | |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 | |diameter||6||4||4||4||4||-||6||4||3||5||5||6 | ||
| Line 45: | Line 45: | ||
GraphMl files and Pictures | GraphMl files and Pictures | ||
W1 SmallWorld_47_0.1_6 | |||
W2 SmallWorld_47_0.3_6 | |||
W3 SmallWorld_47_0.5_6 | |||
Revision as of 15:26, 6 October 2006
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.
| 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