[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.
( 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
( 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.)
( 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.
( 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.
( 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.
( 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.)
( 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.)
( 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.