Finding communities in evolving networks is a difficult task and raises issues different from the classic static detection case. We introduce an approach based on the recent vertex-centred paradigm. The proposed algorithm, named DynLOCNeSs, detects communities by scanning and evaluating each vertex neighbourhood, which can be done independently in a parallel way. It is done by means of a preference measure, using these preferences to handle community changes. We also introduce a new vertex neighbourhood preference measure, CWCN, more efficient than current existing ones in the considered context. Experimental results show the relevance of this measure and the ability of the proposed approach to detect classical community evolution patterns such as grow-shrink and merge-split.
@cite_0: Detecting community structure is fundamental for uncovering the links between structure and function in complex networks and for practical applications in many disciplines such as biology and sociology. A popular method now widely used relies on the optimization of a quantity called modularity, which is a quality index for a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. This finding is confirmed through several examples, both in artificial and in real social, biological, and technological networks, where we show that mod ularity optimization indeed does not resolve a large number of modules. A check of the modules obtained through modularity optimization is thus necessary, and we provide here key elements for the assessment of the reliability of this community detection method.
@cite_18: The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
The main community detection method family is criterion optimisation. A global or local criterion measuring the quality of a graph partition into communities, such as the well-known modularity @cite_18 , is optimised through several iterations of an algorithm loop until convergence. Many existing criteria yield good quality partition (compared to a ground truth for example), but suffer from different drawbacks such as being subject to local extremum or resolution limit @cite_0 . This kind of method is also known to be time-consuming @cite_18 .