SA-min: An Efficient Algorithm for Minimizing the Spread of Influence in a Social Network
Yong Liu, Shengnan Xie, Wei Zhang, QianqianRen
Journal of Information Technology Review, Vol. 9, No. 2, 2018.
DOI: https://doi.org/10.6025/jitr/2018/9/2/48-59
Link: http://www.dline.info/jitr/fulltext/v9n2/jitrv9n2_2.pdf
Abstract:
Minimizing the spread of influence, a dual problem to influence maximization, is to find top-k links from a social
network such that by blocking them the spread of influence is minimized. Kimura etal. [4] first proposed the problem and
presented a greedy algorithm in order to solve this problem. But the greedy algorithm is too expensive and cannot scale to
large scale social networks. In this paper, we design an efficient algorithm called SA-min based on Simulated Annealing (SA)
for the problem. This is the first SA-based algorithm for the problem. Experimental results on real networks show that our
algorithm can outperform the greedy algorithm by more than an order of magnitude while achieving comparable spread
minimization.