A novel method to identify multiple influential nodes in complex networks

Xiaoyu Li, Mingyang Zhou, Xiangyang Wu, Binghong Wang, Liao Luo, Hao Liao, Yang CaoScientia 2019 · DOI

Abstract: In the spread of information, a small fraction of nodes play an important role in the dynamics; therefore, detecting these influential nodes helps control the spread of information. However, classical methods can choose a single influential node yet fail in the case of multiple influential nodes. In this paper, we analyze the collective influence and overlapping influence of multiple spreaders. Further, based on the overlapping influence between spreaders, we clarify the problem of why multiple influential spreaders may have a low collective influence. Finally, a new algorithm is proposed to choose multiple spreaders, and the performance of the algorithm is validated on real networks.

1. Introduction

Identifying the most influential "seed" nodes in a network is a fundamental challenge in network science, with applications ranging from halting viral outbreaks to optimizing marketing campaigns. While traditional metrics like Degree Centrality or PageRank are effective at identifying individually powerful nodes, they often falter when selecting a set of nodes. This is due to the "Superstar Overlap" problem: highly connected nodes often cluster together, leading to redundant collective reach. To maximize group influence, we require a set of nodes that are both individually potent and strategically distributed to minimize redundancy.

2. Methodology: The Rayleigh Quotient and EC Algorithm

This research shifts from simple counting metrics to spectral analysis to quantify group influence.

2.1 The Rayleigh Quotient

The authors utilize the Rayleigh Quotient ($R(A, x) = \frac{x^T Ax}{x^T x}$) to approximate the largest eigenvalue ($\lambda_A$) of the network's adjacency matrix. In epidemic modeling, such as the Susceptible-Infected-Susceptible (SIS) model, this eigenvalue represents a critical tipping point; if the transmission rate exceeds $1/\lambda_A$, the infection spreads globally.

2.2 The EC Greedy Algorithm

To address the NP-hard challenge of selecting an optimal node set, the authors propose the EC algorithm. This greedy approach calculates node importance based on a second-order approximation of the Rayleigh Quotient. After selecting the most influential node, the algorithm "removes" its edges to account for its covered influence, then recalculates and repeats the process until the target number of nodes is reached.

3. Experimental Evaluation

The EC algorithm was validated against five established methods—High Degree (HD), Betweenness (BW), K-shell, Collective Influence (CI), and Non-Backtracking Matrix (NBM)—across four diverse real-world datasets:

  • Airtraffic: US airport flight connections.
  • Bitcoin: A trust network between platform users.
  • ca-HepTh: High Energy Physics collaboration network.
  • Reactome: Human protein-protein interactions.

In all tests, the EC algorithm proved most effective at reducing the principal eigenvalue and limiting the spread of infection in SIS simulations, demonstrating high stability across different network topologies.

4. Discussion: The Role of Loops and Redundancy

A key insight of this work is the impact of network cycles (loops). Many high-performance algorithms, like CI, assume a tree-like structure. However, real-world networks are often dense with loops, where these methods can fail. The Rayleigh-based approach naturally handles these complexities.

Illustration of network structures (a) tree-like, (b) with a loop, and (c) influence propagation.

The paper also mathematically demonstrates the diminishing returns of adding multiple "hubs" that share neighbors. Often, a "bridge" node connecting to an untouched part of the network provides greater marginal benefit than a second major hub.

5. Conclusion and Future Work

The proposed EC algorithm offers a robust framework for identifying multiple influential spreaders by focusing on spectral sensitivity. While the greedy approach is efficient, future work will focus on scaling the method for "mega-scale" networks and extending the Rayleigh Entropy mechanism to directed information flow networks.

Summary updated

Abstract

In the spread of information, a small fraction of nodes play an important role in the dynamics; therefore, detecting these influential nodes helps control the spread of information. However, classical methods can choose a single influential node yet fail in the case of multiple influential nodes. In this paper, we analyze the collective influence and overlapping influence of multiple spreaders. Further, based on the overlapping influence between spreaders, we clarify the problem of why multiple influential spreaders may have a low collective influence. Finally, a new algorithm is proposed to choose multiple spreaders, and the performance of the algorithm is validated on real networks.
BibTeX
@inproceedings{li2019novel,
  author = {Xiaoyu Li and Mingyang ZHOU and Xiangyang Wu and Binghong WANG and Liao LUO and Hao Liao and Yang Cao},
  title = {{A novel method to identify multiple influential nodes in complex networks}},
  booktitle = {Scientia},
  year = {2019},
  doi = {10.1360/n112019-00041},
}
Figure