首页 | 官方网站   微博 | 高级检索  
     

一种基于聚集系数的局部社团划分算法
引用本文:李孔文,顾庆,张尧,陈道蓄.一种基于聚集系数的局部社团划分算法[J].计算机科学,2010,37(7):46-49.
作者姓名:李孔文  顾庆  张尧  陈道蓄
作者单位:南京大学计算机科学与技术系,软件新技术国家重点实验室,南京,210093
基金项目:863国家高技术研究发展计划项目,国家自然科学基金 
摘    要:社团划分算法是复杂网络研究中的一个热点问题.传统的复杂网络社团划分算法都必须获得全局网络的信息.随着网络规模不断增大,获得全局信息的难度随之增加;而在很多情况下只关心网络中某节点所在的局部社团.为了准确、快速地找到大规模复杂网络中的局部社团,提出了一种基于节点聚集系数性质的局部社团划分算法.该算法根据节点的连接频度,利用节点聚集系数的性质,从网络中某一待求节点开始,通过搜索邻居节点,划分该节点的社团结构.该算法只需要了解与待求节点相关的局部网络信息,在解决局部社团划分问题时其时间复杂度比传统的社团划分算法低.同时,该算法也可以应用于复杂网络全局社团结构的划分.利用该算法分别对Zachary空手道俱乐部网络和由Java开发工具包构成的软件网络图进行社团划分实验,并且分别对实验结果与对象网络的具体特征进行了对比分析.

关 键 词:局部社团  聚集系数  社团划分
收稿时间:2009/8/26 0:00:00
修稿时间:2009/10/9 0:00:00

Local Community Detecting Method Based on the Clustering Coefficient
LI Kong-wen,GU Qing,ZHANG Yao,CHEN Dao-xu.Local Community Detecting Method Based on the Clustering Coefficient[J].Computer Science,2010,37(7):46-49.
Authors:LI Kong-wen  GU Qing  ZHANG Yao  CHEN Dao-xu
Affiliation:(State Key Laboratory of Novel Software Technology,Department of Computer Science and Technology,Nanjing University,Nanjing 210093,China)
Abstract:Community detecting has been a research topic in the complex network area. The global information of the whole network, which is rectuired by the traditional community detecting algorithms, is hard to get when the scale of the network grows. On the other hand, in many cases we only care about the local community of one particular node of the network. To make the local community detecting faster and more accurate, this paper proposed a local community detecting method based on the clustering coefficient of the nodes. The proposed method, which leverages the connectivity density and the characteristics of clustering coefficient, starts from the target node of the network and detects the community it belongs to by searching the neighbor nodes. This method rectuires only the local network information related to the target node and is faster compared to the traditional community detecting algorithm. It is also applicable for global community structure detecting. I}he method was applied to the Zachary network and JSCG, and the experiment results were analyzed by comparing with the actual characteristics of the object network.
Keywords:Community  Clustering coefficient  Community detecting
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号