PaperlayerView exact revision on arXiv

Source-linked AI summary

Community Discovery in Dynamic Networks: a Survey

Giulio Rossetti, Rémy Cazabet

arXiv:1707.03186v3cs.SIphysics.soc-ph

TL;DR

Dynamic Community Discovery asks how to identify and track communities as networks evolve, while community persistence and stability remain difficult to determine. This survey develops a taxonomy based on methodological rationale and instantiation, and discusses evaluation, visualization, and applications. Its supported conclusion is that no approach is universally superior; suitability depends on the use case, data, and problem formulation.

  • Problem

    Dynamic Community Discovery must identify evolving communities whose persistence and stability are difficult to determine as network nodes, edges, and local topologies change over time.

  • Method

    The survey organizes DCD approaches into a two-layer taxonomy based on their strategy and rationale, while reviewing methods, trade-offs, evaluation, visualization, and applications.

  • Results

    No DCD approach is superior in all cases; each class has advantages and drawbacks and is more suitable for particular use cases.

  • Takeaways & Limitations

    The taxonomy guides method selection according to problem formulation, data characteristics, and analytical needs, and helps organize comparative analyses within method families.

Abstract

from arXiv · show

Networks built to model real world phenomena are characeterised by some properties that have attracted the attention of the scientific community: (i) they are organised 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 challenging problem started capturing researcher interest recently: the identification of evolving communities. To model the evolution of a system, dynamic networks can be used: nodes and edges are mutable and their presence, or absence, deeply impacts the community structure that composes them. The aim of this survey is 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 art methodologies into a taxonomy, based on their rationale, and their specific instanciation. Given a desired definition of network dynamics, 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 to choose in which direction should future research be oriented.

I. INTRODUCTION

Community discovery seeks meaningful substructures in complex networks, but static-network assumptions poorly fit phenomena that evolve over time. This survey addresses Dynamic Community Discovery by organizing methods, models, evaluation issues, and applications around time-aware community analysis.

  • Community discovery partitions complex networks into meaningful substructures, such as socially connected individuals, related documents, or frequently co-purchased products.
  • Static-network assumptions often fail to represent evolving interactions, whose temporal dimension contains valuable information.
  • Dynamic Community Discovery tracks local network topologies and their mutations as nodes and edges join or leave over time.
  • The survey classifies DCD algorithms by their strategy for identifying time-aware network substructures rather than by technical solution.
  • It discusses advantages, drawbacks, evaluation modifications, visualization methods, and real-world analytical applications of DCD approaches.
  • Dynamic-network modeling ranges from aggregated representations to temporal interactions, with finer temporal detail increasing model complexity and aggregation requiring context-dependent granularity choices.

2. Network Snapshots

Snapshot networks represent evolving systems as ordered graph states or time-bounded aggregations, enabling static tools while introducing reconciliation and window-selection trade-offs. Their usefulness and computational behavior depend on temporal granularity, network semantics, and assumptions about entity persistence.

  • Snapshot representation: Snapshot networks partition network history into ordered graphs, each defined by its node and edge sets.They may represent a relation network’s state at time t or interactions aggregated over a period.
  • Snapshot representation: Snapshots provide a balance between model complexity and expressivity by allowing static algorithms and measures to operate independently on temporal partitions.This avoids requiring analytical tools that explicitly manage temporal information.
  • Trade-offs: Snapshot analysis requires reconciling independently computed results, and the chosen window size can substantially affect downstream analytical outcomes.The two-step mining-and-reconciliation process may degrade result quality.
  • Trade-offs: The choice between temporal and snapshot networks affects storage, processing, and algorithm design, because methods are usually tailored to one representation.Snapshot processing cost typically depends on aggregation and snapshot size, whereas temporal-network processes mainly depend on network changes.
  • Network memory: Temporal-network construction may transform interactions into relations by assigning edge durations through a Time To Live or other decay strategy.Strategies include fixed static or sliding windows, dynamic windows, and global or local decay functions.
  • Network memory: Persistence assumptions, including whether entities accumulate permanently or can vanish, play a crucial role in time-aware mining results.Perfect-memory networks retain old nodes and edges, whereas limited-memory networks allow them to disappear.

1. Community Life-Cycle

Dynamic communities are tracked through a vocabulary of structural events that describes their changes and life-cycles. Their persistence and stability remain difficult to determine because community identity and algorithmic solutions can both vary over time.

  • Community life-cycle: Persistence is inherently ambiguous because deciding whether progressively changing communities remain the same across time cannot be answered unambiguously.The survey illustrates this identity problem through the ship-of-Theseus paradox.
  • Community events: Dynamic community tracking characterizes how node and edge appearances or disappearances perturb community topology.These atomic network operations motivate explicit descriptions of the transformations communities undergo.
  • Community events: The event vocabulary comprises Birth, Death, Growth, Contraction, Merge, Split, Continue, and Resurgence.The first six were introduced in earlier work, Continue was later added, and Resurgence was subsequently proposed.
  • Community events: Merge can be implemented through absorption, where one community disappears and the other persists, or replacement, where affected communities vanish and a new one forms.Replacement can disrupt continuity, while absorption requires a policy for selecting which community ceases to exist.
  • Community life-cycle: A community life-cycle is a directed acyclic graph whose roots are Birth events, leaves are Death events, and central nodes are other community actions.The graph represents a community’s complete evolutive history, including predecessor and successor communities involved in merges or splits.
  • Instability and smoothing: Dynamic community detection faces instability because differences between consecutive partitions may reflect either genuine evolution or algorithmic variation.Slight network changes can produce substantially different partitions with comparable modularity scores.
  • Instability and smoothing: Proposed smoothing strategies include bootstrap, explicit, implicit, and global smoothing to reduce instability across community evolution.Explicit smoothing balances current-step optimality against similarity to the previous partition through a parameter α ∈[0, 1].

IV. CLASSIFICATION

The survey proposes a two-level taxonomy for Dynamic Community Discovery (DCD), separating three definitions of dynamic communities from the techniques used to identify them.

  • Relation to prior classifications: The taxonomy also relates DCD approaches to existing categories such as Two-Stage, Evolutionary Clustering, and Coupling Graph methods.These classifications can overlap; for example, Evolutionary Clustering encompasses Temporal Smoothness and Dynamic Update methods.
  • Scope: Some surveyed methods do not fit one category or can be associated with several categories.The authors retain a two-level classification built from concepts shared by existing classifications.
  • Taxonomy structure: The classification contains three high-level DCD classes based on different definitions of dynamic communities.Each class is refined into subcategories representing different techniques for solving the corresponding problem.
  • High-level classes: Instant-optimal communities depend only on the network state at time t and are therefore nontemporally smoothed.Communities at each step are considered optimal for that step's topology.
  • High-level classes: Temporal Trade-off communities use current topology together with past network states or partitions, balancing the current solution against historical information.They do not depend on future modifications, supporting on-the-fly community discovery.
  • High-level classes: Cross-Time methods use the complete network history to derive one partition across all time steps, incorporating both past and future evolution.These methods produce completely temporally smoothed communities.

A. Instant-optimal Communities Discovery

Instant-optimal discovery detects an optimal partition independently at each network step and then defines dynamic communities by matching partitions across time.

  • Overview: Instant-optimal discovery identifies an optimal partition independently for each network state before connecting communities across time.The approach applies static community detection separately at each evolution step.
  • Two-Stage process: A typical Two-Stage approach first detects static communities at every step and then matches communities between successive steps.This process is explicitly divided into Identify and Match stages.
  • Scope and limitations: Two-Stage approaches and Instant-optimal communities are overlapping but non-equivalent concepts.Two-Stage methods may smooth communities using prior communities, while Instant-optimal methods may match all partitions simultaneously.
  • Scope and limitations: Instant-optimal methods inherit instability from community detection, making structural change difficult to distinguish from algorithmic variation.They also require processing the whole network from scratch at every evolution step and cannot directly use Temporal Networks.
  • Subcategories: Similarity-based methods match communities in adjacent snapshots using a quality function such as Jaccard similarity.Thresholds and 1-to-n or n-to-n matching can represent split and merge operations.
  • Subcategories: Core-node methods link communities across adjacent time steps when they share one or more designated core nodes.Using several core nodes permits identification of split or merge operations.
  • Subcategories: Multi-step matching removes the adjacency constraint, allowing communities to be matched across distant snapshots and enabling resurgence detection.This broader matching can increase computational complexity.

1. Update by Global Optimization

Update by Global Optimization initializes each new community-detection step with the previous partition, using global quality optimization while incorporating temporal continuity.

  • Method: Static community detection commonly optimizes a global quality function such as Modularity or Conductance.Heuristics may merge, split, or move nodes until reaching a local or global maximum.
  • Method: Global optimization methods seed the process at t + 1 with the partition found at t.The subsequent heuristic may be the same as, or different from, the static-case optimizer.
  • Taxonomy: Temporal Trade-off methods include global optimization, rule-based updates, multi-objective optimization, and network smoothing subcategories.These subcategories differ in whether they update partitions, balance objectives, or smooth network history.
  • Multi-objective optimization: Multi-objective optimization balances current-snapshot quality against temporal partition coherence.Its objective combines current cost CS and temporal smoothness cost CT using correction factor α.
  • Multi-objective optimization: An example combines Modularity as CS with Normalized Mutual Information as CT.This instantiates the quality function with separate current-structure and temporal-coherence criteria.

C. Cross-Time Communities Discovery

Cross-Time discovery analyzes the complete temporally annotated network in one process, producing communities whose memberships and properties may be constrained or allowed to evolve.

  • Overview: Cross-Time methods process all network states simultaneously rather than analyzing each evolution step independently.The resulting communities are derived from the complete network history.
  • Advantages and drawbacks: Cross-Time methods avoid instability and community drift and may capture local anomalies or slow multi-step evolution.Their trade-offs include structural constraints in many methods and inability to perform on-the-fly detection when complete history is required.
  • Taxonomy: Cross-Time approaches divide into four categories based on whether memberships and community properties are fixed or evolving.The four combinations are fixed/fixed, fixed/evolving, evolving/fixed, and evolving/evolving.
  • Cross-Time categories: Fixed-membership, fixed-property methods prohibit membership changes and community appearance or disappearance, seeking an average partition over time.Some divide the evolution into periods considered homogeneous.
  • Cross-Time categories: Fixed-membership, evolving-property methods preserve membership while assigning each community a temporal activity profile.The profile captures changes or recurring patterns in interaction activity.
  • Cross-Time categories: Evolving-membership, fixed-property methods allow nodes to switch communities while fixing the number of communities and their density.This constraint follows from the Stochastic Block Models used by these approaches.
  • Cross-Time categories: Evolving-membership, evolving-property methods impose no such constraints: memberships, community existence, and density can all change.Examples include trans-temporal graphs, persistent cliques in link streams, and dynamic stochastic block models.

D. Discussion

The survey’s taxonomy guides dynamic community discovery choices by matching approach classes to analytical goals, while its evaluation review highlights the need for temporal benchmarks. It also surveys synthetic generators that support controlled and ground-truth testing.

  • Discussion: No taxonomy class is universally superior; each has advantages, drawbacks, and more suitable use cases.For fine temporal granularity, the survey advises avoiding first-class methods because they handle only snapshots.
  • Taxonomy: The first taxonomy layer recommends approach classes according to the problem formulation and analytical goal.Its second layer groups methods by shared rationale to support literature framing and less biased comparisons.
  • Taxonomy: Instant Optimal, Cross-Time, and Temporal Trade-off approaches prioritize per-step quality, long-term temporal coherence, and operational compromise, respectively.Temporal Trade-off methods are presented as suitable for continuous monitoring, rapidly evolving data, and some limited-memory settings.
  • Evaluation: Network generators enable controlled testing by tuning characteristics such as size and density, assessing stability, scalability, and ground-truth recovery.Synthetic graphs can provide repeated comparable instances, support increasing network sizes, and sometimes supply planted partitions.
  • Evaluation: Dynamic benchmarks extend static generators or introduce evolving topologies and memberships, but only a few approaches address time-aware ground truths.Examples include node migrations, stochastic-block-model evolution, multilayer or temporal generation, and RDyn2, which produces evolving topologies and communities.

B. Methodologies

The survey reviews external and internal strategies for evaluating community partitions, including ground-truth comparisons, quality functions, and performance measurements. It emphasizes that dynamic community evaluation must account for temporal structure and methodological differences.

  • Evaluation strategies: External evaluation compares detected communities with ground truth or optimizes a partition-quality score, whereas internal evaluation examines topology, complexity, scalability, or runtime.Internal evaluation does not require a direct ranking across partitions because algorithms may use different community definitions.
  • External evaluation: NMI measures similarity between detected and ground-truth partitions on [0,1], reaching its maximum for identical communities, but requires O(z^2) comparisons for approximate community-set size z.This complexity can make NMI unsuitable for evaluating large-scale network partitions.
  • External evaluation: Ground-truth evaluation commonly labels nodes, matches each detected community to the ground-truth label shared by most of its nodes, and computes precision, recall, and F1-community.F1-community averages the harmonic mean of precision and recall across matched communities.
  • External evaluation: O(z) computation is required by the described F1-community approach when the graph is already labeled, and its results can be visualized with density scatter plots.The normalized NF1 version is proposed to address community overlap and redundancy.
  • Dynamic evaluation: Static GN and LFR benchmarks are widely reused for DCD testing, but they evaluate only a particular time instant and omit temporal dynamics.The survey identifies coherent evolving snapshots and time-aware ground-truth partitions as open evaluation issues, with RDyn among the few responses.
  • Quality functions: Quality functions such as modularity, conductance, expansion, density, cut measures, ODF, volume, and edge cut assess different topological properties.Optimizing a golden quality function can favor methods designed to maximize that same measure, limiting fair comparison across methods.

VI. APPLICATIONS

The survey discusses real-world dynamic network sources, visualization methods, and applications for analyzing evolving communities. It distinguishes data types by temporal resolution and visualization strategies by how they represent change over time.

  • Real-world dynamic networks: Dynamic network data come from online services and human activity, including collaborations, social relations, communications, mobility, trade, and web traffic.Dynamic datasets remain relatively small, poorly organized, and rare compared with static network datasets.
  • Real-world dynamic networks: Collaboration, social, communication, and technological networks are major source categories for testing dynamic algorithms.Communication data often include precise timestamps, enabling snapshot graphs, temporal interaction networks, or relations defined with a chosen TTL.
  • Visualization: Dynamic community visualization is challenging because it combines the difficulties of representing evolving networks and evolving community structures.The survey divides methods into dynamic visualizations, such as videos, and static drawings that summarize the full evolution.
  • Visualization: Contour-map visualizations overlay community shapes on laid-out nodes, while time-oriented views can assign the horizontal axis to time and color nodes by community.These approaches provide alternative visual encodings for community membership and temporal change.
  • Visualization: Animation-based methods adapt static layouts by stabilizing node positions despite connectivity changes, while other methods encode communities with shapes, colors, matrices, or aggregated nodes.These representations support different emphases, including structural overview, community size, hierarchy, and positional stability.
  • Visualization: Alluvial and related flow representations show community evolution through node lines, community strips, affiliation changes, and reduced crossings.Some variants facilitate tracking community life cycles or combine structural and alluvial views.

C. DCD as a tool

Dynamic Community Discovery (DCD) applies evolving-community analysis to real-world networks whose nodes, edges, and community structures change over time. The survey reviews applications, unresolved challenges, evaluation gaps, and guidance for selecting methods.

  • C. DCD as a tool: DCD has been applied to online-event detection, social-media group evolution, telecommunications, scientific collaboration, cognition, music preferences, and political affiliation.Examples include keyword communities for popular events, worm containment, evolving scientific fields, brain-network reconfiguration, and senator voting patterns.
  • C. DCD as a tool: DCD tracks changing network topologies and community mutations rather than treating each time point as an unrelated static network.Nodes and edges may join or leave, perturbing communities; dynamic discovery cannot be reduced to repeatedly running a static algorithm.
  • C. DCD as a tool: Common ground has begun to emerge around definitions of community events or operations, despite varied definitions of dynamic communities and approaches to maintaining temporal coherence.Methods seek partitions that are meaningful at individual time points while remaining coherent over longer periods.
  • C. DCD as a tool: DCD evaluation lacks a universally recognized dynamic benchmark and systematic method comparison equivalent to static community detection benchmarks.Comparisons must address differing data models, community operations, formal definitions, and realistic but incompletely known community evolution.
  • C. DCD as a tool: For data with fewer than 10 evolution steps, snapshot-based approaches are prioritized, whereas temporal-network methods are more suitable for 1000s or more steps.Method choice also depends on whether instantaneous community quality or long-term continuity is more important.
  • C. DCD as a tool: The field has few concrete applications beyond those developed by method authors, and its visibility and accessibility remain limited.The survey identifies greater cohesion and easier access for newcomers as future needs.

A. Iterative similarity-based approaches

Iterative similarity-based approaches detect communities independently across network snapshots and then connect them using similarity measures or event rules. These methods track community life cycles, structural changes, and temporal relationships across successive observations.

  • A. Iterative similarity-based approaches: Snapshot-based methods first detect communities separately and then match similar communities across successive snapshots.Matching may use overlap, intersection, custom similarity, or Jaccard-based thresholds.
  • A. Iterative similarity-based approaches: Other approaches detect structural changes by comparing adjacent snapshot clusterings, separating high-activity periods from stable consensus communities and deriving an influence hierarchy.The hierarchy is identified with a Minimum Spanning Tree.
  • A. Iterative similarity-based approaches: Community evolution is represented through events such as continuation, birth, death, split, merge, growth, shrinkage, and dissolution.Some approaches add meta-events to describe combinations or more complex transformations.
  • A. Iterative similarity-based approaches: Some methods identify stable snapshot communities through bootstrap resampling and significance clustering before mapping their changes over time.One procedure generates 1000 Poisson-resampled network variations per snapshot using original edge weights as distribution means.
  • A. Iterative similarity-based approaches: Several approaches construct longer-term structures by linking communities across multiple snapshots, including survival graphs, evolutive chains, and extended life cycles.Community detection can then be applied to the survival graph, or chains can be ranked by the strength of their weakest link.

B. Iterative core-nodes based approaches

Iterative core-nodes-based and temporal-trade-off approaches propagate community information across time while balancing present partition quality against temporal continuity. They include core tracking, temporal regularization, incremental modularity optimization, and specialized models for network types.

  • B. Iterative core-nodes based approaches: Core-node approaches track selected persistent or representative nodes to establish relationships between communities across time.Representative-based methods reduce redundant maximal-clique searches and use predecessor/successor relationships to determine dynamics.
  • B. Iterative core-nodes based approaches: A three-step survival-graph approach detects communities in each snapshot, links them by overlap, and clusters the resulting cross-time graph.The overlap measure is based on shared nodes divided by the smaller community size.
  • B. Iterative core-nodes based approaches: Temporal-trade-off methods initialize or constrain the current partition using previous communities to limit instability and preserve temporal continuity.Examples include temporal topic modeling, prior-partition initialization in Louvain, backtracking in modularity optimization, and penalties on membership changes.
  • B. Iterative core-nodes based approaches: Several methods update communities incrementally after network changes, including hierarchical modularity clustering and rule-based updates for evolving modularity.One method assumes small changes in network size and density do not dramatically affect modularity for non-impacted nodes.
  • B. Iterative core-nodes based approaches: The methods address varied network settings, including bipartite, multi-mode, and density-based graph communities.Their objectives include normalized cut, reconstruction plus temporal regularization, or proximity and density reachability.

C. Partition update by set of rules

Rule-based partition-update approaches respond locally to node and edge changes instead of recomputing all communities from scratch. The surveyed methods use local structures, seeds, labels, cohesion measures, or graph summaries to update communities and detect events.

  • C. Partition update by set of rules: Incremental methods update communities locally after node or edge changes while preserving properties defined by their underlying community model.Examples include adaptive FOCS, iLCD, QCA, local clique clustering, and minimum-cut-tree maintenance.
  • C. Partition update by set of rules: iLCD uses EMSN and EMRSN cohesion measures to decide node membership, while parameters k and t govern new-community formation and merges.New communities arise when an external clique of size k appears, and communities may merge when similarity exceeds threshold t.
  • C. Partition update by set of rules: Some rule-based methods model communities as agents or detect microblog events through locally maintained graph clusters.The approaches respectively apply community-agent decisions or update bi-connected clusters under node and edge additions or deletions.
  • C. Partition update by set of rules: Seed-based methods identify community seeds initially, track and update them under subsequent changes, then expand them into complete communities.CUT uses collections of 3-cliques and a Clique Adjacent Bipartite graph to support seed updates.
  • C. Partition update by set of rules: Online approaches can use prior partitions or skeletal graphs to maintain communities efficiently as streams evolve.LabelRankT uses prior-snapshot partitions, while another method summarizes the dynamic network with a fading-window skeletal graph.
  • C. Partition update by set of rules: TILES5 combines local topology perturbations and constrained label propagation, representing each community through a core and its one-hop periphery.It also detects Birth, Split, Merge, Death, Expansion, and Contraction at runtime.

D. Informed CD by network smoothing

The survey groups dynamic community-discovery methods by how they use temporal information, including neighborhood smoothing, snapshot segmentation, and cross-time aggregation. These approaches differ in how they update communities and whether they model or permit community operations.

  • Particle-and-density methods: Nano-communities model dynamic networks as particles whose evolving neighborhood information supports discovery of densely connected communities.The particle-and-density method can discover a variable number of communities.
  • Particle-and-density methods: Community cores are incrementally tracked across snapshots using historical contacts and useful links rather than all interactions.Nodes and connections may be added or removed at each snapshot.
  • Cross-time methods: GraphScope reorganizes incoming snapshots into segments under the Minimum Description Length principle, closing a segment when further combination lacks storage benefit.It targets dynamic bipartite graphs and combines snapshots only when doing so improves storage.
  • Snapshot segmentation: Stream-Group constructs compact communities, merges them by modularity increase, and uses partition similarity to detect change points.When a new time-slice arrives, its partition is compared with the previous graph segment before incremental updating.
  • Cross-time methods: Average modularity methods optimize a partition over a time window, while sliding windows segment network evolution into stable periods.The sum method builds a duration-weighted cumulative graph; the average method modifies Louvain to optimize average modularity across snapshots.

B. Fixed memberships, evolving properties

This section presents probabilistic and multislice approaches for dynamic communities, including models with fixed memberships and evolving interaction properties. Other approaches encode temporal links directly or identify time-resolved cohesive structures.

  • Fixed memberships, evolving properties: PPSBM keeps node affiliations fixed while modeling each pair of groups’ interaction intensity as a time-dependent Poisson-process function.An adapted EM algorithm estimates both group memberships and the time-varying intensity function.
  • Evolving memberships: Dynamic stochastic block models represent changing memberships through transition matrices, with EM, belief propagation, or spectral clustering used for parameter estimation.Some variants study detectability as a function of community strength and rate of change.
  • Multislice representations: Temporal-link approaches add identity or transversal edges between snapshots and apply static community detection to the resulting temporal network.Transversal links connect nodes across consecutive snapshots when they share a neighboring node across those snapshots.
  • Multislice representations: Multislice modularity links corresponding nodes across adjacent network slices before applying community detection to the resulting graph.The framework supports evolving and other multislice networks, with slice-specific modularity resolution possible.
  • Evolving properties and temporal cohesion: The dynamic-SBM formulation of Xu and Hero allows community properties and densities to evolve, but simultaneous evolution of memberships and properties can create identifiability problems.A separate link-stream approach defines and computes maximal Δ-cliques over time intervals.
Loading 1707.03186v3…