您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (3): 24-29.doi: 10.6040/j.issn.1671-9352.1.2017.041

• • 上一篇    下一篇

基于网络有效阻抗的社区发现算法

张军1,李竞飞2,4,张瑞1,3*,阮兴茂2,张烁2   

  1. 1.呼伦贝尔学院计算机学院, 内蒙古 呼伦贝尔 021008;2.天津大学计算机科学与技术学院, 天津 300350;3.天津大学管理与经济学部, 天津 300072;4.国家计算机网络应急技术处理协调中心, 北京100029
  • 收稿日期:2017-09-19 出版日期:2018-03-20 发布日期:2018-03-13
  • 通讯作者: 张瑞(1982— ),男,博士研究生,讲师,研究方向为机器学习、社交网络、信息系统等. E-mail:zhangr@tju.edu.cn E-mail:zjun0063@163.com
  • 作者简介:张军(1975— ),男,硕士研究生,讲师,研究方向为社交网络和信息系统. E-mail:zjun0063@163.com
  • 基金资助:
    国家重点基础研究发展计划(973计划)项目(2014CB744604,2013CB329304);国家自然基金资助项目(61772363)

Community detection algorithm based on effective resistance of network

ZHANG Jun1, LI Jing-fei2,4, ZHANG Rui1,3*, RUAN Xing-mao2, ZHANG Shuo2   

  1. 1. School of Computer Science and Technology, Hulunbuir College, Hulunbuir 021008, Inner Mongolia, China;
    2. School of Computer Science and Technology, Tianjin University, Tianjin 300350, China;
    3. College of Management and Economics, Tianjin University, Tianjin 300072, China;
    4. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China
  • Received:2017-09-19 Online:2018-03-20 Published:2018-03-13

PDF (PC)

594

摘要： 社区发现在很多领域都有非常重要的应用。受经典电路网络中的阻抗原理启发,提出了一个新颖的社区发现算法。该算法通过迭代调用基于网络总阻抗的割边选择模型来实现社区发现的目标。在每一次迭代过程中,割边选择模型采用启发式策略割除恰当数量的边,使得割边后的网络有效阻抗最大化。理论分析表明该算法具有较低的算法复杂度。利用仿真数据和真实数据对算法进行测试,实验结果表明算法性能良好。

关键词: 社区发现, 最大化, 阻抗, 启发式

Abstract: Community detection has a number of important applications in many areas. Inspired by the principle of effective resistance in traditional electrical circuit, we propose a novel community detection algorithm which can discover communities by iteratively calling the edge-cutting selection model based on the total effective resistance of a network. In each iteration, the edge-cutting selection model cuts an appropriate number of edges in order to maximize the total effective resistance of the updated network. Theoretical analysis shows that our algorithm has relatively low algorithm complexity degree. Extensive empirical experiments have been conducted on simulated and real complex networks, the results show that the proposed algorithm has good performance.

Key words: heuristic, community detection, maximization, effective resistance

中图分类号: 

  • TP391
[1] VU T T, SONG Dawei, WILLIS A, et al. Improving search personalisation with dynamic group formation[C] // Proceedings of the International ACM SIGIR Conference. New York: ACM, 2014: 951-954.
[2] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2):026113.
[3] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 70(6 Pt 2):066111. DOI: 10.1103/PhysRevE.70.066111.
[4] CHOUDHURY D, BHATTACHARJEE S, DAS A. An empirical study of community and sub-community detection in social networks applying Newman-Girvan algorithm[C] // International Conference on Emerging Trends and Applications in Computer Science. New York: IEEE, 2013: 74-77.
[5] ZHU Xiaohu, SONG Wenjun, WANG Chongjun, et al. Improved algorithm based on girvan-newman algorithm for community detection[J]. Journal of Frontiers of Computer Science & Technology, 2010, 4(12):1101-1108.
[6] GHOSH A, BOYD S, SABERI A. Minimizing effective resistance of a graph[J]. Siam Review, 2008, 50(1):37-66.
[7] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):046110.
[8] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[9] YIP K Y, CHEUNG D W, NG M K. HARP: a practical projected clustering algorithm[J]. IEEE Transactions on Knowledge & Data Engineering, 2004, 16(11):1387-1397.
[1] 张鹏,王素格,李德玉,王杰. 一种基于启发式规则的半监督垃圾评论分类方法[J]. 山东大学学报（理学版）, 2017, 52(7): 44-51.
[2] 徐兵,张阳. 基于Hotelling模型的两厂商选址定价完全序贯决策[J]. 山东大学学报（理学版）, 2017, 52(6): 1-9.
[3] 吴平杰,周斌,吴泉源. COT:一种连续时间序列建模的社区发现算法[J]. 山东大学学报（理学版）, 2016, 51(11): 41-49.
[4] 王倩,徐如志，杨峰. 无线多跳网络中基于QoS 保证的TCP速率控制跨层优化算法[J]. J4, 2012, 47(3): 61-66.
[5] 周爱萍,臧永丽. 利用反常粘滞研究吸积盘的脉动不稳定性[J]. J4, 2012, 47(1): 50-54.
[6] 王刚,许信顺*. 一种新的基于多示例学习的场景分类方法[J]. J4, 2010, 45(7): 108-113.
[7] . 基于圆柱模型的三维电阻抗成像问题研究[J]. J4, 2009, 44(5): 45-48.
[8] 周爱萍. 耗散过程对吸积盘磁不稳定性的影响[J]. J4, 2009, 44(1): 44-48 .
[9] 伍远辉1,2,刘天模1,罗宿星2, 孙成3 . 土壤中宏电池对X70钢腐蚀作用的研究[J]. J4, 2009, 44(1): 24-27 .
[10] 吴鹏飞,孟祥增,刘俊晓,马凤娟 . 基于结构与内容的网页主题信息提取研究[J]. J4, 2006, 41(3): 131-134 .
[11] 赵培忻,马建华,王 红 . 随机装卸工问题的Lagrange松弛启发式算法[J]. J4, 2006, 41(1): 106-110 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发