Streaming Community Detection — Updating Communities as Edges Arrive and Disappear

Introduction — Why "Streaming"?

The first article covered the fundamentals of community detection—Modularity, Louvain/Leiden, Infomap, SBM. The second article extended these ideas to higher-order structures, dynamic networks, and multiplex networks.

However, many "dynamic network" approaches in the second article still choose discrete snapshots and run community detection in batch mode on each one. For real-world large-scale networks such as Twitter/X follow graphs, financial transaction networks, and IoT sensor networks, this snapshot workflow breaks down in two ways:

1. Scale: On a graph with billions of nodes and tens of billions of edges, re-running Louvain from scratch every time a single edge changes costs far too much.
2. Real-time requirements: Use cases like fraud detection and trend prediction need to see changes in community structure right away and cannot wait for the next snapshot.

Streaming Community Detection (streaming CD) keeps the community structure up to date incrementally over an edge stream, where edges arrive (or are removed) one at a time. Most methods share one idea: update only the region around the changed edge and avoid recomputing the whole graph.

What This Article Covers

• A distinction by how much each update recomputes: batch recompute, incremental update, and true streaming
• Research history: from LPA and GraphScope, through iLCD, DiDiC, and LabelRankT, to methods that moved away from batch processing
• How representative algorithms work and what they cost: OSLOM, DEMON, DynaMo, TILES, delta-screening Louvain, ANGEL
• The design space: four dimensions—update strategy, temporal model, community properties, and quality criterion
• Comparing and evaluating the methods, and choosing an algorithm for a given situation
• Recent approaches based on GNNs and sketches, and open research questions

Part I: Foundations — From Batch to Streaming

Formal Definition of Edge Streams

In the streaming setting, the graph arrives as a sequence of events (an edge stream):

where:

• $e_i = (u_i, v_i)$: an edge (pair of nodes)
• $t_i$: timestamp ($t_i \leq t_{i+1}$)
• $\text{op}_i \in \{+, -\}$: operation (edge addition $+$ or deletion $-$)

At any time $t$, the graph $G_t = (V_t, E_t)$ is the cumulative result of all stream events up to that point:

The goal of streaming CD is to maintain a community partition $\mathcal{C}_t$ of $G_t$ at each time $t$. Ideally, the update cost per edge arrival is $O(1)$ or $O(\text{polylog}(n))$. A method that traverses the whole graph in $O(m + n)$ is too heavy to run on every arriving edge.

Three Processing Paradigms

Streaming CD methods fall into three groups according to how much they recompute on each update:

The community detection algorithm is rerun on the entire graph for every edge change. The result is accurate, but the cost is $O(m + n)$ or more, so each update takes seconds to minutes on a large graph. Re-running Louvain from scratch each time falls into this category.

Only the region affected by the change, such as the endpoints of the changed edge and their neighbors, is recomputed. The update cost drops to roughly $O(\Delta \cdot k)$ ($\Delta$ = number of changed edges, $k$ = average degree). Delta-screening Louvain is a representative example.

The algorithm updates its internal state in constant or logarithmic time per edge arrival. The method does not traverse the graph; it decides using only the arriving edge and its immediate neighbors. TILES belongs here in principle, although in practice finding triangles costs time proportional to the endpoints' degrees.

The Stability–Responsiveness Trade-off

Streaming CD has to balance stability against responsiveness, and the two pull in opposite directions:

• Stability: Community structure should not change because of noise, such as random edges appearing and disappearing. Assignments that flip back and forth with every small change are undesirable.
• Responsiveness: When the graph structure actually changes (a community splits, a new community emerges, and so on), the algorithm should reflect it quickly.

In the Evolutionary Clustering framework from the second article, the parameter $\alpha$ sets the weight between the two:

A larger $\alpha$ favors fit to the current graph; a smaller $\alpha$ favors similarity to the previous partition. In the streaming setting, the choice between the two has to be made for each edge: is the newly arrived edge a sign of real structural change, or just noise? The algorithm must tell the difference using only the information around that edge.

Part II: Research History — From Batch Processing to Incremental Updates

Prehistory: The Arrival of LPA (2007)

The Label Propagation Algorithm (LPA), proposed by Raghavan, Albert, and Kumara (2007), is simple enough that it extends easily to streaming settings. LabelRankT, DEMON, and ANGEL, covered later, all build on LPA's ideas.

Label Propagation Algorithm (LPA):
  1. Assign each node a unique label
  2. Repeat:
     For each node v:
       Assign v the most frequent label among its neighbors
       (break ties randomly)
  3. Stop when labels converge
  → Nodes with the same label form a community

LPA's complexity is $O(km)$ ($k$ = iterations until convergence, often small in experiments). Each node's update uses only its neighbors' labels, so when an edge is added, only the relevant nodes need updating. This locality is what makes LPA easy to extend to the streaming setting.

GraphScope (2007): Change-Point Detection in Graph Streams

Sun, Faloutsos, Papadimitriou, and Yu (KDD 2007) proposed GraphScope, an early method that analyzes streams of time-evolving graphs without parameter tuning. Using the Minimum Description Length principle (MDL), it automatically detects change points in an edge stream where the graph structure shifts. It is better described as MDL-based change-point detection combined with source/destination group modeling than as a general-purpose community detection algorithm, but it strongly influenced research on streaming graph clustering.

The procedure:

1. Segment the edge stream into intervals $[t_i, t_{i+1})$
2. Assume stable graph structure within each segment; estimate community structure
3. Determine segment boundaries automatically with MDL: compare the cost of introducing a new segment against the cost of encoding new data with the existing segment's model

• $L(\text{model})$: description length of the model (community structure)
• $L(\text{data} \mid \text{model})$: description length of data given the model

When the existing community structure can no longer describe new data efficiently, GraphScope marks a change point, starts a new segment, and updates the community structure.

iLCD (2010): Incremental Detection with Local Criteria

Cazabet, Amblard, and Hanachi (IEEE SocialCom 2010) proposed iLCD (intrinsic Longitudinal Community Detection), an early method designed specifically for detecting communities in dynamically growing networks.

Each time a new edge arrives, iLCD uses a local quality function to decide whether its endpoints join existing communities or form a new one. When edge $(u, v)$ arrives:

1. If neither $u$ nor $v$ belongs to any community, create a new community containing both
2. If one endpoint belongs to an existing community $C$, evaluate whether the other should join $C$ using local density criteria
3. If both belong to different communities, evaluate whether to merge them
4. Periodically check whether nodes at community borders should be reassigned

Because a node can meet the membership criteria of several communities at once, iLCD produces overlapping communities without extra machinery. It also examines only the neighborhood of the arriving edge, so it runs efficiently in a streaming setting.

iLCD showed that community detection can run truly online, processing each graph event as it occurs instead of waiting for snapshots. TILES, covered later, also processes each edge as it arrives.

DiDiC (2010): Distributed Diffusive Approach

Gehweiler and Meyerhenke (2010) introduced DiDiC (Distributed Diffusive Clustering), which forms clusters by diffusion rather than label propagation. Each node maintains a "diffusion vector" $\mathbf{d}_v \in \mathbb{R}^k$, and clusters form as nodes locally diffuse (average) this vector with their neighbors.

DiDiC:
  Each node v holds a k-dimensional diffusion/load vector d_v
  Initialization: seed or load vectors are assigned for the chosen number of clusters
  For each node v (asynchronously, locally):
    d_v ← (1-α) · d_v + α · (1/|N(v)|) Σ_{u ∈ N(v)} d_u
  Node v's community = argmax_i d_v[i]

The diffusion parameter $\alpha$ controls how much neighborhood information is absorbed at each step. Larger $\alpha$ means stronger neighbor influence and faster convergence, but reduced stability.

DiDiC has the following properties:

1. Fully local: Each node's update references only its neighbors' diffusion vectors.
2. Asynchronous: Nodes do not need to update at the same time. In a streaming setting, when edge $(u, v)$ arrives, only the diffusion vectors of $u$ and $v$ (and optionally their neighbors) need updating, with no full graph traversal.
3. Suited to distributed systems: Each node manages its own state independently, with no central coordination.

LabelRankT (2013): Incrementalizing Label Propagation

Xie, Chen, and Szymanski (2013) extended LabelRank for dynamic networks with LabelRankT. Unlike plain LPA, LabelRank-style methods propagate label distributions and use operators such as inflation, cutoff, and conditional updates. The dynamic version restricts the expensive propagation work to nodes affected by edge changes.

LabelRankT:
  Initialize communities with LabelRank label distributions
  For each edge (u, v, op) arriving from the stream:
    1. Build affected set Δ:
       Δ = {u, v} ∪ N(u) ∪ N(v)  (u, v and their neighbors)
    2. Run LabelRank-style propagation only within Δ:
       For each w ∈ Δ:
         update w's label distribution from neighbors
         apply inflation, cutoff, and conditional-update rules
    3. Iterate locally until Δ stabilizes or the update budget is reached
    4. Output the dominant label for each node

LabelRankT's per-edge work is limited to the affected set $\Delta$ and the edges incident to it, not the whole graph. The cost can be estimated as $O(k \cdot m_\Delta)$, where $m_\Delta$ is the number of edges touched inside and around $\Delta$ and $k$ is the number of local iterations; this does not depend on the total graph size $n, m$ when endpoint degrees stay bounded.

LabelRankT also has limitations:

• LabelRank updates label distributions deterministically, so there is no random tie-breaking as in LPA, but the resulting partition depends on the inflation, cutoff, and conditional-update thresholds.
• It outputs a single dominant label per node, so it cannot detect overlapping communities.
• It does not explicitly optimize Modularity or any other quality metric, so the quality of the partition is not guaranteed.

Part III: How the Representative Algorithms Work

OSLOM (2011): Statistically Significant Incremental Detection

Lancichinetti, Radicchi, Ramasco, and Fortunato (2011) developed OSLOM (Order Statistics Local Optimization Method), which tests the statistical significance of communities. The second article touched on it, so this section focuses on how it applies to streaming.

OSLOM decides whether a node set $S$ is a community with a null-hypothesis test based on order statistics, which is where the name comes from.

The procedure works as follows:

1. For each node $i$ neighboring community $S$, compute a score $r_i$: the probability that $i$ has at least $k_i^{\text{int}}$ connections to $S$ under the Configuration Model (null model)
2. Sort these scores in increasing order: $r_{(1)} \leq r_{(2)} \leq \cdots$
3. For the $k$-th smallest score, compute the order-statistic p-value: the probability that the $k$-th order statistic of $n$ uniform random variables is $\leq r_{(k)}$
4. The community's overall significance is determined by the rank $k$ that yields the smallest such p-value

If the resulting p-value is sufficiently small (e.g., $< 0.05$), $S$ is deemed a statistically significant community. Because OSLOM tests significance per node rather than on the community's total edge count, a few outlier nodes do not distort the decision much.

Used incrementally, OSLOM's local tests give a procedure like this:

OSLOM incremental update:
  When edge (u, v) is added:
    1. Identify communities C_u, C_v containing u, v
    2. Recompute p-value for C_u (and C_v):
       - Evaluate p-value if neighbors of u not in C_u are added
       - If p-value improves, add that node to C_u
    3. Also evaluate p-value if nodes are removed from C_u
    4. Consider merging C_u and C_v
  When edge (u, v) is deleted:
    1. Recompute p-value for C_u (if C_u = C_v)
    2. If p-value exceeds threshold, decompose C_u and re-test

Because OSLOM uses p-values, it can check against a null model whether a community could be explained as a chance grouping; Modularity has no such testing framework. The test is also not tied to Modularity's global resolution scale, so small communities are detected when they are statistically significant.

On the other hand, computing p-values is costly, and the original OSLOM is not a lightweight streaming method. Using its local tests incrementally on large streams takes careful engineering.

DEMON (2012): Democracy of Ego-Nets

Coscia, Rossetti, Giannotti, and Pedreschi (2012) proposed DEMON (Democratic Estimate of the Modular Organization of a Network), a "bottom-up" local community detection method that builds communities from each node's surroundings.

In DEMON, communities are decided by each node's vote. The procedure:

DEMON:
  For each node v:
    1. Extract ego-net ego(v)
       ego(v) = subgraph induced by v and all neighbors N(v)
    2. Remove node v from ego(v) (delete all edges to v)
    3. Apply LPA to the remaining graph to detect local communities
    4. Add v to each local community found
  Integrate all nodes' results:
    - Merge local communities with similarity above threshold
    - Merge criterion: Jaccard(C_i, C_j) > ε

Step 2 removes v because, by definition, v connects to every member of ego(v). If v stayed in, the whole ego-net would be detected as one community. Removing v exposes the natural groupings within v's neighborhood. For example, "v's college friends" and "v's coworkers" become separate groups once v is removed, but v's presence joins them into one.

In a streaming setting, only two things need to be re-run:

1. When edge $(u, v)$ arrives, rebuild only $u$'s and $v$'s ego-nets and re-run LPA on them
2. Re-evaluate merges only for the affected local communities

Local communities from different ego-nets can overlap, so in DEMON a node can belong to several communities, and overlapping communities need no extra machinery.

DynaMo (2019): Incremental Modularity Tracking

Zhuang, Chang, and Li (2019) proposed DynaMo, which incrementally updates Modularity $Q$ in response to edge additions and deletions.

When edge $(u, v)$ changes, the modularity gain of moving nodes between communities can be recomputed from local information alone. DynaMo relies on this, so it does not have to rerun Louvain from scratch.

Recall the Modularity definition:

When edge $(u, v)$ is added, $A_{uv}$ changes from 0 to 1, $k_u$ becomes $k_u + 1$, $k_v$ becomes $k_v + 1$, and $m$ becomes $m + 1$. These changes affect only $u$, $v$, and their communities' internal statistics ($\Sigma_{\text{in}}$, $\Sigma_{\text{tot}}$). DynaMo uses this locality and handles two cases:

• If $u$ and $v$ are in the same community: the community's internal edge count increases by 1 and its total degree by 2, so DynaMo updates the community's contribution to $Q$ in $O(1)$.
• If $u$ and $v$ are in different communities: DynaMo recomputes the modularity gain for moving $u$ to $v$'s community (and vice versa) and makes the move if the gain is positive.

DynaMo:
  For each edge (u, v, op) arrival:
    1. Update graph statistics (degrees, community Σ_in, Σ_tot)
    2. If op = + (addition):
       a. u, v in same community → internal edges increase, update Q
       b. u, v in different communities → compute move gain:
          gain(u → C_v) = (internal edge increase from u joining C_v)
                        - (internal edge loss from u leaving C_u)
          If gain > 0, move u to C_v
    3. If op = - (deletion):
       a. u, v in same community → internal edges decrease
       b. Check community connectivity. If disconnected, split
    4. Cascade: if u moves, compute move gains for u's neighbors (limited propagation)

With DynaMo, the widely used Modularity metric can be tracked on every edge update. Unlike batch Louvain, each update recomputes modularity gains from local community statistics only, so you can keep checking whether partition quality is slipping.

TILES (2017): Triangle-Based True Streaming

Rossetti, Pappalardo, Pedreschi, and Giannotti (2017) proposed TILES, one of the more influential methods for tracking communities online. TILES uses triangle formation as the basic unit of a community.

Triangles as the Unit of Community

TILES does not treat two connected people as a community; it holds that social cohesion appears only when they share a common friend. Formally, when edge $(u, v)$ arrives, TILES puts $u$, $v$, and $w$ in the same community only if $u$ and $v$ have a common neighbor $w$ (forming triangle $(u, v, w)$).

Algorithm

TILES Algorithm:
  Data structures:
    - Adjacency list adj[v]: each node's current neighbors
    - Community labels label[v]: each node's community set (overlapping allowed)
    - Edge timestamps ts[(u,v)]: last arrival time of each edge
    - TTL parameter τ: edge time-to-live
 
  For each arriving edge (u, v, t):
    1. ts[(u,v)] ← t    // Update timestamp
    2. adj[u] ← adj[u] ∪ {v}, adj[v] ← adj[v] ∪ {u}
    3. Common neighbors W ← adj[u] ∩ adj[v]
    4. for each w ∈ W:
         // Triangle (u, v, w) formed
         // Extend existing triangle-supported communities, or create a new one
         candidate ← (label[u] ∩ label[w]) ∪ (label[v] ∩ label[w]) ∪ (label[u] ∩ label[v])
         if candidate = ∅:
           candidate ← {new_label()}  // New community for this triangle
         for each ℓ ∈ candidate:
           label[u] ← label[u] ∪ {ℓ}
           label[v] ← label[v] ∪ {ℓ}
           label[w] ← label[w] ∪ {ℓ}
    5. TTL check:
       for each edge (a, b) where t - ts[(a,b)] > τ:
         adj[a] ← adj[a] \ {b}, adj[b] ← adj[b] \ {a}
         // Check if removal affects a, b's communities
         re_evaluate(a, b)

Complexity Analysis

TILES' per-edge complexity:

• Step 3 common neighbor computation: $O(\min(\deg(u), \deg(v)))$ (intersection of sorted lists)
• Step 4 label updates: $O(|W| \cdot |\text{labels}|)$

Ignoring TTL expiration scans, the update is $O(\min(\deg(u), \deg(v)) + |W| \cdot |\text{labels}|)$. The cost grows with the endpoints' degrees and the number of label updates. In real networks with power-law degree distributions, most nodes have small degree, so the average cost stays low.

TTL (Time-To-Live) Mechanism

A distinctive part of TILES is its TTL mechanism. Each edge carries a timestamp, and edges not seen again within a period $\tau$ are removed as "expired."

For example, if two people on a social network last interacted a year ago, the relationship can be treated as no longer active. TTL models how recent a relationship is and removes stale edges automatically.

TTL has three effects:

1. Memory management: Keeps the memory usage of an ever-growing graph within bounds.
2. Noise removal: Separates one-off chance contacts from ongoing relationships.
3. Community dissolution: A community whose edges have all expired disappears.

$\tau$ is chosen from domain knowledge. Plausible values include 30 days for social media messages, 5 years for academic co-authorship, and 1 hour for financial transactions.

The demo below shows communities forming as edges arrive in a stream, then persisting as bridge edges are added and removed:

Delta-Screening Louvain (2021): Scoping the Impact

Zarayeneh and Kalyanaraman (2021) proposed delta-screening, a general framework for incrementalizing Modularity-optimizing algorithms such as Louvain. It pre-screens the nodes whose Modularity gains could change because of an edge modification, then applies Louvain's local move phase only to those nodes.

Screening Principle

When edge $(u, v)$ is added, the Modularity gain of a move is most likely to change for:

1. $u$ and $v$ themselves
2. Nodes in $u$'s community whose gain from moving to $v$'s community may increase
3. Nodes in $v$'s community whose gain from moving to $u$'s community may increase

Formally, node $w$ is "affected" if:

where $\Sigma_{\text{in}}^{C'}$ is the sum of internal edge weights in community $C'$, $k_{w,\text{in}}^{C'}$ is the sum of edge weights from $w$ to community $C'$, and $\Sigma_{\text{tot}}^{C'}$ is the sum of degrees of all nodes in $C'$.

Adding edge $(u, v)$ changes only $k_u$, $k_v$, $m$, and the $\Sigma_{\text{in}}$ and $\Sigma_{\text{tot}}$ of $u$'s and $v$'s communities. Apart from $m$, which enters every node's gain, only nodes neighboring $u$'s or $v$'s community depend on these values, so only those nodes are screened.

delta-screening Louvain:
  Prerequisite: existing community assignment C
  When edge (u, v) changes:
    1. Screening:
       affected ← ∅
       for each node w in C_u ∪ C_v ∪ N(u) ∪ N(v):
         if ΔQ(w → best_community) differs before/after edge change:
           affected ← affected ∪ {w}
    2. Local Louvain:
       Run Louvain's local move phase only on affected nodes
    3. Aggregation:
       Aggregate only affected communities

Experimental Results

In Zarayeneh and Kalyanaraman's experiments on synthetic and real-world networks, edge changes were processed in batches, one per time step. They reported speedups of up to 38× over rerunning Louvain from scratch at each time step, with Modularity nearly unchanged. The speedups are possible because most edge additions and deletions have only a local effect: a single edge change rarely alters the community structure of the whole graph.

ANGEL (2020): Merge-Based Overlapping Communities

Rossetti (2020) proposed ANGEL, a node-centric method that builds on DEMON's ideas, together with ArchAngel, its extension to evolving networks.

Like DEMON, ANGEL starts from each node's ego network; it then folds the local communities into a global collection through merge operations:

ANGEL (one graph):
  For each node u:
    1. Build the ego-net of u, excluding u itself
    2. Run LPA within the ego-net → local communities L
    3. Find the global community G_i that overlaps L the most
    4. If the overlap exceeds the threshold θ: merge G_i ← G_i ∪ L
       Otherwise, add L as a new global community
 
ArchAngel (an evolving graph given as snapshots):
  For each snapshot t:
    1. Run ANGEL on snapshot t
    2. Match the communities of t with those of t−1 by overlap
       to trace how each community evolves

ANGEL works in two stages: it finds communities from a local perspective (ego-nets), then merges them into its global knowledge (the global community set). ArchAngel handles change snapshot by snapshot, not edge by edge, so unlike TILES it does not update communities as each edge arrives (ANGEL README).

Part IV: The Design Space of Streaming CD

The algorithms covered so far can be organized along four dimensions that can be chosen largely independently.

Dimension 1: Update Strategy

• Full recompute: Recompute everything per edge arrival. Highest quality, highest cost
• Local update: Recompute only the affected scope (OSLOM, delta-screening)
• Lazy update: Buffer changes and update in a batch once enough have accumulated (DynaMo batch variant)

Dimension 2: Temporal Model

• Snapshot: Discrete-time graphs (Multislice Modularity from the second article)
• Sliding window: Keep only the most recent $W$ seconds/edges. Discard older data
• Decay: Edge weights decrease exponentially over time: $w(e, t) = w_0 \cdot e^{-\lambda(t - t_e)}$. TILES' TTL is a discrete version

Dimension 3: Community Properties

• Disjoint: Each node belongs to at most one community (LabelRankT, Louvain)
• Overlapping: Nodes can belong to multiple communities (DEMON, TILES, ANGEL, OSLOM)
• Fuzzy: Membership degree is a continuous value in $[0, 1]$. DiDiC's diffusion vectors approximate this

Dimension 4: Quality Criterion

• Modularity: Comparison with Configuration Model (DynaMo, delta-screening)
• Statistical test: Significance-based (OSLOM)
• Triangle density: Triangle sharing defines communities (TILES)
• Information-theoretic: Dynamic or flow-based Map Equation variants

Multiplying the options in the four dimensions gives $3 \times 3 \times 3 \times 4 = 108$ combinations. Not every combination works equally well in practice, but existing algorithms occupy only part of this space, and many combinations have not been tried.

Part V: Comparing and Evaluating the Methods

Concrete Example: TILES vs. LabelRankT

Here, TILES and LabelRankT process the same edge stream on a small 5-node graph (A–E).

Edge stream: +(A,B), +(B,C), +(A,C), +(C,D), +(D,E), +(C,E)

TILES processing:

• +(A,B), +(B,C): No triangles → no communities formed
• +(A,C): Triangle ABC formed → Community 1 = {A, B, C}
• +(C,D), +(D,E): No triangles → D, E remain unassigned
• +(C,E): Triangle CDE formed → Community 2 = {C, D, E}. C now belongs to both (overlap)

Result: Two communities form, {A, B, C} and {C, D, E}, with C as an overlapping member. D and E belonged to no community until a triangle formed.

LabelRankT processing:

• First, initialize all connected nodes with LabelRank label distributions (e.g., A,B,C dominated by one label; D,E by another)
• Upon +(C,E) arrival: Δ = {C, E} ∪ N(C) ∪ N(E) = {A, B, C, D, E} (all nodes)
• Run local label-distribution propagation within Δ. Because C bridges both dense parts, propagation can make one label dominate the whole affected set

Result: If one label comes to dominate, all nodes {A, B, C, D, E} end up in a single community, with no overlap.

Difference: TILES waits for a triangle before forming a community, so it is cautious and produces overlapping communities directly. LabelRankT outputs one dominant label per node, so local propagation tends to merge densely connected regions into one large community.

Benchmarking and Evaluation Challenges

Evaluating streaming CD raises three issues that do not arise for static methods.

Static LFR benchmarks do not change over time, so they are not enough to evaluate streaming methods. Dynamic benchmarks include:

• Dynamic LFR (Greene, Doyle, & Cunningham, 2010): Extends LFR over time. At each timestep, nodes move between communities, and communities are born, die, split, and merge
• RDyn (Rossetti, 2017): A benchmark built for streaming settings. Edge additions and deletions are generated as events, and the ground-truth community structure can be followed over time

Besides standard NMI (Normalized Mutual Information), streaming CD is evaluated with:

• Per-update computation time: Response time per edge arrival
• NMI time series: How agreement with the ground truth changes as the stream progresses
• Community stability: How much community assignments fluctuate over time (lower is more stable)
• Lag: The delay between a real change in community structure and its appearance in the algorithm's output

Whether a streaming method is usable in practice depends largely on scalability. Evaluations measure:

• Throughput: Edges processed per second
• Memory usage: Memory consumption growth rate relative to graph size
• Latency: Delay from edge arrival to result update

Practical Selection Guide

Part VI: Recent Frontiers and Future Directions

GNN-Based Streaming CD

Since 2020, a growing body of research has applied Graph Neural Networks (GNNs) to streaming settings.

EvolveGCN (Pareja et al., 2020) updates the weight parameters of a graph convolutional network (GCN) over time with an RNN (LSTM/GRU):

where $W_t$ is the GCN weight at time $t$ and $H_t$ is the node representation matrix at time $t$ (EvolveGCN-H variant). A GCN is applied to each snapshot built from the edge stream, and the RNN moves the weights smoothly from one snapshot to the next.

ROLAND (You et al., 2022) applies temporal modeling to each GNN layer's output, continuously updating node representations.

GNN-based approaches to streaming CD share three characteristics:

1. Node features: They use attribute information attached to nodes (profiles, content, etc.), not only graph structure
2. Representation learning: They treat community detection as "node embeddings changing over time" and train with clustering-oriented loss functions
3. Inductive inference: They can estimate communities for new nodes right away using learned parameters

GNN-based methods still have open problems:

• Computational cost: GNN forward passes usually run on GPUs, and running one per edge is expensive
• Training data requirements: Sufficient data needed for supervised/self-supervised learning
• Interpretability: It is hard to tell why a particular partition was chosen

Approximation and Sketch-Based Approaches

Another direction for large-scale streams uses the theoretical framework of streaming algorithms:

MinHash / SimHash for node similarity approximation: Each node's neighbor set is summarized as a fixed-length hash sketch that can be updated in $O(1)$ per edge change. Jaccard similarity between nodes is approximated from these sketches, and high-similarity pairs are grouped into communities.

Count-Min Sketch for degree tracking: Node degrees in the edge stream are tracked with little memory and used to approximate Modularity.

These methods carry theoretical approximation guarantees (such as $\epsilon$-$\delta$ approximation), but few streaming algorithms of this kind have been built specifically for community detection so far.

Open Research Questions

Open problems include the following:

1. Theoretical detection limits: Streaming analogues of the Kesten-Stigum threshold for static SBM. How far can communities be detected when only one edge is visible at a time?
2. Edge order dependence: Quantifying how edge arrival order affects results. Does the same edge set yield different communities under different orderings?
3. Scalability barriers: Developing methods that can process billion-edge streams on a single machine
4. Privacy preservation: Running streaming CD with differential privacy guarantees so that nodes' community memberships do not leak
5. Multimodal streams: Handling node attribute changes and edge weight changes at the same time as edge additions and deletions

Conclusion — From Static to Streaming

The methods covered in this three-part series developed in this order: static (first article) → dynamic (second article) → streaming (this article).

Streaming CD is hard because it requires sequential decisions made with incomplete information. Batch processing sees the entire graph; streaming has to update community assignments from the edge that just arrived, without knowing which edge comes next.

Each method deals with this constraint in its own way, inferring global structure from local information. TILES forms a community only when a triangle appears, delta-screening narrows down the affected nodes in advance, and DEMON decides communities by voting within each ego-net.

References

• Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
• Sun, J., Faloutsos, C., Papadimitriou, S., & Yu, P. S. (2007). GraphScope: parameter-free mining of large time-evolving graphs. KDD 2007, 687–696.
• Gehweiler, J., & Meyerhenke, H. (2010). A distributed diffusive heuristic for clustering a virtual P2P supercomputer. IEEE International Parallel & Distributed Processing Symposium (IPDPS), 1–8.
• Xie, J., Chen, M., & Szymanski, B. K. (2013). LabelRankT: Incremental community detection in dynamic networks via label propagation. Workshop on Dynamic Networks Management and Mining (DyNetMM), 25–32.
• Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6(4), e18961.
• Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2012). DEMON: a local-first discovery method for overlapping communities. KDD 2012, 615–623.
• Zhuang, D., Chang, J. M., & Li, M. (2019). DynaMo: Dynamic community detection by incrementally maximizing modularity. IEEE Transactions on Knowledge and Data Engineering, 33(5), 1934–1945.
• Rossetti, G., Pappalardo, L., Pedreschi, D., & Giannotti, F. (2017). Tiles: an online algorithm for community discovery in dynamic social networks. Machine Learning, 106(8), 1213–1241.
• Rossetti, G. (2020). ANGEL: efficient, and effective, node-centric community discovery in static and dynamic networks. Applied Network Science, 5, 26.
• Zarayeneh, N., & Kalyanaraman, A. (2021). Delta-screening: A fast and efficient technique to update communities in dynamic graphs. IEEE Transactions on Network Science and Engineering, 8(2), 1614–1629.
• Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., Schardl, T., & Leiserson, C. (2020). EvolveGCN: Evolving graph convolutional networks for dynamic graphs. AAAI 2020, 5363–5370.
• You, J., Du, T., & Leskovec, J. (2022). ROLAND: graph learning framework for dynamic graphs. KDD 2022, 2358–2366.
• Greene, D., Doyle, D., & Cunningham, P. (2010). Tracking the evolution of communities in dynamic social networks. International Conference on Advances in Social Network Analysis and Mining (ASONAM), 176–183.
• Rossetti, G. (2017). RDyn: graph benchmark handling community dynamics. Journal of Complex Networks, 5(6), 893–912.
• Cazabet, R., Amblard, F., & Hanachi, C. (2010). Detection of overlapping communities in dynamical social networks. 2010 IEEE Second International Conference on Social Computing (SocialCom), 309–314.

Further Reading

• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1–44.
• Rossetti, G., & Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys, 51(2), 1–37.
• Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. KDD 2006, 554–560.