Community Analysis in Dynamic Social Networks

List of Figures......Page 7
List of Tables......Page 9
List of Algorithms......Page 11
Online Communities - A Spreading Phenomenon......Page 15
Addressing Real World Problems......Page 19
Structure of the Thesis......Page 20
Types of Social Networks......Page 23
Analyzing Networks......Page 25
Subgroups in Social Network Analysis......Page 30
Real-World and Virtual Communities......Page 33
Graph Clustering Techniques......Page 36
Partitioning Methods......Page 37
Hierarchical Methods......Page 38
Density-based Methods......Page 40
Resilience Measure for Graph Clusters......Page 41
Quality Measures for Graph Clusterings......Page 42
Tracking Temporal Dynamics of Communities......Page 46
Community Evolution Models......Page 47
Models for the Evolution of Clusters......Page 48
Community Evolution in an Organizational Context......Page 49
The Community Discovery Model......Page 53
Partitioning the Time Axis and Building the Graph of Interactions......Page 55
Clustering Users into Community Instances......Page 58
Evolution of Community Instances......Page 60
Community Survival Graph......Page 62
Communities in the Survival Graph......Page 63
Actor-oriented Visualization of Community Instance Evolution......Page 64
Group-oriented Visualization of Community Instance Evolution......Page 66
Application: Studying Communities with Fluctuating Members......Page 69
The IKUS Data Set......Page 70
Determining Parameters......Page 71
Data Set Characteristics......Page 72
Fluctuating Members......Page 73
Users within Evolving Communities......Page 77
Relevance of a Community for a User......Page 79
Modelling Community Dynamics......Page 81
Concluding Remarks......Page 83
DENGRAPH: Density-based Graph Clustering......Page 87
Density-Reachability in a Graph......Page 88
Graph Clustering for Overlapping Communities......Page 90
DENGRAPH-IO: Incremental Graph Clustering......Page 91
Cluster Changes......Page 92
Correctness of the Incremental Updates......Page 97
Complexity and Computation Time......Page 101
Evaluating Graph Clusters......Page 102
Graph Cluster Stability......Page 103
Graph Cluster Quality......Page 104
Enron Data Set......Page 107
Defining Proximity in the Enron Graph......Page 109
Experiments and Results......Page 110
Application: Graph over Similarity......Page 129
Defining Similarity in the Last.fm Graph......Page 130
Experiments and Results......Page 133
The Impact of the Parameters on the Clustering......Page 146
Characteristics of Core and Border Vertices......Page 147
Impact of Positive and Negative Changes on Running Time......Page 148
Cluster Resilience and DENGRAPH-Stability......Page 149
Related Work......Page 150
Concluding Remarks......Page 151
Main Contributions......Page 153
Future Work......Page 154
Pseudocode......Page 157
Experimental Results......Page 161
Bibliography......Page 171