Community analysis in dynamic social networks [Elektronische Ressource] / von Tanja Falkowski

Sujets

• Informatik
• Soziologie

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2009
• Nombre de lectures: 33
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

Community Analysis
in Dynamic Social Networks
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieurin (Dr.-Ing.)
angenommen durch die Fakultat fur Informatik
der Otto-von-Guericke-Universitat Magdeburg
von Dipl. Wirt.-Inf. Tanja Falkowski
geb. am 18. Oktober 1972 in Gottingen
Gutachter:
Prof. Dr. Ulrik Brandes
Prof. Dr. Rudolf Kruse
Prof. Dr. Myra Spiliopoulou
Magdeburg, den 14. Mai 2009Contents
List of Figures v
List of Tables vii
List of Algorithms ix
1 Introduction 1
1.1 Online Communities - A Spreading Phenomenon . . . . . . . . . . . . . . . 1
1.2 Addressing Real World Problems . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Fundamentals 9
2.1 Social Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Types of Social Networks . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Analyzing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Communities in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Subgroups in Social Network Analysis . . . . . . . . . . . . . . . . 16
2.2.2 Real-World and Virtual Communities . . . . . . . . . . . . . . . . . 19
2.3 Graph Clustering Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Partitioning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 Hierarchical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 Density-based Methods . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Evaluating Graph Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 Resilience Measure for Graph Clusters . . . . . . . . . . . . . . . . 27
2.4.2 Quality Measures for Graph Clusterings . . . . . . . . . . . . . . . 28
2.5 Tracking Temporal Dynamics of Communities . . . . . . . . . . . . . . . . 32
2.5.1 Network Evolution Models . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Community Evolution Models . . . . . . . . . . . . . . . . . . . . . 33
2.5.3 Models for the Evolution of Clusters . . . . . . . . . . . . . . . . . 34
2.5.4 Community Evolution in an Organizational Context . . . . . . . . . 35
3 Community as a Subgraph Formation Over Time 39
3.1 The Community Discovery Model . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.1 Partitioning the Time Axis and Building the Graph of Interactions 41
3.1.2 Clustering Users into Community Instances . . . . . . . . . . . . . 44
3.1.3 Evolution of Community Instances . . . . . . . . . . . . . . . . . . 46
3.1.4 Community Survival Graph . . . . . . . . . . . . . . . . . . . . . . 48
iContents
3.1.5 Communities in the Survival Graph . . . . . . . . . . . . . . . . . . 49
3.2 Visualizing Temporal Dynamics in Communities . . . . . . . . . . . . . . . 50
3.2.1 Actor-oriented Visualization of Community Instance Evolution . . . 50
3.2.2 Group-oriented Visualization of Community Instance Evolution . . 52
3.3 Application: Studying Communities with Fluctuating Members . . . . . . 55
3.3.1 The IKUS Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.2 Determining Parameters . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.3 Data Set Characteristics . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.4 Fluctuating Members . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 Application: Representativeness of Communities for Members . . . . . . . 63
3.4.1 Users within Evolving Communities . . . . . . . . . . . . . . . . . . 63
3.4.2 Relevance of a Community for a User . . . . . . . . . . . . . . . . . 65
3.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5.1 Modelling Community Dynamics . . . . . . . . . . . . . . . . . . . 67
3.5.2 Visualizing Community Dynamics . . . . . . . . . . . . . . . . . . . 69
3.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 Community as a Subgraph that Evolves Over Time 73
4.1 DENGRAPH: Density-based Graph Clustering . . . . . . . . . . . . . . . . 73
4.1.1 Density-Reachability in a Graph . . . . . . . . . . . . . . . . . . . . 74
4.1.2 Graph Clustering for Overlapping Communities . . . . . . . . . . . 76
4.1.3 Complexity and Computation Time . . . . . . . . . . . . . . . . . . 77
4.2 DENGRAPH-IO: Incremental Graph Clustering . . . . . . . . . . . . . . . 77
4.2.1 Cluster Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.2 Correctness of the Incremental Updates . . . . . . . . . . . . . . . . 83
4.2.3 Complexity and Computation Time . . . . . . . . . . . . . . . . . . 87
4.3 Evaluating Graph Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3.1 Graph Cluster Stability . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.2 Graph Cluster Quality . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4 Application: Graph over Interactions . . . . . . . . . . . . . . . . . . . . . 93
4.4.1 Enron Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4.2 De ning Proximity in the Enron Graph . . . . . . . . . . . . . . . . 95
4.4.3 Experiments and Results . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5 Application: Graph over Similarity . . . . . . . . . . . . . . . . . . . . . . 115
4.5.1 Last.fm Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.5.2 De ning Similarity in the Last.fm Graph . . . . . . . . . . . . . . . 116
4.5.3 Experiments and Results . . . . . . . . . . . . . . . . . . . . . . . . 119
4.6 Characteristics of the DENGRAPH-IO Algorithm . . . . . . . . . . . . . . 132
4.6.1 The Impact of the Parameters on the Clustering . . . . . . . . . . . 132
4.6.2 Characteristics of Core and Border Vertices . . . . . . . . . . . . . 133
4.6.3 Relevant Edge-Changes for the Clustering . . . . . . . . . . . . . . 134
4.6.4 Impact of Positive and Negative Changes on Running Time . . . . 134
iiContents
4.6.5 Cluster Resilience and DENGRAPH-Stability . . . . . . . . . . . . 135
4.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5 Conclusion 139
5.1 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
A Pseudocode 143
B Experimental Results 147
Bibliography 157
iiiList of Figures
3.1 Community Discovery Roadmap . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Partitioning the Time Axis. . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Building a Graph for Each Time Window. . . . . . . . . . . . . . . . . . . 44
3.4 Edge Betweenness Clustering. . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5 Dendrogram-cut Based on Highest Modularity. . . . . . . . . . . . . . . . . 47
3.6 Comparing Community Instances . . . . . . . . . . . . . . . . . . . . . . . 51
3.7 Community Survival Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.8 Temporal View of Community Survival Graph with Zoom . . . . . . . . . 55
3.9 Cut-out of Community Survival Graph . . . . . . . . . . . . . . . . . . . . 56
3.10 IKUS: Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.11 IKUS: Dendrogram (Example) . . . . . . . . . . . . . . . . . . . . . . . . 59
3.12 Actor-oriented Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.13 IKUS: Structural Breaks in the Community Evolution . . . . . . . . . . . 62
3.14 Example for Community Instance . . . . . . . . . . . . . . . . . . . . . . . 65
4.1 DENGRAPH: Concepts of Connectivity . . . . . . . . . . . . . . . . . . . 75
4.2 DEH-IO: The update method . . . . . . . . . . . . . . . . . . . . . 80
4.3 DENGRAPH-IO: New Close Relation and Lost Close Relation . . . . . . . 82
4.4 DEH-IO: Detecting a Cluster Split . . . . . . . . . . . . . . . . . . 84
4.5 Modularity Calculation for Clusters with Overlaps . . . . . . . . . . . . . . 91
4.6 Enron: Data Set Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.7 Enron: Inuence of Parameters and (Enron-intern, week) . . . . . . . . 98
4.8 Enron: Inuence of Parameters and (Enr, month) . . . . . . . 99
4.9 Enron: Inuence of Parameters and (Enron-total, week) . . . . . . . . 100
4.10 Enron: Inuence of Parameters and (Enr, month) . . . . . . . . 101
4.11 Enron: Graph in Week 49/2000 (Enron-intern, week) . . . . . . . . . . . . 104
4.12 Enron: Cluster Resilience and DENGRAPH-Stability (Enron-intern, week) 105
4.13 Enron: Graph in Month 1/2001 (Enron-intern, month) . . . . . . . . . . . 106
4.14 Enron: Cluster Resilience and DENGRAPH-Stability (Enron-intern, month)107
4.15 Enron: Graph in Week 50/2001 (Enron-total, week) . . . . . . . . . . . . . 108
4.16 Enron: Cluster Resilience and DENGRAPH-Stability (Enron-total, week) . 109
4.17 Enron: Graph in Month 4/2001 (Enron-total, month) . . . . . . . . . . . . 110
4.18 Enron: Cluster Resilience and DENGRAPH-Stability (Enron-total, month) 111
4.19 Enron: Clustering Results (Enron-total, week) . . . . . . . . . . . . . . . . 114
4