RCELF: A residual-based approach for Influence Maximization Problem

Zhang，Shiqi; Zeng，Xinxun; Tang，Bo

2021-12-01

10.1016/j.is.2021.101828

INFORMATION SYSTEMS   影响因子和分区

0306-4379

Influence Maximization Problem (IMP) is selecting a seed set of nodes in the social network to spread the influence as widely as possible. It has many applications in multiple domains, e.g., viral marketing is frequently used for new products or activities advertisement. While it is a classic and well-studied problem in computer science, unfortunately, all those proposed techniques are compromising among time efficiency, memory consumption, and result quality. In this paper, we conduct comprehensive experimental studies on the state-of-the-art IMP approximate approaches to reveal the underlying trade-off strategies. Interestingly, we find that even the state-of-the-art approaches are impractical when the propagation probability of the network have been taken into consideration. With the findings of existing approaches, we propose a novel residual-based approach (i.e., RCELF) for IMP, which (i) overcomes the deficiencies of existing approximate approaches, and (ii) provides theoretical guaranteed results with high efficiency in both time- and space-perspectives. We demonstrate the superiority of our proposal by extensive experimental evaluation on real datasets.

Applications Database Influence maximization Social network

SCI ; EI

英语

第一 ; 通讯

WOS:000684935000004

20212610570538

Efficiency

Production Engineering:913.1 ; Social Sciences:971

COMPUTER SCIENCE

2-s2.0-85108738195

Scopus

Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China

Zhang，Shiqi,Zeng，Xinxun,Tang，Bo. RCELF: A residual-based approach for Influence Maximization Problem[J]. INFORMATION SYSTEMS,2021,102.

Zhang，Shiqi,Zeng，Xinxun,&Tang，Bo.(2021).RCELF: A residual-based approach for Influence Maximization Problem.INFORMATION SYSTEMS,102.

Zhang，Shiqi,et al."RCELF: A residual-based approach for Influence Maximization Problem".INFORMATION SYSTEMS 102(2021).