第4卷第1期 智能系统学报 Vol 4 Na 1 2009年2月 CAA I Transactions on Intelligent Systems Feb 2009 遗传聚类的社团结构发现 朱大勇'，侯晓荣2，张新丽 (1电子科技大学计算机科学与工程学院，四川成都610054,2电子科技大学自动化工程学院，四川成都 610054,3成都信息工程学院数学与信息科学系，四川成都610054) 摘要：近年来在复杂网络中发现社团的结构引起了广泛的关注，目前已经提出了一些采用进化计算来分析复杂网 络社团结构的方法.但大部分算法还存在处理过程复杂，空间复杂度过高等问题.通过确定网络节点的距离关系和 聚类中心，提出一种新的基于遗传聚类的社团发现算法.将该算法用于真实网络的社团发现，实验结果验证了算法 的可行性和有效性. 关键词：社团结构；遗传聚类；相异性指数；模块度 中图分类号：1P18文献标识码：A文章编号：16734785(2009)01-0081-04 D iscovery of comm un ity structure ba sed on genetic clusterng ZHU Da-yong,HOU Xiao-rong,ZHANG Xini (1.College of Computer Science and Engineering.University of Electronic Science and Technobgy of China,Chengdu 610054,China, 2 College of Automation,University of Electronic Science and Technology of China,Chengdu 610054,China 3.Deparment ofMath and Infomation,Chengdu University of Infomation Technobgy,Chengdu 610054,China) Abstract:The discovery of community structure in complex netorks has received widespread attention in recent years Many methods based on evolutionary computation have been proposed to detect community structures in com- plex netorks,butmost of them are difficult to app ly and have high degrees of space-comp lexity In this paper we presented an algorithm for finding communities in complex netorks using a genetic algorithm which exam ines dis- tances beteen nodes and clustering centers It was tested with real network datasets and the results of experments demonstrated the feasibility of our algorithm. Keywords:community structure;genetic clustering dissm ilarity index,modularity 社团结构的识别和发现是复杂网络的一个重要 聚算法1，采用介数的分裂算法1等等.此外，基于 研究方向，近年来受到计算机科学、物理学和社会学 智能计算也提出了一些社团发现方法.Tasg㎡应 等领域科研人员的广泛关注.大量的研究表明真实的 用遗传算法进行社团发现，该算法需要进行比较复 复杂网络可以自然地分解为社团(communities)或模 杂的处理，以及需要增加额外的计算来进行纠错.文 块(modules)).在每个社团内部，节点之间的连接紧 献[4]采用谱平分将网络拓扑映射为n维空间的数 密，而社团与社团之间的连接相对来说较稀疏.社团 据，然后采用遗传聚类的方法探测网络中的社团：但 结构反映了网络元素之间的拓扑关系，且对应于网络 是，该算法在获得聚类中心后需要将数据进行转换 中的行为和功能单元.社团结构自动发现的研究有助 才能还原为相应的社团结构.文献[5则是采用二 于更好的理解和分析网络的结构和行为特性。 分法对整个网络或网络的子图进行不断的二分来发 目前，己经提出了很多社团发现的算法，包括凝 现社团，而每个染色体是包含网络所有节点的二进 制串，占用空间较大 收稿日期：2008-1107 基金项目：国家自然科学基金资助项目(NSF℃-10571095)；国家973 作者提出通过网络拓扑信息确定网络节点的距 计划资助项目(NKBRPC-2004CB318003);成都信息工程 学院自然科学与技术发展基金资助项目(CSR200506). 离关系和聚类中心，结合模块度函数和遗传聚类分 通信作者：朱大勇.Email dayongzhu75@163.cm 析算法进行复杂网络社团结构的分析和发现， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 4卷第 1期 智 能 系 统 学 报 Vol. 4 №. 1 2009年 2月 CAA I Transactions on Intelligent System s Feb. 2009 遗传聚类的社团结构发现 朱大勇 1 ,侯晓荣 2 ,张新丽 3 (1. 电子科技大学 计算机科学与工程学院 ,四川 成都 610054; 2. 电子科技大学 自动化工程学院 ,四川 成都 610054; 3. 成都信息工程学院 数学与信息科学系 ,四川 成都 610054) 摘 要 :近年来在复杂网络中发现社团的结构引起了广泛的关注 ,目前已经提出了一些采用进化计算来分析复杂网 络社团结构的方法. 但大部分算法还存在处理过程复杂 ,空间复杂度过高等问题. 通过确定网络节点的距离关系和 聚类中心 ,提出一种新的基于遗传聚类的社团发现算法. 将该算法用于真实网络的社团发现 ,实验结果验证了算法 的可行性和有效性. 关键词 :社团结构 ;遗传聚类 ;相异性指数 ;模块度 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2009) 0120081204 D iscovery of commun ity structure based on genetic cluster ing ZHU Da2yong 1 , HOU Xiao2rong 2 , ZHANG Xin2L i 3 (1. College of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China; 2. College of Automation, University of Electronic Science and Technology of China, Chengdu 610054, China; 3. Department of Math and Information, Chengdu University of Information Technology, Chengdu 610054, China) Abstract: The discovery of community structure in comp lex networks has received widesp read attention in recent years. Many methods based on evolutionary computation have been p roposed to detect community structures in com2 p lex networks, but most of them are difficult to app ly and have high degrees of space2comp lexity. In this paper we p resented an algorithm for finding communities in comp lex networks using a genetic algorithm which exam ines dis2 tances between nodes and clustering centers. It was tested with real network datasets and the results of experiments demonstrated the feasibility of our algorithm. Keywords: community structure; genetic clustering; dissim ilarity index; modularity 收稿日期 : 2008211207. 基金项目 :国家自然科学基金资助项目 (NSFC210571095) ;国家 973 计划资助项目 (NKBRPC22004CB318003 ) ;成都信息工程 学院自然科学与技术发展基金资助项目 (CSRF200506). 通信作者 :朱大勇. E2mail: dayongzhu75@163. com. 社团结构的识别和发现是复杂网络的一个重要 研究方向 ,近年来受到计算机科学、物理学和社会学 等领域科研人员的广泛关注. 大量的研究表明真实的 复杂网络可以自然地分解为社团 ( communities)或模 块 (modules). 在每个社团内部 ,节点之间的连接紧 密 ,而社团与社团之间的连接相对来说较稀疏. 社团 结构反映了网络元素之间的拓扑关系 ,且对应于网络 中的行为和功能单元.社团结构自动发现的研究有助 于更好的理解和分析网络的结构和行为特性. 目前 ,已经提出了很多社团发现的算法 ,包括凝 聚算法 [ 1 ] ,采用介数的分裂算法 [ 2 ]等等. 此外 ,基于 智能计算也提出了一些社团发现方法. Tasgin [ 3 ]应 用遗传算法进行社团发现 ,该算法需要进行比较复 杂的处理 ,以及需要增加额外的计算来进行纠错. 文 献 [ 4 ]采用谱平分将网络拓扑映射为 n维空间的数 据 ,然后采用遗传聚类的方法探测网络中的社团 ;但 是 ,该算法在获得聚类中心后需要将数据进行转换 才能还原为相应的社团结构. 文献 [ 5 ]则是采用二 分法对整个网络或网络的子图进行不断的二分来发 现社团 ,而每个染色体是包含网络所有节点的二进 制串 ,占用空间较大. 作者提出通过网络拓扑信息确定网络节点的距 离关系和聚类中心 ,结合模块度函数和遗传聚类分 析算法进行复杂网络社团结构的分析和发现