PaperlayerView exact revision on arXiv

Source-linked AI summary

Effective spreading from multiple leaders identified by percolation in social networks

Shenggong Ji, Linyuan Lu, Chi Ho Yeung, Yanqing Hu

arXiv:1508.04294v1physics.soc-phcs.SI

TL;DR

Finding a coordinated group of influential spreaders is computationally difficult, though a few users can propagate news widely. The paper uses percolation clusters to select distributed spreaders. Tests report greater spreadability than centrality methods at equal cost.

  • Problem

    Finding a coordinated group of spreaders is computationally difficult, even though a few users can propagate news widely.

    Source: §I · pp. 2–3

  • Method

    The protocol scores high-degree nodes across percolation clusters and ranks them to select W spreaders distributed across the network.

    Source: §II · pp. 4–5

  • Results

    At equal cost, percolation yields higher spreadability than k-shell and degree centrality and the highest saturated spreadability; Facebook tests also favor it over tested centrality methods.

    Source: A. Spreadability and coverage redundancy · p. 10, §III · p. 12

  • Takeaways & Limitations

    Evenly distributed coordinated spreaders are presented as essential for increasing coverage and reducing redundancy.

    Source: §III · p. 12

Abstract

from arXiv · show

Social networks constitute a new platform for information propagation, but its success is crucially dependent on the choice of spreaders who initiate the spreading of information. In this paper, we remove edges in a network at random and the network segments into isolated clusters. The most important nodes in each cluster then form a group of influential spreaders, such that news propagating from them would lead to an extensive coverage and minimal redundancy. The method well utilizes the similarities between the pre-percolated state and the coverage of information propagation in each social cluster to obtain a set of distributed and coordinated spreaders. Our tests on the Facebook networks show that this method outperforms conventional methods based on centrality. The suggested way of identifying influential spreaders thus sheds light on a new paradigm of information propagation on social networks.

I. INTRODUCTION

Identifying a coordinated group of influential spreaders is difficult, yet individual users can propagate information widely. The paper uses percolation to identify coordinated spreaders and reports better coverage and lower redundancy than centrality-based heuristics.

I. INTRODUCTION

  • Influential users are rare, although their messages can spread quickly through a network.Source: §I · p. 2
  • Degree, k-core, betweenness, closeness, and LocalRank are among proposed centralities, but betweenness and closeness are computationally impractical for large networks.Source: §I · p. 2
  • Selecting a coordinated group is computationally difficult, unlike choosing independent spreaders by centrality.Source: §I · p. 3
  • The protocol randomly removes edges to form isolated clusters and selects influential users within them as coordinated spreaders.Repeated percolated states improve estimates of social clusters and their influential spreaders.Source: §I · p. 3
  • On Facebook and Enron email networks, the protocol outperforms local- and global-centrality heuristics on propagation coverage and coverage redundancy.Source: §I · p. 3
  • The protocol also identifies different effective spreader characteristics for niche versus popular items, with implications for viral marketing strategies.Source: §I · p. 3

II. RESULTS

The method uses bond percolation as a proxy for information spread, then scores candidate spreaders across clusters. It treats cluster coverage as a guide to selecting a distributed group with reduced redundancy.

II. RESULTS

  • The SIR model’s transmissibility p corresponds to bond-occupation probability p, linking outbreak size to the percolation cluster reached by a spreader.Source: §II · p. 4
  • Bond percolation models information transmission by recovering edges with probability p, interpreted as transmissibility; a giant component emerges above the critical threshold pc.Source: §II · p. 4
  • Across repeated link-recovery trials, the method scores high-degree nodes in the largest clusters, ranks nodes by total score, and selects the top W spreaders.It uses tunable L, usually set equal to or greater than W; results were not sensitive to L.Source: §II · pp. 4–5
  • The method targets separate clusters where news can spread within but not across them, yielding distributed spreaders with reduced redundancy.Source: §II · p. 5

A. Spreadability and coverage redundancy

The section measures spreadability as the fraction of nodes recovered in an SIR outbreak, with transmissibility matched to the edge-recovery probability. Across the reported comparisons, percolation selection combines high coverage with low redundancy and favorable cost tradeoffs.

A. Spreadability and coverage redundancy

  • Percolation achieves the highest spreadability across transmissibility values and, at equal cost, exceeds k-shell and degree centrality.Betweenness centrality saturates at low spreadability, while percolation has the highest saturated spreadability.Source: A. Spreadability and coverage redundancy · pp. 6, 10
  • Identification cost drops sharply just beyond pc, where the method favors lower-degree spreaders than it does below pc.Below pc, the selected spreaders have higher average original degree than those selected above pc.Source: A. Spreadability and coverage redundancy · p. 6
  • On a generated network with four communities, four spreaders landed in different communities in 93.9% of realizations.The authors connect this pattern to the method's segmentation of the network into isolated clusters.Source: A. Spreadability and coverage redundancy · p. 7
  • Percolation has the lowest coverage redundancy among the four methods, with spreaders usually located in different network regions.The paper attributes the lower redundancy to this distribution of spreaders.Source: A. Spreadability and coverage redundancy · p. 7
  • As p increases, percolation solutions become more diverse, and their overlap with degree-centrality selections falls from ≈61.5% at p = 0.01 to less than 5% at p = 0.03.The larger solution space provides alternative spreaders if some selected users are offline.Source: A. Spreadability and coverage redundancy · pp. 8–9

III. DISCUSSION

The discussion frames intentional information spreading around coverage, redundancy, and the cost of selecting spreaders, then presents percolation-based coordination as a way to improve these outcomes.

III. DISCUSSION

  • FIG. 4 relates spreadability to identification cost on Facebook; the described plot uses total cost of the top-k selected nodes on the x-axis and group spreadability on the y-axis.The discussion frames coverage, redundancy, and identification cost as performance measures.Source: §III · pp. 10–11, Figure 4 · p. 11
  • On Facebook, percolation-selected spreaders are more evenly distributed and increase propagation coverage while reducing redundancy relative to conventional centrality methods.The discussion identifies coordination through percolation as central to these comparisons.Source: §III · p. 12
  • Random edge removal identifies isolated clusters where news can spread within clusters but not across them, guiding selection of spreaders in the original network.The paper presents percolation as the protocol's central mechanism, not merely an analogy.Source: §III · p. 12
  • The protocol has computational complexity O(|E|), while the discussion notes that practical details and difficulties are omitted.The authors characterize the complexity as scaling linearly with system size.Source: §III · p. 12

A. Baseline methods

The baseline methods represent influence through direct neighbor counts, network position, or shortest-path roles, each using a different structural signal.

A. Baseline methods

  • Degree centrality assumes nodes with more nearest neighbors have greater influence, but degree reflects direct influence rather than influence mediated by neighbors.A low-degree node with a few highly influential neighbors may outrank a higher-degree node with less influential neighbors.Source: A. Baseline methods · pp. 12–13
  • Kitsak et al. use k-core decomposition, assuming nodes in the same shell have similar influence and higher-shell nodes are likely to infect more nodes.This method treats network location as a signal of influence.Source: A. Baseline methods · p. 13
  • Betweenness centrality measures the fraction of shortest paths between all node pairs that pass through a node; g_st(v) counts such paths through v.The passage describes it as a global, geodesic-path-based ranking measure.Source: A. Baseline methods · p. 13

B. Computational complexity

The protocol selects high-degree nodes from the largest components across percolation realizations, then ranks nodes by their scores. For real networks, its complexity grows linearly with system size.

B. Computational complexity

C. Model networks with community structures

The experiment constructs a 2,000-node network from four 500-node communities, then connects the subnetworks using randomly selected node pairs.

C. Model networks with community structures

D. Datasets

The section points readers to the supplementary information for dataset descriptions and to Table S1 for network statistics.

D. Datasets

  • Dataset descriptions are in Section I of the supplementary information, and real-network statistics are summarized in Table S1.Source: D. Datasets · p. 14

E. SIR model and bond percolation

The SIR model represents spreading through susceptible, infected, and recovered states, with transmission and recovery probabilities at each time step. Its percolation mapping relates an outbreak to the cluster containing the initially infected node.

E. SIR model and bond percolation

  • In the SIR model, susceptible individuals can be infected, infected individuals transmit with probability β and recover with probability γ, and recovered individuals are immune.The simulation proceeds in discrete time steps and stops when no infected nodes remain.Source: E. SIR model and bond percolation · p. 14
  • The SIR process maps to bond percolation, where each link exists with probability equal to transmissibility p.Source: E. SIR model and bond percolation · pp. 14–15
  • An outbreak triggered by one initially infected node has the size of its percolation cluster, and nodes in the same cluster are expected to have the same coverage.Source: E. SIR model and bond percolation · p. 15

Related papers

Loading 1508.04294v1…