Source-linked AI summary
Collective Influence Algorithm to find influencers via optimal percolation in massively large social media
Flaviano Morone, Byungjoon Min, Lin Bo, Romain Mari, Hernan A. Makse
TL;DR
The paper addresses how to identify minimal influencer sets efficiently in large networks. It implements CI with a max-heap, extends it through global message passing, and develops a belief-propagation immunization variant. CI achieves O(N log N), while CIP and CIBP attain near-optimal results but require quadratic-time computation that limits them to small networks.
Problem
Influence maximization seeks minimal influential or immunized node sets, while the optimization problem is NP-hard.
Method
The paper uses finite-radius CI with max-heap processing, extends it to global CI propagation, and introduces a belief-propagation-based collective immunization algorithm.
Results
CI runs in O(N log N), while CIP reaches the exact optimal percolation threshold for random cubic graphs and CIBP matches CIP performance.
Takeaways & Limitations
Finite-radius CI provides a scalable approach, whereas the slightly better CIP and CIBP performance comes with quadratic running time and applies only to small networks.
Abstract
from arXiv · showhide
We elaborate on a linear time implementation of the Collective Influence (CI) algorithm introduced by Morone, Makse, Nature 524, 65 (2015) to find the minimal set of influencers in a network via optimal percolation. We show that the computational complexity of CI is O(N log N) when removing nodes one-by-one, with N the number of nodes. This is made possible by using an appropriate data structure to process the CI values, and by the finite radius l of the CI sphere. Furthermore, we introduce a simple extension of CI when l is infinite, the CI propagation (CI_P) algorithm, that considers the global optimization of influence via message passing in the whole network and identifies a slightly smaller fraction of influencers than CI. Remarkably, CI_P is able to reproduce the exact analytical optimal percolation threshold obtained by Bau, Wormald, Random Struct. Alg. 21, 397 (2002) for cubic random regular graphs, leaving little improvement left for random graphs. We also introduce the Collective Immunization Belief Propagation algorithm (CI_BP), a belief-propagation (BP) variant of CI based on optimal immunization, which has the same performance as CI_P. However, this small augmented performance of the order of 1-2 % in the low influencers tail comes at the expense of increasing the computational complexity from O(N log N) to O(N^2 log N), rendering both, CI_P and CI_BP, prohibitive for finding influencers in modern-day big-data. The same nonlinear running time drawback pertains to a recently introduced BP-decimation (BPD) algorithm by Mugisha, Zhou, arXiv:1603.05781. For instance, we show that for big-data social networks of typically 200 million users (eg, active Twitter users sending 500 million tweets per day), CI finds the influencers in less than 3 hours running on a single CPU, while the BP algorithms (CI_P, CI_BP and BDP) would take more than 3,000 years to accomplish the same task.
I. IMPLEMENTING CI IN LINEAR TIME.
The CI algorithm removes nodes adaptively by their current Collective Influence value. A max-heap avoids repeated full sorting, while finite-radius updates limit recomputation to nearby nodes.
- CI removes the node with the highest current CI_l(i) value until the giant component is destroyed.
- A straightforward implementation costs O(N^2 log N) because it recomputes and sorts CI values at every removal.
- A max-heap stores the CI values so that the largest value remains at the root without maintaining a fully sorted list.
- The implementation computes initial CI values, builds the heap, repeatedly removes and heapifies the root, then updates affected subtrees.
- Each removal changes CI values only for nodes within distance ℓ+1 of the removed node.
A. Running time
The optimized CI implementation achieves O(N log N) running time and uses an eigenvalue condition to stop near the percolation threshold without separately computing the giant component.
- O(N log N) is achieved because initialization costs O(N), while removal and update steps cost at most O(log N) across O(N) iterations.
- At N = 2 × 10^8 nodes, simulations confirm nearly linear scaling of the CI running time.
- For 0.2 billion-node ER graphs, running time is less than 2.5 hours with ℓ=2 and 5 hours with ℓ=3.
- The algorithm can stop when λ(ℓ; q) = 1, an approximate condition that works well for locating destruction of the giant component.
B. Reinsertion
The reinsertion refinement reconstructs the network from the percolation point by adding removed nodes back according to how many clusters they join.
- Reinsertion starts at the percolation point, where the network is fragmented into many clusters.
- Figure 5 compares the giant component, second-largest cluster, and λ(ℓ; q) against the number of removed nodes.
- At each step, the algorithm reinserts the removed node that joins the smallest number of clusters.
- The selection criterion minimizes the number of joined clusters rather than their sizes.
II. CI PROPAGATION
CIP extends CI from a finite local sphere to global message passing while retaining the objective of minimizing the largest eigenvalue of the non-backtracking matrix. It combines incoming and outgoing influence information, improves results over CI, but has quadratic-logarithmic running time.
- CIP extends CI to incorporate global information beyond the local CI sphere and is obtained asymptotically as the radius ℓ approaches infinity.
- CIP uses left and right non-backtracking eigenvector messages to measure information received by and propagated from each node.The combined quantity captures both IN-fluence and OUT-fluence.
- CIP iterates message equations to convergence, computes node scores, removes the highest-scoring node, and repeats until λmax = 1.
- CIP produces better results than CI and reaches the analytically known optimal fraction qc = 1/4 in random cubic graphs.Figure 7 compares giant components and the eigenvalue against the exact threshold at q = 0.25.
- O(N^2 log N) running time prevents CIP from scaling to very large networks, despite its parameter-free design and quasi-optimal small-system performance.The paper does not develop CIP further because additional parameters would not reduce its quadratic running time.
III. COLLECTIVE IMMUNIZATION
The paper formulates optimal percolation through SIR immunization and belief propagation, using message passing to identify immunized nodes that minimize outbreak size. The resulting CIBP algorithm matches CIP performance but remains unsuitable for large networks because it is quadratic.
- SIR and message passing: SIR dynamics represent immunized nodes as removed sites and use message passing to compute long-time susceptibility probabilities.The framework considers initially infected nodes, transmission probability, and locally tree-like networks.
- CIBP algorithm: CIBP combines SIR spreading dynamics with belief-propagation updating rules to solve the optimal immunization problem.The algorithm iteratively updates cavity messages and local fields until convergence, with reinforcement used when message equations fail to converge.
- Optimization objective: The immunization objective is to find the minimal set of nodes that minimizes the outbreak size F = P_i n_i (1 −ν_i).Node variables encode whether each node is immunized or remains present.
- Performance and scalability: CIBP has the same performance as CIP on random cubic graphs, reproducing the exact result for small systems while improving over CI.Its quadratic running time restricts application to small networks.
- Performance and scalability: O(N^2 log N) complexity makes CIBP unsuitable for large systems, like CIP and BPD.The figure compares running times for CI, CIP, and BPD as network size increases.
IV. CONCLUSIONS
The paper develops a nearly linear-time implementation of CI and introduces global and belief-propagation extensions. The extensions improve solutions slightly or match optimal results, but their quadratic complexity limits scalability.
- CI implementation: O(N log N) CI is achieved for one-by-one node removal by exploiting the finite CI-sphere radius and a max-heap.The heap avoids fully sorting CI values and saves a factor O(N).
- Algorithmic extensions: CIP incorporates global rearrangement of CI values after each removal and corresponds to the ℓ→∞ limit of CI.CIBP combines SIR dynamics with message-passing updates for optimal percolation.