Difference between revisions of "Social Network Generation"
|Line 203:||Line 203:|
Revision as of 10:35, 4 December 2006
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 and Geomi are incremental scale-free networks generators such as the Barabasi and Albert model.
About datasets and pictures
- 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].
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:latticeSize (the lattice size (length of row or column dimension)) and clusteringExponent (the clustering exponent parameter).
Scale-Free Networks Generator
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: 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  and UCINet .
|Name||Team Collaboration (with external collaborators)||Infovis component 1||Infovis component 2||Infovis component 3||Infovis component 4|
Infovis Component 1 ivComp1.xml
Infovis Component 2 ivComp2.xml
Infovis Component 3 ivComp3.xml
Infovis Component 4 ivComp4.xml
|Source||Pajek||Article ||Article||Article |
Gondola Genealogy gondolaGen.xml
MSTTransmission 1 Mst1.xml
MSTTransmission 2 Mst2.xml
HIV Transmission Hiv.xml
Almost Complete Graphs
|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|
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 (Email number is coded with link width in the nodelink, edge color in the matrix)
Email exchange per research group during a week emailGWeek.xml (Email number is coded with link width in the nodelink, edge color in the matrix)
Email exchange per research group during a month emailGMonth.xml (Email number is coded with link width in the nodelink, edge color in the matrix)
Email exchange per research group during a year emailGYear.xml (Email number is coded with link width in the nodelink, edge color in the matrix)