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.net1 遗传聚类的社团发现方法 遗传聚类方法是通过进化迭代把数据对象划分 到不同的簇中. 通常随机选取 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卷