主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
淦文燕,赫南,李德毅,王建民.一种基于拓扑势的网络社区发现方法.软件学报,2009,20(8):2241-2254
一种基于拓扑势的网络社区发现方法
Community Discovery Method in Networks Based on Topological Potential
投稿时间:2007-07-02  修订日期:2008-03-14
DOI:
中文关键词:  拓扑势  数据场  社区发现  复杂网络
英文关键词:topological potential  data field  community discovery  complex network
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60675032 (国家自然科学基金); the National Basic Research Program of China under Grant Nos.2007CB310800, 2007CB311003 (国家重点基础研究发展计划(973))
作者单位
淦文燕 清华大学 软件学院,北京 100084 
赫南 北京航空航天大学 计算机科学与技术系,北京 100191 
李德毅 电子系统工程研究所,北京 100039 
王建民 清华大学 软件学院,北京 100084 
摘要点击次数: 4657
全文下载次数: 13606
中文摘要:
      从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n3/γ)~O(n2),n为网络节点数,m为边数,2<γ<3为一个常数.
英文摘要:
      Inspired from the idea of data fields, a community discovery algorithm based on topological potential is proposed. The basic idea is that a topological potential function is introduced to analytically model the virtual interaction among all nodes in a network and, by regarding each community as a local high potential area, the community structure in the network can be uncovered by detecting all local high potential areas margined by low potential nodes. The experiments on some real-world networks show that the algorithm requires no input parameters and can discover the intrinsic or even overlapping community structure in networks. The time complexity of the algorithm is O(m+n3/γ)~O(n2), where n is the number of nodes to be explored, m is the number of edges, and 2<γ<3 is a constant.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利