  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.
