Skip to main content

Dynamic Community Detection

Description​

In addressing the hidden relations among the nodes in the graph, especially those not connected directly, community detection can be helpful. This familiar graph analytics task has been solved with various methods. However, demand for scale and speed has increased over the years and therefore led to the construction of dynamic community detection algorithms. Community detection lends itself well to dynamic operation for two reasons:

  • Locality: community changes tend to be local in scope after partial updates
  • Complexity: algorithms often have high time complexity that scales with the number of nodes in the network

Academic research of temporal graphs yielded LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation (Xie et al.).

drawing

Illustration of how a dynamic community detection algorithm adapts to local changes

Materials​

Implementation​

Dynamic Community Detection

Dynamic Community Detection

Dynamic Community Detection is implemented as part of the MAGE project. Be sure to check it out at the above link. ☝️

Blog posts​

Dynamic Community Detection

If you’re doing graph analytics, the chances are that you have run community detection on the dataset. Algorithms take more time to run on large graphs, and handling the volume of work that comes along with a large and frequently updated dataset is an engineering problem. It makes sense to wonder if it’s possible to leverage the small size of an average update to deliver a performance boost. We at Memgraph recognize your challenges. In this article, you will learn about the merits of online community detection methods and get acquainted with the LabelRankT algorithm by Xie et al., now available in MAGE 1.1.

Monitoring a Dynamic Contact Network with Online Community Detection

As MAGE wants to use his knowledge to help people, in this tutorial you will learn with him how to build a utility that monitors a dynamic contact network. The utility will a) use the detected communities to show rumor-spreading clusters and b) track the average cluster size.

Use cases​

Graphs that describe real-life networks often contain community structures. This insight applies to use cases such as customer segmentation, contact tracing, medical diagnostics, and quantification of environmental hazards in public health.

Medical

Tracking the evolution of communities across time provides a way to monitor entities such as viruses or rumors in real-time as they spread. With the COVID-19 pandemic being a top global concern, this problem is in search of a solution. One way to tackle it would be to pinpoint the main transmission focal points by using dynamic community detection.

Retail

With new items being sold every day, using dynamic community detection one can quickly follow the trends as they form and submit recommendations based on trends within a community. This approach enables the vendor to adapt more flexibly to unexpected events.