Please wait a minute...
Data Analysis and Knowledge Discovery  2019, Vol. 3 Issue (7): 94-102    DOI: 10.11925/infotech.2096-3467.2018.1389
Current Issue | Archive | Adv Search |
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
Download: PDF (767 KB)   HTML ( 12 ) 
Export: BibTeX | EndNote (RIS)      
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.
Key words： Social Network      Overlapping Community      Influence Maximization     
Received: 10 December 2018      Published: 06 September 2019
ZTFLH:  TP301.6 G35  
Corresponding Authors: Liqing Qiu     E-mail: liqingqiu2005@126.com
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Liqing Qiu
Wei Jia
Xin Fan

Cite this article:

Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community. Data Analysis and Knowledge Discovery, 2019, 3(7): 94-102.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2018.1389     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2019/V3/I7/94

数据集 Oregon Ca_AstroPh Email_Enron Amazon
节点 11 011 18 772 36 692 262 111
边 22 678 198 110 183 831 1 234 877
最大度 2 370 427 1 367 366
平均度 4.120 9.377 7.384 4.505
平均聚类系数 0.297 0.631 0.497 0.420
[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.
[1] Wang Xiwei,Jia Ruonan,Wei Yanan,Zhang Liu. Clustering User Groups of Public Opinion Events from Multi-dimensional Social Network[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[2] Ma Yingxue,Zhao Jichang. Patterns and Evolution of Public Opinion on Weibo During Natural Disasters： Case Study of Typhoons and Rainstorms[J]. 数据分析与知识发现, 2021, 5(6): 66-79.
[3] Gao Yilin,Min Chao. Comparing Technology Diffusion Structure of China and the U.S. to Countries Along the Belt and Road[J]. 数据分析与知识发现, 2021, 5(6): 80-92.
[4] Li Yueyan,Wang Hao,Deng Sanhong,Wang Wei. Research Trends of Information Retrieval——Case Study of SIGIR Conference Papers[J]. 数据分析与知识发现, 2021, 5(4): 13-24.
[5] Xu Yabin, Sun Qiutian. Identifying Leaders and Dissemination Paths of Public Opinion[J]. 数据分析与知识发现, 2021, 5(2): 32-42.
[6] Peng Guan,Yuefen Wang. Advances in Patent Network[J]. 数据分析与知识发现, 2020, 4(1): 26-39.
[7] Yan Wen,Lijian Ma,Qingtian Zeng,Wenyan Guo. POI Recommendation Based on Geographic and Social Relationship Preferences[J]. 数据分析与知识发现, 2019, 3(8): 30-39.
[8] Xiaolan Wu,Chengzhi Zhang. Analysis of Knowledge Flow Based on Academic Social Networks:
A Case Study of ScienceNet.cn[J]. 数据分析与知识发现, 2019, 3(4): 107-116.
[9] Xinrui Wang,Yue He. Predicting Stock Market Fluctuations with Social Media Behaviors: Case Study of Sina Finance Blog[J]. 数据分析与知识发现, 2019, 3(11): 108-119.
[10] Wu Jiehua,Shen Jing,Zhou Bei. Classifying Multilayer Social Network Links Based on Transfer Component Analysis[J]. 数据分析与知识发现, 2018, 2(9): 88-99.
[11] Ye Guanghui,Hu Jinglan,Xu Jian,Xia Lixin. Analyzing Growth Trends and Attachment Mode of Social Blog Tags[J]. 数据分析与知识发现, 2018, 2(6): 70-78.
[12] Guo Bo,Zhao Junrui,Sun Yu. Analyzing Characteristics and Dynamics of User Behaviors in Social Q&A Community: Case Study of Zhihu.com[J]. 数据分析与知识发现, 2018, 2(4): 48-58.
[13] Wang Feifei,Zhang Shengtai. Analyzing Information Behaviors of Mobile Social Network Users[J]. 数据分析与知识发现, 2018, 2(4): 99-109.
[14] Zhang Ling,Luo Manman,Zhu Lijun. Analyzing Information Dissemination on Social Networks[J]. 数据分析与知识发现, 2018, 2(2): 46-57.
[15] Chen Fen,Fu Xi,He Yuan,Xue Chunxiang. Identifying Weibo Opinion Leaders with Social Network Analysis and Influence Diffusion Model[J]. 数据分析与知识发现, 2018, 2(12): 60-67.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626，82624938   E-mail:jishu@mail.las.ac.cn