Several research studies have shown that complex networks modeling real-world phenomena are characterized by striking properties: (i) they are organized according to community structure, and (ii) their structure evolves with time. Many researchers have worked on methods that can efficiently unveil substructures in complex networks, giving birth to the field of community discovery. A novel and fascinating problem started capturing researcher interest recently: the identification of evolving communities. Dynamic networks can be used to model the evolution of a system: nodes and edges are mutable, and their presence, or absence, deeply impacts the community structure that composes them. This survey aims to present the distinctive features and challenges of dynamic community discovery and propose a classification of published approaches. As a "user manual," this work organizes state-of-the-art methodologies into a taxonomy, based on their rationale, and their specific instantiation. Given a definition of network dynamics, desired community characteristics, and analytical needs, this survey will support researchers to identify the set of approaches that best fit their needs. The proposed classification could also help researchers choose in which direction to orient their future research. are a few examples of observable events that are often investigated using instruments borrowed from graph theory. One main issue to address while studying this type of real-world events lies in the identification of meaningful substructures hidden within the overall complex system. How to partition a complex network into communities is a widely studied problem (Fortunato 2010; Coscia et al. 2011) : several works, from a broad set of disciplines, proposed different community definitions and approaches able to retrieve such structures automatically. The magnitude of works that cover this fascinating topic highlights its ubiquity: communities can capture groups of strongly connected online documents, individuals sharing a social environment as well as products being frequently purchased together. Most of the scientific literature dedicated to the community discovery (CD) problem starts from a very stringent assumption: real-world phenomena can be modeled with static networks-that is, mathematical objects frozen in time. Unfortunately, such a simplified scenario seldom fits the evolving nature of the world we live in. Indeed, one of the key features that characterize interaction phenomena is that they naturally unfold through time: social interactions evolve, phone calls have a limited duration, and human mobility changes as time goes by. The temporal dimension conveys highly valuable information that the analyst needs to exploit to better understand the reality that he or she observes. The need to include such knowledge in the tools offered by graph theory has been one of the linchpins in an entirely new field of investigation that emerged in the past decade: dynamic network analysis. Within this new field, well-known problems defined in static settings were reformulated, and time-aware approaches able to solve them were proposed. Among them, dynamic community discovery (DCD) represents one of the most challenging problems. As time goes by, nodes and edges can join and leave a dynamic network, producing relevant perturbations on its topology: communities are the basic bricks of that complex structure and as such are profoundly affected by local changes. Whereas classical CD algorithms aim to identify hidden substructures, dynamic approaches are devoted to the tracking of such local topologies and of their mutations, a goal that can be fulfilled pursuing different strategies and modeling choices. In this survey, we have thus chosen to design a taxonomy of DCD algorithms not by considering the technical solution they use to find them but rather the strategy they use to identify time-aware meaningful network substructures. Our aim is to support researchers and analysts in choosing the approach, or at least the class of approaches, that better fits their needs and data. For each of the proposed classes of DCD algorithms, we discuss both advantages and drawbacks. Moreover, we provide a brief description of those methods that implement their rationale. To provide a comprehensive view of this field of research, we also discuss issues related to the evaluation of DCD algorithms, which requires modifications compared to the static case; moreover, we summarize other works on DCD, such as dynamic community visualization methods, and analytical applications to real-world problems. The survey is organized as follows. In Section 2, we discuss the general concepts behind dynamic network analysis and the mathematical models used to describe, in graph-theoretical terms, temporal evolving phenomena. In Section 3, we formalize the CD problem on dynamic networks and discuss community life cycle and instability. In Section 4, we introduce our DCD taxonomy describing the peculiarity, pros, and cons of each class of approaches. A detailed description of the methods is then made available in the appendix. In Section 5 we introduce and discuss two classes of techniques often used to compare and characterize communities identified by DCD algorithms, namely internal and external quality evaluation. In Section 6, we review some real-world scenarios that have been studied through the lenses of dynamic community mining and address the problem of visualizing analytical results. Section 7 concludes the survey, providing insights into DCD-related open issues. Fig. 1. Network representations. Moving from a static graph to interaction ones, the model complexity increases while the grain of the temporal information available decreases (Rossetti 2015). 2 DYNAMIC NETWORKS Since its beginning, complex network analysis has been approached by researchers through the definition of very specific mining problems. Among them, CD (Fortunato 2010; Coscia et al. 2011), link-based object ranking (Getoor and Diehl 2005; Duhan et al. 2009), and frequent pattern mining (Milo et al. 2002; Alon 2007) are examples of analytical tasks originally defined on networks frozen in time. The absence of the time dimension comes from historical reasons: the graph theory ancestry of the field and the scarcity of existing dynamic data at the time the field of complex networks emerged. With the explosion of human-generated data, often collected by sociotechnical platforms, more and more datasets having rich temporal information that can be studied as dynamic networks becomes available. Many works tried to transpose well-known graph mining problems from static networks to temporal networks: temporal motifs mining (Kovanen et al. 2011), diffusion (Lee et al. 2012), link prediction (Tabourier et al. 2016), and so forth. To better address the central topic of this survey, in Section 2.1 we introduce the most used formalisms to represent dynamic networks, and in Section 2.2 we discuss one of the leading issues arising when dealing with temporally annotated networks: network memory. Time plays a crucial role in shaping network topologies. One of the most important issue to address to reason on time-evolving networks is thus related to the mathematical formalism used to describe them. Figure 1 shows four different conceptual solutions that gradually introduce the temporal dimension in the network modeling process. In one respect, we find the complete atemporal scenario (i.e., a single network snapshot capturing a static glimpse of a dynamic phenomenon): network dynamics can be gradually introduced by adopting labels that weights nodes and edges, thus capturing an aggregate network. Following this approach, weights models the number of occurrence of a given node/edge in a predetermined observation window: with this little increment in the model complexity, several time-dependent analyses neglected before become possible (i.e., tie strength estimation). Aggregation strategies, however, suffer a severe limitation: they do not capture dynamics. For this reason, several works model dynamic phenomena with temporally ordered series of network snapshots. This simple modeling choice allows one to efficiently keep track of the perturbations occurring on the network topology. However, while the expressivity of the model is increased, the analytical complexity increases as well. When dealing with network snapshots to perform time-aware mining tasks, two issues need to be addressed: (i) how to keep track of multiple stages of the network life and (ii) how to harmonize the analytical results obtained in a snapshot with the outcome of subsequent ones. Dynamic network partition, as well as aggregation, suffers from a pressing issue: to be performed, a temporal granularity-a threshold to transform the original dynamic system-needs to be fixed. Since the identification of such a threshold is not trivial-it is, indeed, context dependent and often profoundly impacts analytical results-recent works propose modeling dynamic phenomena without any aggregation, keeping all temporal details. Such studies usually decompose a dynamic network in its elementary bricks: temporally ordered, timestamped, interactions or relations. We will describe in more details such an approach, namely temporal networks modeling, in the next section. Temporal networks, avoiding aggregation, allow for a complete and fine-grain description of network dynamics: as a drawback, this solution increases the complexity of the network model and requires the definition of novel analytical methodologies. Different problems, as well as available data, impose different modeling choices: static networks, as well as weighted ones, are often used to identify stable patterns and describe the actual status of a network, whereas snapshots and interactions are proxies for the study of increasingly dynamic scenarios. Obviously, starting from fine-grain temporal data, it is possible to generate all of the other models by subsequent aggregations. Since we are interested in community detection approaches that deal with temporally annotated graphs, in the following we will highlight the major strengths and drawbacks of the most used models in this context: temporal networks and network snapshots. In this survey, we will not discuss static and weighted networks, as by definition, they do not allow one to make direct use of temporal information, thus reducing dynamic problems to static ones: for an in-depth overview of CD approaches defined for such scenarios, refer to Fortunato (2010), Fortunato and Hric (2016), Xie et al. (2013b), and Coscia et al. (2011). 2.1.1 Temporal Networks. Several formalisms have been proposed to represent evolving networks without loss of information: temporal networks (Holme and Saramäki 2012), time-varying graphs (Casteigts et al. 2012), interaction networks (Rossetti et al. 2015) , and link streams and stream graphs (Viard et al. 2016; Latapy et al. 2017) , to name the most popular. Hereafter, we use the term temporal networks with a general definition that encompasses all of those formalisms. A temporal network models a dynamic structure in which both nodes and edges may appear and disappear as time goes by. More formally, we have the following definition. A temporal network is a graph G = (V , E,T ), where V is a set of triplets of the form (v, t s , t e ), with v a vertex of the graph and t s , t e ∈ T respectively being the birth and death timestamps of the corresponding vertex (with t s ≤ t e ); E is a set of quadruplets (u, v, t s , t e ), with u, v ∈ V being vertices of the graph, and t s , t e ∈ T respectively being the birth and death timestamps of the corresponding edge (with t s ≤ t e ).
A more thorough survey of dynamic community detection methods is presented in REF .
Community Discovery in Dynamic Networks: A Survey
CSUR
Computer Science Physics