8.22 基于演化优化的网络社区检测
社区是网络中一部分节点的集合，同一个社区中的节点拥有相似的特征和性质。一般来说，社区内边的连接密度要大于社区间边的连接密度。网络社区检测就是通过一定的算法发现网络的社区结构。网络社区检测对于研究和分析潜在的网络拓扑结构具有十分重要的意义[1] 。
适应度函数
1 . 基于单目标优化模型的社区检测
● 模块度模型
模块度 (Q) 是单目标优化中使用最广泛的适应度函数，模块度的概念最早是由 Newman et al [2]提出的。其公式如下：
其中 n 和 m 分别表示网络中节点和边的数量。如果节点 i 和 j 在同一个社区，那么 =1；否则=0。Q值越大说明社区的划分效果越好。但是，将模块度作为适应度函数依然存在一些问题[3] ：第一，优化模块度是 NP-hard 问题；第二，模块度存在分辨率极限。为了解决这些问题，科学家又提出了一些新的评价指标，如扩展模块度[4]等。同时针对加权、有向及自循环的网络又提出了新的评价指标 Q sw [5] 。文献 [6-7] 中对 Q sw 调整后将其应用于解决有向、加权网络的社区检测问题。
在现实生活中，很多网络中的节点往往不只属于某一个社区，文献 [8] 提出了新的模块度指标来检测网络中的重叠社区结构。除了以上的模块度评价标准，文献 [9] 提出了局部模块度指标；文献 [10]提出了二分模块度指标。
● 多分辨率模型
多分辨模型的提出是为了解决分辨率限制的问题。文献[11]提出了新的适应度函数——模块密度(D)。
2 . 基于多目标优化模型的社区检测
● 一般网络模型
将最大化社区内连接和最小化社区间连接作为两个目标，文献 [12] 提出了基于多目标演化优化的社区检测算法 MOGA-Net。在该方法中，社区检测被建模成多目标优化问题，并采用 NSGA-II 的框架解决这个问题。文献 [13] 提出了基于 MOEA/D 的多目标社区检测算法，这个工作的最大创新点在于采用了新的多目标模型。文献 [14] 提出了一个三目标优化模型。另外，文献 [15-16] 总结了多目标社区检测中目标函数的选择。
● 符号网络模型
对于符号网络的社区检测，文献 [17] 提出了基于 signed ratio association 和 signed ratio cut 的两目标模型；文献 [18] 采用 NSGA-II 的符号网络社区检测模型。
● 重叠网络模型
前面我们指出在现实生活中一些网络中的节点往往不只属于某一个社区。针对网络的重叠社区检测，文献 [19] 设计了一个基于三目标的演化优化算法，其中一个目标函数用于控制社区划分的质量，另外两个相互矛盾的目标函数用于权衡社区之间的重叠程度。
● 动态网络模型
动态网络是随着时间不断变化的特殊网络，分析动态网络可以有效地预测未来的变化趋势。学者们针对动态网络的社区检测设计了一系列的演化算法[20-21] 。
个体表示
在社区检测这类问题中，每个个体都代表了一个网络划分。一般来说，初始化个体时有两种典型的个体表示方式，一种是基因座编码方式[12-13] ；另一种是字符串编码方式[22-24] 。
基因座编码方式显性地表达了网络的连接关系，但是相应的算子，如交叉、变异算子很难设计。字符串编码方式简单，并且有利于初始化编码和遗传算子设计。
遗传算子
交叉和变异是最常用的遗传算子，目的是产生新的后代种群以利于繁殖更新。对于基因座编码方式来说，均匀交叉和两点交叉是目前解决社区检测问题的最具有代表性的交叉算子。均匀交叉和两点交叉都能保持网络中的有效连接，文献 [12-13] 采用了均匀交叉的方式；文献 [13,25-26] 采用了两点交叉的方式。对于字符串编码方式来说，使用最广泛的交叉算子是单向交叉和双向交叉，双向交叉是对单向交叉的改进，它可以有效地结合父代个体共同的优秀特征。
最常用的变异算子是基于邻居的单点变异算子[12,22-24] ，它可以有效地避免对搜索空间的无效搜索，大大提高了算法的效率。
局部搜索
为了提高社区检测问题的搜索能力，在演化算法中常常引用了局部搜索方法。在文献 [22] 中，作者设计了基于爬山策略的局部搜索算子。爬山策略实质上是一种贪婪算法，通过对解的小幅度改变以得到目标值最大程度的提高。但是文献 [22] 提出的局部搜索方法容易造成无效搜索，往往使得算法效率较低。为了提高局部搜索的效率，学者们又提出了一些基于启发式的局部搜索方法。划分社区时，没有边连接的两点被划分在同一个社区内的可能性很小。基于这个启示，在文献 [23] 中，作者提出在局部搜索中将节点分配给邻近的社区以获得目标值最大程度的提高。为了进一步提高搜索能力，文献[24] 提出了一个基于三层学习策略的局部搜索方法，可以同时提高种群多样性及算法的全局搜索能力。另外，文献 [27] 提出了一个多目标局部搜索方法，可以权衡算法的收敛速度和种群的多样性。