|
|
Influence Maximization Algorithm Based on Overlapping Community |
Liqing Qiu( ),Wei Jia,Xin Fan |
College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China |
|
|
Abstract [Objective] This paper proposes a new algorithm for influence maximization based on overlapping community, called IM-BOC algorithm, aiming to the low efficiency of greedy algorithm. [Methods] This method selects candidate seed set by combing propagation degree and k-core firstly, then it utilizes CELF algorithm to ensure the optimal seed set, which can improve both efficiency and accuracy. [Results] The experimental results show that running time of our algorithm can improve about 89% when facing Amazon dataset. [Limitations] Our IM-BOC algorithm allocates the number of candidate seeds only according to the number of community nodes, which has insufficient theoretical evidence. [Conclusions] IM-BOC algorithm is applicable to large scale networks under the premise of ensuring the influence spread.
|
Received: 10 December 2018
Published: 06 September 2019
|
|
Corresponding Authors:
Liqing Qiu
E-mail: liqingqiu2005@126.com
|
[1] |
Domingos P, Richardson M. Mining the Network Value of Customers [C]// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2001: 57-66.
|
[2] |
Kemple D, Kleinberg J M, Tardos É. Maximizing the Spread of Influence Through a Social Network [C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003: 137-146.
|
[3] |
Chen W, Wang Y, Yang S. Efficient Influence Maximization in Social Networks [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009: 199-208.
|
[4] |
Leskovec J, Krause A, Guestrin C, et al. Cost-effective Outbreak Detection in Networks [C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007: 420-429.
|
[5] |
Galstyan A, Musoyan V, Cohen P . Maximizing Influence Propagation in Network with Community Structure[J]. Physical Review E, 2009,79(5):056102.
|
[6] |
郭进时, 汤红波, 吴凯 , 等. 基于社区结构的影响力最大化算法[J]. 计算机应用, 2013,33(9):2436-2439, 2459.
doi: 10.11772/j.issn.1001-9081.2013.09.2436
|
[6] |
( Guo Jinshi, Tang Hongbo, Wu Kai , et al. Influence Optimization Model Based on Community Structure[J]. Journal of Computer Applications, 2013,33(9):2436-2439, 2459.)
doi: 10.11772/j.issn.1001-9081.2013.09.2436
|
[7] |
王双, 李斌, 刘学军 , 等. 基于社区划分的影响力最大化算法[J]. 计算机工程与应用, 2016,52(19):42-47.
|
[7] |
( Wang Shuang, Li Bin, Liu Xuejun , et al. Division of Community- Based Influence Maximization Algorithm[J]. Computer Engineering and Applications, 2016,52(19):42-47.)
|
[8] |
吴海林 . 基于社区划分和改进PageRank的影响力最大化算法[J]. 移动通信, 2017,41(10):83-86.
|
[8] |
( Wu Hailin . An Influence Maximization Algorithm Based on Community Partition and Improved PageRank[J]. Mobile Communications, 2017,41(10):83-86.)
|
[9] |
张成建 . 基于重叠社区结构的社交网络最大影响力研究[D]. 秦皇岛: 燕山大学, 2015.
|
[9] |
( Zhang Chengjian . Analysis of the Social Network’s Biggest Influence Based on the Overlapping Community Structure[D]. Qinhuangdao: Yanshan University, 2015.)
|
[10] |
Shang J, Zhou S, Li X , et al. CoFIM: A Community-Based Framework for Influence Maximization on Large-Scale Networks[J]. Knowledge-Based Systems, 2017,117:88-100.
|
[11] |
胡庆成, 张勇, 邢春晓 . 基于有重叠社区划分的社会网络影响最大化方法研究[J]. 计算机科学, 2018,45(6):38-41.
|
[11] |
( Hu Qingcheng, Zhang Yong, Xing Chunxiao . K-clique Heuristic Algorithm for Influence Maximization in Social Network[J]. Computer Science, 2018,45(6):38-41.)
|
[12] |
Xie J, Szymanski B K, Liu X. SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process [C]// Proceedings of the 11th IEEE International Conference on Data Mining Workshops. IEEE, 2012: 344-349.
|
[13] |
王李冬, 张赟 . 大规模社交网络重叠社区发现技术综述[J]. 杭州师范大学学报: 自然科学版, 2016,15(3):331-336.
|
[13] |
( Wang Lidong, Zhang Yun . Overlapping Community Detection in Large-Scale Social Networks[J]. Journal of Hangzhou Normal University: Nature Science Edition, 2016,15(3):331-336.)
|
[14] |
Chen W, Yuan Y, Zhang L. Scalable Influence Maximization in Social Networks Under the Linear Threshold Model [C]// Proceedings of the 2010 IEEE International Conference on Data Mining. IEEE, 2010: 88-97.
|
[15] |
Kitsak M, Gallos L K, Havlin S , et al. Identification of Influential Spreaders in Complex Networks[J]. Nature Physics, 2010,6(11):888-893.
|
[16] |
曹玖新, 董丹, 徐顺 , 等. 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015,38(2):238-248.
|
[16] |
( Cao Jiuxin, Dong Dan, Xu Shun , et al. A k-Core Based Algorithm for Influence Maximization in Social Networks[J]. Chinese Journal of Computers, 2015,38(2):238-248.)
|
[17] |
刘院英, 郭景峰, 蒋建伟 . 求解影响最大化问题的一种混合算法[J]. 科学技术与工程, 2018,18(7):179-184.
|
[17] |
Liu Yuanying, Guo Jingfeng, Jiang Jianwei. A Hybrid Algorithm for Influence Maximization[J]. Science Technology & Engineering, 2018,18(7):179-184.
|
[18] |
王俊, 余伟, 胡亚慧 , 等. 基于3-layer中心度的社交网络影响力最大化算法[J]. 计算机科学, 2014,41(1):59-63.
|
[18] |
( Wang Jun, Yu Wei, Hu Yahui , et al. Heuristic Algorithm Based on 3-layer Centrality for Influence Maximization in Social Networks[J]. Computer Science, 2014,41(1):59-63.)
|
[19] |
李阅志, 祝园园, 钟鸣 . 基于k-核过滤的社交网络影响最大化算法[J]. 计算机应用, 2018,38(2):464-470.
|
[19] |
( Li Yuezhi, Zhu Yuanyuan, Zhong Ming . K-Core Filtered Influence Maximization Algorithms in Social Networks[J]. Journal of Computer Applications, 2018,38(2):464-470.)
|
[20] |
Jung K, Heo W, Chen W. IRIE: Scalable and Robust Influence Maximization in Social Networks [C]// Proceedings of the 12th IEEE International Conference on Data Mining. IEEE, 2012: 918-923.
|
[21] |
Tang J, Tang X, Yuan J . An Efficient and Effective Hop-Based Approach for Influence Maximization in Social Networks[J]. Social Network Analysis & Mining, 2018,8(1):10.
|
[22] |
Raghavan U N, Albert R, Kumara S . Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J]. Physical Review E, 2007,76(3):036106.
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|