面向大规模学术社交网络的社区发现模型

doi:10.11772/j.issn.1001-9081.2015.09.2565

计算机应用 ›› 2015, Vol. 35 ›› Issue (9): 2565-2568.DOI: 10.11772/j.issn.1001-9081.2015.09.2565

面向大规模学术社交网络的社区发现模型

李春英^1,2, 汤庸², 汤志康³, 黄泳航², 袁成哲², 赵剑冬¹

1. 广东技术师范学院计算机网络中心, 广州 510665;
2. 华南师范大学计算机学院, 广州 510631;
3. 广东技术师范学院计算机科学学院, 广州 510665

收稿日期:2015-04-20 修回日期:2015-06-18 出版日期:2015-09-10 发布日期:2015-09-17
通讯作者: 汤志康(1978-),男,山东临沂人,讲师,硕士,主要研究方向:社交网络与大数据应用、社区发现,fzutang@126.com
作者简介:李春英(1978-),女,黑龙江齐齐哈尔人,副教授,博士研究生,CCF会员,主要研究方向:社交网络与大数据应用、服务计算、社区发现;汤庸(1964-),男,湖南张家界人,教授,博士生导师,博士,CCF会员,主要研究方向:信息搜索与数据挖掘、协同计算与移动互联网应用。
基金资助:
国家863计划项目(2013AA01A212);国家自然科学基金资助项目(61272067,61370229);广东省自然基金团队研究项目(S2012030006242);广东省自然科学基金-博士科研启动项目(2014A030310238);广东省教育厅特色创新项目(2014WTSCX078);广东技术师范学院校级项目(2014)。

Community detection model in large scale academic social networks

LI Chunying^1,2, TANG Yong², TANG Zhikang³, HUANG Yonghang², YUAN Chengzhe², ZHAO Jiandong¹

1. Computer Network Center, Guangdong Polytechnic Normal University, Guangzhou Guangdong 510665, China;
2. School of Computer, South China Normal University, Guangzhou Guangdong 510631, China;
3. School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou Guangdong 510665, China

Received:2015-04-20 Revised:2015-06-18 Online:2015-09-10 Published:2015-09-17

摘要/Abstract

摘要： 针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。

关键词: 社交网络, 社区发现, 重叠社区, 标签传播, 最大极大团, 自适应阈值

Abstract: Concerning the problem that community detection algorithm based on label propagation in complex networks has a pre-parameter limit in the real network and redundant labels, a community detection model in large scale academic social networks was proposed. The model detected Utmost Maximal Cliques (UMC) in the academic social network and arbitrary intersection between the UMC is the empty set, and then let nodes of each UMC share the unique label by reducing redundant labels and random factors, so the model increased the efficiency and stability of the algorithm. Meanwhile the model completed label propagation of the UMC adjacent nodes using closeness from core node groups (UMC) to spread around, Non-UMC adjacent nodes in the network were updated according to the maximum weight of its neighbor nodes. In the post-processing stage an adaptive threshold method removed useless labels, thereby effectively overcame the pre-parameter limitations in the real complex network. The experimental results on academic social networking platform-SCHOLAT data set prove that the model has an ability to assign nodes with certain generality to the same community, and it provides support of the academic social networks precise personalized service in the future, such as latent friend recommendation and paper sharing.

Key words: social network, community detection, overlapping community, label propagation, Utmost Maximal Clique (UMC), adaptive threshold

中图分类号:

TP391.3

李春英, 汤庸, 汤志康, 黄泳航, 袁成哲, 赵剑冬. 面向大规模学术社交网络的社区发现模型[J]. 计算机应用, 2015, 35(9): 2565-2568.

LI Chunying, TANG Yong, TANG Zhikang, HUANG Yonghang, YUAN Chengzhe, ZHAO Jiandong. Community detection model in large scale academic social networks[J]. Journal of Computer Applications, 2015, 35(9): 2565-2568.

参考文献

[1] PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005,435(7043):814-818.
[2] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010,466(7307):761-764.
[3] LANCICHINETTI A, FORTUNATO S, KERTÉSZ J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics, 2009,11(3):033015.
[4] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks [EB/OL]. [2015-01-08]. http://wenku.baidu.com/view/d6c2d36ba98271fe910ef9c9.html.
[5] JIN H, WANG S, LI C. Community detection in complex networks by density-based clustering [J]. Physica A: Statistical Mechanics and its Applications, 2013,392(19):4606-4618.
[6] XIA Z, BU Z. Community detection based on a semantic network [J]. Knowledge-Based Systems, 2012,26:30-39.
[7] BARBIERI N, BONCHI F, MANCO G. Cascade-based community detection [C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York: ACM, 2013:33-42.
[8] DEV H, ALI M E, HASHEM T. User interaction based community detection in online social networks [M]//BHOWMICK S S, DYRESON C, JENSEN C S, et al. Database Systems for Advanced Applications, LNCS 8422. Berlin: Springer, 2014:296-310.
[9] GREGORY S. Finding overlapping communities in networks by label propagation [EB/OL]. [2015-01-08]. http://iopscience.iop.org/1367-2630/12/10/103018/pdf/1367-2630_12_10_103018.pdf.
[10] XIE J, SZYMANSKI B K. Towards linear time overlapping community detection in social networks [M]//TAN P-N, CHAWLA S, HO C K, et al. Advances in Knowledge Discovery and Data Mining, LNCS 7302. Berlin:Springer, 2012:25-36.
[11] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks [J]. Physica A: Statistical Mechanics and its Applications, 2010,389(7):1493-1500.
[12] XIE J, SZYMANSKI B K. Community detection using a neighborhood strength driven label propagation algorithm [C]//Proceedings of the 2011 IEEE Network Science Workshop. Piscataway: IEEE, 2011:188-195.
[13] CORDASCO G, GARGANO L. Community detection via semi-synchronous label propagation algorithms [C]//Proceedings of the 2010 IEEE International Workshop on Business Applications of Social Network Analysis. Piscataway: IEEE, 2010,1-8.
[14] LOU H, LI S, ZHAO Y. Detecting community structure using label propagation with weighted coherent neighborhood propinquity [J]. Physica A, 2013,392(14):3095-3105.
[15] UGANDER J, BACKSTROM L. Balanced label propagation for partitioning massive graph [C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York: ACM, 2013:507-516.
[16] KUZMIN K, SHAH S Y, SZYMANSKI B K. Parallel overlapping community detection with SLPA [C]//Proceedings of the 2013 International Conference on Social Computing. Washington, DC: IEEE Computer Society, 2013:204-212.
[17] LI C, TANG Y, LIN H, et al. A parallelize overlapping community detection algorithm in complex networks based on label propagation [EB/OL]. [2014-12-28]. http://info.scichina.com/sciF/CN/10.1360/N112014-00258.(李春英,汤庸,林海,等.基于标签传播的可并行复杂网络重叠社区发现算法[EB/OL]. [2014-12-28]. http://info.scichina.com/sciF/CN/10.1360/N112014-00258.)

面向大规模学术社交网络的社区发现模型

Community detection model in large scale academic social networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[2]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[3]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[4]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[5]	赵旭剑, 王崇伟. 基于图卷积网络的微博新闻故事线抽取方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3139-3144.
[6]	李翔锟, 贾彩燕. 融合重叠社区正则化及隐式反馈的协同过滤方法[J]. 计算机应用, 2021, 41(1): 53-59.
[7]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[8]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[9]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[10]	王思鹏, 杜昌平, 叶志贤, 宋广华, 郑耀. 基于多步神经网络观测器的扑翼飞行器缓变故障检测[J]. 计算机应用, 2020, 40(8): 2449-2454.
[11]	杨书新, 梁文, 朱凯丽. 社交网络中对立影响最大化算法[J]. 计算机应用, 2020, 40(7): 1944-1949.
[12]	张皓然, 王学渊, 李小霞. 基于自适应阈值活动语音检测和最小均方误差对数谱幅度估计的低信噪比降噪算法[J]. 计算机应用, 2020, 40(6): 1763-1768.
[13]	王忠锋, 徐志远, 宋纯贺, 张宏宇, 蔡颖凯. 基于梯度的深度网络剪枝算法[J]. 计算机应用, 2020, 40(5): 1253-1259.
[14]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[15]	冯丽萍, 韩琦, 周志刚, 白增亮. 社交网络影响的不良信息扩散建模及最优控制策略[J]. 计算机应用, 2020, 40(3): 735-739.