Social Network Generation: Difference between revisions

Latest revision as of 11:27, 2 March 2010

This wiki page is under construction...

Research work and images have been realised by Nathalie Henry and Jean-Daniel Fekete, using MatrixExplorer, built with the Infovis Toolkit.

Social Network Characterization

Social networks involve persons or groups called actors and relationship between them, with a lot of variety in the kind of actors and relationships. As described in Wasserman and Faust, actors can be people, subgroups, organizations or collectivities; relations may be friendship (relationships), interactions, communications, transactions, movement or kinship. However, the nature of actors and relations does not really matter: we focus on their structure. We can classify the social networks studied in the literature in three categories:

Tree-like are trees with additional links forming cycles with a specified probability. This category includes genealogy data and very sparse graphs such as Sexually-Transmitted Disease (STD) transmission patterns. We call them “almost trees” because they have are mostly acyclic and nodes have very few parents.
Almost complete graphs are complete graphs with missing relations. For example, data about trade between countries, cities or companies are almost complete graphs. They are interesting to study as valued graphs; since they usually carry values on their edges.
Small-world networks (also scale-free or power-law degree-distribution networks) have been studied intensely since they were first described in Watts and Strogatz. They defined them as graphs with three properties: power-law degree distribution, high clustering coefficient and small average shortest path. They are locally dense (sparse with dense sub-graphs).

Three methods exist to select datasets for assessing the quality of analysis systems in the context of social networks: selecting one or two real datasets hoping they are representative, selecting several datasets or generating random datasets with well-known characteristics shared by social networks. With this last method, one should generate datasets with a controlled set of properties and evaluate the systems knowing the properties in advance. It should then eliminate biases linked to a particular dataset and eases the replication of experiments. Unfortunately, while generating tree-like and almost-complete graphs is relatively straightforward, generating graphs with a small-world network structure is still a research topic for computer scientists and physicists. This page shows the results of popular and available network generators. In light of the real social networks we present in the #Real Social Networks, we consider them unsuitable for evaluations since users can easily notice their artifical nature.

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. Let's note that for each network generated we only keep the biggest component. Generators present in Pajek[1] and Geomi[2] are incremental scale-free networks generators such as the Barabasi and Albert model.

About datasets and representations

All datasets are downloadable in GraphMl format.
Node-Link diagrams are ordered with the linLog algorithm of Andreas Noack [Graph Drawing 2005] (with edge-repulsion coefficient of 2.5f).
Matrices are shown both with the initial order (middle image) and reordered with the TSP-Based algorithm (right image) described by Henry and Fekete [Infovis 2006].

Small-World Generators

WattsBetaSmallWorldGenerator

Parameters: numVertices (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
numVertices	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
numVertices	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

W1 SmallWorld_47_0.1_6.xml

W2 SmallWorld_47_0.3_6.xml

W3 SmallWorld_47_0.5_6.xml

W4 SmallWorld_47_0.7_6.xml

W5 SmallWorld_47_0.9_6.xml

W6 SmallWorld_47_0.3_2.xml

W7 SmallWorld_47_0.3_4.xml

W8 SmallWorld_47_0.3_8.xml

W9 SmallWorld_47_0.3_10.xml

W10 SmallWorld_47_0.7_4.xml

W11 SmallWorld_47_0.1_8.xml

W12 SmallWorld_94_0.1_8.xml

KleinbergSmallWorldGenerator

Parameters:latticeSize (the lattice size (length of row or column dimension)) and clusteringExponent (the clustering exponent parameter).

Parameters and Resulting Graph characteristics
graphs	W1	W2	W3	W4	W5	W6	W7	W8	W9	W10	W11
latticeSize	7	7	7	7	7	7	7	10	10	10	10
clusteringExponent	0.1	0.5	1	2	2.5	4	8	2	4	8	12
numVertices	49	49	49	49	49	49	49	100	100	100	100
numEdges	490	490	490	490	490	490	490	1000	1000	1000	1000
components	1	1	1	1	1	1	1	1	1	1	1
density	0.45	0.45	0.45	0.45	0.45	0.45	0.45	0.32	0.32	0.32	0.32
clusteringCoefficient	0.08	0.09	0.14	0.19	0.19	0.26	0.32	0.18	0.23	0.32	0.33
diameter	4	4	4	4	4	5	5	5	6	7	7
averageShortestDistance	2.38	2.36	2.37	2.44	2.48	2.54	2.73	3.1	3.57	3.65	3.68
minDegree	9	9	9	9	9	9	9	9	9	9	9
maxDegree	14	12	13	12	12	13	12	13	13	14	12

W1 SmallWorld_49_0.1.xml

W2 SmallWorld_49_0.5.xml

W3 SmallWorld_49_1.0.xml

W4 SmallWorld_49_2.0.xml

W5 SmallWorld_49_2.5.xml

W6 SmallWorld_49_4.0.xml

W7 SmallWorld_49_8.0.xml

W8 SmallWorld_100_2.0.xml

W9 SmallWorld_100_4.0.xml

W10 SmallWorld_100_8.0.xml

W11 SmallWorld_100_12.0.xml

Scale-Free Networks Generator

BarabasiAlbertGenerator

Parameters: init_vertices (number of vertices that the graph should start with), numEdgesToAttach (the number of edges that should be attached from the new vertex to pre-existing vertices at each time step) and numSteps (number of time steps). init_vertices must be superior or equal to numEdgesToAttach.

Parameters and Resulting Graph characteristics
graphs	W1	W2	W3	W4	W5	W6	W7	W8
init_vertices	4	4	4	4	2	2	2	4
numEdgesToAttach	2	2	2	1	1	1	2	4
numSteps	10	50	100	100	100	50	50	50
numVertices	14	53	104	80	76	51	52	54
numEdges	40	200	400	158	150	100	200	400
components	1	1	1	1	1	1	1	1
density	0.45	0.27	0.19	0.16	0.16	0.2	0.27	0.37
clusteringCoefficient	0.15	0.2	0.07	0.51	0.51	0.66	0.16	0.23
diameter	4	6	6	11	14	8	5	4
averageShortestDistance	2.24	2.81	3.18	5.26	5.7	3.74	2.8	2.15
minDegree	2	1	2	1	1	1	2	4
maxDegree	5	16	19	8	12	16	17	26

W1 ScaleFree_4_2_10.xml

W2 ScaleFree_4_2_50.xml

W3 ScaleFree_4_2_100.xml

W4 ScaleFree_4_1_100.xml

W5 ScaleFree_2_1_100.xml

W6 ScaleFree_2_1_50.xml

W7 ScaleFree_2_2_50.xml

W8 ScaleFree_4_4_50.xml

EppsteinPowerLawGenerator

Parameters: numVertices (the number of vertices for the generated graph), numEdges (the number of edges the generated graph will have, should be Theta(numVertices)) and r (the model parameter).

Real Social Networks

Here is a panel of undirected networks issued from scientific articles, benchmarks or contests. Social network visualization or analysis tools provide also some real datasets: Pajek [3] and UCINet [4].

Small-World

Parameters and Resulting Graph characteristics for Co-Authoring Networks	Name	Team Collaboration (with external collaborators)	Infovis component 1	Infovis component 2	Infovis component 3	Infovis component 4
Source	Collected	Contest	Contest	Contest	Contest
numNodes	146	135	48	47	32
numEdges	540	321	91	114	109
components	1	1	1	1	1
density	0.16	0.13	0.2	0.23	0.33
clusteringCoefficient	0.91	0.82	0.79	0.83	0.81
diameter	4	11	7	10	6
averageShortestDistance	2.65	4.4	3.71	3.84	2.6
minDegree	1	1	1	1	1
maxDegree	57	22	11	15	15

TeamCollaborationExternal TeamCollaborationExternal.xml

Infovis Component 1 ivComp1.xml

Infovis Component 2 ivComp2.xml

Infovis Component 3 ivComp3.xml

Infovis Component 4 ivComp4.xml

Tree-like

Parameters and Resulting Graph characteristics for Genealogy and Virus Transmission	Name	genealogy	MSTTransmission1	MSTTransmission2	HIVTransmission
Source	Pajek	Article [5]	Article[6]	Article [7]
numVertices	242	38	84	243
numEdges	510	78	182	514
components	1	1	1	1
density	0.09	0.23	0.16	0.09
clusteringCoefficient	0.66	0.53	0.52	0.65
diameter	11	10	9	23
averageShortestDistance	5.78	4.42	4.31	8.27
minDegree	1	1	1	1
maxDegree	14	7	17	20

Gondola Genealogy GondolaGen.xml

MSTTransmission 1 Mst1.xml

MSTTransmission 2 Mst2.xml

HIV Transmission Hiv.xml

Almost Complete Graphs

Parameters and Resulting Graph characteristics for Email Communication within a research lab.
Name	emailDay per person	emailWeek per person	emailMonth per person	emailYear per person	emailDay per team	emailWeek per team	emailMonth per team	emailYear per team
Source	Collected	Collected	Collected	Collected	Collected	Collected	Collected	Collected
numVertices	134	200	242	447	30	33	35	42
numEdges	442	1676	3514	11462	183	410	564	980
components	1	1	1	1	1	1	1	1
density	0.16	0.2	0.24	0.24	0.45	0.61	0.68	0.75
clusteringCoefficient	0.52	0.55	0.62	0.71	0.62	0.78	0.83	0.84
diameter	9	7	6	6	5	3	3	3
averageShortestDistance	4.29	2.92	2.52	2.42	2.17	1.71	1.57	1.45
minDegree	1	1	1	1	1	1	1	3
maxDegree	15	51	86	195	16	26	34	40

Email exchange per person during a day emailDay.xml

Email exchange per person during a week emailWeek.xml

Email exchange per person during a month emailMonth.xml

Email exchange per person during a year emailYear.xml

Email exchange per research group during a day emailGDay.xml

Number of email coded with link width in the nodelink, edge color in the matrix

Email exchange per research group during a week emailGWeek.xml

Number of email coded with link width in the nodelink, edge color in the matrix

Email exchange per research group during a month emailGMonth.xml

Number of email coded with link width in the nodelink, edge color in the matrix

Email exchange per research group during a year emailGYear.xml

Number of email coded with link width in the nodelink, edge color in the matrix

Social Network Generation: Difference between revisions

Latest revision as of 11:27, 2 March 2010

Contents

Social Network Characterization

Issues on Social Network Generation for Evaluating Visualizations

About datasets and representations

Small-World Generators

Scale-Free Networks Generator

Real Social Networks

Small-World

Tree-like

Almost Complete Graphs

Navigation menu

@@ Line 1: / Line 1: @@
+This wiki page is under construction...
+Research work and images have been realised by Nathalie Henry and Jean-Daniel Fekete, using MatrixExplorer, built with the Infovis Toolkit.
+== Social Network Characterization ==
+Social networks involve persons or groups called actors and relationship between them, with a lot of variety in the kind of actors and relationships.  As described in Wasserman and Faust, actors can be people, subgroups, organizations or collectivities; relations may be friendship (relationships), interactions, communications, transactions, movement or kinship.  However, the nature of actors and relations does not really matter: we focus on their structure.  We can classify the social networks studied in the literature in three categories:
+* Tree-like are trees with additional links forming cycles with a specified probability. This category includes genealogy data and very sparse graphs such as Sexually-Transmitted Disease (STD) transmission patterns.  We call them “almost trees” because they have are mostly acyclic and nodes have very few parents.
+* Almost complete graphs are complete graphs with missing relations. For example, data about trade between countries, cities or companies are almost complete graphs.  They are interesting to study as valued graphs; since they usually carry values on their edges.
+* Small-world networks (also scale-free or power-law degree-distribution networks) have been studied intensely since they were first described in Watts and Strogatz.  They defined them as graphs with three properties: power-law degree distribution, high clustering coefficient and small average shortest path.  They are locally dense (sparse with dense sub-graphs).
+Three methods exist to select datasets for assessing the quality of analysis systems in the context of social networks: selecting one or two real datasets hoping they are representative, selecting several datasets or generating random datasets with well-known characteristics shared by social networks.  With this last method, one should generate datasets with a controlled set of properties and evaluate the systems knowing the properties in advance.  It should then eliminate biases linked to a particular dataset and eases the replication of experiments.  Unfortunately, while generating tree-like and almost-complete graphs is relatively straightforward, generating graphs with a small-world network structure is still a research topic for computer scientists and physicists.  This page shows the results of popular and available network generators.  In light of the real social networks we present in the [[#Real Social Networks]], we consider them unsuitable for evaluations since users can easily notice their artifical nature.
-This wiki page is still in construction...
 == Issues on Social Network Generation for Evaluating Visualizations ==
@@ Line 8: / Line 19: @@
 ).  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.
+Here are some results of available generators present in the JUNG package. Let's note that for each network generated we only keep the biggest component.  Generators present in Pajek[http://vlado.fmf.uni-lj.si/pub/networks/pajek/] and Geomi[http://www.cs.usyd.edu.au/~visual/valacon/geomi/] are incremental scale-free networks generators such as the Barabasi and Albert model.
+=== About datasets and representations ===
+* All datasets are downloadable in GraphMl format.
+* Node-Link diagrams are ordered with the linLog algorithm of Andreas Noack [Graph Drawing 2005] (with edge-repulsion coefficient of 2.5f).
+* Matrices are shown both with the initial order (middle image) and reordered with the TSP-Based algorithm (right image) described by Henry and Fekete [Infovis 2006].
-=== Small-World Generator ===
+=== Small-World Generators ===
 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.
+'''numVertices''' (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
+|  Parameters and Resulting Graph characteristics
 |-
 | 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'''
+|'''numVertices'''||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
@@ Line 28: / Line 45: @@
 |'''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
+|numVertices||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
@@ Line 47: / Line 64: @@
 |}
-GraphMl files and Pictures:
+W1 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.1_6.xml SmallWorld_47_0.1_6.xml]
-* Node-Link diagrams are ordered with the linLog algorithm of Andreas Noack [Graph Drawing 2005] (with edge-repulsion coefficient of 2.5f).
-* Matrices are shown both with the initial order (middle image) and reordered with the TSP-Based algorithm (right image) described by Henry and Fekete [Infovis 2006].
-W1 [[SmallWorld_47_0.1_6]]
 [[image:wSmallWorld_47_0.1_6.JPG|150px]]
@@ Line 58: / Line 71: @@
-W2 SmallWorld_47_0.3_6
+W2 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.3_6.xml SmallWorld_47_0.3_6.xml]
 [[image:wSmallWorld_47_0.3_6.JPG|150px]]
@@ Line 65: / Line 78: @@
-W3 SmallWorld_47_0.5_6
+W3 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.5_6.xml SmallWorld_47_0.5_6.xml]
 [[image:wSmallWorld_47_0.5_6.JPG|150px]]
@@ Line 71: / Line 84: @@
 [[image:wSmallWorldM_47_0.5_6.PNG|165px]]
-W4 SmallWorld_47_0.7_6
+W4  [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.7_6.xml SmallWorld_47_0.7_6.xml]
 [[image:wSmallWorld_47_0.7_6.JPG|150px]]
@@ Line 77: / Line 90: @@
 [[image:wSmallWorldM_47_0.7_6.PNG|165px]]
-W5 SmallWorld_47_0.9_6
+W5 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.9_6.xml SmallWorld_47_0.9_6.xml]
 [[image:wSmallWorld_47_0.9_6.JPG|150px]]
@@ Line 83: / Line 97: @@
 [[image:WSmallWorldM_47_0.9_6.PNG|165px]]
-W6 SmallWorld_47_0.3_2
+W6  [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.3_2.xml SmallWorld_47_0.3_2.xml]
 [[image:wSmallWorld_47_0.3_2.JPG|150px]]
@@ Line 89: / Line 103: @@
 [[image:WSmallWorldM_47_0.3_2.PNG|165px]]
-W7 SmallWorld_47_0.3_4
+W7 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.3_4.xml SmallWorld_47_0.3_4.xml]
 [[image:wSmallWorld_47_0.3_4.JPG|150px]]
@@ Line 95: / Line 110: @@
 [[image:WSmallWorldM_47_0.3_4.PNG|165px]]
-W8 SmallWorld_47_0.3_8
+W8 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.3_8.xml SmallWorld_47_0.3_8.xml]
 [[image:wSmallWorld_47_0.3_8.JPG|150px]]
@@ Line 102: / Line 118: @@
-W9 SmallWorld_47_0.3_10
+W9 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.3_10.xml SmallWorld_47_0.3_10.xml]
 [[image:wSmallWorld_47_0.3_10.JPG|150px]]
@@ Line 109: / Line 125: @@
-W10 SmallWorld_47_0.7_4
+W10 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.7_4.xml SmallWorld_47_0.7_4.xml]
 [[image:wSmallWorld_47_0.7_4.JPG|150px]]
@@ Line 115: / Line 131: @@
 [[image:wSmallWorldM_47_0.7_4.PNG|165px]]
-W11 SmallWorld_47_0.1_8
+W11 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.1_8.xml SmallWorld_47_0.1_8.xml]
 [[image:wSmallWorld_47_0.1_8.JPG|150px]]
@@ Line 121: / Line 137: @@
 [[image:wSmallWorldM_47_0.1_8.PNG|165px]]
-W12 SmallWorld_94_0.1_8
+W12 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_94_0.1_8.xml SmallWorld_94_0.1_8.xml]
 [[image:wSmallWorld_94_0.1_8.JPG|150px]]
@@ Line 134: / Line 150: @@
 {| border="1"
-|+ Parameters and Resulting Graph characteristics
+|  Parameters and Resulting Graph characteristics
 |-
 | graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11
 |- style="background:lightgrey;"
-|'''numNodes (sqrt)''' || 7 || 7 || 7 || 7 || 7 || 7 || 7 || '''10''' || '''10''' || '''10''' || '''10'''
+|'''latticeSize''' || 7 || 7 || 7 || 7 || 7 || 7 || 7 || '''10''' || '''10''' || '''10''' || '''10'''
 |- style="background:lightgrey;"
-|'''clustering exponent''' ||'''0.1''' || '''0.5''' || '''1'''|| '''2''' || '''2.5''' || '''4''' || '''8''' || '''2''' || '''4''' || '''8''' || '''12'''
+|'''clusteringExponent''' ||'''0.1''' || '''0.5''' || '''1'''|| '''2''' || '''2.5''' || '''4''' || '''8''' || '''2''' || '''4''' || '''8''' || '''12'''
 |-
-|numNodes || 49 || 49 || 49 || 49 || 49 || 49 || 49 || 100 || 100 || 100 || 100
+|numVertices || 49 || 49 || 49 || 49 || 49 || 49 || 49 || 100 || 100 || 100 || 100
 |-
 |numEdges || 490 || 490 || 490 || 490 || 490 || 490 || 490 || 1000 || 1000 || 1000 || 1000
@@ Line 161: / Line 177: @@
 |}
-W1 SmallWorld_49_0.1
+W1 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_0.1.xml SmallWorld_49_0.1.xml]
 [[image:kSmallWorld_49_0.1.PNG|150px]]
@@ Line 167: / Line 183: @@
 [[image:kSmallWorldM_49_0.1.PNG|165px]]
-W2 SmallWorld_49_0.5
+W2 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_0.5.xml SmallWorld_49_0.5.xml]
 [[image:kSmallWorld_49_0.5.PNG|150px]]
@@ Line 173: / Line 190: @@
 [[image:kSmallWorldM_49_0.5.PNG|165px]]
-W3 SmallWorld_49_1.0
+W3 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_1.0.xml SmallWorld_49_1.0.xml]
 [[image:kSmallWorld_49_1.0.PNG|150px]]
@@ Line 179: / Line 197: @@
 [[image:kSmallWorldM_49_1.0.PNG|165px]]
-W4 SmallWorld_49_2.0
+W4 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_2.0.xml SmallWorld_49_2.0.xml]
 [[image:kSmallWorld_49_2.0.PNG|150px]]
@@ Line 185: / Line 204: @@
 [[image:kSmallWorldM_49_2.0.PNG|165px]]
-W5 SmallWorld_49_2.5
+W5 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_2.5.xml SmallWorld_49_2.5.xml]
 [[image:kSmallWorld_49_2.5.PNG|150px]]
@@ Line 191: / Line 211: @@
 [[image:kSmallWorldM_49_2.5.PNG|165px]]
-W6 SmallWorld_49_4.0
+W6 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_4.0.xml SmallWorld_49_4.0.xml]
 [[image:kSmallWorld_49_4.0.PNG|150px]]
@@ Line 197: / Line 218: @@
 [[image:kSmallWorldM_49_4.0.PNG|165px]]
-W7 SmallWorld_49_8.0
+W7  [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_8.0.xml SmallWorld_49_8.0.xml]
 [[image:kSmallWorld_49_8.0.PNG|150px]]
@@ Line 203: / Line 225: @@
 [[image:kSmallWorldM_49_8.0.PNG|165px]]
-W8 SmallWorld_100_2.0
+W8  [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_100_2.0.xml SmallWorld_100_2.0.xml]
 [[image:kSmallWorld_100_2.0.PNG|150px]]
@@ Line 209: / Line 232: @@
 [[image:kSmallWorldM_100_2.0.PNG|165px]]
-W9 SmallWorld_100_4.0
+W9 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_100_4.0.xml SmallWorld_100_4.0.xml]
 [[image:kSmallWorld_100_4.0.PNG|150px]]
@@ Line 215: / Line 238: @@
 [[image:kSmallWorldM_100_4.0.PNG|165px]]
-W10 SmallWorld_100_8.0
+W10 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_100_8.0.xml SmallWorld_100_8.0.xml]
 [[image:kSmallWorld_100_8.0.PNG|150px]]
@@ Line 221: / Line 244: @@
 [[image:kSmallWorldM_100_8.0.PNG|165px]]
-W11 SmallWorld_100_12.0
+W11 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_100_12.0.xml SmallWorld_100_12.0.xml]
 [[image:kSmallWorld_100_12.0.PNG|150px]]
@@ Line 234: / Line 257: @@
 {| border="1"
-|+ Parameters and Resulting Graph characteristics
+|  Parameters and Resulting Graph characteristics
 |-
 | graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8
 |- style="background:lightgrey;"
-|'''numStartingNodes'''||4||4||4||4||2||2||2||4
+|'''init_vertices'''||4||4||4||4||2||2||2||4
 |- style="background:lightgrey;"
-|'''numAdditionnalEdges'''||2||2||2||1||1||1||2||4
+|'''numEdgesToAttach'''||2||2||2||1||1||1||2||4
 |- style="background:lightgrey;"
-|'''numSteps'''||10||50||100||100||100||50||50||50
+|'''numSteps'''||10||50||100|| 100||100||50||50||50
 |-
-|numNodes||14||53||104||80||76||51||52||54
+|numVertices||14||53||104|| 80||76||51||52||54
 |-
 |numEdges||40||200||400||158||150||100||200||400
@@ Line 262: / Line 285: @@
 |maxDegree||5||16||19||8||12||16||17||26
 |}
+W1 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_4_2_10.xml ScaleFree_4_2_10.xml]
+[[image:baScaleFree_4_2_10.PNG|150px]]
+[[image:baScaleFreeMInit_4_2_10.PNG|165px]]
+[[image:baScaleFreeM_4_2_10.PNG|165px]]
+W2 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_4_2_50.xml ScaleFree_4_2_50.xml]
+[[image:baScaleFree_4_2_50.PNG|150px]]
+[[image:baScaleFreeMInit_4_2_50.PNG|165px]]
+[[image:baScaleFreeM_4_2_50.PNG|165px]]
+W3 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_4_2_100.xml ScaleFree_4_2_100.xml]
+[[image:baScaleFree_4_2_100.PNG|150px]]
+[[image:baScaleFreeMInit_4_2_100.PNG|165px]]
+[[image:baScaleFreeM_4_2_100.PNG|165px]]
+W4 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_4_1_100.xml ScaleFree_4_1_100.xml]
+[[image:baScaleFree_4_1_100.PNG|150px]]
+[[image:baScaleFreeMInit_4_1_100.PNG|165px]]
+[[image:baScaleFreeM_4_1_100.PNG|165px]]
+W5 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_2_1_100.xml  ScaleFree_2_1_100.xml]
+[[image:baScaleFree_2_1_100.PNG|150px]]
+[[image:baScaleFreeMInit_2_1_100.PNG|165px]]
+[[image:baScaleFreeM_2_1_100.PNG|165px]]
+W6 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_2_1_50.xml ScaleFree_2_1_50.xml]
+[[image:baScaleFree_2_1_50.PNG|150px]]
+[[image:baScaleFreeMInit_2_1_50.PNG|165px]]
+[[image:baScaleFreeM_2_1_50.PNG|165px]]
+W7 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_2_2_50.xml ScaleFree_2_2_50.xml]
+[[image:baScaleFree_2_2_50.PNG|150px]]
+[[image:baScaleFreeMInit_2_2_50.PNG|165px]]
+[[image:baScaleFreeM_2_2_50.PNG|165px]]
+W8 [http://insitu.lri.fr/~nhenry/socnets/bascalefree/baScaleFree_4_4_50.xml ScaleFree_4_4_50.xml]
+[[image:baScaleFree_4_4_50.PNG|150px]]
+[[image:baScaleFreeMInit_4_4_50.PNG|165px]]
+[[image:baScaleFreeM_4_4_50.PNG|165px]]
@@ Line 268: / Line 342: @@
 Parameters: '''numVertices''' (the number of vertices for the generated graph), '''numEdges''' (the number of edges the generated graph will have, should be Theta(numVertices)) and '''r''' (the model parameter).
-== Issues on using real Social Networks for Evaluating Visualizations ==
+== Real Social Networks ==
 Here is a panel of undirected networks issued from scientific articles, benchmarks or contests.  Social network visualization or analysis tools provide also some real datasets: Pajek [http://vlado.fmf.uni-lj.si/pub/networks/data/] and UCINet [http://vlado.fmf.uni-lj.si/pub/networks/data/UciNet/UciData.htm].
+=== Small-World ===
 {| border="1"
-|+ Parameters and Resulting Graph characteristics
+|  Parameters and Resulting Graph characteristics for Co-Authoring Networks
+|Name ||Team Collaboration (with external collaborators)||Infovis component 1 ||Infovis component 2 || Infovis component 3||Infovis component 4
+|-style="background:lightgrey"
+|'''Source'''||Collected ||Contest||Contest||Contest||Contest
 |-
-|Name||Infovis Comp4
+|numNodes||146||135||48||47||32
-|-style="background:lightgrey;"
+|-
-|'''Type'''|| Co-authoring network
+|numEdges||540||321||91||114||109
+|-
+|components||1||1||1||1||1
+|-style="background:#FFFFCC"
+|density||0.16||0.13||0.2||0.23||0.33
+|-style="background:#FFFFCC"
+|clusteringCoefficient||0.91||0.82||0.79||0.83||0.81
 |-
-|File||
+|diameter||4||11||7||10||6
 |-
-|numNodes||32
+|averageShortestDistance||2.65||4.4||3.71||3.84||2.6
 |-
-|numEdges||109
+|minDegree||1||1||1||1||1
 |-
-|components||1
+|maxDegree||57||22||11||15||15
+|}
+TeamCollaborationExternal [http://insitu.lri.fr/~nhenry/socnets/realsmallworld/teamCollaborationExternalAnonym.xml TeamCollaborationExternal.xml]
+[[image: teamCollaborationExternal.PNG|150px]]
+[[image: teamCollaborationExternalMInit.PNG|165px]]
+[[image: teamCollaborationExternalM.PNG|165px]]
+Infovis Component 1 [http://insitu.lri.fr/~nhenry/socnets/realsmallworld/ivComp1.xml ivComp1.xml]
+[[image: ivComp1.PNG|150px]]
+[[image: ivComp1MInit.PNG|165px]]
+[[image: ivComp1M.PNG|165px]]
+Infovis Component 2 [http://insitu.lri.fr/~nhenry/socnets/realsmallworld/ivComp2.xml ivComp2.xml]
+[[image: ivComp2.PNG|150px]]
+[[image: ivComp2MInit.PNG|165px]]
+[[image: ivComp2M.PNG|165px]]
+Infovis Component 3 [http://insitu.lri.fr/~nhenry/socnets/realsmallworld/ivComp3.xml ivComp3.xml]
+[[image: ivComp3.PNG|150px]]
+[[image: ivComp3MInit.PNG|165px]]
+[[image: ivComp3M.PNG|165px]]
+Infovis Component 4 [http://insitu.lri.fr/~nhenry/socnets/realsmallworld/ivComp4.xml ivComp4.xml]
+[[image: ivComp4.PNG|150px]]
+[[image: ivComp4MInit.PNG|165px]]
+[[image: ivComp4M.PNG|165px]]
+=== Tree-like ===
+{| border="1"
+|  Parameters and Resulting Graph characteristics for Genealogy and Virus Transmission
+|Name ||genealogy||MSTTransmission1||MSTTransmission2||HIVTransmission
+|-style="background:lightgrey"
+|'''Source'''||Pajek||Article [http://sextrans.bmjjournals.com/cgi/content/abstract/80/4/280]||Article[http://sextrans.bmjjournals.com/cgi/content/abstract/80/4/280]||Article [http://sti.bmjjournals.com/cgi/content/abstract/78/suppl_1/i159]
+|-
+|numVertices||242||38||84||243
+|-
+|numEdges||510||78||182||514
+|-
+|components||1||1||1||1
 |-style="background:#FFFFCC"
-|density||0.33
+|density||0.09||0.23||0.16||0.09
 |-style="background:#FFFFCC"
-|clusteringCoefficient||0.81
+|clusteringCoefficient||0.66||0.53||0.52||0.65
 |-
-|diameter||6
+|diameter||11||10||9||23
 |-
-|averageShortestDistance||2.60
+|averageShortestDistance||5.78||4.42||4.31||8.27
 |-
-|minDegree||
+|minDegree||1||1||1||1
 |-
-|maxDegree||
+|maxDegree||14||7||17||20
 |}
+Gondola Genealogy [http://insitu.lri.fr/~nhenry/socnets/realtreelike/GondolaGen.xml GondolaGen.xml]
+[[image: gondolaGen.PNG|150px]]
+[[image: gondolaGenMInit.PNG|165px]]
+[[image: gondolaGenM.PNG|165px]]
+MSTTransmission 1 [http://insitu.lri.fr/~nhenry/socnets/realtreelike/Mst1.xml Mst1.xml]
+[[image: mst1.PNG|150px]]
+[[image: mst1MInit.PNG|165px]]
+[[image: mst1M.PNG|165px]]
+MSTTransmission 2 [http://insitu.lri.fr/~nhenry/socnets/realtreelike/Mst2.xml Mst2.xml]
+[[image: mst2.PNG|150px]]
+[[image: mst2MInit.PNG|165px]]
+[[image: mst2M.PNG|165px]]
+HIV Transmission [http://insitu.lri.fr/~nhenry/socnets/realtreelike/Hiv.xml Hiv.xml]
+[[image: hiv.PNG|150px]]
+[[image: hivMInit.PNG|165px]]
+[[image: hivM.PNG|165px]]
+=== Almost Complete Graphs ===
+{| border="1"
+|  Parameters and Resulting Graph characteristics for Email Communication within a research lab.
+|-
+|Name||emailDay per person||emailWeek per person||emailMonth  per person||emailYear per person||emailDay per team||emailWeek per team||emailMonth per team||emailYear per team
+|-style="background:lightgrey"
+|'''Source'''||Collected||Collected||Collected||Collected||Collected||Collected||Collected||Collected
+|-
+|numVertices||134||200||242||447||30||33||35||42
+|-
+|numEdges||442||1676||3514||11462||183||410||564||980
+|-
+|components||1||1||1||1||1||1||1||1
+|-style="background:#FFFFCC"
+|density||0.16||0.2||0.24||0.24||0.45||0.61||0.68||0.75
+|-style="background:#FFFFCC"
+|clusteringCoefficient||0.52||0.55||0.62||0.71||0.62||0.78||0.83||0.84
+|-
+|diameter||9||7||6||6||5||3||3||3
+|-
+|averageShortestDistance||4.29||2.92||2.52||2.42||2.17||1.71||1.57||1.45
+|-
+|minDegree||1||1||1||1||1||1||1||3
+|-
+|maxDegree||15||51||86||195||16||26||34||40
+|}
+Email exchange per person during a day [http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailDay.xml emailDay.xml]
+[[image: emailDay.PNG|150px]]
+[[image: emailDayMInit.PNG|165px]]
+[[image: emailDayM.PNG|165px]]
+Email exchange per person during a week [http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailWeek.xml emailWeek.xml]
+[[image: emailWeek.PNG|150px]]
+[[image: emailWeekMInit.PNG|165px]]
+[[image: emailWeekM.PNG|165px]]
+Email exchange per person during a month [http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailMonth.xml emailMonth.xml]
+[[image: emailMonth.PNG|150px]]
+[[image: emailMonthMInit.PNG|165px]]
+[[image: emailMonthM.PNG|165px]]
+Email exchange per person during a year [http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailYear.xml emailYear.xml]
+[[image: emailYear.PNG|150px]]
+[[image: emailYearMInit.PNG|165px]]
+[[image: emailYearM.PNG|165px]]
+Email exchange per research group during a day  [http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailGDay.xml emailGDay.xml]
+[[image: emailGDay.PNG|150px]]
+[[image: emailGDayMInit.PNG|165px]]
+[[image: emailGDayM.PNG|165px]]
+<blockquote>
+Number of email coded with link width in the nodelink, edge color in the matrix
+</blockquote>
+<blockquote>
+[[image: emailGDayS.PNG|150px]]
+[[image: emailGDayMC.PNG|165px]]
+</blockquote>
+Email exchange per research group during a week
+[http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailGWeek.xml emailGWeek.xml]
+[[image: emailGWeek.PNG|150px]]
+[[image: emailGWeekMInit.PNG|165px]]
+[[image: emailGWeekM.PNG|165px]]
+<blockquote>
+Number of email coded with link width in the nodelink, edge color in the matrix
+</blockquote>
+<blockquote>
+[[image: emailGWeekS.PNG|150px]]
+[[image: emailGWeekMC.PNG|165px]]
+</blockquote>
+Email exchange per research group during a month
+[http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailGMonth.xml emailGMonth.xml]
+[[image: emailGMonth.PNG|150px]]
+[[image: emailGMonthMInit.PNG|165px]]
+[[image: emailGMonthM.PNG|165px]]
+<blockquote>
+Number of email coded with link width in the nodelink, edge color in the matrix
+</blockquote>
+<blockquote>
+[[image: emailGMonthS.PNG|150px]]
+[[image: emailGMonthMC.PNG|150px]]
+</blockquote>
+Email exchange per research group during a year
+[http://insitu.lri.fr/~nhenry/socnets/realalmostcomplete/emailGYear.xml emailGYear.xml]
+[[image: emailGYear.PNG|150px]]
+[[image: emailGYearMInit.PNG|165px]]
+[[image: emailGYearM.PNG|165px]]
+<blockquote>
+Number of email coded with link width in the nodelink, edge color in the matrix
+</blockquote>
+<blockquote>
+[[image: emailGYearS.PNG|150px]]
+[[image: emailGYearMC.PNG|165px]]
+</blockquote>
+[[Category:Datasets]]
+[[Category:Coffee Room]]
+[[Category:Methods]]

Social Network Generation: Difference between revisions

Latest revision as of 11:27, 2 March 2010

Social Network Characterization

Issues on Social Network Generation for Evaluating Visualizations

About datasets and representations

Small-World Generators

Scale-Free Networks Generator

Real Social Networks

Small-World

Tree-like

Almost Complete Graphs

Navigation menu

Search