基于信号自适应传递的社团发现算法

doi:10.11772/j.issn.1001-9081.2015.06.1552

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1552-1554.DOI: 10.11772/j.issn.1001-9081.2015.06.1552

基于信号自适应传递的社团发现算法

谭春妮¹, 张玉梅², 张嘉桐³, 吴晓军^1,2

1. 陕西师范大学物理学与信息技术学院, 西安 710119;
2. 陕西师范大学计算机科学学院, 西安 710119;
3. 西北大学文化遗产学院, 西安 710127

收稿日期:2015-01-07 修回日期:2015-04-07 发布日期:2015-06-12
通讯作者: 吴晓军(1970-),男,陕西凤翔人,教授,博士,主要研究方向:复杂系统。xjwu@snnu.edu.cn
作者简介:谭春妮(1989-),女,陕西宝鸡人,硕士研究生,主要研究方向:智能信息处理;张玉梅(1977-),女,陕西榆林人,副教授,博士,CCF会员,主要研究方向:非线性时间序列建模及预测;张嘉桐(1995-),女,黑龙江汤原人,主要研究方向:传感器网络.
基金资助:
陕西自然科学基金资助项目(2014JZ021);陕西省重点科技创新团队项目(2014KTZ-18);榆林市产学研合作项目(2012cxy3-6)。

Community detection algorithm based on signal adaptive transmission

TAN Chunni¹, ZHANG Yumei², ZHANG Jiatong³, WU Xiaojun^1,2

1. School of Physics and Information Technology, Shaanxi Normal University, Xi'an Shaanxi 710119, China;
2. School of Computer Science, Shaanxi Normal University, Xi'an Shaanxi 710119, China;
3. School of Cultural Heritage, Northwest University, Xi'an Shaanxi 710127, China

Received:2015-01-07 Revised:2015-04-07 Published:2015-06-12

摘要/Abstract

摘要：

为了准确地检测出复杂网络的社团结构,提出一种基于信号自适应传递的社团发现方法。首先使信号在复杂网络上自适应地传递,从而获取网络中各节点对整个网络的影响向量,然后把网络中节点的拓扑结构转化成代数向量空间上的几何关系,最后结合聚类特性发现网络中的社团结构。为获取更加合理的空间向量,提出最佳传递次数,缩小搜索空间,增强算法寻优能力。该算法在计算机生成网络、Zachary网络和美国大学生足球赛网络上进行实验测试, 并与GN算法、谱聚类算法、极值优化算法和信号传递算法进行实验对比,社团划分的准确性和精确性均有所提高,证明该算法具有有效性和可行性。

关键词: 复杂网络, 社团结构, 自适应, 传递次数, 社团发现算法

Abstract:

In order to accurately detect the community structure of complex networks, a community detection algorithm based on signal adaptive transmission was proposed. First, the signal was adaptively passed on complex networks,thereby getting the vector affecting on the entire network of each node, then the topological structure of each node was translated into geometrical relationships of algebra vector space. Thus, according to the nature of the clustering, the community structure of the network was detected. In order to get the feasible spatial vectors, the optimum transfer number was determined, which reduced the searching space, and effectively strengthened the search capability of community detection.The proposed algorithm was tested on computer-generated network, Zachary network and American college football network. Compared with Girvan-Newman (GN) algorithm, spectral clustering algorithm,extremal optimization algorithm and signal transmission algorithm, the results show that the accuracy and precision of the proposed community division algorithm is feasible and effective.

Key words: complex network, community structure, adaptability, transfer number, community detection algorithm

中图分类号:

TP393.02

谭春妮, 张玉梅, 张嘉桐, 吴晓军. 基于信号自适应传递的社团发现算法[J]. 计算机应用, 2015, 35(6): 1552-1554.

TAN Chunni, ZHANG Yumei, ZHANG Jiatong, WU Xiaojun. Community detection algorithm based on signal adaptive transmission[J]. Journal of Computer Applications, 2015, 35(6): 1552-1554.

参考文献

[1] WANG X, LI X, CHEN G.Complex network theory and its applications [M]. Beijing: Tsinghua University Press, 2006:162-165.(汪小帆, 李翔, 陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:162-165.)
[2] SHI C, CAI Y N, FU D, et al. A link clustering based overlap-ping community detection algorithm [J]. Data & Knowledge Engineering, 2013, 87: 394-404.
[3] LI K, PANG Y. A unified community detection algorithm in complex network [J]. Neurocomputing, 2014, 130: 36-43.
[4] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of National Academy of Sciences, 2001, 99(12): 7821-7826.
[5] DUCH J, ARENAS. A community detection in complex networks using extremal optimization [J].Physical Review E, 2005, 72(2): 027104.
[6] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach [J]. The European Physical Journal B, 2004, 38(2): 331-338.
[7] DONETTI L, MUNOZ M A. Detecting network communities: a new systematic and efficient algorithm [J]. Journal of Statistical Mechanics: Theory and Experiment, 2004, 37(10): 10012.
[8] HU Y, LI M, ZHANG P, et al.Community detection by signaling on complex networks [J].Physcial Review E: Statistical, Nonlinear and Soft Matter Physics, 2008, 78: 016115.
[9] WASSERMAN S, FAUST K. Social network analysis: methods and applications [M]. Cambridge: Cambridge University Press, 1994:249-290.
[10] YANG B, LIU J. Discovering global network communities based on local centralities [J]. ACM Transactions on the Web, 2008, 2(1): article 9.
[11] NEWMAN M E J, GIRAN M. Finding and evaluating community structure in networks [J]. Physical Review E, 2004, 69(2):293-313.
[12] ZHANG C, SHEN H. Modularity function for community structure based on natural density of networks [J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 185-191.(张聪, 沈惠璋.网络自然密度社团结构模块度函数[J].电子科技大学学报, 2012, 41(2):185-191.)
[13] ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropology Research, 1977, 33(4): 452-473.
[14] XIE Z, WANG X. Review of the algorithm analysis research for community structure in complex networks [C]. Complex Systems and Complexity Science, 2005, 2(3): 1-12.(解, 汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学, 2005, 2(3):1-12.)

[1]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[2]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[3]	刘双元, 郑王里, 林云汉. 面向三维特征描述子的自适应二进制简化方法[J]. 计算机应用, 2021, 41(7): 2062-2069.
[4]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[5]	侯笑晗, 金国栋, 谭力宁, 薛远亮. 基于自适应和最优特征的合成孔径雷达舰船检测方法[J]. 计算机应用, 2021, 41(7): 2150-2155.
[6]	李辉, 吴传生, 刘俊, 刘文. 基于梯度曲面面积与稀疏约束的图像平滑方法[J]. 计算机应用, 2021, 41(7): 2039-2047.
[7]	蔡瑞光, 张德生, 肖燕婷. 参数独立的加权局部均值伪近邻分类算法[J]. 计算机应用, 2021, 41(6): 1694-1700.
[8]	林筠超, 万源. 基于图结构优化的自适应多度量非监督特征选择方法[J]. 计算机应用, 2021, 41(5): 1282-1289.
[9]	王治和, 常筱卿, 杜辉. 基于万有引力的自适应近邻传播聚类算法[J]. 计算机应用, 2021, 41(5): 1337-1342.
[10]	李杏峰, 黄玉清, 任珍文, 李毅红. 基于自适应邻域的鲁棒多视图聚类算法[J]. 计算机应用, 2021, 41(4): 1093-1099.
[11]	张康, 陈建平. 复杂环境下基于采样空间自调整的航迹规划算法[J]. 计算机应用, 2021, 41(4): 1207-1213.
[12]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[13]	黄思远, 张敏情, 柯彦, 毕新亮. 基于显著性检测的图像隐写分析方法[J]. 计算机应用, 2021, 41(2): 441-448.
[14]	郭丽峰, 王倩丽. 自适应安全的带关键字搜索的外包属性基加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3266-3273.
[15]	刘晓龙, 王士同. 渐进式分离的开放集模糊域自适应算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3127-3131.

基于信号自适应传递的社团发现算法

Community detection algorithm based on signal adaptive transmission

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics