Cazabet Rémy Homepage

Dynamic Community Discovery: a (Live) Survey

This page is a live version of the article: Community Discovery in Dynamic Networks: a Survey, written by Giulio Rossetti and myself. Please note that some of the contents of this page are not in the original survey, so, if you use it, please add a reference to this page.

About this page

The weakness of all survey article is that they are obsolete as soon as they are published, as new methods are proposed all the time. At first, we wanted to maintain actively a live survey, adding new methods as soon as they were published, but this task is actually too time consuming.
As an inbetween solution, we propose this page which contains references and description of all methods included in the published survey, and we offer the possibility to all researcher to include their own method, if it was not already present.

This first attempt is managed manually: you need to send us an email with all useful information (summary of your method in a few lines, reference to the article, reference to an implementation if available, etc.)

The mechanism could be upgraded to a wiki-like behaviour. If you want to propose an improved version of it, feel free to contact us, we are very open to a take over by someone else with motivation/time/fresh ideas.

Methods

This table lists all methods included in the original survey, plus methods contributed by authors, marked with the symbol .
If you want to add your own method, complete something or spot a mistake, feel free to tell us.

Article	Date	Category	Community Definition	Dynamicity	Code	Summary

A1 - Iterative Similarity-based approaches

In similarity-based approaches, a quality function is used to quantify the similarity between communities in different snapshots (e.g., Jaccard among node sets).
Communities in adjacent time-steps having the highest similarity are considered part of the same dynamic community. Particular cases can be handled, such as a lower threshold of similarity, or the handling of $1$ to $n$ or $n$ to $n$ matchings, thus defining complex operations such as split and merge.

A2 - Iterative Core-nodes based approaches

Methods in this subcategory identify one or several special node(s) for each community -- for instance those with the highest value of a centrality measure -- called core-nodes. Two communities in adjacent time-steps containing the same core-node can subsequently be identified as part of the same dynamic community. It is thus possible to identify splits or merge operations by using several core-nodes for a single community.

A3 - Multi-step matching

Methods in this subcategory do not match communities only between adjacent time-steps. Conversely, they try to match them even in snapshots potentially far apart in the network evolution. The matching itself can be done, as in other sub-categories, using a similarity measure or core-nodes. The removal of the adjacency constraint allows to identify resurgence operations, i.e. a community existing at $t$ and $t+n$ but not between $t+1$ and $t+(n-1)$. It can, however, increase the complexity of the matching algorithm, and on-the-fly detection becomes inconsistent, as past affiliations can change.

These methods allows a smoothing of the communities of labels

B1 - Update by Global Optimization

A popular method for static CD is to optimize a Global Quality Function, such as Modularity or Conductance.

This process is typically done using a heuristic (gradient descent, simulated annealing, etc) that iteratively merges and/or splits communities, and/or moves nodes from a community to another until a local or global maximum is reached.

Methods in this subcategory use the partition existing at $t$ as a seed to initialize a Global optimization process at $t+1$. The heuristic used can be the same as in the static case or a different one. A typical example of a method in this category Aynaud-2010 consists in using the Louvain algorithm: in its original definition, at initialization, each node is in its community.
The partition update version of it consists in initializing Louvain with communities found in the previous step.

B2 - Update by Set of Rules

Methods in this subcategory consider the list of network changes (edge/node apparitions, vanishing) that occurred between the previous step and the current one, and define a list of rules that determine how networks changes lead to communities update.
Methods that follow such rationale can vary significantly from one to the other.

B3 - Informed CD by Multi-objective optimization

When addressing community detection on Snapshot Graphs, two different aspects need to be evaluated for each snapshot: partition quality and temporal partition coherence.
The multi-objective optimization subclass groups together algorithms that try to balance both of them at the same time so that a partition identified at time $t$ represents the natural evolution of the one identified at time $t-1$.
This approach optimizes a quality function of the form: \[ c = \alpha CS + (1-\alpha) CT \] with $CS$ the cost associated with current snapshot (i.e. how well the community structure fits the graph at time $t$, and $CT$ the smoothness w.r.t. the past history (i.e., how different is the actual community structure w.r.t. the one at time $t-1$ and $\alpha \in [0,1]$ is a correction factor.

An instantiation of such optimization schema could be defined using modularity as $CS$ and Normalized Mutual Information as $CT$ as done in Folino-2010.

B4 - Informed CD by network smoothing

Methods in this subcategory search for communities at $t$ by running a CD algorithm, not on the graph as it is at $t$, but on a version of it that is smoothed according to the past evolution of the network, for instance by adding weights to keep track of edges' age. In a later step, communities are usually matched between snapshots, as in typical Two-Stage approaches.
Contrary to previous subcategories, it is not the previous communities that are used to take the past into account, but the previous state of the network.

C1 - Fixed Memberships, fixed properties

Methods in this subcategory do not allow nodes to switch communities, nor communities to appear or disappear. They also assume that communities stay the same throughout the studied period.
As a consequence, they search for the best partition, on average, over a time period.
In most cases, they improve the solution by slicing the evolution in several time periods, each of them considered homogeneous, and separated by dramatic changes in the structure of the network, a problem related to change point detection.

C2 - Fixed memberships, evolving properties

Methods in this subcategory are aware that communities are not homogeneous along time.
For instance, nodes in a community can interact more actively during some recurrent time-periods (hours, days, weeks, etc.), or their activity might increase or decrease along time.
To each community -- whose membership cannot change -- they assign a temporal profile corresponding to the evolution of its activity.

C3 - Evolving memberships, fixed properties

Methods in this subcategory allow node memberships to change along time, i.e., nodes can switch between communities.
However, because they use Stochastic Block Models approaches, for which the co-evolution of memberships and properties of communities is not possible (see Matias-2015), the number of communities and their density is fixed for the whole period of analysis.

C4 - Evolving memberships, evolving properties

Methods in this category do not impose constraints on how dynamic communities can evolve: nodes can switch between them, communities can appear or disappear, and their density can change.
Two main approaches are currently present in this category:

Edges are added between nodes in different snapshots. Static community detection algorithms are consequently run on this trans-temporal network
Searching for persistent cliques of a minimal size in link streams.

Column Dynamicity

Dynamic networks can be represented by several means:

Snapshots: The network evolution is represented by an ordered series of static graphs
TN-Interval Graph: The network is a temporal network (no snapshots), edges exist during intervals. It is assumed that the network is relatively stable, i.e communities found by dynamic algorithms at $t$ should be close to what a static algorithm would find on the static network defined by existing edges at that time
TN-Instantaneous: The network is a temporal network (no snapshots), edges are transient, they have no duration, therefore the network is never fully defined at a given time $t$

Community Definition

There is no universally accepted definition of what are good communities, or good graph clusters. This column states for each method the definition it adopts.

It can be one of commonly used definitions (Stochastic Block Model, Modularity, etc.) or one of the following ones:

Independent (PP): The method is not dependent on a particular definition, because it is a Post Process (PP), i.e any static method can be used in the first place to find non-dynamic communities, and the method "makes the link" between them.
Ad hoc: This method does not rely on a well-known definition of communities, but define an Ad hoc process, usely ensuring that communities are dense and well separated from the rest of the network.
Ad hoc static: the method uses as a first step a particular static community detection algorithm that cannot be obviously related to a well known community definition.

Dynamic Community Discovery: a (Live) Survey

Categories

(A) Instant Optimal

(B) Temporal Trade-Off

(C) Cross-Time

Methods

Dynamic Community Discovery: a (Live) Survey Readme: Purpose of this page

Categories

(A) Instant Optimal

(B) Temporal Trade-Off

(C) Cross-Time

Methods

Dynamic Community Discovery: a (Live) Survey