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

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 Online: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]. 《计算机应用》唯一官方网站, 2024, 44(9): 2660-2666.
[2]	方介泼, 陶重犇. 应对零日攻击的混合车联网入侵检测系统[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2763-2769.
[3]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[4]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[5]	徐航, 杨智, 陈性元, 韩冰, 杜学绘. 基于自适应敏感区域变异的覆盖引导模糊测试[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2528-2535.
[6]	吴锦富, 柳毅. 基于随机噪声和自适应步长的快速对抗训练方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1807-1815.
[7]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[8]	李威, 陈玲, 徐修远, 朱敏, 郭际香, 周凯, 牛颢, 张煜宸, 易珊烨, 章毅, 罗凤鸣. 基于多任务学习的间质性肺病分割算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1285-1293.
[9]	韦修喜, 彭茂松, 黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1009-1017.
[10]	刘一迪, 温自豪, 任富香, 李诗音, 唐德玉. 自适应球形演化的药物-靶标相互作用预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 989-994.
[11]	刘勇, 杨锟. 新能源汽车电池回收网点竞争选址模型及算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 595-603.
[12]	李俊杰, 望育梅, 李志军, 刘雨. 全景视频基于块的视口自适应传输方案综述[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 536-547.
[13]	王震, 张珊珊, 邬斌扬, 苏万华. 基于自适应粒子群优化算法的串联复合涡轮储能优化策略[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 611-618.
[14]	闫文杰, 党东月. 基于特征自适应提取的宽度量子态层析模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3861-3866.
[15]	刘晶鑫, 黄雯静, 徐亮胜, 黄冲, 吴建生. 字典学习与样本关联保持结合的无监督特征选择模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3766-3775.

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

Community detection algorithm based on signal adaptive transmission

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics