Information dynamics algorithm for detecting communities in networks

Emanuele Massaro, Andrea Guazzini, Franco Bagnoli, Pietro LiòarXiv 2011 · arXiv

Introduction

Community detection—identifying groups of nodes that are more densely connected to each other than to the rest of the network—is a cornerstone of network science. However, traditional algorithms often struggle with two realities: overlapping memberships and the need for a "God’s eye view" of the entire network. This paper introduces a community detection algorithm inspired by human psychology and ecological competition. By combining information diffusion with a "memory factor" (the oblivion effect) and a non-linear competition phase, the authors create a local algorithm capable of identifying overlapping communities and hierarchical structures from the perspective of individual nodes.

The Information Dynamics Model

The proposed "Information Dynamics Algorithm" is a modification of van Dongen’s Markov Cluster (MCL) algorithm. It operates through an iterative two-phase process:

  1. The Communication Phase (Diffusion with Memory): Information spreads through the network via a Markov matrix. Crucially, the authors introduce a memory parameter ($m$). This mimics the "oblivion effect"—the human tendency to prioritize recent information over old data. The state of a node is a weighted average of its previous state and the new information arriving from its neighbors.
  2. The Competition Phase (Non-linear Processing): Inspired by ecological models where species compete for resources, this phase uses a power parameter ($\alpha$) to enhance the "stronger" community signals and suppress the "weaker" ones. This prevents the information from simply washing out into a uniform blur across the network.

By alternating these phases, the network eventually reaches an asymptotic state where community structures become visible in the nodes' state vectors.

Experimental Validation

The authors validated their approach using several distinct network types, ranging from simple artificial graphs to real-world biological and social benchmarks. A primary test case is a 9-node artificial network designed to evaluate the detection of overlapping nodes and bridge structures.

Figure 2: A 9-node artificial network used to demonstrate the identification of bridge nodes (4 and 6) and overlapping community structures.

Other datasets included:

  • Zachary’s Karate Club: A classic social network benchmark (34 nodes) representing a real-world split in a university club.
  • Bottlenose Dolphin Network: A real-world biological social network (62 nodes) based on seven years of observations.
  • Hierarchical Artificial Network: A complex, multi-level generated network used to test the algorithm's ability to "scan" through different levels of granularity.

Key Insights and Results

Subjective Node Vision and Bridge Identification

Unlike global algorithms, this method allows us to see the network from the "point of view" of a specific node. A node’s state vector reveals not just which community it belongs to, but how strongly it feels connected to others. This naturally identifies overlapping nodes (like nodes 4 and 6 in the artificial test) by assigning them "middle" values in the state vector, indicating their role as communicators between distinct communities.

Figure 5: Analysis of the 9-node network. (a) Probability distributions across nodes. (b) State vector values showing the algorithm's ability to distinguish community membership and identify transition nodes.

Hierarchical Scanning

The authors use Shannon entropy to monitor the system's evolution, discovering that "plateaus" in the entropy curve correspond to different hierarchical levels of the network. By adjusting the parameters $m$ and $\alpha$, the algorithm can effectively "zoom in" or "zoom out" on the network structure. On the complex artificial network, the algorithm demonstrated that it could identify all levels of the hierarchy—from small sub-communities up to the entire network as a single cluster.

Conclusion and Future Work

The Information Dynamics Algorithm successfully identified nuanced substructures in benchmark networks, providing more detail than simple binary splits. While currently an exploratory tool, the authors suggest that limiting computational memory resources would make the model even more ecologically plausible. Future work aims to apply these cognitive heuristics to dynamic environments where links appear and disappear over time, further mimicking the fluidity of human social life.

Summary updated

Abstract

The problem of community detection is relevant in many scientific disciplines, from social science to statistical physics. Given the impact of community detection in many areas, such as psychology and social sciences, we have addressed the issue of modifying existing well performing algorithms by incorporating elements of the domain application fields, i.e. domain-inspired. We have focused on a psychology and social network - inspired approach which may be useful for further strengthening the link between social network studies and mathematics of community detection. Here we introduce a community-detection algorithm derived from the van Dongen's Markov Cluster algorithm (MCL) method by considering networks' nodes as agents capable to take decisions. In this framework we have introduced a memory factor to mimic a typical human behavior such as the oblivion effect. The method is based on information diffusion and it includes a non-linear processing phase. We test our method on two classical community benchmark and on computer generated networks with known community structure. Our approach has three important features: the capacity of detecting overlapping communities, the capability of identifying communities from an individual point of view and the fine tuning the community detectability with respect to prior knowledge of the data. Finally we discuss how to use a Shannon entropy measure for parameter estimation in complex networks.
BibTeX
@misc{massaro2011information,
  author = {Emanuele Massaro and Andrea Guazzini and Franco Bagnoli and Pietro Liò},
  title = {{Information dynamics algorithm for detecting communities in networks}},
  year = {2011},
  eprint = {1112.1224},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1112.1224},
}
Figure