Perturb and Combine to Identify Influential Spreaders in Real-World
  Networks
  Some of the most effective influential spreader detection algorithms are
unstable to small perturbations of the network structure. Inspired by bagging
in Machine Learning, we propose the first Perturb and Combine (P&C) procedure
for networks. It (1) creates many perturbed versions of a given graph, (2)
applies a node scoring function separately to each graph, and (3) combines the
results. Experiments conducted on real-world networks of various sizes with the
k-core, generalized k-core, and PageRank algorithms reveal that P&C brings
substantial improvements. Moreover, this performance boost can be obtained at
almost no extra cost through parallelization. Finally, a bias-variance analysis
suggests that P&C works mainly by reducing bias, and that therefore, it should
be capable of improving the performance of all vertex scoring functions,
including stable ones.
