Influence maximization/optimization in complex networks through optimal percolation

Keywords: Social dynamics, Networks, Percolation

Influence maximization in complex networks through optimal percolation

Annotated paper

I think this article will be of interest to people investigating social or other networks over which something is transmitted over the edges (whether these are infections, messages, opinions...). These arise in many problems in science and engineering, especially those involving complex social networks. In these networks one can often assign importance to nodes by seeing how much does their removal disrupt the potential spread of the unit being transmitted across the network.

In particular, the optimal influence problem tries to maximize the influence on the network by affecting the least number of nodes. This article presents a novel algorithm that can find very good approximate solutions to this problem, which is generally NP-hard. They do this by first expressing the problem in terms of a percolation process, so that maximum influence corresponds to making the giant connected component disappear with the least number of nodes removed. Although for small networks this can be tackled using methods from statistical mechanics, an adaptive algorithm is more effective for large networks. They demonstrate its effectiveness, as well as its superiority against other heuristic algorithms, in both synthetic and real networks.

Although I think the article does a good job at summarizing the results in the 4 pages of the letter, I think some more explanation on the connection of the optimal influence problem and their mathematical formulation would be useful to aid the reader's understanding (leaving the SI only for non-crucial details). For instance, I think that it should be mentioned that the stability of the $G=0$ solution, under locally tree like assumption, is what determines whether the GCC is present or not, for large networks. Optimal influence chooses the minimum number of nodes that make the $G=0$ solution. Similarly, I think the vector $\mathbf{w}_0$ is introduced without explaining what it represents (a perturbation to the order parameter vector $v_{i\rightarrow j}$.

'Smaller is smarter' in superspreading of influence in social network

Containing Epidemic Outbreaks by Message-Passing Techniques