Social Network Generation: Difference between revisions
No edit summary |
|||
| Line 4: | Line 4: | ||
). 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. | ). 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: | 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. | |||
{| border="1" | |||
|+ Parameters and Resulting Graph characteristics | |||
|- | |||
| graphs || wSmallWorld_47_0.1_6 ||wSmallWorld_47_0.3_6 || wSmallWorld_47_0.5_6 | |||
|- | |||
|'''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 | |||
wSmallWorld_47_0.1_6 | |||
wSmallWorld_47_0.3_6 | |||
wSmallWorld_47_0.5_6 | |||
Revision as of 14:57, 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 | wSmallWorld_47_0.1_6 | wSmallWorld_47_0.3_6 | wSmallWorld_47_0.5_6 | |||||||||
| 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
wSmallWorld_47_0.1_6 wSmallWorld_47_0.3_6 wSmallWorld_47_0.5_6