text: Network representations can help reveal the behavior of complex systems. Useful information can be derived from the network properties and invariants, such as components, clusters or cliques, as well as from their changes over time. The evolution of clusters of nodes (or communities) is one of the major focus of research. However, the time dimension increases complexity, introducing new constructs and requiring novel and enhanced algorithms. In spite of recent improvements, the relative scarcity of timestamped representations of empiric networks, with known ground truth, hinders algorithm validation. A few approaches have been proposed to generate synthetic temporal networks that conform to static topological specifications while in general adopting an ad-hoc approach to temporal evolution. We believe there is still a need for a principled synthetic network generator that conforms to problem domain topological specifications from a static as well as temporal perspective. Here we present such a system. The unique attributes of our system include accepting arbitrary node degree and cluster size distributions and temporal evolution under user control, while supporting tunable joint distribution and temporal correlation of node degrees. Theoretical contributions include the analysis of conditions for "graphability" of sequences of inter and intra cluster node degrees and cluster sizes and the development of a heuristic to search for the cluster membership of nodes that minimizes the shared information distance between clusterings. Our work shows that this system is capable of generating networks under user controlled topology with up to thousands of nodes and hundreds of clusters with strong topology adherence. Much larger networks are possible with relaxed requirements. The generated networks support algorithm validation as well as problem domain analysis.
  @cite_30: 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.
  @cite_28: Real-world social networks from a variety of domains can naturally be modelled as dynamic graphs. However, approaches to detecting communities have largely focused on identifying communities in static graphs. Recently, researchers have begun to consider the problem of tracking the evolution of groups of users in dynamic scenarios. Here we describe a model for tracking the progress of communities over time in a dynamic network, where each community is characterised by a series of significant evolutionary events. This model is used to motivate a community-matching strategy for efficiently identifying and tracking dynamic communities. Evaluations on synthetic graphs containing embedded events demonstrate that this strategy can successfully track communities over time in volatile networks. In addition, we describe experiments exploring the dynamic communities detected in a real mobile operator network containing millions of users.
  @cite_16: Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.
  @cite_26: 
summary: There have been some proposals to generate synthetic temporal networks. In @cite_30 the authors propose a generator for simple networks with a cyclic nature based on a variation of the stochastic block model. In @cite_28 the authors have adapted the LFR benchmark @cite_16 , while introducing over time ad-hoc modifications to the network. In @cite_26 the authors propose RDyn, a system to generate temporal networks respecting a power-law distribution of community sizes and node degrees with tunable clustering and injected lifecycle events that, while disrupting cluster quality, are subsequently re-balanced through re-wiring of node links.