On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks
Influence maximization problem aims to identify the most influential individuals so as to help in developing effective viral marketing strategies over social networks. Previous studies mainly focus on designing efficient algorithms or heuristics on a static social network. As a matter of fact, real-...
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2017/5049836 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832561318002950144 |
|---|---|
| author | Xiaodong Liu Xiangke Liao Shanshan Li Si Zheng Bin Lin Jingying Zhang Lisong Shao Chenlin Huang Liquan Xiao |
| author_facet | Xiaodong Liu Xiangke Liao Shanshan Li Si Zheng Bin Lin Jingying Zhang Lisong Shao Chenlin Huang Liquan Xiao |
| author_sort | Xiaodong Liu |
| collection | DOAJ |
| description | Influence maximization problem aims to identify the most influential individuals so as to help in developing effective viral marketing strategies over social networks. Previous studies mainly focus on designing efficient algorithms or heuristics on a static social network. As a matter of fact, real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time. In this paper, we propose an incremental approach, IncInf, which can efficiently locate the top-K influential individuals in evolving social networks based on previous information instead of calculation from scratch. In particular, IncInf quantitatively analyzes the influence spread changes of nodes by localizing the impact of topology evolution to only local regions, and a pruning strategy is further proposed to narrow the search space into nodes experiencing major increases or with high degrees. To evaluate the efficiency and effectiveness, we carried out extensive experiments on real-world dynamic social networks: Facebook, NetHEPT, and Flickr. Experimental results demonstrate that, compared with the state-of-the-art static algorithm, IncInf achieves remarkable speedup in execution time while maintaining matching performance in terms of influence spread. |
| format | Article |
| id | doaj-art-cc48d38d15cf40a7ade49031d382ae61 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-cc48d38d15cf40a7ade49031d382ae612025-02-03T01:25:28ZengWileyComplexity1076-27871099-05262017-01-01201710.1155/2017/50498365049836On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social NetworksXiaodong Liu0Xiangke Liao1Shanshan Li2Si Zheng3Bin Lin4Jingying Zhang5Lisong Shao6Chenlin Huang7Liquan Xiao8School of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaSchool of Computer, National University of Defense Technology, Changsha 410073, ChinaInfluence maximization problem aims to identify the most influential individuals so as to help in developing effective viral marketing strategies over social networks. Previous studies mainly focus on designing efficient algorithms or heuristics on a static social network. As a matter of fact, real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time. In this paper, we propose an incremental approach, IncInf, which can efficiently locate the top-K influential individuals in evolving social networks based on previous information instead of calculation from scratch. In particular, IncInf quantitatively analyzes the influence spread changes of nodes by localizing the impact of topology evolution to only local regions, and a pruning strategy is further proposed to narrow the search space into nodes experiencing major increases or with high degrees. To evaluate the efficiency and effectiveness, we carried out extensive experiments on real-world dynamic social networks: Facebook, NetHEPT, and Flickr. Experimental results demonstrate that, compared with the state-of-the-art static algorithm, IncInf achieves remarkable speedup in execution time while maintaining matching performance in terms of influence spread.http://dx.doi.org/10.1155/2017/5049836 |
| spellingShingle | Xiaodong Liu Xiangke Liao Shanshan Li Si Zheng Bin Lin Jingying Zhang Lisong Shao Chenlin Huang Liquan Xiao On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks Complexity |
| title | On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks |
| title_full | On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks |
| title_fullStr | On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks |
| title_full_unstemmed | On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks |
| title_short | On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks |
| title_sort | on the shoulders of giants incremental influence maximization in evolving social networks |
| url | http://dx.doi.org/10.1155/2017/5049836 |
| work_keys_str_mv | AT xiaodongliu ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT xiangkeliao ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT shanshanli ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT sizheng ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT binlin ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT jingyingzhang ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT lisongshao ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT chenlinhuang ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks AT liquanxiao ontheshouldersofgiantsincrementalinfluencemaximizationinevolvingsocialnetworks |