Precise influence evaluation in complex networks

Bingyu Zhu, Qingyun Sun, Jianxin Li, Daqing LiarXiv 2023 · DOI · arXiv

Abstract

Identifying influential spreaders in complex networks—nodes capable of triggering large-scale cascades—is a fundamental challenge in network science. Existing approaches typically fall into two categories: fast but imprecise heuristic centrality measures, or accurate but computationally prohibitive dynamic simulations. We introduce ALGE (Active Learning based on Graph Entropy), a three-stage framework that leverages Graph Neural Networks (GNNs) and active learning to achieve simulation-level precision with heuristic-level efficiency. By fine-tuning a pre-trained model on a strategically selected subset of nodes, ALGE captures individualized structural features across diverse network types, significantly outperforming traditional and deep learning baselines in both ranking accuracy and influence maximization.

Introduction

The ability to pinpoint nodes that drive spreading processes is vital for managing viral marketing, epidemic control, and infrastructure resilience. However, traditional metrics like degree centrality or k-shell often fail to account for the unique structural nuances of specific networks, leading to high "disputation"—inconsistent rankings across different algorithms. Conversely, running exhaustive Susceptible-Infected-Recovered (SIR) simulations is too slow for large-scale applications. The challenge is creating a method that is as fast as a heuristic but as precise as a simulation, while remaining adaptable to diverse network types.

Methodology: The ALGE Framework

ALGE addresses these challenges through a multi-stage learning process designed to bridge the gap between general spreading physics and network-specific quirks:

  1. Pre-training (ALGE-B): A Graph Attention Network (GATv2) is trained on synthetic networks to learn the general mapping between local graph structures and spreading outcomes based on the SIR model.
  2. Active Learning (AL): To adapt to a specific target network, the framework uses Graph Entropy to compute a correlation matrix. This identifies "representative nodes" that best capture the network's unique topology.
  3. Fine-tuning (ALGE-C): The basic model is fine-tuned using the actual simulation results of only these few representative nodes. This allows the model to learn individualized information with minimal computational overhead.
The ALGE framework overview, showing pre-training, active learning for node selection, and final prediction stages.

Results and Discussion

The framework was evaluated across a massive variety of real-world networks (26-34 datasets), including biological, social, and infrastructure systems.

Ranking Accuracy

ALGE-C consistently achieved the highest Kendall’s coefficient across nearly all tested networks, indicating superior correlation with ground-truth simulation results. As shown in the comparison below, ALGE-C (0.93) significantly outperforms both traditional heuristics like K-shell and advanced deep learning models like RCNN and Graph-based LSTM.

Comparison of predicted vs. true influence ranks. ALGE-C achieves the highest correlation (0.93) among all tested methods.

Quantitative Precision and Influence Maximization

Unlike most methods that only rank nodes, ALGE-C predicts the actual number of nodes a spreader will infect. The transition from the basic model (ALGE-B) to the fine-tuned model (ALGE-C) results in a dramatic reduction in Mean Squared Error (MSE) across all datasets.

Furthermore, the authors applied these values to the Influence Maximization Problem (IMP) via the ALGE-Greedy algorithm. By quantifying the "influence range" of nodes, ALGE-Greedy effectively minimizes influence overlap between selected seeds, ensuring the collective spread is maximized. This approach outperformed the state-of-the-art "Collective Influence" (CI) method, maintaining higher infection rates over time.

Conclusion

ALGE represents a significant step toward precise and efficient influence evaluation in complex networks. By combining the generalizability of GNNs with the targeted efficiency of active learning, it overcomes the limitations of both heuristics and simulations. Future work will focus on scaling the correlation matrix computation for massive graphs and extending the framework to alternative spreading dynamics such as the Linear Threshold model.

Summary updated

BibTeX
@misc{zhu2023precise,
  author = {Bingyu Zhu and Qingyun Sun and Jianxin Li and Daqing Li},
  title = {{Precise influence evaluation in complex networks}},
  year = {2023},
  eprint = {2310.12181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.12181},
}
Figure