Please wait a minute...
Advanced Search
数据分析与知识发现  2019, Vol. 3 Issue (7): 94-102    DOI: 10.11925/infotech.2096-3467.2018.1389
  研究论文 本期目录 | 过刊浏览 | 高级检索 |
基于重叠社区的影响力最大化算法 *
仇丽青(),贾玮,范鑫
山东科技大学计算机科学与工程学院 青岛 266590
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
全文: PDF(767 KB)   HTML ( 9
输出: BibTeX | EndNote (RIS)      
摘要 

目的】针对影响力最大化问题中贪心算法时间效率低的局限, 提出基于重叠社区的影响力最大化算法。【方法】基于重叠社区, 综合传播度最大的节点和重叠节点选出候选种子集, 并采用CELF算法确定最优种子集, 从而提高影响范围。【结果】实验数据表明, 在亚马逊数据集上IM-BOC算法运行时间最大幅度能够提高约89%。【局限】仅凭社区节点的数量分配候选种子节点的数量, 可能存在一定误差。【结论】基于重叠社区的IM-BOC算法在保证影响范围的前提下, 适用于大型社交网络。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
仇丽青
贾玮
范鑫
关键词 社交网络重叠社区影响力最大化    
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 wordsSocial Network    Overlapping Community    Influence Maximization
收稿日期: 2018-12-10     
中图分类号:  TP301.6 G35  
基金资助:*本文系2018年度青岛市社会科学规划项目“社会网络视角下的情感图谱研究: 以突发公共卫生事件为例”(QDSKL1801103);国家自然科学基金青年基金项目“时间演化尺度下大规模社会网络特征分析与社区结构挖掘”(622814971);山东科技大学优秀教学团队建设计划资助项目“嵌入式计算机技术系列课程群教学团队, 程序设计技术系列课程群教学团队”的研究成果之一(JXTD20170503);山东科技大学优秀教学团队建设计划资助项目“嵌入式计算机技术系列课程群教学团队, 程序设计技术系列课程群教学团队”的研究成果之一(JXTD20180503)
通讯作者: 仇丽青     E-mail: liqingqiu2005@126.com
引用本文:   
仇丽青,贾玮,范鑫. 基于重叠社区的影响力最大化算法 *[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community. Data Analysis and Knowledge Discovery, DOI:10.11925/infotech.2096-3467.2018.1389.
链接本文:  
http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2018.1389
图1  IC模型的传播过程
数据集 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  数据集基本信息
图2  参数r值比较
图3  参数b值比较
图4  传播范围
图5  运行时间
[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
( 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.
[1] 伍杰华,沈静,周蓓. 基于迁移成分分析的多层社交网络链接分类*[J]. 数据分析与知识发现, 2018, 2(9): 88-99.
[2] 钱晓东,李敏. 基于复杂网络重叠社区的电子商务用户复合类型识别*[J]. 数据分析与知识发现, 2018, 2(6): 79-91.
[3] 郭博,赵隽瑞,孙宇. 社会化问答社区用户行为统计特性及其动力学分析: 以知乎网为例[J]. 数据分析与知识发现, 2018, 2(4): 48-58.
[4] 王飞飞,张生太. 移动社交网络微信用户信息发布行为统计特征分析*[J]. 数据分析与知识发现, 2018, 2(4): 99-109.
[5] 张凌,罗曼曼,朱礼军. 基于社交网络的信息扩散分析研究*[J]. 数据分析与知识发现, 2018, 2(2): 46-57.
[6] 李纲,王晓,郭洋. 基于成员合作共现的微信群内部关系研究*[J]. 数据分析与知识发现, 2018, 2(11): 54-63.
[7] 曾金,陆伟,丁恒,陈海华. 基于图像语义的用户兴趣建模*[J]. 数据分析与知识发现, 2017, 1(4): 76-83.
[8] 叶光辉, 夏立新. 专家检索与专家排名研究评述*[J]. 数据分析与知识发现, 2017, 1(2): 1-10.
[9] 王曰芬,贾新露,傅柱. 学术社交网络用户内容使用行为研究*——基于科学网热门博文的实证分析[J]. 现代图书情报技术, 2016, 32(6): 63-72.
[10] 许鑫, 翟姗姗, 姚占雷. 学术博客的学科交互实证分析——以科学网博客为例[J]. 现代图书情报技术, 2015, 31(7-8): 13-23.
[11] 刘郝霞, 彭商濂. 一种基于邻近节点影响强度标签传播社区发现方法[J]. 现代图书情报技术, 2015, 31(4): 58-64.
[12] 吴昊, 刘东苏. 社交网络中的好友推荐方法研究[J]. 现代图书情报技术, 2015, 31(1): 59-65.
[13] 何静, 郭进利, 徐雪娟. 微博用户行为统计特性及其动力学分析[J]. 现代图书情报技术, 2013, 29(7/8): 94-100.
[14] 王嘉琦, 徐朝军, 李艺. 基于LDA模型的社交网站自动量化评价研究[J]. 现代图书情报技术, 2013, 29(3): 58-64.
[15] 牛亚真, 祝忠明. 个性化服务中跨系统用户建模方法研究综述[J]. 现代图书情报技术, 2012, 28(5): 1-6.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn