基于潜在特征的重叠社团识别算法

doi:10.11772/j.issn.1001-9081.2015.12.3477

计算机应用 ›› 2015, Vol. 35 ›› Issue (12): 3477-3480.DOI: 10.11772/j.issn.1001-9081.2015.12.3477

基于潜在特征的重叠社团识别算法

孙辉霞¹, 李跃新²

1. 甘肃民族师范学院计算机科学系, 甘肃合作 747000;
2. 湖北大学计算机与信息工程学院, 武汉 430062

收稿日期:2015-05-28 修回日期:2015-08-05 出版日期:2015-12-10 发布日期:2015-12-10
通讯作者: 孙辉霞(1971-),女(撒拉族),青海循化人,副教授,硕士,主要研究方向:算法分析、计算机图形学
作者简介:李跃新(1958-),男,湖北武汉人,教授,博士,主要研究方向:人工智能、知识工程、智能控制系统、嵌入式系统。
基金资助:
国家自然科学基金资助项目(61170306);湖北省自然科学基金面上项目(2014CFB536);湖北省国际交流与合作项目(2012IHA0140);湖北省科技重大支撑项目(2014BAA089);湖北大学校自然科学基金资助项目(530-095183);甘肃民族师范学院院长基金资助项目(11-16)。

Overlapping community discovering algorithm based on latent features

SUN Huixia¹, LI Yuexin²

1. Department of Computer Science, Gansu Normal University for Nationalities, Hezuo Gansu 747000 China;
2. School of Computer Science and Information Engineering, Wuhan University, Wuhan Hubei 430062, China

Received:2015-05-28 Revised:2015-08-05 Online:2015-12-10 Published:2015-12-10

摘要/Abstract

摘要： 针对标签空间的指数增长这一问题,提出了一种基于潜在特征的重叠社团识别算法。首先,提出了一种包含重叠社团的网络产生式模型。根据该产生式模型,通过最大化目标网络的产生概率来推导网络中节点的潜在特征,并给出了优化目标函数。然后,通过将网络诱导为二部图,分析得出了潜在特征个数的下届,并据此对标签空间进行优化。实验表明,提出的重叠社团识别算法与BigClam算法相比较,在保持运行效率和查准率基本不变的前提下,可以明显提高检索结果的召回率。该算法可以有效地应对社团识别中标签空间的指数增长。

关键词: 社会网络, 重叠社团, 机器学习, 标注, 二部图

Abstract: In order to solve the problem of exponential increase of label space, an overlapping community discovery algorithm based on latent feature was proposed. Firstly, a generative model for network including overlapping communities was proposed. And based on the proposed generative model, an optimal object function was presented by maximizing the generative probability of the whole network, which was used to infer the latent features for each node in the network. Next, the network was induced into a bipartite graph, and the lower bound of feature number was analyzed, which was used to optimize the object function. The experiments show that, the proposed overlapping community discovering algorithm can improve the recall greatly while keeping the precision and execution efficiency unchanged, which indicates that the proposed algorithm is effective with the exponential increase of label space.

Key words: social network, overlapping community, machine learning, labelling, bipartite graph

中图分类号:

TP391

孙辉霞, 李跃新. 基于潜在特征的重叠社团识别算法[J]. 计算机应用, 2015, 35(12): 3477-3480.

SUN Huixia, LI Yuexin. Overlapping community discovering algorithm based on latent features[J]. Journal of Computer Applications, 2015, 35(12): 3477-3480.

参考文献

[1] HU H, WANG K, XU L, et al. Online social network analysis based on complex network theory[J]. Journal of Complex Systems and Complexity Science, 2008, 5(2):1-14. (胡海波,王科,徐玲,等.基于复杂网络理论的在线社会网络分析[J].复杂系统与复杂性科学,2008,5(2):1-14.)
[2] CHEN K. Social network analysis in machine learning technology review[J]. Journal of Nanjing University of Posts and Telecommunications:Natural Science, 2011, 31(3):83-89. (陈可佳.社会网络分析中的机器学习技术综述[J].南京邮电大学学报:自然科学版,2011,31(3):83-89.)
[3] LUO Z, DING F, JIANG X, et al. New progress in research on complex network community detection algorithm[J]. Journal of National University of Defense Technology, 2011, 33(1):47-52. (骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报,2011,33(1):47-52.)
[4] YANG J, LESKOVEC J. Overlapping communities explain core-periphery organization of networks[J]. The Digital Age and the Future of Social Network Science and Engineering, 2014, 102(12):1892-1902.
[5] LESKOVEC J, McAULEY J. Learning to discover social circles in ego networks[C]//NIPS 2012:Proceedings of the 26th Annual Conference on Advances in Neural Information Processing Systems 25. Cambridge:MIT Press, 2012:548-556.
[6] BECKER E, ROBISSON B, CHAPPLE C E, et al. Multifunctional proteins revealed by overlapping clustering in protein interaction network[J]. Bioinformatics, 2012, 28(1):84-90.
[7] 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.
[8] ZHENG X,SUN J. The author collaboration network and its analysis in the field of link analysis[J]. Journal of Library Intelligence, 2009(4):29-32. (郑曦,孙建军.链接分析领域的作者合作网络及其分析[J].图书情报工作,2009(4):29-32.)
[9] AIROLDI E M, BLEI D M, FIENBERG S E, et al. Mixed membership stochastic block models[J]. Journal of Machine Learning Research, 2008, 9:1981-2014.
[10] GOPALAN P K, BLEI D M. Efficient discovery of overlapping communities in massive networks[J]. Proceedings of the National Academy of Sciences, 2013, 110(36):14534-14539.
[11] ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder:locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8):1021-1023.
[12] YANG J, LESKOVEC J. Overlapping community detection at scale:a nonnegative matrix factorization approach[C]//Proceedings of the 2013 ACM International Conference on Web Search and Data Mining. New York:ACM, 2013:587-596.
[13] da SILVA P N, GONALVES E C, PLASTINO A, et al. Distinct chains for different instances:an effective strategy for multi-label classifier chains[C]//Proceedings of the 2014 European Conference on Machine Learning and Knowledge Discovery in Databases, LNCS 8725. Berlin:Springer, 2014:453-468.
[14] BONCHI F, GIONIS A, UKKONEN A. Overlapping correlation clustering[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining. Piscataway:IEEE, 2011:51-60.

[1]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[2]	郭棉, 张锦友. 移动边缘计算环境中面向机器学习的计算迁移策略[J]. 计算机应用, 2021, 41(9): 2639-2645.
[3]	秦斌斌, 彭良康, 卢向明, 钱江波. 司机分心驾驶检测研究进展[J]. 计算机应用, 2021, 41(8): 2330-2337.
[4]	孙鹤立, 孙玉柱, 张晓云. 基于生成对抗网络的事件描述生成[J]. 计算机应用, 2021, 41(5): 1256-1261.
[5]	秦静, 左长青, 汪祖民, 季长清, 王宝凤. 基于堆叠分类器的心电异常监测模型设计[J]. 计算机应用, 2021, 41(3): 887-890.
[6]	姜倩玉, 王凤英, 贾立鹏. 基于感知哈希算法和特征融合的恶意代码检测方法[J]. 计算机应用, 2021, 41(3): 780-785.
[7]	孟祥瑞, 杨文忠, 王婷. 基于图文融合的情感分析研究综述[J]. 计算机应用, 2021, 41(2): 307-317.
[8]	刘晓龙, 王士同. 渐进式分离的开放集模糊域自适应算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3127-3131.
[9]	楼豪杰, 郑元林, 廖开阳, 雷浩, 李佳. 基于Siamese-YOLOv4的印刷品缺陷目标检测[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3206-3212.
[10]	李灿, 杨雅婷, 马玉鹏, 董瑞. 基于语种相似性挖掘的神经机器翻译语料库扩充方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3145-3150.
[11]	吴赛赛, 梁晓贺, 谢能付, 周爱莲, 郝心宁. 面向领域实体关系联合抽取的标注方法[J]. 计算机应用, 2021, 41(10): 2858-2863.
[12]	王雅辉, 钱宇华, 刘郭庆. 基于模糊优势互补互信息的有序决策树算法[J]. 计算机应用, 2021, 41(10): 2785-2792.
[13]	蒋阳升, 王胜男, 涂家祺, 李莎, 王红军. 面向高铁站的热舒适度和能耗综合预测[J]. 计算机应用, 2021, 41(1): 249-257.
[14]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[15]	朱琳, 于海涛, 雷新宇, 刘静, 王若凡. 基于MRI图像的阿尔茨海默症患者脑网络特征识别算法[J]. 计算机应用, 2020, 40(8): 2455-2459.

基于潜在特征的重叠社团识别算法

Overlapping community discovering algorithm based on latent features

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics