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:
- 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.
- 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.
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.
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