Efficient and effective influence maximization in large-scale social networks via two frameworks

Jinliang Yuan, Ruisheng Zhang, Jianxin Tang, Rongjing Hu, Zepeng Wang and Huan Li

Physica A: Statistical Mechanics and its Applications, 2019, vol. 526, issue C

Abstract: Influence maximization is to find a small subset of nodes in a network so that the scope of influence spread can be maximized, and it is a significant optimization problem in rumor control and viral marketing. Although there have been a lot of research works for this problem, it is still difficult to design algorithms to meet three requirements simultaneously, i.e., fast computation, low memory consumption and guaranteed accuracy when scaling to large-scale networks. In this paper, we research the efficient and effective influence maximization algorithms from two directions. One is to design an effective similarity-based framework for enhancing the influence spread of the centrality-based heuristic algorithms, and another is to improve greedy algorithm for efficiency by a two-stage framework. The extensive experiments in undirected and directed networks all demonstrate that two heuristic algorithms using the proposed framework acquire comparable results to the state of the art and are two orders of magnitude faster than D-SSA in a million of network. Simultaneously, the improved greedy algorithm is 2 to 12 times faster than CELF with the almost same influence spread.

Keywords: Social networks; Influence maximization; Heuristic algorithms; Greedy algorithms (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119305680
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:526:y:2019:i:c:s0378437119305680

DOI: 10.1016/j.physa.2019.04.202

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 ().