期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

用于社团发现的Girvan-Newman改进算法 被引量：12

Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection
在线阅读 下载PDF
导出
摘要 为了克服Girvan-Newman算法运行效率的不足,提出了一个基于modularity极值近似的社团发现算法MEA。该算法采用modularity增量作为社团结构的度量,使用贪心策略获得最优社团分划的近似解。通过理论分析,并在实际的数据集上进行实验验证,结果表明MEA算法是快速、有效的。 To improve the efficiency of Girvan-Newman（G-N） algorithm, a community detection algorithm named modularity extreme approximation （MEA） is given. MEA algorithm uses the increment of modularity as the measure for community structure and finds the solution with a greedy strategy. The theoretical analysis and experimental results show the MEA algorithm is more effective and faster than the G-N algorithm.
作者 朱小虎 宋文军 王崇骏 谢俊元
机构地区 南京大学计算机软件新技术国家重点实验室 南京大学计算机科学与技术系
出处 《计算机科学与探索》 CSCD 2010年第12期1101-1108,共8页 Journal of Frontiers of Computer Science and Technology
基金 国家自然科学基金No.60503021 60721002 60875038 国家教育部重点项目No.108151 江苏省科技支撑计划No.BE2009142~~
关键词 社会网络分析 社团结构发现 Girvan—Newman算法 贪心策略 social networks analysis community structure detection Girvan-Newman algorithm greedy strategy
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献13

  • 1Knoke D, Kuklinski H J. Network analysis[M]. Beverly Hills: Sage Publication, 1982.
  • 2Wasserman S, Faust K. Social network analysis: Methods and applications[M]. Cambridge, UK: Cambridge University Press, 1994.
  • 3Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2): 26-113.
  • 4Estrada E, Hatano N. Communicability in complex networks[J]. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2008, 77:36-111.
  • 5Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proc of the National Academy of Sciences, USA, 2002, 99(12): 7821-7826.
  • 6Tarjan R E. Efficiency of a good but not linear set union algorithm[J]. Journal of the ACM, 1975, 22(2): 215-225.
  • 7Freeman L C. A set of measures of centrality based upon betweenness[J]. Sociometry, 1977, 40(1): 35-41.
  • 8Brandes U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25: 163-177.
  • 9Newman Shortest MEJ paths, Scientific collaboration networks. II weighted networks, and centrality[J] Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2001, 64:1-7.
  • 10Newman M E J. Modularity and community structure in network[J]. Proc of the National Academy of Sciences,USA, 2006, 103(23): 8577-8582.

同被引文献87

  • 1王丹,刘发升.复杂网络的社区发现算法研究[J].计算机时代,2009(3):57-59. 被引量：5
  • 2刘婷,胡宝清.基于聚类分析的复杂网络中的社团探测[J].复杂系统与复杂性科学,2007,4(1):28-35. 被引量：16
  • 3戴朝华,朱云芳,陈维荣,林建辉.云遗传算法及其应用[J].电子学报,2007,35(7):1419-1424. 被引量：84
  • 4吴文涛.图对称理论在社会网络分析若干重要问题中的应用.复旦大学,2010.
  • 5信息架构本质:分布式数据挖掘.hltp:llwww.ibm,com.ldeveloperworks/en/arehiteeture/ar-infoarch6/.
  • 6Girvan M, Newman EJ. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America; 6/11/2002, Vol. 99 Issue 12, p7821, 6p, 7 Diagrams, 1 Graph.
  • 7Amazon Elastic Map Reduce. [2010-09-26].http: //aws. Ama- zon.corn/ elastieMapReduce/.
  • 8Newman M E J, Girvan M. Finding and evaluating community structure in networks [ J ]. Physical Review E, 2004, 69(2) :026113.
  • 9Leicht E A, Newman M E J. Community structure in directed networks [ J ]. Phys. Rev. Lett, 2008,100 : 118703.
  • 10Han J,Kamber M,Pei J.Data mining:Concepts and techniques[M].3rd ed.San Francisco:Morgan Kaufmann Publishers,2011.

引证文献12

二级引证文献45

计算机科学与探索
2010年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部