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.
Besides the static analysis, the report discusses communities evolution (dynamic communities), although it points out that the analysis of dynamic communities is still in its infancy." It suggest that it would be desirable to have a unified framework, in which clusters are deduced both from the current structure of the graph and from the knowledge of the cluster structure at previous times." We have implemented that idea, since we use the previous history of community structure throughout the whole algorithm (according to the @math and @math parameters), and not only during the nodes initialization (as in @cite_4 ).
@cite_4
1912249326 2022651954 2295989749 2014714110
Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterward the communities across layers. Alternatively, one can develop dedicated dynamic procedures so that multiple snapshots are simultaneously taken into account while detecting communities, which allows us to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario. The discovery of evolving communities in dynamic networks is an important research topic that poses challenging tasks. Evolutionary clustering is a recent framework for clustering dynamic networks that introduces the concept of temporal smoothness inside the community structure detection method. Evolutionary-based clustering approaches try to maximize cluster accuracy with respect to incoming data of the current time step, and minimize clustering drift from one time step to the successive one. In order to optimize both these two competing objectives, an input parameter that controls the preference degree of a user towards either the snapshot quality or the temporal quality is needed. In this paper the detection of communities with temporal smoothness is formulated as a multiobjective problem and a method based on genetic algorithms is proposed. The main advantage of the algorithm is that it automatically provides a solution representing the best trade-off between the accuracy of the clustering obtained, and the deviation from one time step to the successive. Experiments on synthetic data sets show the very good performance of the method when compared with state-of-the-art approaches. Evolutionary community discovery is a hot research topic which clusters the dynamic or temporal network. The communities detected in dynamic network should get reasonable partition for the current data while simultaneously not deviate drastically from the previous ones. In this paper, the evolutionary community discovery algorithm based on leader nodes (EvoLeaders) is proposed to cluster the dynamic network. Compared with the static community discovery algorithm based on leader nodes (the Top Leaders algorithm), experimental results over two real-world datasets demonstrate that the EvoLeaders is more suitable for dynamic scenarios. Community structure is a key property of complex networks. Many algorithms have been proposed to automatically detect communities in static networks but few studies have considered the detection and tracking of communities in an evolving network. Tracking the evolution of a given community over time requires a clustering algorithm that produces stable clusters. However, most community detection algorithms are very unstable and therefore unusable for evolving networks. In this paper, we apply the methodology proposed in [seifi2012] to detect what we call community cores in evolving networks. We show that cores are much more stable than "classical" communities and that we can overcome the disadvantages of the stabilized methods.