[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.
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 ( 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. ( 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. ( Wu Hailin . An Influence Maximization Algorithm Based on Community Partition and Improved PageRank[J]. Mobile Communications, 2017,41(10):83-86.)
[9]
张成建 . 基于重叠社区结构的社交网络最大影响力研究[D]. 秦皇岛: 燕山大学, 2015. ( 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. ( 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. ( 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. ( 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. 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. ( 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. ( 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.
