InfoVis:Wiki - User contributions [en]

Social Network Generation

2007-01-26T13:03:35Z

Socnet:

This wiki page is under construction...

== 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[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 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11||W12
|- style="background:lightgrey;"
|'''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
|- style="background:lightgrey;"
|'''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
|- 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'''
|-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'''
|-
|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 [http://insitu.lri.fr/~nhenry/socnets/wsmallworld/wSmallWorld_47_0.1_6.xml SmallWorld_47_0.1_6.xml]

[[image:wSmallWorld_47_0.1_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.1_6.PNG|165px]]
[[image:wSmallWorldM_47_0.1_6.JPG|165px]]

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]]
[[image:wSmallWorldMInit_47_0.3_6.PNG|165px]]
[[image:wSmallWorldM_47_0.3_6.PNG|165px]]

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]]
[[image:wSmallWorldMInit_47_0.5_6.PNG|165px]]
[[image:wSmallWorldM_47_0.5_6.PNG|165px]]

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]]
[[image:wSmallWorldMInit_47_0.7_6.PNG|165px]]
[[image:wSmallWorldM_47_0.7_6.PNG|165px]]

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]]
[[image:WSmallWorldMInit_47_0.9_6.PNG|165px]]
[[image:WSmallWorldM_47_0.9_6.PNG|165px]]

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]]
[[image:WSmallWorldMInit_47_0.3_2.PNG|165px]]
[[image:WSmallWorldM_47_0.3_2.PNG|165px]]

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]]
[[image:WSmallWorldMInit_47_0.3_4.PNG|165px]]
[[image:WSmallWorldM_47_0.3_4.PNG|165px]]

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]]
[[image:WSmallWorldMInit_47_0.3_8.PNG|165px]]
[[image:WSmallWorldM_47_0.3_8.PNG|165px]]

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]]
[[image:WSmallWorldMInit_47_0.3_10.PNG|165px]]
[[image:WSmallWorldM_47_0.3_10.PNG|165px]]

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]]
[[image:wSmallWorldMInit_47_0.7_4.PNG|165px]]
[[image:wSmallWorldM_47_0.7_4.PNG|165px]]

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]]
[[image:wSmallWorldMInit_47_0.1_8.PNG|165px]]
[[image:wSmallWorldM_47_0.1_8.PNG|165px]]

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]]
[[image:wSmallWorldMInit_94_0.1_8.PNG|165px]]
[[image:wSmallWorldM_94_0.1_8.PNG|165px]]

KleinbergSmallWorldGenerator

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

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11
|- style="background:lightgrey;"
|'''latticeSize''' || 7 || 7 || 7 || 7 || 7 || 7 || 7 || '''10''' || '''10''' || '''10''' || '''10'''
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.32 || 0.32 || 0.32 || 0.32
|-style="background:#FFFFCC"
|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 [http://insitu.lri.fr/~nhenry/socnets/ksmallworld/kSmallWorld_49_0.1.xml SmallWorld_49_0.1.xml]

[[image:kSmallWorld_49_0.1.PNG|150px]]
[[image:kSmallWorldMInit_49_0.1.PNG|165px]]
[[image:kSmallWorldM_49_0.1.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_0.5.PNG|165px]]
[[image:kSmallWorldM_49_0.5.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_1.0.PNG|165px]]
[[image:kSmallWorldM_49_1.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_2.0.PNG|165px]]
[[image:kSmallWorldM_49_2.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_2.5.PNG|165px]]
[[image:kSmallWorldM_49_2.5.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_4.0.PNG|165px]]
[[image:kSmallWorldM_49_4.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_49_8.0.PNG|165px]]
[[image:kSmallWorldM_49_8.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_100_2.0.PNG|165px]]
[[image:kSmallWorldM_100_2.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_100_4.0.PNG|165px]]
[[image:kSmallWorldM_100_4.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_100_8.0.PNG|165px]]
[[image:kSmallWorldM_100_8.0.PNG|165px]]

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]]
[[image:kSmallWorldMInit_100_12.0.PNG|165px]]
[[image:kSmallWorldM_100_12.0.PNG|165px]]

=== 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8
|- style="background:lightgrey;"
|'''init_vertices'''||4||4||4||4||2||2||2||4
|- style="background:lightgrey;"
|'''numEdgesToAttach'''||2||2||2||1||1||1||2||4
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density||0.45||0.27||0.19||0.16||0.16||0.2||0.27||0.37
|-style="background:#FFFFCC"
|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 [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]]

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 [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 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
|-
|numNodes||146||135||48||47||32
|-
|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
|-
|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 [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.09||0.23||0.16||0.09
|-style="background:#FFFFCC"
|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 [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]]

File:EmailGYearS.PNG

2006-11-16T13:36:42Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGYearMInit.PNG

2006-11-16T13:35:49Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGYearMC.PNG

2006-11-16T13:35:41Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGYearM.PNG

2006-11-16T13:35:33Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGYear.PNG

2006-11-16T13:35:29Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGWeekS.PNG

2006-11-16T13:35:26Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGWeekMInit.PNG

2006-11-16T13:35:22Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGWeekMC.PNG

2006-11-16T13:35:18Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGWeekM.PNG

2006-11-16T13:35:14Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGWeek.PNG

2006-11-16T13:35:08Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGMonthS.PNG

2006-11-16T13:34:46Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGMonthMInit.PNG

2006-11-16T13:34:41Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGMonthMC.PNG

2006-11-16T13:34:37Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGMonthM.PNG

2006-11-16T13:34:32Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGMonth.PNG

2006-11-16T13:34:28Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGDayS.PNG

2006-11-16T13:34:23Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGDayMInit.PNG

2006-11-16T13:34:16Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGDayMC.PNG

2006-11-16T13:33:10Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGDayM.PNG

2006-11-16T13:33:00Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailGDay.PNG

2006-11-16T13:32:55Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

Social Network Generation

2006-11-16T13:32:49Z

Socnet: /* Almost Complete Graphs */

This wiki page is under construction...

== 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[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.

=== 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11||W12
|- style="background:lightgrey;"
|'''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
|- style="background:lightgrey;"
|'''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
|- 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'''
|-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'''
|-
|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:
* 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]]
[[image:wSmallWorldMInit_47_0.1_6.PNG|165px]]
[[image:wSmallWorldM_47_0.1_6.JPG|165px]]

W2 SmallWorld_47_0.3_6

[[image:wSmallWorld_47_0.3_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.3_6.PNG|165px]]
[[image:wSmallWorldM_47_0.3_6.PNG|165px]]

W3 SmallWorld_47_0.5_6

[[image:wSmallWorld_47_0.5_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.5_6.PNG|165px]]
[[image:wSmallWorldM_47_0.5_6.PNG|165px]]

W4 SmallWorld_47_0.7_6

[[image:wSmallWorld_47_0.7_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.7_6.PNG|165px]]
[[image:wSmallWorldM_47_0.7_6.PNG|165px]]

W5 SmallWorld_47_0.9_6

[[image:wSmallWorld_47_0.9_6.JPG|150px]]
[[image:WSmallWorldMInit_47_0.9_6.PNG|165px]]
[[image:WSmallWorldM_47_0.9_6.PNG|165px]]

W6 SmallWorld_47_0.3_2

[[image:wSmallWorld_47_0.3_2.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_2.PNG|165px]]
[[image:WSmallWorldM_47_0.3_2.PNG|165px]]

W7 SmallWorld_47_0.3_4

[[image:wSmallWorld_47_0.3_4.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_4.PNG|165px]]
[[image:WSmallWorldM_47_0.3_4.PNG|165px]]

W8 SmallWorld_47_0.3_8

[[image:wSmallWorld_47_0.3_8.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_8.PNG|165px]]
[[image:WSmallWorldM_47_0.3_8.PNG|165px]]

W9 SmallWorld_47_0.3_10

[[image:wSmallWorld_47_0.3_10.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_10.PNG|165px]]
[[image:WSmallWorldM_47_0.3_10.PNG|165px]]

W10 SmallWorld_47_0.7_4

[[image:wSmallWorld_47_0.7_4.JPG|150px]]
[[image:wSmallWorldMInit_47_0.7_4.PNG|165px]]
[[image:wSmallWorldM_47_0.7_4.PNG|165px]]

W11 SmallWorld_47_0.1_8

[[image:wSmallWorld_47_0.1_8.JPG|150px]]
[[image:wSmallWorldMInit_47_0.1_8.PNG|165px]]
[[image:wSmallWorldM_47_0.1_8.PNG|165px]]

W12 SmallWorld_94_0.1_8

[[image:wSmallWorld_94_0.1_8.JPG|150px]]
[[image:wSmallWorldMInit_94_0.1_8.PNG|165px]]
[[image:wSmallWorldM_94_0.1_8.PNG|165px]]

KleinbergSmallWorldGenerator

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

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11
|- style="background:lightgrey;"
|'''latticeSize''' || 7 || 7 || 7 || 7 || 7 || 7 || 7 || '''10''' || '''10''' || '''10''' || '''10'''
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.32 || 0.32 || 0.32 || 0.32
|-style="background:#FFFFCC"
|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

[[image:kSmallWorld_49_0.1.PNG|150px]]
[[image:kSmallWorldMInit_49_0.1.PNG|165px]]
[[image:kSmallWorldM_49_0.1.PNG|165px]]

W2 SmallWorld_49_0.5

[[image:kSmallWorld_49_0.5.PNG|150px]]
[[image:kSmallWorldMInit_49_0.5.PNG|165px]]
[[image:kSmallWorldM_49_0.5.PNG|165px]]

W3 SmallWorld_49_1.0

[[image:kSmallWorld_49_1.0.PNG|150px]]
[[image:kSmallWorldMInit_49_1.0.PNG|165px]]
[[image:kSmallWorldM_49_1.0.PNG|165px]]

W4 SmallWorld_49_2.0

[[image:kSmallWorld_49_2.0.PNG|150px]]
[[image:kSmallWorldMInit_49_2.0.PNG|165px]]
[[image:kSmallWorldM_49_2.0.PNG|165px]]

W5 SmallWorld_49_2.5

[[image:kSmallWorld_49_2.5.PNG|150px]]
[[image:kSmallWorldMInit_49_2.5.PNG|165px]]
[[image:kSmallWorldM_49_2.5.PNG|165px]]

W6 SmallWorld_49_4.0

[[image:kSmallWorld_49_4.0.PNG|150px]]
[[image:kSmallWorldMInit_49_4.0.PNG|165px]]
[[image:kSmallWorldM_49_4.0.PNG|165px]]

W7 SmallWorld_49_8.0

[[image:kSmallWorld_49_8.0.PNG|150px]]
[[image:kSmallWorldMInit_49_8.0.PNG|165px]]
[[image:kSmallWorldM_49_8.0.PNG|165px]]

W8 SmallWorld_100_2.0

[[image:kSmallWorld_100_2.0.PNG|150px]]
[[image:kSmallWorldMInit_100_2.0.PNG|165px]]
[[image:kSmallWorldM_100_2.0.PNG|165px]]

W9 SmallWorld_100_4.0

[[image:kSmallWorld_100_4.0.PNG|150px]]
[[image:kSmallWorldMInit_100_4.0.PNG|165px]]
[[image:kSmallWorldM_100_4.0.PNG|165px]]

W10 SmallWorld_100_8.0

[[image:kSmallWorld_100_8.0.PNG|150px]]
[[image:kSmallWorldMInit_100_8.0.PNG|165px]]
[[image:kSmallWorldM_100_8.0.PNG|165px]]

W11 SmallWorld_100_12.0

[[image:kSmallWorld_100_12.0.PNG|150px]]
[[image:kSmallWorldMInit_100_12.0.PNG|165px]]
[[image:kSmallWorldM_100_12.0.PNG|165px]]

=== 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8
|- style="background:lightgrey;"
|'''init_vertices'''||4||4||4||4||2||2||2||4
|- style="background:lightgrey;"
|'''numEdgesToAttach'''||2||2||2||1||1||1||2||4
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density||0.45||0.27||0.19||0.16||0.16||0.2||0.27||0.37
|-style="background:#FFFFCC"
|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

[[image:baScaleFree_4_2_10.PNG|150px]]
[[image:baScaleFreeMInit_4_2_10.PNG|165px]]
[[image:baScaleFreeM_4_2_10.PNG|165px]]

W2 ScaleFree_4_2_50

[[image:baScaleFree_4_2_50.PNG|150px]]
[[image:baScaleFreeMInit_4_2_50.PNG|165px]]
[[image:baScaleFreeM_4_2_50.PNG|165px]]

W3 ScaleFree_4_2_100

[[image:baScaleFree_4_2_100.PNG|150px]]
[[image:baScaleFreeMInit_4_2_100.PNG|165px]]
[[image:baScaleFreeM_4_2_100.PNG|165px]]

W4 ScaleFree_4_1_100

[[image:baScaleFree_4_1_100.PNG|150px]]
[[image:baScaleFreeMInit_4_1_100.PNG|165px]]
[[image:baScaleFreeM_4_1_100.PNG|165px]]

W5 ScaleFree_2_1_100

[[image:baScaleFree_2_1_100.PNG|150px]]
[[image:baScaleFreeMInit_2_1_100.PNG|165px]]
[[image:baScaleFreeM_2_1_100.PNG|165px]]

W6 ScaleFree_2_1_50

[[image:baScaleFree_2_1_50.PNG|150px]]
[[image:baScaleFreeMInit_2_1_50.PNG|165px]]
[[image:baScaleFreeM_2_1_50.PNG|165px]]

W7 ScaleFree_2_2_50

[[image:baScaleFree_2_2_50.PNG|150px]]
[[image:baScaleFreeMInit_2_2_50.PNG|165px]]
[[image:baScaleFreeM_2_2_50.PNG|165px]]

W8 ScaleFree_4_4_50

[[image:baScaleFree_4_4_50.PNG|150px]]
[[image:baScaleFreeMInit_4_4_50.PNG|165px]]
[[image:baScaleFreeM_4_4_50.PNG|165px]]

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 [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 for Co-Authoring Networks
|Name ||Team Collaboration (with external collaborators)||Team Collaboration (within the team)||Infovis component 1 ||Infovis component 2 || Infovis component 3||Infovis component 4
|-style="background:lightgrey"
|'''Source'''||Collected ||Collected||Contest||Contest||Contest||Contest
|-
|numNodes||146||96||135||48||47||32
|-
|numEdges||540||316||321||91||114||109
|-
|components||1||1||1||1||1||1
|-style="background:#FFFFCC"
|density||0.16||0.19||0.13||0.2||0.23||0.33
|-style="background:#FFFFCC"
|clusteringCoefficient||0.91||0.91||0.82||0.79||0.83||0.81
|-
|diameter||4||5||11||7||10||6
|-
|averageShortestDistance||2.65||2.81||4.4||3.71||3.84||2.6
|-
|minDegree||1||1||1||1||1||1
|-
|maxDegree||57||29||22||11||15||15
|}

TeamCollaborationExternal

[[image: teamCollaborationExternal.PNG|150px]]
[[image: teamCollaborationExternalMInit.PNG|165px]]
[[image: teamCollaborationExternalM.PNG|165px]]

TeamCollaborationWithin

[[image: teamCollaborationWithin.PNG|150px]]
[[image: teamCollaborationWithinMInit.PNG|165px]]
[[image: teamCollaborationWithinM.PNG|165px]]

Infovis Component 1

[[image: ivComp1.PNG|150px]]
[[image: ivComp1MInit.PNG|165px]]
[[image: ivComp1M.PNG|165px]]

Infovis Component 2

[[image: ivComp2.PNG|150px]]
[[image: ivComp2MInit.PNG|165px]]
[[image: ivComp2M.PNG|165px]]

Infovis Component 3

[[image: ivComp3.PNG|150px]]
[[image: ivComp3MInit.PNG|165px]]
[[image: ivComp3M.PNG|165px]]

Infovis Component 4

[[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.09||0.23||0.16||0.09
|-style="background:#FFFFCC"
|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

[[image: gondolaGen.PNG|150px]]
[[image: gondolaGenMInit.PNG|165px]]
[[image: gondolaGenM.PNG|165px]]

MSTTransmission 1

[[image: mst1.PNG|150px]]
[[image: mst1MInit.PNG|165px]]
[[image: mst1M.PNG|165px]]

MSTTransmission 2

[[image: mst2.PNG|150px]]
[[image: mst2MInit.PNG|165px]]
[[image: mst2M.PNG|165px]]

HIV Transmission

[[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

[[image: emailDay.PNG|150px]]
[[image: emailDayMInit.PNG|165px]]
[[image: emailDayM.PNG|165px]]

Email exchange per person during a week

[[image: emailWeek.PNG|150px]]
[[image: emailWeekMInit.PNG|165px]]
[[image: emailWeekM.PNG|165px]]

Email exchange per person during a month

[[image: emailMonth.PNG|150px]]
[[image: emailMonthMInit.PNG|165px]]
[[image: emailMonthM.PNG|165px]]

Email exchange per person during a year

[[image: emailYear.PNG|150px]]
[[image: emailYearMInit.PNG|165px]]
[[image: emailYearM.PNG|165px]]

Email exchange per research group during a day
(Email number is coded with link width in the nodelink, edge color in the matrix)

[[image: emailGDay.PNG|150px]]
[[image: emailGDayS.PNG|150px]]
[[image: emailGDayMInit.PNG|165px]]
[[image: emailGDayM.PNG|165px]]
[[image: emailGDayMC.PNG|165px]]

Email exchange per research group during a week
(Email number is coded with link width in the nodelink, edge color in the matrix)

[[image: emailGWeek.PNG|150px]]
[[image: emailGWeekS.PNG|150px]]
[[image: emailGWeekMInit.PNG|165px]]
[[image: emailGWeekM.PNG|165px]]
[[image: emailGWeekMC.PNG|165px]]

Email exchange per research group during a month
(Email number is coded with link width in the nodelink, edge color in the matrix)

[[image: emailGMonth.PNG|150px]]
[[image: emailGMonthS.PNG|150px]]
[[image: emailGMonthMInit.PNG|165px]]
[[image: emailGMonthM.PNG|165px]]
[[image: emailGMonthMC.PNG|150px]]

Email exchange per research group during a year
(Email number is coded with link width in the nodelink, edge color in the matrix)

[[image: emailGYear.PNG|150px]]
[[image: emailGYearS.PNG|150px]]
[[image: emailGYearMInit.PNG|165px]]
[[image: emailGYearM.PNG|165px]]
[[image: emailGYearMC.PNG|165px]]

File:EmailMonthMInit.PNG

2006-11-16T12:59:14Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailYearMInit.PNG

2006-11-16T12:58:15Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailYearM.PNG

2006-11-16T12:58:05Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailYear.PNG

2006-11-16T12:57:58Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailWeekMInit.PNG

2006-11-16T12:57:52Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailWeekM.PNG

2006-11-16T12:57:44Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailWeek.PNG

2006-11-16T12:57:37Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailMonthM.PNG

2006-11-16T12:57:26Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailMonth.PNG

2006-11-16T12:57:18Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailDayMInit.PNG

2006-11-16T12:57:11Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailDayM.PNG

2006-11-16T12:57:04Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:EmailDay.PNG

2006-11-16T12:56:57Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

Social Network Generation

2006-11-16T12:51:43Z

Socnet: /* Almost Complete Graphs */

This wiki page is under construction...

== 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[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.

=== 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11||W12
|- style="background:lightgrey;"
|'''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
|- style="background:lightgrey;"
|'''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
|- 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'''
|-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'''
|-
|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:
* 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]]
[[image:wSmallWorldMInit_47_0.1_6.PNG|165px]]
[[image:wSmallWorldM_47_0.1_6.JPG|165px]]

W2 SmallWorld_47_0.3_6

[[image:wSmallWorld_47_0.3_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.3_6.PNG|165px]]
[[image:wSmallWorldM_47_0.3_6.PNG|165px]]

W3 SmallWorld_47_0.5_6

[[image:wSmallWorld_47_0.5_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.5_6.PNG|165px]]
[[image:wSmallWorldM_47_0.5_6.PNG|165px]]

W4 SmallWorld_47_0.7_6

[[image:wSmallWorld_47_0.7_6.JPG|150px]]
[[image:wSmallWorldMInit_47_0.7_6.PNG|165px]]
[[image:wSmallWorldM_47_0.7_6.PNG|165px]]

W5 SmallWorld_47_0.9_6

[[image:wSmallWorld_47_0.9_6.JPG|150px]]
[[image:WSmallWorldMInit_47_0.9_6.PNG|165px]]
[[image:WSmallWorldM_47_0.9_6.PNG|165px]]

W6 SmallWorld_47_0.3_2

[[image:wSmallWorld_47_0.3_2.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_2.PNG|165px]]
[[image:WSmallWorldM_47_0.3_2.PNG|165px]]

W7 SmallWorld_47_0.3_4

[[image:wSmallWorld_47_0.3_4.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_4.PNG|165px]]
[[image:WSmallWorldM_47_0.3_4.PNG|165px]]

W8 SmallWorld_47_0.3_8

[[image:wSmallWorld_47_0.3_8.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_8.PNG|165px]]
[[image:WSmallWorldM_47_0.3_8.PNG|165px]]

W9 SmallWorld_47_0.3_10

[[image:wSmallWorld_47_0.3_10.JPG|150px]]
[[image:WSmallWorldMInit_47_0.3_10.PNG|165px]]
[[image:WSmallWorldM_47_0.3_10.PNG|165px]]

W10 SmallWorld_47_0.7_4

[[image:wSmallWorld_47_0.7_4.JPG|150px]]
[[image:wSmallWorldMInit_47_0.7_4.PNG|165px]]
[[image:wSmallWorldM_47_0.7_4.PNG|165px]]

W11 SmallWorld_47_0.1_8

[[image:wSmallWorld_47_0.1_8.JPG|150px]]
[[image:wSmallWorldMInit_47_0.1_8.PNG|165px]]
[[image:wSmallWorldM_47_0.1_8.PNG|165px]]

W12 SmallWorld_94_0.1_8

[[image:wSmallWorld_94_0.1_8.JPG|150px]]
[[image:wSmallWorldMInit_94_0.1_8.PNG|165px]]
[[image:wSmallWorldM_94_0.1_8.PNG|165px]]

KleinbergSmallWorldGenerator

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

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8||W9||W10||W11
|- style="background:lightgrey;"
|'''latticeSize''' || 7 || 7 || 7 || 7 || 7 || 7 || 7 || '''10''' || '''10''' || '''10''' || '''10'''
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.45 || 0.32 || 0.32 || 0.32 || 0.32
|-style="background:#FFFFCC"
|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

[[image:kSmallWorld_49_0.1.PNG|150px]]
[[image:kSmallWorldMInit_49_0.1.PNG|165px]]
[[image:kSmallWorldM_49_0.1.PNG|165px]]

W2 SmallWorld_49_0.5

[[image:kSmallWorld_49_0.5.PNG|150px]]
[[image:kSmallWorldMInit_49_0.5.PNG|165px]]
[[image:kSmallWorldM_49_0.5.PNG|165px]]

W3 SmallWorld_49_1.0

[[image:kSmallWorld_49_1.0.PNG|150px]]
[[image:kSmallWorldMInit_49_1.0.PNG|165px]]
[[image:kSmallWorldM_49_1.0.PNG|165px]]

W4 SmallWorld_49_2.0

[[image:kSmallWorld_49_2.0.PNG|150px]]
[[image:kSmallWorldMInit_49_2.0.PNG|165px]]
[[image:kSmallWorldM_49_2.0.PNG|165px]]

W5 SmallWorld_49_2.5

[[image:kSmallWorld_49_2.5.PNG|150px]]
[[image:kSmallWorldMInit_49_2.5.PNG|165px]]
[[image:kSmallWorldM_49_2.5.PNG|165px]]

W6 SmallWorld_49_4.0

[[image:kSmallWorld_49_4.0.PNG|150px]]
[[image:kSmallWorldMInit_49_4.0.PNG|165px]]
[[image:kSmallWorldM_49_4.0.PNG|165px]]

W7 SmallWorld_49_8.0

[[image:kSmallWorld_49_8.0.PNG|150px]]
[[image:kSmallWorldMInit_49_8.0.PNG|165px]]
[[image:kSmallWorldM_49_8.0.PNG|165px]]

W8 SmallWorld_100_2.0

[[image:kSmallWorld_100_2.0.PNG|150px]]
[[image:kSmallWorldMInit_100_2.0.PNG|165px]]
[[image:kSmallWorldM_100_2.0.PNG|165px]]

W9 SmallWorld_100_4.0

[[image:kSmallWorld_100_4.0.PNG|150px]]
[[image:kSmallWorldMInit_100_4.0.PNG|165px]]
[[image:kSmallWorldM_100_4.0.PNG|165px]]

W10 SmallWorld_100_8.0

[[image:kSmallWorld_100_8.0.PNG|150px]]
[[image:kSmallWorldMInit_100_8.0.PNG|165px]]
[[image:kSmallWorldM_100_8.0.PNG|165px]]

W11 SmallWorld_100_12.0

[[image:kSmallWorld_100_12.0.PNG|150px]]
[[image:kSmallWorldMInit_100_12.0.PNG|165px]]
[[image:kSmallWorldM_100_12.0.PNG|165px]]

=== 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.

{| border="1"
|+ Parameters and Resulting Graph characteristics
|-
| graphs || W1 ||W2|| W3 || W4 ||W5 ||W6||W7||W8
|- style="background:lightgrey;"
|'''init_vertices'''||4||4||4||4||2||2||2||4
|- style="background:lightgrey;"
|'''numEdgesToAttach'''||2||2||2||1||1||1||2||4
|- style="background:lightgrey;"
|'''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
|- style="background:#FFFFCC"
|density||0.45||0.27||0.19||0.16||0.16||0.2||0.27||0.37
|-style="background:#FFFFCC"
|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

[[image:baScaleFree_4_2_10.PNG|150px]]
[[image:baScaleFreeMInit_4_2_10.PNG|165px]]
[[image:baScaleFreeM_4_2_10.PNG|165px]]

W2 ScaleFree_4_2_50

[[image:baScaleFree_4_2_50.PNG|150px]]
[[image:baScaleFreeMInit_4_2_50.PNG|165px]]
[[image:baScaleFreeM_4_2_50.PNG|165px]]

W3 ScaleFree_4_2_100

[[image:baScaleFree_4_2_100.PNG|150px]]
[[image:baScaleFreeMInit_4_2_100.PNG|165px]]
[[image:baScaleFreeM_4_2_100.PNG|165px]]

W4 ScaleFree_4_1_100

[[image:baScaleFree_4_1_100.PNG|150px]]
[[image:baScaleFreeMInit_4_1_100.PNG|165px]]
[[image:baScaleFreeM_4_1_100.PNG|165px]]

W5 ScaleFree_2_1_100

[[image:baScaleFree_2_1_100.PNG|150px]]
[[image:baScaleFreeMInit_2_1_100.PNG|165px]]
[[image:baScaleFreeM_2_1_100.PNG|165px]]

W6 ScaleFree_2_1_50

[[image:baScaleFree_2_1_50.PNG|150px]]
[[image:baScaleFreeMInit_2_1_50.PNG|165px]]
[[image:baScaleFreeM_2_1_50.PNG|165px]]

W7 ScaleFree_2_2_50

[[image:baScaleFree_2_2_50.PNG|150px]]
[[image:baScaleFreeMInit_2_2_50.PNG|165px]]
[[image:baScaleFreeM_2_2_50.PNG|165px]]

W8 ScaleFree_4_4_50

[[image:baScaleFree_4_4_50.PNG|150px]]
[[image:baScaleFreeMInit_4_4_50.PNG|165px]]
[[image:baScaleFreeM_4_4_50.PNG|165px]]

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 [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 for Co-Authoring Networks
|Name ||Team Collaboration (with external collaborators)||Team Collaboration (within the team)||Infovis component 1 ||Infovis component 2 || Infovis component 3||Infovis component 4
|-style="background:lightgrey"
|'''Source'''||Collected ||Collected||Contest||Contest||Contest||Contest
|-
|numNodes||146||96||135||48||47||32
|-
|numEdges||540||316||321||91||114||109
|-
|components||1||1||1||1||1||1
|-style="background:#FFFFCC"
|density||0.16||0.19||0.13||0.2||0.23||0.33
|-style="background:#FFFFCC"
|clusteringCoefficient||0.91||0.91||0.82||0.79||0.83||0.81
|-
|diameter||4||5||11||7||10||6
|-
|averageShortestDistance||2.65||2.81||4.4||3.71||3.84||2.6
|-
|minDegree||1||1||1||1||1||1
|-
|maxDegree||57||29||22||11||15||15
|}

TeamCollaborationExternal

[[image: teamCollaborationExternal.PNG|150px]]
[[image: teamCollaborationExternalMInit.PNG|165px]]
[[image: teamCollaborationExternalM.PNG|165px]]

TeamCollaborationWithin

[[image: teamCollaborationWithin.PNG|150px]]
[[image: teamCollaborationWithinMInit.PNG|165px]]
[[image: teamCollaborationWithinM.PNG|165px]]

Infovis Component 1

[[image: ivComp1.PNG|150px]]
[[image: ivComp1MInit.PNG|165px]]
[[image: ivComp1M.PNG|165px]]

Infovis Component 2

[[image: ivComp2.PNG|150px]]
[[image: ivComp2MInit.PNG|165px]]
[[image: ivComp2M.PNG|165px]]

Infovis Component 3

[[image: ivComp3.PNG|150px]]
[[image: ivComp3MInit.PNG|165px]]
[[image: ivComp3M.PNG|165px]]

Infovis Component 4

[[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.09||0.23||0.16||0.09
|-style="background:#FFFFCC"
|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

[[image: gondolaGen.PNG|150px]]
[[image: gondolaGenMInit.PNG|165px]]
[[image: gondolaGenM.PNG|165px]]

MSTTransmission 1

[[image: mst1.PNG|150px]]
[[image: mst1MInit.PNG|165px]]
[[image: mst1M.PNG|165px]]

MSTTransmission 2

[[image: mst2.PNG|150px]]
[[image: mst2MInit.PNG|165px]]
[[image: mst2M.PNG|165px]]

HIV Transmission

[[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

[[image: emailDay.PNG|150px]]
[[image: emailDayMInit.PNG|165px]]
[[image: emailDayM.PNG|165px]]

Email exchange per person during a week

[[image: emailWeek.PNG|150px]]
[[image: emailWeekMInit.PNG|165px]]
[[image: emailWeekM.PNG|165px]]

Email exchange per person during a month

[[image: emailMonth.PNG|150px]]
[[image: emailMonthMInit.PNG|165px]]
[[image: emailMonthM.PNG|165px]]

Email exchange per person during a year

[[image: emailYear.PNG|150px]]
[[image: emailYearMInit.PNG|165px]]
[[image: emailYearM.PNG|165px]]

Email exchange per research group during a day

[[image: emailGDay.PNG|150px]]
[[image: emailGDayMInit.PNG|165px]]
[[image: emailGDayM.PNG|165px]]

Email exchange per research group during a week

[[image: emailGWeek.PNG|150px]]
[[image: emailGWeekMInit.PNG|165px]]
[[image: emailGWeekM.PNG|165px]]

Email exchange per research group during a month

[[image: emailGMonth.PNG|150px]]
[[image: emailGMonthMInit.PNG|165px]]
[[image: emailGMonthM.PNG|165px]]

Email exchange per research group during a year

[[image: emailGYear.PNG|150px]]
[[image: emailGYearMInit.PNG|165px]]
[[image: emailGYearM.PNG|165px]]

File:Mst2MInit.PNG

2006-11-16T12:41:04Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Mst2M.PNG

2006-11-16T12:40:59Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Mst2.PNG

2006-11-16T12:40:54Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Mst1MInit.PNG

2006-11-16T12:40:48Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Mst1M.PNG

2006-11-16T12:39:55Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Mst1.PNG

2006-11-16T12:39:38Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:HivMInit.PNG

2006-11-16T12:39:23Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:HivM.PNG

2006-11-16T12:39:14Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:Hiv.PNG

2006-11-16T12:39:05Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:GondolaGenMInit.PNG

2006-11-16T12:38:56Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:GondolaGenM.PNG

2006-11-16T12:38:42Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

File:GondolaGen.PNG

2006-11-16T12:37:55Z

Socnet:

== Summary ==

== Copyright status ==

== Source ==

Tasks Taxonomy for Graphs

2006-10-16T09:39:08Z

Socnet: /* High-Level Tasks */

== Low-Level Tasks ==

From [Amar et al. 2005] and [Lee et al 2006].

* General Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Retrieve Value ||Given a set of cases, find attributes of those cases.
|-
|Filter||Given some conditions on attributes values, find data cases satisfying those conditions.
|-
|Compute Derived Value||Given a set of data cases, compute an aggregate numeric representation of those data cases.(e.g. average, median, and count)
|-
|Find Extremum||Find data cases possessing an extreme value of an attribute over its range within the data set.
|-
|Sort||Given a set of data cases, rank them according to some ordinal metric.
Determine Range Given a set of data cases and an attribute of interest, find the span of values within the set.
|-
|Characterize Distribution||Given a set of data cases and a quantitative attribute of interest, characterize the distribution of that attribute’s values over the set.
|-
|Find Anomalies||Identify any anomalies within a given set of data cases with respect to a given relationship or expectation, e.g. statistical outliers.
|-
|Cluster||Given a set of data cases, find clusters of similar attribute values.
|-
|Correlate||Given a set of data cases and two attributes, determine useful relationships between the values of those attributes.
|-
|Scan|| Quickly review a set of items.
|-
|Set Operation|| Given multiple sets of items, perform set operations on them. For example, find the intersection of the set of nodes.
|}

* Graph Specific Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Find Adjacent Nodes ||Given a node, find its adjacent nodes.
|}

== Graph Task Taxonomy ==

Examples are illustrated using 4 types of graphs:
*(FOAF): friend-of-a-friend
*(FW): food web
*(GO): gene ontology
*(ARM): airport routing map

=== Topology-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Adjacency (direct connection)
|
* Find the set of nodes adjacent to a node?
* How many nodes are adjacent to a node?
* Which node has a maximum number of adjacent nodes?
||
*(FOAF) Find the names of the direct friends of Eric.
*(FW) How many kinds of organisms do golden eagles eat?
*(FOAF) Who is the most popular person?
|-
| Accessibility (direct or indirect connection)
|
* Find the set of nodes accessible from a node.
* How many nodes are accessible from a node?
* Find the set of nodes accessible from a node where the distance is less than or equal to n.
* How many nodes are accessible from a node where the distance is less than or equal to n?
||
*(FOAF) Who are your friends, your friends’ friends, and so on?
*(FOAF) How many friends are you connected to in this way?
*(ARM) To what cities can we go from Seoul, Korea by changing planes only once?
|-
| Commmon Connection
|
* Given nodes, find a set of nodes that are connected to all of them.
||
*(FOAF)Find all the people who know both John and Jack.
|-
| Connectivty
|
*Find the shortest path between two nodes.
*Identify clusters.
*Identify connected components.
*Find bridges.
*Find articulation points.
||
*(ARM) What is the shortest path from Seoul, Korea to Athens, Greece?
*(FOAF) Count the number of clusters.
*(FW) There may be subgraphs independent of each other. Count the number of connected components in the graph.
*(FOAF) Who is the person whose removal from the graph results in an unconnected graph?
*(FW) Which is the eating link whose removal from the graph results in an unconnected graph?
|}

=== Attribute-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| On the Nodes
|
* Find the nodes having a specific attribute value.
* Review the set of nodes.
||
*(FOAF) Who do you know from the people currently shown on screen?
*(FOAF) How many people do you know from the ones currently shown on screen?
*(FOAF) Are there any foreign-sounding names?
|-
| On the Links
|
* Given a node, find the nodes connected only by certain types of links.
* Which node is connected by a link having the largest/smallest value?
||
*(GO) Find the nodes connected by “is-a” relationships from the “Biological Process” node.
*(FW) If a link has an attribute representing the percentage of the diet, what is main food of American crow?
|}

=== Browsing Tasks ===
{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Follow Path
|
* Follow a given path
||
* (FOAF) A user looks into A’s friend B, B’s friend C, and C’s friend D.
* (FW) Follow the flow of energy from grasses, to a rabbit that eats grass, to a carnivore that eats the rabbit, and to a carnivore that eats that carnivore.
|-
| Revisit
|
* Return to a previously visited node.
||
*(FOAF) After they follow a path in the above task, they may want to see A’s other friends.
*(FW) Find another carnivore that eats the same rabbit.
|}

=== Overview Tasks ===
This is a compound exploratory task to get estimated values quickly. For example, we might ask users to estimate the size of the social network. Note that sometimes it is more important to be able to estimate the answer than to get an accurate one. Some of the topology tasks can be done easily using an overview of the graph as well. For example, using particular layout algorithms, it is easy to see whether or not there are clusters and connected components. Other algorithms help to find shortest paths between nodes. Overview also helps to find patterns.

Examples:
* estimate size of the network
* estimate the number of connected components
* is the network clustered?
* can you identify different patterns of connection?
* (FOAF) has the network a small-world structure?

== High-Level Tasks ==

High-Level tasks which are not a combination of lower level tasks.

* When we compare two or more food webs, we can ask the following questions: What do they have in common? What are the differences among those food webs? Is there any missing or conflicting information?
* Due to errors in the data, several nodes may represent the same entity. For example, the co-authorship graphs often have duplicate author nodes. One important task is to identify whether two or more nodes represent the same person.
* How has the graph changed over time?

== References ==

* [Amar et al. 2005] Amar, R., Eagan, J., and Stasko, J. Low-Level Components of Analytic Activity in Information Visualization, Proceedings of the Symposium on Information Visualization (InfoVis ’05), pp. 111-117, 2005.

* [Lee et al. 2006] Lee, B., Plaisant, C., Parr, CS., Fekete, JD. and Henry, N. Task Taxonomy for Graph Visualization, In BEyond time and errors: novel evaLuation methods for Information Visualization (BELIV'06), Venice, Italy, May 2006, to be published.

Tasks Taxonomy for Graphs

2006-10-16T09:38:20Z

Socnet: /* Overview Tasks */

== Low-Level Tasks ==

From [Amar et al. 2005] and [Lee et al 2006].

* General Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Retrieve Value ||Given a set of cases, find attributes of those cases.
|-
|Filter||Given some conditions on attributes values, find data cases satisfying those conditions.
|-
|Compute Derived Value||Given a set of data cases, compute an aggregate numeric representation of those data cases.(e.g. average, median, and count)
|-
|Find Extremum||Find data cases possessing an extreme value of an attribute over its range within the data set.
|-
|Sort||Given a set of data cases, rank them according to some ordinal metric.
Determine Range Given a set of data cases and an attribute of interest, find the span of values within the set.
|-
|Characterize Distribution||Given a set of data cases and a quantitative attribute of interest, characterize the distribution of that attribute’s values over the set.
|-
|Find Anomalies||Identify any anomalies within a given set of data cases with respect to a given relationship or expectation, e.g. statistical outliers.
|-
|Cluster||Given a set of data cases, find clusters of similar attribute values.
|-
|Correlate||Given a set of data cases and two attributes, determine useful relationships between the values of those attributes.
|-
|Scan|| Quickly review a set of items.
|-
|Set Operation|| Given multiple sets of items, perform set operations on them. For example, find the intersection of the set of nodes.
|}

* Graph Specific Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Find Adjacent Nodes ||Given a node, find its adjacent nodes.
|}

== Graph Task Taxonomy ==

Examples are illustrated using 4 types of graphs:
*(FOAF): friend-of-a-friend
*(FW): food web
*(GO): gene ontology
*(ARM): airport routing map

=== Topology-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Adjacency (direct connection)
|
* Find the set of nodes adjacent to a node?
* How many nodes are adjacent to a node?
* Which node has a maximum number of adjacent nodes?
||
*(FOAF) Find the names of the direct friends of Eric.
*(FW) How many kinds of organisms do golden eagles eat?
*(FOAF) Who is the most popular person?
|-
| Accessibility (direct or indirect connection)
|
* Find the set of nodes accessible from a node.
* How many nodes are accessible from a node?
* Find the set of nodes accessible from a node where the distance is less than or equal to n.
* How many nodes are accessible from a node where the distance is less than or equal to n?
||
*(FOAF) Who are your friends, your friends’ friends, and so on?
*(FOAF) How many friends are you connected to in this way?
*(ARM) To what cities can we go from Seoul, Korea by changing planes only once?
|-
| Commmon Connection
|
* Given nodes, find a set of nodes that are connected to all of them.
||
*(FOAF)Find all the people who know both John and Jack.
|-
| Connectivty
|
*Find the shortest path between two nodes.
*Identify clusters.
*Identify connected components.
*Find bridges.
*Find articulation points.
||
*(ARM) What is the shortest path from Seoul, Korea to Athens, Greece?
*(FOAF) Count the number of clusters.
*(FW) There may be subgraphs independent of each other. Count the number of connected components in the graph.
*(FOAF) Who is the person whose removal from the graph results in an unconnected graph?
*(FW) Which is the eating link whose removal from the graph results in an unconnected graph?
|}

=== Attribute-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| On the Nodes
|
* Find the nodes having a specific attribute value.
* Review the set of nodes.
||
*(FOAF) Who do you know from the people currently shown on screen?
*(FOAF) How many people do you know from the ones currently shown on screen?
*(FOAF) Are there any foreign-sounding names?
|-
| On the Links
|
* Given a node, find the nodes connected only by certain types of links.
* Which node is connected by a link having the largest/smallest value?
||
*(GO) Find the nodes connected by “is-a” relationships from the “Biological Process” node.
*(FW) If a link has an attribute representing the percentage of the diet, what is main food of American crow?
|}

=== Browsing Tasks ===
{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Follow Path
|
* Follow a given path
||
* (FOAF) A user looks into A’s friend B, B’s friend C, and C’s friend D.
* (FW) Follow the flow of energy from grasses, to a rabbit that eats grass, to a carnivore that eats the rabbit, and to a carnivore that eats that carnivore.
|-
| Revisit
|
* Return to a previously visited node.
||
*(FOAF) After they follow a path in the above task, they may want to see A’s other friends.
*(FW) Find another carnivore that eats the same rabbit.
|}

=== Overview Tasks ===
This is a compound exploratory task to get estimated values quickly. For example, we might ask users to estimate the size of the social network. Note that sometimes it is more important to be able to estimate the answer than to get an accurate one. Some of the topology tasks can be done easily using an overview of the graph as well. For example, using particular layout algorithms, it is easy to see whether or not there are clusters and connected components. Other algorithms help to find shortest paths between nodes. Overview also helps to find patterns.

Examples:
* estimate size of the network
* estimate the number of connected components
* is the network clustered?
* can you identify different patterns of connection?
* (FOAF) has the network a small-world structure?

== High-Level Tasks ==

== References ==

* [Amar et al. 2005] Amar, R., Eagan, J., and Stasko, J. Low-Level Components of Analytic Activity in Information Visualization, Proceedings of the Symposium on Information Visualization (InfoVis ’05), pp. 111-117, 2005.

* [Lee et al. 2006] Lee, B., Plaisant, C., Parr, CS., Fekete, JD. and Henry, N. Task Taxonomy for Graph Visualization, In BEyond time and errors: novel evaLuation methods for Information Visualization (BELIV'06), Venice, Italy, May 2006, to be published.

Tasks Taxonomy for Graphs

2006-10-16T09:35:01Z

Socnet: /* Browsing Tasks */

== Low-Level Tasks ==

From [Amar et al. 2005] and [Lee et al 2006].

* General Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Retrieve Value ||Given a set of cases, find attributes of those cases.
|-
|Filter||Given some conditions on attributes values, find data cases satisfying those conditions.
|-
|Compute Derived Value||Given a set of data cases, compute an aggregate numeric representation of those data cases.(e.g. average, median, and count)
|-
|Find Extremum||Find data cases possessing an extreme value of an attribute over its range within the data set.
|-
|Sort||Given a set of data cases, rank them according to some ordinal metric.
Determine Range Given a set of data cases and an attribute of interest, find the span of values within the set.
|-
|Characterize Distribution||Given a set of data cases and a quantitative attribute of interest, characterize the distribution of that attribute’s values over the set.
|-
|Find Anomalies||Identify any anomalies within a given set of data cases with respect to a given relationship or expectation, e.g. statistical outliers.
|-
|Cluster||Given a set of data cases, find clusters of similar attribute values.
|-
|Correlate||Given a set of data cases and two attributes, determine useful relationships between the values of those attributes.
|-
|Scan|| Quickly review a set of items.
|-
|Set Operation|| Given multiple sets of items, perform set operations on them. For example, find the intersection of the set of nodes.
|}

* Graph Specific Tasks
{|border="1"
|-
|'''Task'''||'''Description'''
|-
|Find Adjacent Nodes ||Given a node, find its adjacent nodes.
|}

== Graph Task Taxonomy ==

Examples are illustrated using 4 types of graphs:
*(FOAF): friend-of-a-friend
*(FW): food web
*(GO): gene ontology
*(ARM): airport routing map

=== Topology-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Adjacency (direct connection)
|
* Find the set of nodes adjacent to a node?
* How many nodes are adjacent to a node?
* Which node has a maximum number of adjacent nodes?
||
*(FOAF) Find the names of the direct friends of Eric.
*(FW) How many kinds of organisms do golden eagles eat?
*(FOAF) Who is the most popular person?
|-
| Accessibility (direct or indirect connection)
|
* Find the set of nodes accessible from a node.
* How many nodes are accessible from a node?
* Find the set of nodes accessible from a node where the distance is less than or equal to n.
* How many nodes are accessible from a node where the distance is less than or equal to n?
||
*(FOAF) Who are your friends, your friends’ friends, and so on?
*(FOAF) How many friends are you connected to in this way?
*(ARM) To what cities can we go from Seoul, Korea by changing planes only once?
|-
| Commmon Connection
|
* Given nodes, find a set of nodes that are connected to all of them.
||
*(FOAF)Find all the people who know both John and Jack.
|-
| Connectivty
|
*Find the shortest path between two nodes.
*Identify clusters.
*Identify connected components.
*Find bridges.
*Find articulation points.
||
*(ARM) What is the shortest path from Seoul, Korea to Athens, Greece?
*(FOAF) Count the number of clusters.
*(FW) There may be subgraphs independent of each other. Count the number of connected components in the graph.
*(FOAF) Who is the person whose removal from the graph results in an unconnected graph?
*(FW) Which is the eating link whose removal from the graph results in an unconnected graph?
|}

=== Attribute-based Tasks ===

{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| On the Nodes
|
* Find the nodes having a specific attribute value.
* Review the set of nodes.
||
*(FOAF) Who do you know from the people currently shown on screen?
*(FOAF) How many people do you know from the ones currently shown on screen?
*(FOAF) Are there any foreign-sounding names?
|-
| On the Links
|
* Given a node, find the nodes connected only by certain types of links.
* Which node is connected by a link having the largest/smallest value?
||
*(GO) Find the nodes connected by “is-a” relationships from the “Biological Process” node.
*(FW) If a link has an attribute representing the percentage of the diet, what is main food of American crow?
|}

=== Browsing Tasks ===
{| border="1"
|-
|'''Task'''||'''Description''' || '''Examples'''
|-
| Follow Path
|
* Follow a given path
||
* (FOAF) A user looks into A’s friend B, B’s friend C, and C’s friend D.
* (FW) Follow the flow of energy from grasses, to a rabbit that eats grass, to a carnivore that eats the rabbit, and to a carnivore that eats that carnivore.
|-
| Revisit
|
* Return to a previously visited node.
||
*(FOAF) After they follow a path in the above task, they may want to see A’s other friends.
*(FW) Find another carnivore that eats the same rabbit.
|}

=== Overview Tasks ===

== High-Level Tasks ==

== References ==

* [Amar et al. 2005] Amar, R., Eagan, J., and Stasko, J. Low-Level Components of Analytic Activity in Information Visualization, Proceedings of the Symposium on Information Visualization (InfoVis ’05), pp. 111-117, 2005.

* [Lee et al. 2006] Lee, B., Plaisant, C., Parr, CS., Fekete, JD. and Henry, N. Task Taxonomy for Graph Visualization, In BEyond time and errors: novel evaLuation methods for Information Visualization (BELIV'06), Venice, Italy, May 2006, to be published.