PaperlayerView exact revision on arXiv

Source-linked AI summary

Influence maximization in complex networks through optimal percolation

Flaviano Morone, Hernan A. Makse

arXiv:1506.08326v1physics.soc-phcond-mat.dis-nncs.SI

TL;DR

Identifying the smallest set of influential nodes remains difficult because existing methods do not optimize a collective objective. The paper maps influence maximization onto optimal percolation using the network’s non-backtracking structure, finding that its strategy can use half a million fewer people and save ∼35% of vaccine stockpile in a social network.

  • Problem

    Existing methods for identifying influential spreaders do not optimize an objective, leaving the minimal influencer set unresolved.

  • Method

    The paper formulates influence maximization as optimal percolation, minimizing the leading eigenvalue by removing the fewest nodes.

  • Results

    Using half a million less people in this social network saved ∼35% of vaccine stockpile.

  • Takeaways & Limitations

    Optimal influencers include weakly connected nodes surrounded by hierarchical coronas of hubs at different ℓ-levels.

  • Takeaways & Limitations

    The developed method is strictly valid only when G = 0.

Abstract

from arXiv · show

The whole frame of interconnections in complex networks hinges on a specific set of structural nodes, much smaller than the total size, which, if activated, would cause the spread of information to the whole network [1]; or, if immunized, would prevent the diffusion of a large scale epidemic [2,3]. Localizing this optimal, i.e. minimal, set of structural nodes, called influencers, is one of the most important problems in network science [4,5]. Despite the vast use of heuristic strategies to identify influential spreaders [6-14], the problem remains unsolved. Here, we map the problem onto optimal percolation in random networks to identify the minimal set of influencers, which arises by minimizing the energy of a many-body system, where the form of the interactions is fixed by the non-backtracking matrix [15] of the network. Big data analyses reveal that the set of optimal influencers is much smaller than the one predicted by previous heuristic centralities. Remarkably, a large number of previously neglected weakly-connected nodes emerges among the optimal influencers. These are topologically tagged as low-degree nodes surrounded by hierarchical coronas of hubs, and are uncovered only through the optimal collective interplay of all the influencers in the network. Eventually, the present theoretical framework may hold a larger degree of universality, being applicable to other hard optimization problems exhibiting a continuous transition from a known phase [16].

Additional information

The paper formulates influence maximization as minimizing the largest eigenvalue of a non-backtracking matrix, identifying optimal node removals that destroy network loops. Its collective strategy outperforms heuristic methods in synthetic and large-scale social networks, while revealing weakly connected influencers.

  • Optimal percolation: Optimal immunization or spreading removes the fewest nodes while minimizing the largest non-backtracking eigenvalue λ and destroying all network loops.Removing a loop can reduce λ to zero, whereas removing a leaf need not decrease it.
  • Optimal percolation: At the optimal percolation transition, λ = 1; the giant component is then a unicyclic graph that abruptly becomes a tree when the transition is crossed.For q ≥ qc, the minimum is λ = 0, whereas for q < qc the minimum remains λ > 1.
  • Weak-nodes: Weak-nodes are low-connectivity nodes surrounded by hierarchical coronas of hubs and can be crucial influencers missed by heuristic strategies.The optimal set emerges from the collective interplay of influencers rather than degree-based selection alone.
  • Synthetic networks: CI performs close to the true optimum in synthetic networks and produces a much smaller giant component than competing methods after removing 15% of nodes in a scale-free network.The synthetic-network comparisons include EO, HDA, PR, HD, CC, EC, and k-core.

METHODS · A. BP adaptive

The methods section includes a BP adaptive component and identifies mappings between optimal immunization, spreading problems, and optimal percolation. It also references an interpretation in terms of non-backtracking walks and generalization to 2ℓ-body interactions.

  • METHODS: The provided methods material attributes the paper to Flaviano Morone and Hern´an A. Makse.The author names appear in the supplied methods passages.
  • METHODS: The methods address mapping optimal immunization and spreading problems onto optimal percolation.This mapping is identified in the subsection heading provided.
  • METHODS: The methods section connects BP adaptive procedures with a broader optimal-percolation mapping.The section title and mapping subsection heading jointly indicate this methodological relationship.
  • METHODS: The paper includes a methods subsection on interpreting the framework in terms of non-backtracking walks.The supplied heading explicitly names “NB walks” as an interpretive framework.
  • METHODS: The methods discuss generalization to 2ℓ-body interactions.The supplied passage heading explicitly identifies this generalization.

I. HEURISTIC METHODS USED TO IDENTIFY INFLUENTIAL SPREADERS IN COMPLEX NETWORKS · II. COLLECTIVE THEORY OF OPTIMAL INFLUENCE · A. Optimal Percolation

The paper contrasts heuristic node rankings with a collective theory that formulates influence optimization as optimal percolation. The theory minimizes the largest eigenvalue of a modified non-backtracking matrix to identify node removals that destroy the giant component.

  • I. HEURISTIC METHODS USED TO IDENTIFY INFLUENTIAL SPREADERS IN COMPLEX NETWORKS: Heuristic methods rank nodes using intuitive individual attributes rather than optimizing a global influence function or collective interactions.These methods include degree, PageRank, k-core, eigenvector, closeness, betweenness, and graph-partitioning strategies.
  • I. HEURISTIC METHODS USED TO IDENTIFY INFLUENTIAL SPREADERS IN COMPLEX NETWORKS: For multiple spreaders, k-shell ranking is not optimal because influence depends on interactions and overlap among the full set of spreaders.K-core performs well for individually identifying spreaders but poorly for multiple spreaders; separated core nodes can improve optimality.
  • II. COLLECTIVE THEORY OF OPTIMAL INFLUENCE: The collective theory maps optimal influence onto finding the minimal node set that minimizes the largest eigenvalue of the network’s non-backtracking matrix.The general optimization problem is intractably hard, but the paper presents perturbative approximations and a fast algorithm with running time O(N log N).
  • II. COLLECTIVE THEORY OF OPTIMAL INFLUENCE: Higher-order approximations outperform previous heuristic strategies while modeling the first non-trivial attack as the ground state of a spin-glass-like system.The approach is used to simulate optimized immunization, quarantine, and superspreading protocols on very large real networks.
  • A. Optimal Percolation: Optimal percolation seeks the minimum removed-node fraction qc such that the giant connected component vanishes, G(qc) = 0.For q ≥ qc, the remaining network consists of clusters with subextensive sizes.
  • A. Optimal Percolation: The method replaces direct minimization of the giant component with minimization of the largest eigenvalue λ(n; q), whose stability condition is λ(n; q) < 1.The modified operator is expressed through the non-backtracking matrix for locally tree-like random networks, and the exact limit requires that assumption.
  • A. Optimal Percolation: As q approaches qc, configurations satisfying λ(n; q) < 1 become fewer and vanish at qc, marking the transition to a fragmented network.For q > qc, optimal configurations have G(q) = 0, whereas nonoptimal removals can leave G(q) > 0.
  • A. Optimal Percolation: Minimizing the modified non-backtracking eigenvalue attacks network loops: at λ = 1, removing one node can sharply reduce λ to zero and leave a tree-like fragmented giant component.The theory therefore identifies loop destruction as the best attack strategy; trees have largest eigenvalue zero, while networks with many loops have λ > 1.

B. Mapping of optimal immunization and spreading problems onto optimal per- · C. Limit of applicability of the theory of influence

The paper maps optimal immunization and spreading onto optimal percolation by minimizing the giant component, while identifying the transition conditions under which the theory applies. Its influence mapping is exact for locally tree-like networks and degrades as loop density increases.

  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: Optimal immunization and spreading are mapped exactly onto minimizing a network’s giant component, establishing a shared optimal-percolation framework.Immunization removes nodes to fragment the network, while spreading minimizes inactive nodes to maximize information diffusion.
  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: In the Linear Threshold Model, optimal spreading finds the minimum initial spreader set that percolates information through the entire network.The mapping uses threshold θi = ki −1; setting θi = 1 recovers optimal immunization.
  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: The theory applies when the transition at qc is second order, allowing local stability of G = 0 to identify optimal solutions.For intermediate thresholds θi = ki −2, ki −3, . . . 2, the transition is first order and requires independent treatment.
  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: For first-order transitions, the largest eigenvalue of the non-backtracking operator is not guaranteed to provide the optimal set.The stated limitation applies to optimal spreading with intermediate Linear Threshold Model thresholds.
  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: The framework generally cannot translate optimal spreaders under SIR or SIS models into optimal percolation because they lack a transition from G = 0 to G > 0.Consequently, these models cannot be treated under the paper’s stability theory.
  • B. Mapping of optimal immunization and spreading problems onto optimal percolation: The theory holds for optimization problems on locally tree-like random networks that map to optimal percolation with a second-order transition between G = 0 and G > 0.Under these conditions, the CI algorithm can be used accordingly.
  • C. Limit of applicability of the theory of influence: The influence mapping is strictly valid for locally tree-like networks because message-passing probabilities are assumed independent.This includes Erdős-Rényi, scale-free, and configuration-model networks in the thermodynamic limit.
  • C. Limit of applicability of the theory of influence: Results derived for tree-like graphs can apply to loopy networks when loop density is not excessively large, but deteriorate where loops are abundant.Finite-dimensional lattices are given as an example where the locally tree-like approximation loses quality.

D. Random influence · E. Derivation of the main formula: cost energy function of influence, Eq. (4)

Random removal decoupled from the non-backtracking matrix recovers the random-percolation threshold for random networks, whereas coupling removal to that matrix yields the optimal threshold. The derivation of Eq. (4) uses eigenvalue growth on very large locally tree-like graphs and expands the resulting cost function into increasingly high-order many-body interactions.

  • D. Random influence: Random node removal is modeled by sampling n_i from P(n; q), decoupled from the non-backtracking matrix.Because P(n; q) factorizes over sites, the matrix expectation can be taken over n.
  • D. Random influence: For random networks, the averaged largest eigenvalue is governed by the largest eigenvalue of the non-backtracking matrix and the degree-distribution moments.The parameter κ is the ratio of the first two moments of the degree distribution.
  • D. Random influence: The condition λ(q_c) = 1 recovers the random-percolation threshold when node removal is decoupled from the non-backtracking matrix.This result applies to random networks, while generic graphs need not have eigenvalues related to the first two degree-distribution moments.
  • D. Random influence: For generic graphs, the optimal threshold arises by coupling node removal with the non-backtracking matrix rather than treating removal independently.The random-network eigenvalue relation is stated to hold only when the original graph is random.
  • E. Derivation of the main formula: cost energy function of influence, Eq. (4): Eq. (4) is derived for very large locally tree-like graphs by using λ(n) to determine the growth rate of iterated vectors under the matrix M̂.The derivation applies the Power Method and embeds the 2M × 2M matrix in an N × N × N × N space.
  • E. Derivation of the main formula: cost energy function of influence, Eq. (4): The embedded representation uses adjacency-matrix components and Kronecker deltas to preserve the non-backtracking character of network walks.The matrix is represented on network nodes rather than directed edges, with |w_0⟩_ij = A_ij in the enlarged node space.
  • E. Derivation of the main formula: cost energy function of influence, Eq. (4): The eigenvalue expansion becomes a systematic diagrammatic series whose terms encode interactions among node variables and degree-dependent factors.A diagram represents products such as n_i n_j z_i z_j, with the number of variables determining interaction order.

F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions · G. Odd (2ℓ+ 1)-body interactions

The interaction terms are organized by non-backtracking walks, with the leading 2ℓ-body contribution becoming exact as N →∞ when loop-containing graphs are suppressed. The framework also extends the cost function to odd (2ℓ+1)-body interactions through a Power Method expansion.

  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: The dominant graph for interaction order ℓ is a direct path of length 2ℓ−1 containing 2ℓ nodes.The initial and final nodes may coincide in other allowed walks, and loops or repeated node visits are otherwise permitted.
  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: In sparse locally tree-like random graphs, loop-containing non-backtracking graphs are suppressed by powers of 1/N.Non-self-intersecting closed walks occur with probability O(1/N), while self-intersecting closed walks have probability O(1/N 2).
  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: For very large networks, retaining only the leading 2ℓ-body interaction gives a good approximation to |wℓ(n)|2 and becomes exact as N →∞.For small networks, all terms, including loop-containing contributions, should be considered.
  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: Each |wℓ(n)|2 term corresponds to a non-backtracking walk of length 2ℓ−1, allowing edges to be crossed multiple times.Variables ni attach to visited nodes, while the walk’s endpoints carry extra degree factors zi1 and zi2ℓ.
  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: Neglecting loops reduces the interaction to shortest-path non-backtracking walks whose visited nodes are distinct and lie within a radius-ℓ ball.This leading expression is identified with the influence cost energy function in Eq. (4).
  • F. Interpretation in terms of NB walks and generalization to 2ℓ-body interactions: The resulting leading expression is the cost energy function of influence given by Eq. (4).It follows from the loop-free reduction of the non-backtracking-walk expansion.
  • G. Odd (2ℓ+ 1)-body interactions: The even-interaction cost function can be extended to odd (2ℓ+1)-body interactions using a Power Method expansion of ⟨wℓ(n)| M̂ |wℓ(n)⟩.For N →∞, the resulting asymptotic expression neglects loops, and an analogous approximant λ′ℓ(n) can be introduced.

H. HD attack at ℓ= 0 one-body problem

The ℓ=0 one-body formulation reproduces the high-degree attack by ranking nodes through the nonnegative field h_i = k_i(k_i −1), so minimization removes the highest-degree nodes first. Its threshold matches the known HD result, but finite cutoffs show much slower fragility than the k_max →∞ limit suggests.

  • H. HD attack at ℓ= 0 one-body problem: The one-body interaction treats influencers independently in an external field h_i = k_i(k_i −1), omitting the collective effects present for ℓ≥2.The field is site-dependent and always nonnegative.
  • H. HD attack at ℓ= 0 one-body problem: Because h_i increases monotonically with degree, minimizing the one-body energy removes the N_q nodes with the highest degrees, exactly implementing the HD strategy.The minimization is achieved by setting n_i = 0 for the first N_q highest-degree nodes and n_i = 1 for the rest.
  • H. HD attack at ℓ= 0 one-body problem: The stability condition gives exactly the critical threshold q_c expected for the HD attack and recovers the known result when k_max →∞.This correspondence is derived using the degree distribution of the network after hub removal.
  • H. HD attack at ℓ= 0 one-body problem: For γ = 2, the infinite-cutoff result predicts q_c = 0 for any m, reflecting extreme fragility as the natural cutoff diverges linearly with system size.At γ = 2, k_max ∼N.
  • H. HD attack at ℓ= 0 one-body problem: With finite k_max, q_c vanishes only as the inverse logarithm of the cutoff; even for k_max of order hundreds of millions it remains of order 0.1, while k_max = 10^3 gives q_c ≈0.2 for all γ.These finite-cutoff results motivate searching for attack strategies beyond hub removal.

III. OPTIMIZATION WITH THE CAVITY METHOD

The cavity method maps optimal percolation onto a spin-glass ground-state problem with a fixed number of removed nodes, using an RS message-passing solution. In the 2-body approximation, it estimates a transition at qc = 0.248, while RS and EO bounds remain close to the true optimum and support scalability to very large networks.

  • Spin-glass formulation: Optimal percolation becomes finding the ground state of a spin-glass system.The optimization is formulated with Ising spin variables and an energy function.
  • Spin-glass formulation: Removed nodes are represented by spin down, si = −1, while retained nodes are spin up, si = 1.Thus, fixing the number of influencers fixes the magnetization.
  • Cavity solution: The RS cavity equations update directed-edge messages self-consistently and can be solved iteratively as a message-passing algorithm.The cavity fields and biases represent incoming and outgoing messages between neighboring nodes.
  • Cavity solution: The RS cavity method is limited to a single pure state, while 1RSB can incorporate multiple solutions; analysis of 1RSB is deferred to future work.The paper therefore restricts its treatment to the RS method.
  • Results: qc = 0.248 is the transition point found in the 2-body interaction approximation for size N = 104.The true optimal eigenvalue instead jumps discontinuously from zero to one at qc, whereas the 2-body approximation smooths the jump.
  • Results: The RS lower bound and EO upper bound are very close to each other and therefore to the true optimum.This comparison provides evidence that the approximate solutions are close to optimal.
  • Results: The algorithm was designed for very large networks because it can optimize configurations as well as possible at scale.This scalability is identified as the main reason for designing the CI algorithm.

IV. MINIMIZATION WITH EXTREMAL OPTIMIZATION (EO)

The section presents Extremal Optimization (EO) and its τ-parameterized variant for minimizing the largest non-backtracking eigenvalue, while noting that EO is accurate but not scalable to large networks. Applied to Erdős–Rényi networks, τ-EO enables finite-size scaling of the optimal influence threshold and suggests multiple equivalent optimal influencer sets.

  • Method scope: EO is an efficient near-optimal method that incorporates the full energy function, including loops, but it is not scalable to large networks.The method is used for small systems and to extrapolate solutions when direct EO becomes impractical.
  • EO algorithm: EO minimizes the energy by removing nodes with the lowest fitness while preserving the prescribed number of removed nodes.Each node’s fitness depends on the states of other nodes, so the algorithm repeatedly updates fitness values and swaps nodes between removed and retained sets.
  • τ-EO variant: τ-EO randomizes rank-based node exchanges, enabling global reconfigurations that can cross energy barriers and find better minima.The deterministic EO algorithm is recovered for τ →∞, while the study reports τ = 1.7 as producing the best results.
  • Finite-size scaling: Finite-size scaling of the optimal influence threshold qc, defined by λ(qc) = 1, is consistent with the reported scaling law and extrapolates toward the infinite-size limit.The application uses Erdős–Rényi networks with average degree ⟨k⟩= 3.5 and system sizes N = 25, 26, 27, 28, averaging over 100 realizations.
  • Optimal solutions: The model contains infinitely many ways to choose the set of optimal influencers, raising the possibility of a hidden symmetry relating these solutions.This interpretation connects the observed zero modes with distinct optimal influencer sets.

A. τ-EO with multibody interactions

The τ-EO algorithm is extended to systems with multibody interactions by redefining node fitness while preserving the optimization procedure. These systems show a broader zero-eigenvalue interval, supporting a discontinuous threshold behavior in the infinite-interaction limit.

  • Method: τ-EO handles multibody systems by changing the fitness definition bi and then applying the algorithm as in the two-body case.The extension is illustrated for systems with 3-, 4-, and 5-body interactions; for 4-body interactions, zi = ki −1.
  • Results: The eigenvalue remains zero over a larger interval of q than in the two-body system.This observation is reported for systems with 3-, 4-, and 5-body interactions.
  • Results: In the limit of infinitely many interactions, the eigenvalue is expected to jump at qc from zero to one.The broader zero-eigenvalue interval is presented as evidence supporting this limiting behavior.
  • Threshold analysis: For ER networks with average degree ⟨k⟩= 3.5, the infinite-size optimal threshold qopt is obtained by extrapolation.This threshold is the value shown in Fig. 2a of the main text.

V. CI ALGORITHM · A. Optimization for G(q)̸ = 0 · B. Scalability of the CI algorithm

The CI framework identifies influencers by adaptively removing nodes with the largest collective influence, achieving near-optimal fragmentation efficiently. Its extension to q < qc follows a smooth reinsertion trajectory and provides scalable optimization with stated complexity bounds.

  • V. CI ALGORITHM: The CI algorithm adaptively removes nodes with the highest collective influence, updating neighbor degrees after each removal to achieve near-optimal, fast network destruction.Collective influence corresponds exactly to the EO fitness, CIℓ(i) = b_i^n, and the removal history affects subsequent selections.
  • V. CI ALGORITHM: Using larger ball radii improves performance, with ℓ = 3, 4 already reaching top performance; ℓ should not exceed the original network diameter.For radii larger than the network diameter, CIℓ(i) = 0 and nodes become indistinguishable to the algorithm.
  • A. Optimization for G(q)̸ = 0: The theory computes the optimal threshold qc, the smallest removal fraction yielding G(qc) = 0, together with its corresponding configuration n∗.For q < qc, the giant component remains nonzero and its stability is governed by a more complicated operator dependent on the solution itself.
  • A. Optimization for G(q)̸ = 0: Assuming optimal configurations vary smoothly, the algorithm starts at n∗ for q = qc and reinserts removed nodes one at a time while preserving maximal fragmentation.Each reinserted node is selected by minimizing c(i), the number of clusters it would join, with indexes recalculated after every reinsertion.
  • A. Optimization for G(q)̸ = 0: The reinsertion algorithm runs in O(MN log N), reducible to O(N log N) when M = O(N) by reinserting a finite fraction of nodes at each step.The stated bound combines O(M) index assignment with O(N log N) sorting.
  • B. Scalability of the CI algorithm: For finite ℓ, computing CIℓ(i) for all nodes requires O(N) operations, while sorting the values requires O(N log N).The per-node calculation is O(1) because the ball radius is finite, although its prefactor increases with ℓ.
  • B. Scalability of the CI algorithm: Removing nodes one by one would yield O(N 2 log N), but removing a finite fraction at each step preserves performance and reduces complexity to O(N log N).The prefactor depends on the percentage of nodes removed at each step.

C. Effect of the percentage of fixed nodes during adaptive CI

Removing a finite fraction of nodes at each adaptive step reduces CI’s time complexity while preserving performance for removal rates up to 0.25%. On an ER network with N = 10^5 nodes and average degree ⟨k⟩ = 3.5, this corresponds to 250 nodes per step.

  • Computational efficiency: Removing a finite fraction of nodes per adaptive step reduces time complexity from N^2 log N to N log N.This contrasts finite-fraction removal with one-by-one removal.
  • Experimental setting: For the considered ER network, N = 10^5 nodes and average degree ⟨k⟩ = 3.5 make 0.25% equivalent to 250 nodes per step.The experiment evaluates the percentage of fixed nodes at each adaptive step.
  • Performance: CI performance is practically unaffected by removing up to 0.25% of nodes at each step.The comparison is against one-by-one removal.

VI. COMPARISON WITH OTHER HEURISTIC METHODS · VII. COMPARISON WITH BELIEF PROPAGATION ALGORITHM OF ALTARELLI · ET AL. [14]

The paper compares CI with scalable and non-scalable heuristics, finding limitations in betweenness centrality and equal-graph-partitioning. Against BP, CI performs at least as well while BP becomes computationally prohibitive as p approaches zero and on very large networks.

  • VI. COMPARISON WITH OTHER HEURISTIC METHODS: CI is compared with high-degree, high-degree adaptive, PageRank, k-core, eigenvector, and closeness centralities, plus scalable comparisons on Twitter and Mobile Networks.The large-network comparison includes HDA, HD, PR, and k-core.
  • VI. COMPARISON WITH OTHER HEURISTIC METHODS: Betweenness centrality has O(NM) time complexity and cannot handle the paper’s 10+ million people network.Its computational cost prevents examination of large graphs, and it does not outperform other centralities.
  • VI. COMPARISON WITH OTHER HEURISTIC METHODS: Equal-graph-partitioning can work for homogeneous random regular graphs but loses much performance on heterogeneous scale-free networks.The comparison uses the same network parameters, size, and EGP definition as Ref., reproducing its curve and qc.
  • ET AL. [14]: BP does not apply directly to the paper’s problem because Ref. [14] uses p for initially infected individuals, whereas this work assumes p = 0.The paper models epidemic initiation as typically involving O(1) initiators, while Ref. [14] illustrates results for p = 0.1.
  • ET AL. [14]: For p > 0, Ref. [14] reports that reasonable targeted immunization methods give the same infected-node fraction versus immunized-node fraction.The cited comparison at p = 10% includes BP, greedy, HDA, eigenvector centrality, and simulated annealing, all showing the same performance.
  • ET AL. [14]: As p →0, BP becomes unfeasible because its time complexity diverges as p−3; the paper therefore compares BP in this limit and at p = 0.1.The paper’s own results are illustrated for p = 0, with the closest feasible comparison performed as p approaches zero.
  • ET AL. [14]: BP does not perform better than CI, and its poor scalability makes it prohibitive for the paper’s 10+ million people networks.The BP message-update cost is O(N ki−1), creating practical difficulties for nodes with large degree, including scale-free graphs.

A. BP adaptive · B. Comparison · 1. First comparison

Adaptive BP reconstructs some otherwise inaccessible immunization curves but fails at stronger transmission values, while direct comparison in the CI regime finds BP no better than CI and slightly worse than HDA. The comparison is also constrained by BP’s computational cost, which diverges as p^-3 as p → 0.

  • A. BP adaptive: For w = 0.4, BP’s infected-fraction curve is continuous, whereas larger w values interrupt the curves at a certain q.The interruption arises where the free energy is non-convex and the chemical potential is flat.
  • A. BP adaptive: Adaptive BP effectively reconstructs missing curve segments for some w > 0.4, but cannot fully reconstruct them at still larger w because the algorithm no longer converges.The non-convergence is associated with a phase transition limiting the replica-symmetric cavity method.
  • 1. First comparison: In the closest CI regime, BP is not better than CI and performs slightly worse than HDA.The comparison uses the giant component because f coincides with G when p → 0 and w → 1.
  • 1. First comparison: BP’s running time diverges as p^-3 for p → 0 because numerical discretization requires Nbin ∼ 1/p bins.This prevents direct use of BP at p = 0.
  • 1. First comparison: When BP does not converge, unconverged marginals still allow magnetizations to assign removed nodes and produce the full G(q) curve.Nodes are removed when sign(⟨σ_i⟩) = 1 and retained when sign(⟨σ_i⟩) = −1.
  • 1. First comparison: A 1RSB-based BP analysis obtains slightly larger lower bounds on qc than the RS approach of Altarelli et al.The cited 1RSB treatment improves the analytical lower bound by accounting for one-step replica symmetry breaking.
  • 1. First comparison: The BPD variant improves BP time complexity and can be tested in scale-free networks, but CI shows the best performance in their comparison.BPD is a Belief Propagation Guided Decimation algorithm for the undirected feedback vertex set problem.

2. Second comparison · VIII. A NEW PARADIGM OF INFLUENCE IN SOCIAL MEDIA: TWITTER

The comparison finds little difference between BP and CI when a finite fraction is initially infected, whereas CI performs best when an outbreak begins with a superspreader event. The paper then applies optimal percolation to Twitter, defining influence through giant-cluster reduction and approximating the social network with mention links because follower data are inaccessible and incomplete.

  • 2. Second comparison: When p > 0, any reasonable targeted immunization technique performs equally well because the initially infected population washes out optimization differences.Here p denotes the fraction of the network already infected at the epidemic’s start.
  • 2. Second comparison: When p = 0 and an epidemic starts with a superspreader event O(1), strategies differ substantially, with CI being the best so far.The analytical BP estimate of f(q) provides a lower bound on the actual infected fraction.
  • 2. Second comparison: EO estimates the optimal threshold accurately as an upper bound but cannot provide the optimal configuration for large systems because the problem is NP-hard.BP analytical predictions provide lower bounds, whereas EO provides upper bounds, so the estimates can be close to the optimum.
  • 2. Second comparison: CI is presented as a scalable ~O(N log N) approximation that incorporates the physics of the optimal configuration but cannot guarantee the optimum unless P = NP.The paper argues that practical benchmarking should compare configurations and corresponding giant components on large networks, assessing running time and efficiency.
  • VIII. A NEW PARADIGM OF INFLUENCE IN SOCIAL MEDIA: TWITTER: The Twitter section tests optimal percolation as a new paradigm of influence in real networks, despite the theory’s tree-like structural assumption not necessarily holding.The broader study also considers a phone-call network for epidemic immunization.
  • VIII. A NEW PARADIGM OF INFLUENCE IN SOCIAL MEDIA: TWITTER: In social media, node influence is measured by the drop in giant-cluster size after node removal, linking the measure to spreading news across the network.The theory is tested on approximately 16 million tweets sampled between January 23rd and February 8th, 2011.
  • VIII. A NEW PARADIGM OF INFLUENCE IN SOCIAL MEDIA: TWITTER: Because Twitter’s API cannot provide the full follower network in reasonable time and many follower links are inactive, the study uses a mention network whose links have stronger ties.Mentions are tweets containing @username and commonly involve personal conversations.

IX. HALTING EPIDEMICS: MOBILE PHONE CALL NETWORK

The CI theory provides a near-optimal protocol for selecting people for immunization or quarantine when resources are limited. Applied to a 14,346,653-node Mexican mobile-phone call network, CI outperforms heuristic strategies, using about 500,000 fewer people and vaccines while fragmenting the network more effectively.

  • Immunization and quarantine: The theory offers a near-optimal protocol for selecting people for vaccination or quarantine when immunization doses are limited or expensive.Its purpose is to guide the allocation of scarce immunization resources.
  • Network construction: The Mexican mobile-phone call network contains N = 14, 346, 653 nodes, with average degree ⟨k⟩= 3.53 and maximum degree kmax = 419.Edges represent at least three reciprocal calls between two people during a three-month observation window.
  • Performance: CI fragments the network using about 500, 000 fewer people than the best heuristic strategy, HDA, implying the same number of vaccines saved.The phone-call network’s scale also rules out several quadratic-or-larger heuristic methods and BP.
  • Performance: When CI produces a zero giant component, HDA still yields G ∼0.3, corresponding to a connected network of ∼4 × 10^6 people.Together with the Twitter result, this supports CI’s performance in real networks containing loops despite its locally tree-like theoretical foundation.
Loading 1506.08326v1…