A probability-driven structure-aware algorithm for influence maximization under independent cascade model

Yudong Gong, Sanyang Liu and Yiguang Bai

Physica A: Statistical Mechanics and its Applications, 2021, vol. 583, issue C

Abstract: Influence maximization (IM) is the problem of finding a set of nodes that can achieve the maximal influence spreads into the network, which faces two significant but intractable issues in latest studies: (i) Curse of scales: with the increase of the network scale, traditional methods cost extensive times in guaranteeing accuracy, which re-evaluate influence spread of every node in network, leading to significant computational overhead; (ii) Generalization issue: with more and more studies on various networks and propagation parameters, it is difficult to find a universally appropriate algorithm that performs well in each topology. In this paper, we propose a novel probability-driven structure-aware (PDSA) algorithm, which begins by cutting/updating network according to the edge activation probability parameters of the IC model, and then uses a graph traversal algorithm (e.g., breadth first search algorithm) to evaluate the influence spread scores of each node. Meanwhile, we adopt a kind of centrality-based independent cascade (CIC) model to approximate a more realistic propagation scenario. Through extensive experiments with six real-world/synthetic networks and six CIC/IC models, we demonstrate that PDSA achieves great performance over state-of-the-art algorithms in terms of effect and efficiency. Even facing various complex topologies and propagation parameters, PDSA exhibits excellent robustness in solving IM problems.

Keywords: Influence maximization; Structure adaptation; Independent cascade; Graph traversal (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437121005914
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:583:y:2021:i:c:s0378437121005914

DOI: 10.1016/j.physa.2021.126318

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().