Efficient and effective influence maximization in social networks: A hybrid-approach
- Title
- Efficient and effective influence maximization in social networks: A hybrid-approach
- Author
- 김상욱
- Keywords
- Social network; Information diffusion; Influence maximization; Monte-Carlo simulations
- Issue Date
- 2018-10
- Publisher
- ELSEVIER SCIENCE INC
- Citation
- INFORMATION SCIENCES, v. 465, page. 144-161
- Abstract
- Influence Maximization (IM) is the problem of finding a seed set composed of k nodes that maximize their influence spread over a social network. Kempe et al. showed the problem to be NP-hard and proposed a greedy algorithm (referred to as SimpleGreedy) that guarantees 63% influence spread of its optimal solution. However, SimpleGreedy has two performance issues: at a micro level, it estimates the influence spread of a single node by running Monte-Carlo (MC) simulations that are fairly expensive; at a macro level, after selecting one seed at each step, it re-evaluates the influence spread of every node in a social network, leading to significant computational overhead. In this paper, we propose Hybrid-IM that addresses the two issues in both micro and macro levels by combining PB-IM (Path Based Influence Maximization) and CB-IM (Community Based Influence Maximization). Furthermore, we identify two technical issues that could improve the performance of Hybrid-IM more and propose two strategies to address those issues. Through extensive experiments with four real-world datasets, we show that Hybrid-IM achieves great improvement (up to 43 times) in performance over state-of-the-art methods and finds the seed set that provides the influence spread very close to that of the state-of-the-art methods. (C) 2018 Elsevier Inc. All rights reserved.
- URI
- https://www.sciencedirect.com/science/article/pii/S0020025518305176?via%3Dihubhttps://repository.hanyang.ac.kr/handle/20.500.11754/120414
- ISSN
- 0020-0255; 1872-6291
- DOI
- 10.1016/j.ins.2018.07.003
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML