HMPA: Solving Label Invasion in Overlapping Community Discovery

TL;DR

The Hierarchical Multi-label Propagation Algorithm (HMPA) addresses the instability and "label flooding" of traditional overlapping community detection. By defining a Node Hierarchy (Core vs. Boundary) and using Label Propagation Gain, it restricts how labels spread, resulting in higher accuracy and up to 3x faster convergence than established methods like COPRA.

Background & Motivation: Why MLPAs Fail in Fuzzy Networks

Community discovery is the cornerstone of social network analysis. While Multi-label Propagation Algorithms (MLPAs) are praised for their nearly linear time complexity, they are notoriously unstable.

The root cause is "Label Invasion." In networks where community boundaries are not crisp (fuzzy structures), high-influence labels from one group can "invade" another via boundary nodes, eventually causing the collapse of distinct community structures. Furthermore, current methods use static thresholds to limit how many communities a node can join, which is often a "one-size-fits-all" failure in complex topologies.

Methodology: The Three-Stage Refinement

HMPA avoids the pitfalls of random propagation by introducing structural awareness across three distinct phases:

1. Initial Structural Unfolding

Instead of starting from scratch with multi-labels, HMPA first uses LPAm (Modularity-specialized Label Propagation) to identify a rough "skeleton" of non-overlapping communities. This provides the "prior knowledge" needed for the next steps.

2. Node Hierarchy Marking

Using a PageRank-like recursive logic, HMPA assigns a hierarchy value ($h_u$) to each node. Nodes deep within a community (Core) receive higher values, while those on the periphery (Boundary) receive lower ones.

3. Overlapping Region Refining & Adaptive Filtering

The core innovation is Label Propagation Gain. The strength of a label moving from node $u$ to $\sigma$ is governed by: $gain(u,\sigma )=\lg \frac{h_u}{h_{\sigma }}$ This effectively "dampens" the influence of boundary nodes trying to push external labels back into the stable core of a community. Finally, an Adaptive Label Filter using the steepest descent method replaces fixed thresholds, allowing nodes to decide how many communities they belong to based on local evidence.

Experimental Validation

HMPA was tested against COPRA and SLPA on LFR synthetic benchmarks and nine real-world social networks.

Accuracy in Fuzzy Structures

On LFR networks with high overlap ($on$ > 3000), traditional COPRA's performance collapses (NMI drops to zero). HMPA maintains a high NMI and F-Score, proving that the Hierarchy mechanism successfully protects community integrity.

Efficiency and Stability

In real-world tests (e.g., cond-mat-2003), HMPA converged in 103 iterations compared to COPRA's 363 iterations, while delivering a higher Modularity ($Q_{ov}$). Importantly, the standard deviation of its results was near zero, solving the notorious "non-deterministic" instability of propagation methods.

Deep Insight & Conclusion

The brilliance of HMPA lies in its realization that not all nodes are created equal in the propagation process. By treating boundary nodes as lower-authority "messengers" and core nodes as high-authority "anchors," the algorithm mirrors the social reality of how groups interact.

Limitations: While the time complexity is nearly linear in sparse networks, the second-stage hierarchy calculation ($O(m^2/n)$) might become a bottleneck in extremely dense graphs. Future work in applying this to dynamic networks where hierarchies shift in real-time is the next logical frontier.