Influence Maximization Algorithm Based on Reverse Reachable Set

Gengxin Sun and Chih-Cheng Chen

Mathematical Problems in Engineering, 2021, vol. 2021, 1-12

Abstract:

Most of the existing influence maximization algorithms are not suitable for large-scale social networks due to their high time complexity or limited influence propagation range. Therefore, a D-RIS (dynamic-reverse reachable set) influence maximization algorithm is proposed based on the independent cascade model and combined with the reverse reachable set sampling. Under the premise that the influence propagation function satisfies monotonicity and submodularity, the D-RIS algorithm uses an automatic debugging method to determine the critical value of the number of reverse reachable sets, which not only obtains a better influence propagation range but also greatly reduces the time complexity. The experimental results on the two real datasets of Slashdot and Epinions show that D-RIS algorithm is close to the CELF (cost-effective lazy-forward) algorithm and higher than RIS algorithm, HighDegree algorithm, LIR algorithm, and pBmH (population-based metaheuristics) algorithm in influence propagation range. At the same time, it is significantly better than the CELF algorithm and RIS algorithm in running time, which indicates that D-RIS algorithm is more suitable for large-scale social network.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2021/5535843.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2021/5535843.xml (text/xml)

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:hin:jnlmpe:5535843

DOI: 10.1155/2021/5535843

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().