一种可变分辨率的社团发现算法.pdf

《一种可变分辨率的社团发现算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第33卷第3期东北大学学报(自然科学版)Vo1．33，No．32012年3月JournalofNortheasternUniversity(NaturalScience)Mar．2012一种可变分辨率的社团发现算法陈东明，夏方朝，贾路路，徐晓伟(1．东北大学软件学院，辽宁沈阳110819；2．阿肯色大学信息科学系，美国小石城72204)摘要：介绍了复杂网络及社团结构的相关概念，给出节点的综合特征值和增益函数的定义，然后提出一种新的社团发现算法(CNCD)．综合特征值与节点的度数及其聚类系数有关，用于发现社团

2、中的核心节点；增益函数决定何时获得社团结构的最佳划分．作者用C+十语言实现算法，并使用经典数据集对算法进行验证，实验结果表明此算法不仅能够得到正确的社团结构，而且通过动态调整算法中的参数值，能够得到比传统算法更加详细的社团划分结果，获得网络的细节信息．关键词：复杂网络；社团结构；核心节点；综合特征值；增益函数中图分类号：TP391文献标志码：A文章编号：1005—3026(2012)03—0348—04ACommunityDiscoveryAlgorithmwithVariableResolutionCHE

3、NDong-ming，XIAFang-zhao，JIALu．1u，XUXiao—wei(1．SchoolofSoftware，NortheasternUniversity，Shenyang110819，China；2．DepartmentofInformationScience，UniversityofArkansas，LittleRock72204，UAS．Correspondingauthor：CHENDong-ming，E—mail：chendm@mail．neu．edu．cn)Abstract：In

4、troducingsomerelationalconceptionsofcomplexnetworkandcommunitystructure，anewcommunitydiscoveryalgorithmbasedoncorenodesdetectingwasproposed．Integratedfeaturevalueandgainfunctionareemployedinthenewalgorithm．Comprehensiveeigenvaluewhichi8relatedtothenodedegr

5、eeandclusteringcoefficientiSusedtodetectcorenodesincommunityandthegainfunctionjudgeswhentogetthebestpartitionofcommunitystructure．ThenewalgorithmisimplementedwithC++．Experimentalresultsontheclassicdatasetsdemonstratethefeasibilityandeffectivenessofthealgor

6、ithm．Further，theparametercanbetunedtogetmoredetailedstructureofthecomplexnetworkthantraditionalalgorithmwhichisveryusefulinmanysituations．Keywords：complexnetwork；communitystructure；corenode；comprehensiveeigenvalue(CE)；gainfunction20世纪90年代以来，以Internet为代表的信解

7、决的基本问题；大多数社区发现算法虽然性能息技术的迅猛发展使人类社会大步迈人了网络时优越，但所需计算量却很大．这说明复杂网络中社代．人类社会的日益网络化给生产和生活带来了区发现的研究还需要付出大量的努力．聚类巨大的便利，也带来了一定的负面冲击，因此，需(clustering)直被认为是最重要的无监督学习问要人们对各种人工和自然的复杂网络行为有更好题E3J，本文以聚类为根本提出一种基于核心节点的认识．通信网络、电力网络、生物网络和社会网查找的可获得网络细节信息的社区发现方络等分别是通信科学、电力科学、生命科学和

8、社会法[4—51．科学等不同学科的研究对象，而复杂网络理论所1相关概念介绍要研究的是看上去不同的复杂网络之间的共性和处理它们的普适方法_1j．尽管复杂网络的社区本算法在复杂网络的图表示、节点的度数、簇发现问题得到了大量的研究，但还存在一些尚未系数、社区定义等概念的基础上，给出综合特征值收稿日期：2011—08—09基金项目：国家自然科学基金资助项目(60872040)；辽宁省自然科学基金资助项目(20102059