2011 · 57 citations · 23 references
ComputingData ScienceComplex SystemsGraph VisualizationSocial InfluenceCommunity DetectionCommunity StructureNetwork DynamicsNetwork StabilitySocial Network AnalysisSocial NetworksCommunity EvolutionCommunity Stability AnalysisDynamic Community DetectionNetwork Community DetectionSocial Graph AnalysisTemporal Community Detection
Social network analysis is a discipline that has emerged to analyze social structures and information networks to uncover patterns of interaction among the vertices in the network. Most social networks are dynamic, and studying the evolution of these networks over time could provide insight into the behavior of individuals expressed by the nodes in the graph and the flow of information among them. In a dynamic network, communities, which are groups of densely interconnected nodes, are affected by changes in the underlying population. The analysis of communities and their evolutions can help determine the shifting structural properties of the networks. We present a framework for modeling and detecting community evolution over time. First, our proposed community matching algorithm efficiently identifies and tracks similar communities over time. Then, a series of significant events and transitions are defined to characterize the evolution of networks in terms of its communities and individuals. We also propose two metrics called stability and influence metrics to describe the active behavior of the individuals. We present experiments to explore the dynamics of communities on the Enron email and DBLP datasets. Evaluating the events using topics extracted from the detected communities demonstrates that we can successfully track communities over time in real datasets.
23
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Uncovering the overlapping community structure of complex networks in nature and society
Gergely Palla, Imre Derényi, Illés J. Farkas et al. · Nature · 2005 · 5.4K citations · Full text
Jure Leskovec, Jon Kleinberg, Christos Faloutsos · 2005 · 2.3K citations
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
Peter J. Mucha, Thomas Richardson, K. T. Macon et al. · Science · 2010 · 2.2K citations · Full text