[科普中国]-基于进化多目标优化的社区发现算法

遗传算法1（简称GA）是一种由生物进化理论指导搜索算法。通过搜索来找到最优或者接近最优的解。

首先回顾模块度的数学意义，即网络中连接两个同种类型的节点的边（即同一社区内部的边）的比例减去在同样社区结构下任意连接这两个节点的边的比例的期望值。

第一个目标是使得每个社团内部的边数尽可能多，同时第二个目标是小使得网络尽可能划分为很多度较少的社团。这两个相互冲突的子目标反映了一个好的社团划分中两个不同的方面：内部链接紧密（即第一个子式），外部链接稀疏（即第二个子式）。模块度Q本质上就是这两个目标的折中。

当采用进化算法解决社团发现问题时，需要用基因型（genotype）来表示一个社团划分，即为该划分进行编码。同样，也需要对基因型进行解码，即表示它的划分结果。在此，我们使用了邻接点表示法，每个基因型包含了n个基因（n为网络中结点个数），每个基因表示了节点i的一个邻居结点编号。因此，第i个基因的值j表示了结点i和j之间有边相连，从社团划分结果来看，即结点i和j被划分到了同一社团。解码过程需要对图中每一个连通分量进行识别，隶属于同一个连通分量的所有结点被划分到同一个社团。