Source-linked AI summary
Identifying a set of influential spreaders in complex networks
Jian-Xiong Zhang, Duan-Bing Chen, Qiang Dong, Zhi-Dan Zhao
TL;DR
Influence maximization requires choosing a small set of source spreaders that can reach many users without excessive computational cost or overlapping influence. The paper introduces VoteRank, an iterative neighbor-voting method that weakens the voting ability of elected spreaders’ neighbors. Across four real networks, VoteRank is reported to spread information faster, affect a larger final scale, and outperform other group-spreader methods in computational time.
Problem
Influence maximization seeks a small set of source spreaders that maximizes information spreading, but existing approaches may select nearby spreaders or require substantial computation.
Method
VoteRank iteratively elects spreaders using neighbor voting, sets elected nodes’ voting ability to zero, and decreases the voting ability of their neighbors.
Results
VoteRank outperforms traditional methods in spreading speed and final affected scale, and surpasses other group-spreader methods in computational time.
Takeaways & Limitations
Using information from previously selected nodes provides a simple, effective way to choose decentralized spreaders, especially as the number of selected spreaders grows.
Takeaways & Limitations
Extending VoteRank to temporal networks remains an open direction for further study.
Abstract
from arXiv · showhide
Identifying a set of influential spreaders in complex networks plays a crucial role in effective information spreading. A simple strategy is to choose top-$r$ ranked nodes as spreaders according to influence ranking method such as PageRank, ClusterRank and $k$-shell decomposition. Besides, some heuristic methods such as hill-climbing, SPIN, degree discount and independent set based are also proposed. However, these approaches suffer from a possibility that some spreaders are so close together that they overlap sphere of influence or time consuming. In this report, we present a simply yet effectively iterative method named VoteRank to identify a set of decentralized spreaders with the best spreading ability. In this approach, all nodes vote in a spreader in each turn, and the voting ability of neighbors of elected spreader will be decreased in subsequent turn. Experimental results on four real networks show that under Susceptible-Infected-Recovered (SIR) model, VoteRank outperforms the traditional benchmark methods on both spreading speed and final affected scale. What's more, VoteRank is also superior to other group-spreader identifying methods on computational time.
Introduction
Influence maximization seeks a small set of source spreaders that maximizes information diffusion, while existing ranking and heuristic approaches can select overlapping or computationally costly groups. VoteRank addresses this by iteratively selecting decentralized spreaders using neighbor-based voting and reduced voting ability.
- Motivation: Influence maximization chooses initial source spreaders to maximize the scale of information spreading in complex networks.Applications include advertising and word-of-mouth diffusion.
- Existing approaches: Selecting highly ranked nodes one by one can place spreaders close together, causing overlapping influence regions.This motivates methods that account for the group configuration of selected spreaders.
- Existing approaches: Ranking methods such as degree, PageRank, ClusterRank, and k-shell decomposition commonly identify influential individual nodes.The related work also discusses closeness, betweenness, LeaderRank, HITS, TwitterRank, and other heuristic measures.
- Existing approaches: Greedy hill-climbing can identify broad-impact groups but is very time consuming, while SPIN is faster yet remains difficult to apply to large networks.The passage gives a 28.25-minute CPU time example for selecting 30 nodes in one network.
- VoteRank: VoteRank selects spreaders one by one through neighbor voting, sets an elected node’s voting ability to zero, and decreases its neighbors’ voting abilities.Because it updates local information after each selection, the method is intended for networks with millions of nodes.
Methods and Materials
The study evaluates VoteRank and competing spreader-selection methods with SIR-based spreading metrics, structural separation, and four real networks. VoteRank elects nodes iteratively from local voting scores while weakening the influence of previously selected spreaders and their neighbors.
- Evaluation model: The SIR model represents each node as Susceptible, Infected, or Recovered and initializes only the selected source spreaders as infected.Infected nodes transmit to neighbors with probability µ and recover with probability β.
- VoteRank Algorithm: VoteRank assigns each node a voting score and voting ability, then repeatedly votes, selects the highest-scoring node, updates abilities, and stops after r spreaders.Initially, every node has tuple (0, 1); elected nodes no longer vote in later turns.
- VoteRank Algorithm: In directed networks, nodes vote only for in-neighbors, while the elected node and its out-neighbors receive the voting-ability update.A directed edge u to v indicates that v receives information from u.
- Performance Metrics: Performance is assessed using infected scale F(t), final affected scale F(tc), and average shortest path length Ls among selected spreaders.The study uses these metrics to evaluate spreading scale and structural separation.
- Data Description: The experiments cover undirected YOUTUBE and COND-MAT networks and directed BERKSTAN and NOTRE DAME networks.The networks represent social friendships, scientific collaborations, and hyperlinks.
Results
Across four real networks, VoteRank produced faster spreading and larger final affected scales than benchmark methods, while selecting more decentralized spreaders. Its advantages persisted across source-spreader counts and infection rates, with limited sensitivity to initial voting ability in undirected networks.
- Spreading performance: VoteRank spread information faster and eventually affected a larger scale than other methods on four real networks.The comparison used F(t) with λ = 1.5 and p = 0.002; results were averaged over 100 independent runs.
- Spreading performance: VoteRank achieved a wider final affected scale F(tc) than benchmark methods with the same number of source spreaders, especially for larger groups.
- Spreading performance: VoteRank achieved a wider spread scale than other methods across the tested infection rates λ, particularly on YOUTUBE, BERKSTAN, and NOTRE DAME.The study varied λ from 1 to 2 to make method differences clearer; Figure 4 used p = 0.002.
- Spreader structure: VoteRank-Non outperformed K-shellRank-Non when the number of source spreaders was large, while VoteRank and VoteRank-Non produced very similar results.The improved methods prohibit direct links between any two selected spreaders; VoteRank even outperformed K-shellRank-Non for p larger than 0.0015 in YOUTUBE.
- Parameter effects: In undirected networks, initial voting ability had little effect on F(tc), whereas smaller initial voting ability was relatively better in directed networks.Figure 6 varied the decreasing factor f and initial voting ability with λ = 1.5 and p = 0.002.
- Spreader structure: VoteRank-selected spreaders had larger average shortest-path lengths than those selected by other methods, indicating greater decentralization.This comparison used the NOTRE DAME and CONDMAT networks because shortest-path calculation is time consuming on large networks.
Computational complexity analysis
VoteRank's computational cost combines initialization, spreader selection, and local updates, yielding a complexity expression that is efficient for sparse networks with few selected spreaders.
- The algorithm initializes voting ability and scores, selects the highest-scoring node, then updates information within distance two of that spreader.These are the three components of total computational time.
- The total computational complexity for selecting r spreaders is O(m + r log n + rm2/n2) when an efficient selection structure is used.The expression combines initialization, selection, and update costs.
- Initializing voting ability costs O(n), score initialization costs O(m), and the combined first step is O(m).Setting initial voting ability to 1 reduces this step to O(1).
- Selecting the highest voting score costs O(n), or O(log n) with a red-black tree, while local updates cost O(< k >2) = O(m2/n2).The update only touches nodes at distance two from the newly selected spreader.
Discussion
VoteRank improves spreading by using previously selected nodes to rank subsequent spreaders, while its advantage is limited for small r and temporal-network extension remains open.
- Discussion: Using information from r −1 ranked nodes to rank the rth node boosts information spreading, especially in large-scale networks.The method uses already selected nodes to determine the next influential spreader.
- Discussion: VoteRank outperforms K-shellRank on undirected networks and PageRank, ClusterRank, and IndegreeRank on directed networks.The reported comparisons distinguish between undirected and directed network settings.
- Discussion: When r is small, VoteRank's advantage is not significant because little information from previously selected nodes is available.The accumulated information becomes more useful as r increases.
- Discussion: Performance remains fairly stable across different infected rates λ and initial-spreader scales p for information spreading.This stability is reported in the discussion of the experimental results.
- Discussion: Extending VoteRank to temporal networks is identified as an important topic for further study.The paper discusses temporal-network structure and dynamics as an open direction.