第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 ]则是采用二 分法对整个网络或网络的子图进行不断的二分来发 现社团 ,而每个染色体是包含网络所有节点的二进 制串 ,占用空间较大. 作者提出通过网络拓扑信息确定网络节点的距 离关系和聚类中心 ,结合模块度函数和遗传聚类分 析算法进行复杂网络社团结构的分析和发现
82- 智能系统学报 第4卷 1遗传聚类的社团发现方法 :与其他网络上节点之间的最短路径来确定这两 个节点之间的距离相似或相异程度人.相异性指数 遗传聚类方法是通过进化迭代把数据对象划分 的定义如下： 到不同的簇中.通常随机选取k个对象作为初始的k 个簇的质心：然后，根据簇中心和其他对象之间的距 离关系来进行簇的划分.采用遗传聚类方法来实现 N(1 N-2) (1) 复杂网络的社团发现，主要存在两个问题：一是网络 其中：d和d为节点i到节点k的最短路径 的拓扑信息很难直接映射为聚类中心和其他对象之 Newman等人考虑了社团内部边和连接社团之 间的距离关系；二是需要根据聚类中心和网络的社 间的边的数量关系，提出了模块度作为网络划分质 团结构确定遗传算法的适应度函数 量的度量标准1在本文中，以模块度Q来确定种 本文提出的社团发现方法首先获取网络的拓扑 群中个体的适应度.在N个节点的无向网络G(y 信息，并计算所有节点对的相异性指数[6](dissmi- E)中，V是节点集，E是边集.网络的模块度定义为 larity index);然后，通过节点的相似度度量标准进 0=∑(e-a,2 2 行社团划分，以网络社团结构的模块度作为算法的 式(2)中：e是网络中第个社团内部连接各节点的 适应度函数控制进化过程.该算法不需要将网络拓 边在网络所有边的数目中所占的比例；a,表示与第 扑信息映射为n维数据空间，而且染色体占用的空 个社团中的节点相连的边在网络所有边的数目中 间较少：另外，算法最终的结果可直接对应于发现的 所占的比例 网络社团结构 在进化迭代时，根据种群中个体所代表的k个 11编码及初始化种群 社团中心节点，用相异性指数作为度量将每个网络 复杂网络社团发现的求解结果是得到已发现社 节点划分到距离自己最近的社团.得到k个社团 团的聚类中心.因此，在编码时不采用二进制方式， 聚类)后再计算网络的模块度，以此作为种群中每 而是直接以网络节点的编号构造染色体.一个社团 个个体的适应度，用于后续的遗传操作 的网络中心节点代表一个基因（即问题的求解结 13遗传算子 果)，多个聚类中心节点的编号连接在一起形成串. 在进行遗传操作时，根据每个个体的适应度进 图1中的染色体代表k个社团的聚类中心 行选择、交叉和变异操作.选择操作采用轮盘的方式 Community Center ld 5 来确定进行交叉操作的个体.适应度越大的个体选 Community Center Id, 32 中进行交叉的概率也就越大.个体交叉后，从上一代 Community Center Id, 12 种群中选择出来的一些优良的个体遗传到下一代种 ，， 群中 Community Center ld 9 在交叉操作时，选取父辈种群的配对个体.通过 随机选取交叉点，交换它们的部分基因.交叉使得遗 图1算法中染色体的编码方式 传信息得到交换，种群获得新一代的个体.交叉的方 Fig 1 Chromosome representation of the algorithm 式如下图所示 parentI 两个新的个体 初始化种群时，随机地从网络中选取k个节点 parent2 作为k个社团的聚类中心参数k的确定将在14 5 4 5 4 节讨论)来建立染色体种群中的个体数量由参数p 32 17 32 17 交叉点 交叉 设定，因此整个种群所占用的空间为k如 12 15 15 12 12适应度函数 计算种群中每个个体的适应度，首先要确定网 9 33 33 络中节点之间的距离关系，这样才能明确各个网络 节点与社团中心节点的相似程度，以便将网络节点 图2算法中染色体的交叉操作 划分到离自己最近的社团.网络节点之间的相似度 Fig 2 Crossover operation of chromosome in algorithm 采用相异性指数6进行度量，也就是通过两个节点 在初始化种群和进行交叉操作时，同一个染色 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1 遗传聚类的社团发现方法 遗传聚类方法是通过进化迭代把数据对象划分 到不同的簇中. 通常随机选取 k个对象作为初始的 k 个簇的质心 ;然后 ,根据簇中心和其他对象之间的距 离关系来进行簇的划分. 采用遗传聚类方法来实现 复杂网络的社团发现 ,主要存在两个问题 :一是网络 的拓扑信息很难直接映射为聚类中心和其他对象之 间的距离关系 ;二是需要根据聚类中心和网络的社 团结构确定遗传算法的适应度函数. 本文提出的社团发现方法首先获取网络的拓扑 信息 ,并计算所有节点对的相异性指数 [ 6 ] ( dissim i2 larity index) ;然后 ,通过节点的相似度度量标准进 行社团划分 ,以网络社团结构的模块度作为算法的 适应度函数控制进化过程. 该算法不需要将网络拓 扑信息映射为 n维数据空间 ,而且染色体占用的空 间较少 ;另外 ,算法最终的结果可直接对应于发现的 网络社团结构. 1. 1 编码及初始化种群 复杂网络社团发现的求解结果是得到已发现社 团的聚类中心. 因此 ,在编码时不采用二进制方式 , 而是直接以网络节点的编号构造染色体. 一个社团 的网络中心节点代表一个基因 (即问题的求解结 果 ) ,多个聚类中心节点的编号连接在一起形成串. 图 1中的染色体代表 k个社团的聚类中心. 图 1 算法中染色体的编码方式 Fig. 1 Chromosome rep resentation of the algorithm 初始化种群时 ,随机地从网络中选取 k个节点 作为 k个社团的聚类中心 (参数 k的确定将在 1. 4 节讨论 )来建立染色体. 种群中的个体数量由参数 p 设定 ,因此整个种群所占用的空间为 k ×p. 1. 2 适应度函数 计算种群中每个个体的适应度 ,首先要确定网 络中节点之间的距离关系 ,这样才能明确各个网络 节点与社团中心节点的相似程度 ,以便将网络节点 划分到离自己最近的社团. 网络节点之间的相似度 采用相异性指数 [ 6 ]进行度量 ,也就是通过两个节点 i, j与其他网络上节点之间的最短路径来确定这两 个节点之间的距离 (相似或相异程度 ). 相异性指数 的定义如下 : Λ( i, j) = ∑ N k≠i, j [ dik - djk ] 2 (N - 2) . (1) 其中 : dik和 djk为节点 i, j到节点 k的最短路径. Newman等人考虑了社团内部边和连接社团之 间的边的数量关系 ,提出了模块度作为网络划分质 量的度量标准 [ 7 ] . 在本文中 ,以模块度 Q 来确定种 群中个体的适应度. 在 N 个节点的无向网络 G (V, E)中 , V是节点集 , E是边集. 网络的模块度定义为 Q = ∑( eii - ai ) 2 . (2) 式 (2)中 : eii是网络中第 i个社团内部连接各节点的 边在网络所有边的数目中所占的比例; ai 表示与第 i个社团中的节点相连的边在网络所有边的数目中 所占的比例. 在进化迭代时 ,根据种群中个体所代表的 k个 社团中心节点 ,用相异性指数作为度量将每个网络 节点划分到距离自己最近的社团. 得到 k个社团 (聚类 )后再计算网络的模块度 ,以此作为种群中每 个个体的适应度 ,用于后续的遗传操作. 1. 3 遗传算子 在进行遗传操作时 ,根据每个个体的适应度进 行选择、交叉和变异操作. 选择操作采用轮盘的方式 来确定进行交叉操作的个体. 适应度越大的个体选 中进行交叉的概率也就越大. 个体交叉后 ,从上一代 种群中选择出来的一些优良的个体遗传到下一代种 群中. 在交叉操作时 ,选取父辈种群的配对个体. 通过 随机选取交叉点 ,交换它们的部分基因. 交叉使得遗 传信息得到交换 ,种群获得新一代的个体. 交叉的方 式如下图所示. 图 2 算法中染色体的交叉操作 Fig. 2 Cross2over operation of chromosome in algorithm 在初始化种群和进行交叉操作时 ,同一个染色 ·82· 智 能 系 统 学 报 第 4卷
第1期 朱大勇，等：遗传聚类的社团结构发现 ·83· 体中可能出现相同聚类中心节点)的情况，因此需 行了社团发现实验.实验结果表明该算法有效并获 要对相同的中心节点进行变异处理，即通过随机选 得了较好的社团划分.同时，相对于文献[3.5用网 取网络节点的方式改变原有染色体中出现的相同基 络中所有节点来构造染色体，本文所提出的算法占 因相同的中心节点).通过这种方式，保证了在遗 用更少的空间 传过程中，进行节点聚类时社团数目不会发生变化. 21 Zachary Karate Clubl网络 变异的过程如图3所示。 Zachary Karate Club网络是社会学的经典研究 之一.它描述了美国一所大学中空手道俱乐部会员 相互间的社会关系.网络中共有节点34个，如图4 32 重复 32 所示.应用遗传聚类的方法，设置种群个数50个，在 变异 6 迭代50次后，网络划分为两个社团所计算的个体适 应度网络模块度)Q=037146614,这和实际网络 9 9 的社团划分情况一致 图3算法中染色体的变异操作 13 Fig 3 Mutation operation of chromosome in algprithm 14算法流程及参数 28 根据遗传聚类的方式，对网络社团中心节点进 29 行进化迭代，算法的流程如下： 1)根据给定的网络，计算网络中所有节点对的 7 19 26 相异性指数， 17 2设置遗传迭代参数，包括迭代次数和种群个数 图4 Zachary Karate Club网络的社团结构 3)随机初始化种群中的个体，如果发现个体中 Fig 4 Community structure of Zachary Karate Club netork 有相同的聚类中心，则对该个体进行变异操作 22 College Football网络 4)重复进化迭代： College Footballl网络是Newman等人对美国大 a)选取个体对进行交叉，如果新个体产生相同 学生橄榄球联赛的2000个赛季的比赛情况进行分 的聚类中心节点，则进行变异操作； 析整理而建立的网络模型，它包含115个节点及 b计算新种群中每个个体的适应度计算网络 616边.用本文的算法进化迭代100次，将网络划分 划分的模块度)和整个种群的最大适应度： 为12个社团，适应度达到056183589.该结果与实 c如果上一代种群的最大适应度大于下一代 种群的最大适应度，则将下一代种群中具有最小适 际社团的划分一致.图5显示了College Footballl网 络的结构 应度的个体替换为上一代种群中具有最大适应度的 个体： d)当种群中适应度最大的个体没有改变或迭 代次数到达设定的范围时则终止算法， 在复杂网络社团发现中，不用人工干涉而自动 确定社团的个数k即聚类网络中心节点数)是一个 复杂的问题.有的算法将其转换为某种阈值来进行 分析，但这也仅仅是将确定社团个数变成了确定另 外一个参数.在本文中首先对网络进行二分，然后根 据网络模块度在优化过程中是否收敛即平方误差 准则函数是否小于指定的值)来确定参数k 2实验结果 为了验证所提出的方法的有效性和可行性，对 图5 College Football网络结构 Fig 5 Netork structure of College Football Zachary Karate Club网络和College Footballl网络进 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
体中可能出现相同聚类中心 (节点 )的情况 ,因此需 要对相同的中心节点进行变异处理 ,即通过随机选 取网络节点的方式改变原有染色体中出现的相同基 因 (相同的中心节点 ). 通过这种方式 ,保证了在遗 传过程中 ,进行节点聚类时社团数目不会发生变化. 变异的过程如图 3所示. 图 3 算法中染色体的变异操作 Fig. 3 Mutation operation of chromosome in algorithm 1. 4 算法流程及参数 根据遗传聚类的方式 ,对网络社团中心节点进 行进化迭代 ,算法的流程如下 : 1)根据给定的网络 ,计算网络中所有节点对的 相异性指数. 2)设置遗传迭代参数,包括迭代次数和种群个数. 3)随机初始化种群中的个体 ,如果发现个体中 有相同的聚类中心 ,则对该个体进行变异操作. 4)重复进化迭代 : a)选取个体对进行交叉 ,如果新个体产生相同 的聚类中心节点 ,则进行变异操作; b)计算新种群中每个个体的适应度 (计算网络 划分的模块度 )和整个种群的最大适应度; c)如果上一代种群的最大适应度大于下一代 种群的最大适应度 ,则将下一代种群中具有最小适 应度的个体替换为上一代种群中具有最大适应度的 个体; d)当种群中适应度最大的个体没有改变或迭 代次数到达设定的范围时则终止算法. 在复杂网络社团发现中 ,不用人工干涉而自动 确定社团的个数 k (即聚类网络中心节点数 )是一个 复杂的问题. 有的算法将其转换为某种阈值来进行 分析 ,但这也仅仅是将确定社团个数变成了确定另 外一个参数. 在本文中首先对网络进行二分 ,然后根 据网络模块度在优化过程中是否收敛 (即平方误差 准则函数是否小于指定的值 )来确定参数 k. 2 实验结果 为了验证所提出的方法的有效性和可行性 ,对 Zachary Karate Club网络和 College Football网络进 行了社团发现实验. 实验结果表明该算法有效并获 得了较好的社团划分. 同时 ,相对于文献 [ 3, 5 ]用网 络中所有节点来构造染色体 ,本文所提出的算法占 用更少的空间. 2. 1 Zachary Karate Club网络 Zachary Karate Club网络是社会学的经典研究 之一. 它描述了美国一所大学中空手道俱乐部会员 相互间的社会关系. 网络中共有节点 34个 ,如图 4 所示. 应用遗传聚类的方法 ,设置种群个数 50个 ,在 迭代 50次后 ,网络划分为两个社团所计算的个体适 应度 (网络模块度 ) Q = 0. 371 466 14,这和实际网络 的社团划分情况一致. 图 4 Zachary Karate Club网络的社团结构 Fig. 4 Community structure of Zachary Karate Club network 2. 2 College Football网络 College Football网络是 Newman等人对美国大 学生橄榄球联赛的 2 000个赛季的比赛情况进行分 析整理而建立的网络模型 ,它包含 115个节点及 616边. 用本文的算法进化迭代 100次 ,将网络划分 为 12个社团 ,适应度达到 0. 561 835 89. 该结果与实 际社团的划分一致. 图 5显示了 College Football网 络的结构. 图 5 College Football网络结构 Fig. 5 Network structure of College Football 第 1期 朱大勇 ,等 :遗传聚类的社团结构发现 ·83·
·84 智能系统学报 第4卷 [5 ]L U Xin,LIDeyi WANG Shuliang,et al Effective algo- 3结束语 rithm for detecting community structure in complex networks 在网络数据分析中，复杂网络的社团发现是一 based on GA and clustering [J ]Lecture Notes in Computer Science,2007,4488:657-664 个非常具有挑战性的问题.本文以相异性指数作为 [6 ZHOU Haijun Distance,dissm ilarity index and network 网络节点的距离度量，结合模块度提出用遗传聚类 community structure [J ]Phys Rev E,2003,67 (6): 来分析和发现网络社团结构.相对于其他算法而言， 061901 该方法以聚类中心作为染色体，减少了种群的空间 [7]NEWMAN M E J,GRVAN M.Finding and evaluating 占用：同时，不需要将网络拓扑信息（邻接矩阵）映 community structure in netorks [J].Phys Rev E,2004, 射到维数据空间，减少了数据的失真.聚类结果也 69(2):026113 不需要进行还原处理可直接得到已划分的社团结 作者简介： 构，降低了算法的复杂性.利用网络的拓扑信息改进 朱大勇，男，1975年生，讲师.主要 研究方向为复杂网络、对等计算、分布 算法的选择、交叉和变异操作以增加个体的多样性， 式信息检索、软件工程.参加过多项科 提高算法的收敛速度，是今后进一步的研究方向。 研项目，发表学术论文20余篇」 参考文献： [1 ]NEWMAN M E J.Fast algprithm for detecting community structure in netorks [J ]Phys Rev E,2004,69 (6): 张新丽，女，1973年生，副教授.主 066133. 要研究方向为复杂系统、神经网络.参 [2]GRVAN M,NEWMAN M E J.Community structure in so- 加过多项科研项目，发表学术论文10 cial and biolgical netorks [J ]Proc Natl Acad Sci, 余篇 2001,99:7821-7826 [3]TASGN M,HERDAGDELEN A,B NGOL H Community detection in complex neworks using genetic algorithms [J /OL ]2008-09-13 ]http://arxiv org/abs/0711. 侯晓荣，男，1966年生，教授、博士 0491. 生导师.主要研究方向为智能推理、机 [4浏婷，胡宝清.基于聚类分析的复杂网络中的社团探 器证明.参加过多项科研项目，发表学 测[J]复杂系统与复杂性科学，2007,4(1)：2835 术论文30余篇. LU Ting.HU Baoqing Detecting community in complex netorks using cluster analysis[J ]Comp lex Systems and Complexity Science,2007,4(1):28-35. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
3 结束语 在网络数据分析中 ,复杂网络的社团发现是一 个非常具有挑战性的问题. 本文以相异性指数作为 网络节点的距离度量 ,结合模块度提出用遗传聚类 来分析和发现网络社团结构. 相对于其他算法而言 , 该方法以聚类中心作为染色体 ,减少了种群的空间 占用 ;同时 ,不需要将网络拓扑信息 (邻接矩阵 )映 射到 n维数据空间 ,减少了数据的失真. 聚类结果也 不需要进行还原处理可直接得到已划分的社团结 构 ,降低了算法的复杂性. 利用网络的拓扑信息改进 算法的选择、交叉和变异操作以增加个体的多样性 , 提高算法的收敛速度 ,是今后进一步的研究方向. 参考文献 : [ 1 ]NEWMAN M E J. Fast algorithm for detecting community structure in networks [ J ]. Phys Rev E, 2004, 69 ( 6) : 066133. [ 2 ] GIRVAN M, NEWMAN M E J. Community structure in so2 cial and biological networks [ J ]. Proc Natl Acad Sci, 2001, 99: 782127826. [ 3 ] TASGIN M, HERDAGDELEN A, B INGOL H. Community detection in comp lex networks using genetic algorithm s [J /OL ]. [ 2008209213 ]. http: / / arxiv. org/ abs/0711. 0491. [ 4 ]刘 婷 , 胡宝清. 基于聚类分析的复杂网络中的社团探 测 [J ]. 复杂系统与复杂性科学 , 2007, 4 (1) : 28235. L IU Ting, HU Baoqing. Detecting community in comp lex networks using cluster analysis[ J ]. Comp lex System s and Comp lexity Science, 2007, 4 (1) : 28235. [ 5 ]L IU Xin, L IDeyi, WANG Shuliang, et al. Effective algo2 rithm for detecting community structure in comp lex networks based on GA and clustering [J ]. Lecture Notes in Computer Science, 2007, 4488: 6572664. [ 6 ] ZHOU Haijun. D istance, dissimilarity index and network community structure [ J ]. Phys Rev E, 2003, 67 ( 6 ) : 061901. [ 7 ] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks [J ]. Phys Rev E, 2004, 69 (2) : 026113. 作者简介 : 朱大勇 ,男 , 1975年生 ,讲师. 主要 研究方向为复杂网络、对等计算、分布 式信息检索、软件工程. 参加过多项科 研项目 ,发表学术论文 20余篇. 张新丽 ,女 , 1973年生 ,副教授. 主 要研究方向为复杂系统、神经网络. 参 加过多项科研项目 ,发表学术论文 10 余篇. 侯晓荣 ,男 , 1966年生 ,教授、博士 生导师. 主要研究方向为智能推理、机 器证明. 参加过多项科研项目 ,发表学 术论文 30余篇. ·84· 智 能 系 统 学 报 第 4卷