论文:M. Tasgin, A. Herdagdelen, H. Bingol, Community detection in complex networks using genetic algorithms, arXiv: Physics and Society, 2008.

背景介绍

接论文阅读笔记一,这一篇论文仍然是复杂网络领域中社团划分这一研究方向,不同于传统划分方法,作者在这篇论文中首次提出将遗传算法应用于社团划分,证明这一可行性。仍然是选择模块度作为适应度函数,目的为获得其全局最优解。
$$
Q = \Sigma_i(e_{ii} - a_i^2)
$$
不同于一般的模块度表示,上式是模块度的另一种表示,其中i遍历所有社团,$e_{ii}$是两节点均在社团i中边的数量占网络中总边数比例,$a_i$是至少一个节点在社团i中边的数量占网络总边数的比例。

不同于以往的划分方法,作者提出的基于遗传算法的划分方法无需提前指定社团划分数量,而社团划分数量正是在遗传算法所体现的结果。

表示方法

无向图$G(V,E)$中$|V|$表示n个节点,$|E|$表示e条边。约定节点的固定顺序为:$V = {v_1, v_2, ..., v_n}$,$V$的划分$\Omega$用n维向量$\kappa = [k^1, k^2, ..., k^n]$表示,其中$k^i\epsilon{1, 2, ..., |\Omega|}$,其作为节点$v_i$的社团下标。

遗传算法

初始化阶段

这一阶段,先随机初始化,后随机选取邻居节点加入至同一社团。

交叉操作

两个父母染色体分别称为$\kappa_{src}, \kappa_{dest}$,随机选择一个节点$v_i$,将$K_{src}$中该节点的社团复制到$K_{dest}$上,这样的操作重复多次。

变异操作

随机选取一个染色体$\kappa$,随机选取两个节点$v_{j},v_{i}$,将这两个节点所在的社团融合。

实验结果

在实验中使用多套遗传算法参数,$g$为迭代的代数,定义$S$作为划分结果与真实结果的相差度,$S$值越小代表划分结果越好,反之越差,当$S=0$时,代表划分结果完全一致。(其实我个人以为这个地方可以直接使用NMI指数。)

计算机生成网络

一个关键的参数是$z_{out}$,它取值为${1,... ,12}$,当为12时,该参数描述了生成图社团结构的明显程度,当为12时生成图几乎为一个随机网络,当为0时,社团结构最为明显。作者实验中选取了128个节点,平均度为16的生成网络网络,对不同的$z_{out}$值分别生成100个网络,共计1200个网络。

首先给出多组不同$z_{out}$的结果:

当$z_{out}$为6时,n为128时,划分结果:

当$z_{out}$为6时,n为512时,划分结果:

大学生足球网络

实际数据集的划分结果:

总结

在实验中可以看到基于遗传算法的社团划分方法与传统方法结果相差不大,作者证明了将遗传算法应用于社团划分的可行性。在后续我们看到研究者们基于此作出的各种优化。