Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks

Golshan Golnari, Amir Asiaee T., Arindam Banerjee, Zhi-Li Zhang
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:930-939, 2015.

Abstract

Influence maximization in social networks has been studied extensively in computer science community for the last decade. However, almost all of the efforts have been focused on the progressive influence models, such as independent cascade (IC) and Linear threshold (LT) models, which cannot capture the reversibility of choices. In this paper, we present the Heat Conduction (HC) model which is a non-progressive influence model and has favorable real-world interpretations. Moreover, we show that HC unifies, generalizes, and extends the existing non-progressive models, such as the Voter model [1] and nonprogressive LT [2]. We then prove that selecting the optimal seed set of influential nodes is NP-hard for HC but by establishing the submodularity of influence spread, we can tackle the influence maximization problem with a scalable and provably near-optimal greedy algorithm. To the best of our knowledge, we are the first to present a scalable solution for influence maximization under non-progressive LT model, as a special case of HC model. In sharp contrast to the other greedy influence maximization methods, our fast and efficient C2GREEDY algorithm benefits from two analytically computable steps: closed-form computation for finding the influence spread as well as the greedy seed selection. Through extensive experiments on several and large real and synthetic networks, we show that C2GREEDY outperforms the state-of-the-art methods, under HC model, in terms of both influence spread and scalability.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-golnari15a, title = {Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks}, author = {Golnari, Golshan and T., Amir Asiaee and Banerjee, Arindam and Zhang, Zhi-Li}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {930--939}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/golnari15a/golnari15a.pdf}, url = {https://proceedings.mlr.press/r13/golnari15a.html}, abstract = {Influence maximization in social networks has been studied extensively in computer science community for the last decade. However, almost all of the efforts have been focused on the progressive influence models, such as independent cascade (IC) and Linear threshold (LT) models, which cannot capture the reversibility of choices. In this paper, we present the Heat Conduction (HC) model which is a non-progressive influence model and has favorable real-world interpretations. Moreover, we show that HC unifies, generalizes, and extends the existing non-progressive models, such as the Voter model [1] and nonprogressive LT [2]. We then prove that selecting the optimal seed set of influential nodes is NP-hard for HC but by establishing the submodularity of influence spread, we can tackle the influence maximization problem with a scalable and provably near-optimal greedy algorithm. To the best of our knowledge, we are the first to present a scalable solution for influence maximization under non-progressive LT model, as a special case of HC model. In sharp contrast to the other greedy influence maximization methods, our fast and efficient C2GREEDY algorithm benefits from two analytically computable steps: closed-form computation for finding the influence spread as well as the greedy seed selection. Through extensive experiments on several and large real and synthetic networks, we show that C2GREEDY outperforms the state-of-the-art methods, under HC model, in terms of both influence spread and scalability.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks %A Golshan Golnari %A Amir Asiaee T. %A Arindam Banerjee %A Zhi-Li Zhang %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-golnari15a %I PMLR %P 930--939 %U https://proceedings.mlr.press/r13/golnari15a.html %V R13 %X Influence maximization in social networks has been studied extensively in computer science community for the last decade. However, almost all of the efforts have been focused on the progressive influence models, such as independent cascade (IC) and Linear threshold (LT) models, which cannot capture the reversibility of choices. In this paper, we present the Heat Conduction (HC) model which is a non-progressive influence model and has favorable real-world interpretations. Moreover, we show that HC unifies, generalizes, and extends the existing non-progressive models, such as the Voter model [1] and nonprogressive LT [2]. We then prove that selecting the optimal seed set of influential nodes is NP-hard for HC but by establishing the submodularity of influence spread, we can tackle the influence maximization problem with a scalable and provably near-optimal greedy algorithm. To the best of our knowledge, we are the first to present a scalable solution for influence maximization under non-progressive LT model, as a special case of HC model. In sharp contrast to the other greedy influence maximization methods, our fast and efficient C2GREEDY algorithm benefits from two analytically computable steps: closed-form computation for finding the influence spread as well as the greedy seed selection. Through extensive experiments on several and large real and synthetic networks, we show that C2GREEDY outperforms the state-of-the-art methods, under HC model, in terms of both influence spread and scalability. %Z Reissued by PMLR on 04 October 2026.
APA
Golnari, G., T., A.A., Banerjee, A. & Zhang, Z.. (2015). Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:930-939 Available from https://proceedings.mlr.press/r13/golnari15a.html. Reissued by PMLR on 04 October 2026.

Related Material