Community detection is an important tool for analyzing the social graph of mobile phone users. The problem of nding communities in static graphs has been widely studied. However, since mobile social networks evolve over time, static graph algorithms are not sucient. To be useful in practice (e.g. when used by a telecom analyst), the stability of the partitions becomes critical. We tackle this particular use case in this paper: tracking evolution of com- munities in dynamic scenarios with focus on stability. We propose two modications to a widely used static community detection algorithm: we introduce xed nodes and preferential attachment to pre-existing com- munities. We then describe experiments to study the stability and quality of the resulting partitions on real-world social networks, represented by monthly call graphs for millions of subscribers.
Many related papers have investigated the importance of communities, and served us as reference. Foundational concepts and examples for communities detection may be found in @cite_0 . For instance, the interactions between the major characters of the novel Les Misérables'' by Victor Hugo can be viewed as a graph with 77 nodes, and the characters organized as communities (the example is very intuitive and easy to grasp for the fans of the novel). Another classic example is Zachary’s karate club, an organization with 34 nodes that split into two separate clubs in real life. Each new part can be mapped almost perfectly to the two main communities of friends detected in the original club. The paper also analyzes algorithms, such as shortest-path and random walk. Of course, the graphs considered in @cite_0 have a much smaller scale than the ones considered in this work.
@cite_0
2095293504
We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.