基于隶属度的社会化网络重叠社区发现及动态集群演化分析

doi:10.3969/j.issn.0372-2112.2016.03.014

电子学报 ›› 2016, Vol. 44 ›› Issue (3): 587-594.DOI: 10.3969/j.issn.0372-2112.2016.03.014

基于隶属度的社会化网络重叠社区发现及动态集群演化分析

国琳^1,2, 左万利^1,2, 彭涛^1,2

1. 吉林大学计算科学与技术学院, 吉林长春 130012;
2. 吉林大学符号计算与知识工程教育部重点实验室, 吉林长春 130012

收稿日期:2014-06-07 修回日期:2014-10-15 出版日期:2016-03-25
- 通讯作者:
- 左万利
- 作者简介:
- 国琳女,1987年8月生于吉林吉林,2013年至今于吉林大学计算机学院攻读博士学位,从事社会化网络、知识挖据及搜索引擎有关研究. E-mail:guolin13@mails.jlu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.60973040); 国家自然科学青年基金 (No.61300148); 吉林省重点科技攻关项目基金 (No.20130206051GX); 吉林省科技计划青年科研基金 (No.20130522112JH); 中国博士后基金项目 (No.2012M510879); 吉林大学基本科研业务费科学前沿与交叉项目 (No.201103129)

Overlapping Community Detection and Dynamic Group Evolution Analysis Based on the Degree of Membership in Social Network

GUO Lin^1,2, ZUO Wan-li^1,2, PENG Tao^1,2

1. College of Computer Science and Technology of Jilin University, Changchun, Jilin 130012, China;
2. Symbol Computation and Knowledge Engineer of Ministry of Education of Jilin University, Changchun, Jilin 130012, China

Received:2014-06-07 Revised:2014-10-15 Online:2016-03-25 Published:2016-03-25
- Supported by:
- National Natural Science Foundation of China (No.60973040); Youth Fund of National Natural Science Foundation of China (No.61300148); Key Technology Research and Development Program of Jilin Province (No.20130206051GX); Youth Research Fund of Science and Technology Program of Jilin Province (No.20130522112JH); Post-doctoral Foundation of China (No.2012M510879); Fundamental Fund for Science Frontier and Cross Project of Jilin University (No.201103129)

摘要/Abstract

摘要：

社会化网络中节点的复合属性可能为临时或过时状态,并且节点拥有一定能力维持固有状态,所以不可单纯依据新增数据或节点现有特征确定社区划分.本文提出可重叠社区发现算法及集群动态更新方案,根据网络历史数据分析节点对原始集群的隶属程度,并结合新增数据确定节点变化趋势,实现网络结构分析及社区动态更新.本文分别在不同数据集中测试聚类效果,实验结果证明算法既保持对新增数据的敏感度,也防止了节点短暂特征或节点维持固有状态的能力对划分结果的负面影响.

关键词: 社区发现, 社会化网络, 聚类, 重叠社区, 自适应算法

Abstract:

The complex social attributes of nodes in the network have a certain ability to maintain the former state,so it is inappropriate to determine community division merely based on newly added data.This paper proposes an overlapping community detection algorithm and dynamic cluster update strategy,which,by fully analyzing historical network data to compute the degree of nodes belonging to communities,determines the evolution tendency of nodes through incorporating incremental data to analyze the structure of the network and update the division results automatically.Experiments on several typical datasets demonstrate that the algorithm not only ensures the sensitivity to incremental data,but also avoids the negative effect of temporary features in maintaining intrinsic states on the clustering results.

Key words: community detection, social internet, clustering, overlapping community, adaptive algorithm

中图分类号:

TP391

国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.

GUO Lin, ZUO Wan-li, PENG Tao . Overlapping Community Detection and Dynamic Group Evolution Analysis Based on the Degree of Membership in Social Network[J]. Acta Electronica Sinica, 2016, 44(3): 587-594.

参考文献

[1] Flake G W,Lawrence S,Giles C L,et al.Coetzee.Self-organization and identification of web community[J]. Computer,2002,35(3):66-70.
[2] Thakur G S,Tiwari R,Thai M T,et al.Detection of local community structures in complex dynamic networks with random walks[J]. IET Systems Biolpgy,2009,3(4):266-278.
[3] 潘磊,金杰,王琮骏,等.社会网络中基于局部信息的边社区挖掘[J]. 电子学报,2012,40(11):2255-2262. Pan Lei,Jin Jie,Wang Chong-jun,et al.Detecting link communities based on local information in social networks[J]. Acta Electronica Sinica,2012,40(11):2255-2262.(in Chinese)
[4] Tantipathananandh C,Berger-wolf T,Kempe D.A framework for community identification in dynamic social networks[A]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. California,USA:ACM,2007.717-726.
[5] Wang W,Liu D,Liu X,et al.Fuzzy overlapping community detection based on local random walk and multidimensional scaling[J]. Physica A:Statistical Mechanics and Its Applications,2013,392(24):6578-6586.
[6] Christiano T,Zhao L.Uncovering overlapping cluster structures via stochastic competitive learning[J]. Information Sciences,2013,247:40-61.
[7] Wang C-D,Lai J-H,Yu P S.NEIWalk:Community discovery in dynamic content-based networks[J]. IEEE Transactions on Knowledge and Data Engineering,2013,26(7):1734-1748.
[8] Comar P M,Tan P-N,Jain A K.A framework for joint community detection across multiple related networks[J]. Neurocomputing,2012,76(1):93-104.
[9] Fortunato S.Community detection in graphs[J]. Physics Reports,2010,486(3-5):75-174.
[10] Zhang S,Wang R,Zhang X.Identification of overlapping community structure in complex networks using fuzzy cc-means clustering[J]. Physica A:Statistical Mechanics and Its Applications,2007,374:483-490.
[11] Yang J,Leskovec J.Overlapping community detection at scale:A nonnegative matrix factorization approach[A]. Proceedings of the 6th ACM International Conference on Web Search and Data Mining[C]. Roman,Italy:ACM,2013.587-596.
[12] Perez-Suarez A,Martinez-Trinidad J F,Carrasco-Ochoa J A.An algorithm based on density and compactness for dynamic overlapping clustering[J]. Pattern Recognition,2013,46(11):3040-3055.
[13] Pons-Porrata A,Ruiz-Shulcloper J,Berlanga-Llavori R,et al.Un algoritmo incremental para la obtención de cubrimientos con datos mezclados[A]. Proceedings of the 7th Iberoamerican Conference on Pattern Recognition[C]. Mexico:CIARP,2002.405-416.
[14] Aslam J,Pelekhov K,Rus D.Static and dynamic information organization with star clusters[A]. Proceedings of the 7th International Conference on Information and Knowledge Management[C]. Bethesda,Maryland,USA:ACM,1998.208–217.
[15] Pérez-Suárez A,Medina-Pagola J.A clustering algorithm based on generalized stars[A]. Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition[C]. Leipzig,Germany:Springer,2007.248-262.
[16] Gil-García R,Pons-Porrata A.Dynamic hierarchical algorithms for document clustering[J]. Pattern Recognition Letters,2010,31(6):469-477.

基于隶属度的社会化网络重叠社区发现及动态集群演化分析

Overlapping Community Detection and Dynamic Group Evolution Analysis Based on the Degree of Membership in Social Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[2]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[3]	王波, 王悦, 王伟, 侯嘉尧. 开放环境下自适应聚类优化包络的相机来源取证[J]. 电子学报, 2022, 50(8): 1840-1850.
[4]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[5]	易令, 李泽平. 基于深度强化学习的码率自适应算法研究[J]. 电子学报, 2022, 50(5): 1192-1200.
[6]	李凯, 张可心. 结构α-熵的加权高斯混合模型的子空间聚类[J]. 电子学报, 2022, 50(3): 718-725.
[7]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[8]	路皓翔, 刘振丙, 张静, 王子民. 结合多尺度循环卷积和多聚类空间的红外图像增强[J]. 电子学报, 2022, 50(2): 415-425.
[9]	赵嘉, 王刚, 吕莉, 樊棠怀. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
[10]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[11]	江巨浪, 刘国明, 朱柱, 黄忠, 郑江云. 基于快速模糊聚类的动态多直方图均衡化算法[J]. 电子学报, 2022, 50(1): 167-176.
[12]	孟海宁, 冯锴, 朱磊, 张贝贝, 童新宇, 黑新宏. 基于Laplacian图谱的短文本聚类算法[J]. 电子学报, 2021, 49(9): 1716-1723.
[13]	张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.
[14]	李鹏, 闵慧, 罗爱静. 基于动态图的PPI网络构建和复合物挖掘算法研究[J]. 电子学报, 2021, 49(8): 1489-1497.
[15]	姜春茂, 赵书宝. 基于阴影集的多粒度三支聚类集成[J]. 电子学报, 2021, 49(8): 1524-1532.