Overlapping community and entropy of neighborhood information for identifying influential nodes in complex networks – Scientific Reports

OCNEI is a ranking metric that pinpoints influential nodes by blending two complementary signals: neighborhood entropy (capturing local structural uncertainty and influence diversity) and overlapping community structure (exposing bridge roles across modules). This combination consistently outperforms classical and state-of-the-art baselines in diffusion accuracy, rank fidelity, and robustness tests across single-layer and multilayer social networks.

Computational complexity

OCNEI comprises three stages:

• Overlapping community detection: Implemented with MSLPAS, which runs in near-linear time with respect to the number of edges and scales with the number of iterations and parallel threads.
• Neighborhood Entropy of Influence (NEI): For each node and its h-hop neighbors, OCNEI computes degree-based probabilities and local entropy. This costs approximately O(n · d̄^h), where n is the number of nodes and d̄ is average degree.
• Community-aware adjustment: A CP factor integrates intra- and inter-community effects. In the worst case, the overhead grows with the number of communities and the paths considered within and across them.

Together, the total cost is well-approximated by the sum of these components and remains scalable for large, sparse graphs.

Experimental setup

• Environment: MATLAB R2024a; each experiment repeated 30 times and averaged.
• Diffusion model: SIR with a fixed recovery rate and infection rate sweeping 0.01–0.1.
• Seeds: top-30 nodes by each method (unless otherwise noted).
• Evaluation metrics:
  • EDV (Estimated Diffusion Value): efficient proxy for expected infections.
  • Kendall’s τ: rank correlation with SIR ground truth.
  • MCS ratio: size of the largest connected component after targeted removals.
• Other settings: default thresholds set to 0.6; 500 iterations for stochastic processes.

Datasets

We assess single-layer real networks of varying scales and a multilayer platform:

• Rice-Facebook: student friendship network with rich node attributes.
• Hamsterster: friendship ties in a pet community, useful for community studies.
• Twitter (medium): a connected subgraph of 3,560 users and their interactions.
• Amazon (medium): product co-purchase graph linking frequently bought-together items.
• Instagram-Activities (large): likes/comments interactions among users.
• YouTube (large): subscription network capturing content-following behavior.
• Higgs-FSRT (multilayer): integrated Friendships and Retweet layers around the Higgs event, used to stress-test overlapping-community awareness.

Baselines

Classical centralities: degree (DC), betweenness (BC), closeness (CC), eigenvector (EC), and k-shell (KSC).

Advanced methods:

• ASPAG: semi-local centrality using ASP with augmented graphs to capture short- and long-range ties.
• CGCAN: CNN+GCN embedding framework for learned node influence.
• MNEN: combines a node’s contribution with neighbors and exclusive neighbors.
• URank: entropy of adjacency information in unweighted, undirected graphs.
• CBLA: overlays community detection on classical centralities to emphasize bridges.

Ablation: what NEI and overlapping communities each add

We compare NEI-only, OC-only, and the full OCNEI on the Higgs-FSRT multilayer network using EDV, Kendall’s τ, and MCS ratio (with robustness measured after removing 25 nodes). NEI primarily sharpens local influence assessment by encoding uncertainty and neighbor diversity. The OC module highlights cross-community connectors. The full OCNEI consistently ranks best: it achieves higher EDV, stronger τ, and faster MCS decline under targeted removals, showing that neither component alone fully captures influence in networks with both local heterogeneity and overlapping meso-scale structure.

Results

Diffusion (EDV) across seed sizes

Across seed sets from 2 to 30, OCNEI delivers the highest or highly competitive EDV on all networks. As seeds grow, EDV increases, but OCNEI remains more adaptive: with small seed sets it prioritizes overlap-aware bridges to ensure broad coverage; with larger sets it maintains efficiency as diffusion homogenizes. Gains widen on larger graphs (Instagram-Activities, YouTube), underscoring scalability.

With 30 seeds, OCNEI improves EDV by 12.4% over ASPAG, 9.8% over CGCAN, 10.5% over MNEN, 6.0% over URank, and 3.7% over CBLA.

Rank fidelity (Kendall’s τ)

OCNEI achieves stronger correlation with SIR ground truth than both classical and advanced methods. Improvements over DC, BC, CC, EC, and KSC are 32.4%, 28.1%, 27.5%, 19.0%, and 11.7%, respectively. Against ASPAG, CGCAN, MNEN, URank, and CBLA, OCNEI lifts τ by 2.8%, 7.2%, 6.9%, 2.2%, and 4.8%. The advantage stems from jointly modeling local entropy and overlapping community connectivity.

Robustness (MCS ratio under targeted removals)

Removing nodes in descending rank order shows OCNEI isolates network backbones more effectively. After 5 removals, OCNEI’s MCS curve aligns with ASPAG and URank, while CGCAN, MNEN, and CBLA drop faster. At 20 removals, OCNEI drives MCS from ~85% to ~70%, evidencing accurate identification of critical hubs and bridges. At 50 removals, MCS falls to ~60%, approaching fragmentation. Although MNEN can trigger similar disruption one node earlier in a case, its instability and weaker diffusion performance reduce reliability. Overall, OCNEI provides the best balance of precision and stability.

Why OCNEI outperforms URank

Both are entropy-based, but URank measures only adjacency information entropy in single-layer, non-overlapping settings. OCNEI generalizes this by:

• Integrating overlapping community memberships to value inter-community bridges.
• Modeling neighbor influence diversity and local structural uncertainty together.
• Extending naturally to multilayer and overlapping graphs without heavy data demands.

Real-world impact

• Communications: Improve stability and accuracy in wireless/optical systems and visible-light positioning by reinforcing key relays and mitigating noise propagation.
• Data systems: Guide placement, caching, and deduplication through influence-aware locality, enhancing coherence and access efficiency in large stores.
• Neuroscience: Reveal synchrony drivers and resilience in fractional-order spiking networks by identifying structurally critical neurons and pathways.

Takeaway

By unifying neighborhood entropy with overlapping community awareness, OCNEI offers a scalable, topology-driven way to surface both locally dominant and globally bridging nodes. The result is higher diffusion reach, better agreement with epidemic ground truth, and stronger network dismantling power than leading baselines—especially as networks grow in size and structural overlap.