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.
To perform community detection in graphs with 92 million nodes (see ), efficient algorithms are required. We based our research on the Louvain Method algorithm originally published in @cite_5 . As discussed in , it was modified in @cite_4 to get a dynamic algorithm. However, that algorithm still lacks stability. We used the implementation of @cite_4 as baseline to evaluate our Dynamic Louvain Method.
@cite_5 @cite_4
2131681506 1528751587
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad hoc modular networks. Complex networks can often be divided in dense sub-networks called communities. Using a partition edit distance, we study how three community detection algorithms transform their outputs if the input network is slightly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in an evolving network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finally use it on an evolving network of blogs.