第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·