下载掌阅APP，畅读海量书库
立即打开
复杂网络是复杂系统（比如万维网、在线社区、组织系统、商业系统、电网系统、神经系统、新陈代谢系统、食物链网络、合作系统、疾病控制系统、资源分配系统、交通系统、信息预测与推荐系统等）的重要研究方向 [22-23] ，如何使用高效计算模型分析、挖掘和解译庞大数据中的潜在有用信息是复杂网络的重要研究内容。复杂网络不仅能有效展现网络单元（节点）之间相互作用的拓扑结构特性及其动态演化过程，还能够很好地表达复杂系统数据间的潜在关联及其功能特性。在复杂网络的表示方法中，节点（顶点）代表复杂系统的基本实体，边（链接）则表示系统中实体间的相互作用方式或关系 [24-25] 。
在生物系统的研究中，生物分子间复杂的相互作用被抽象为网络模型。分子网络描述了各种不同的生物活动进程是如何运作的，包括细胞间信号传递、新陈代谢和基因调控等，通常将这些生物分子网络看作一个系统来分析它们所完成的生物功能 [26] 。在社交网络中，把人作为节点，人与人之间的交流建模为边，通过对该网络的分析，可以把社交网络分成多个子网络（相当于社团）。同时还可以找到网络中最有影响力的节点，即找到社交网络中的核心人。
社区检测就是把复杂网络划分，找到具有共同点的网络节点，进一步研究网络性质。在实际应用中，社区检测可以为相同社区的用户提供更准确的服务，对电路系统、物流系统等进行全局优化，在资源分配和疾病控制上也能起到重要作用。用于社区检测的方法有很多，如传统的基于优化规则的贪心算法、多阶段贪心算法 [78] 、遗传算法等，这些算法的缺点均是容易陷入局部最优。下面将介绍Memetic算法在社区检测上的具体应用。Memetic算法通过将全局搜索与局部搜索机制相结合的思路，在一定程度上缓解了陷入局部最优的问题。
在解决实际问题时，其目标往往不是单一的，而是多个目标的优化，如购买商品时则是希望它既好又便宜，所以多目标问题的求解非常重要，同时多目标优化不同于单目标优化时只存在一个解，多目标优化的解是一组互相无法比较优劣的解集。多目标Memetic算法的思想就是把多目标遗传算法全局优化的框架和一个或多个的局部优化算法混合，形成新算法。常用的求解多目标问题的遗传算法方法包括基于支配的NSGA-Ⅱ [27] 和基于分解的MOEA/D [28] 。
对于一个无向网络，可以将它表示为 G =（ V ， E ），其中 V 表示节点集， E 表示网络中边的集合。网络的邻接矩阵为 A ，若节点 i 与节点 j 连接，则 A ij =1，反之为0。设有两个不相交的节点子集 V 1 和 V 2 ，即 V 1 ∩ V 2 =Ø、 V 1 ∈ V 、 V 2 ∈ V 。则模块密度 D 定义为：
其中，
，表示
V
i
节点集内部的所有边；
表示
V
i
内部节点到外部节点的边；
表示
V
i
内的节点数。将模块密度
D
差分成两部分，即可构成多目标Memetic优化算法的两个目标函数，第一个目标函数NAR（Negative Ratio Association）反映了社区内节点连接的紧密程度，第二个目标函数RC（Ratio Cut）反映了社区间的分离程度。将目标函数规范为最小化问题，则最终的多目标函数为：
在解决社区检测类问题时，因为每个节点都有自己的社区编号，所以可以将个体 x a 编码为：
其中， x ai 代表个体 x a 对节点 v i 赋予的标签，它的取值范围即为社区编号范围。若 x ai = x aj 则认为节点 v i 和 v j 在同一编号的社区中，否则不在同一社区。
常用的局部搜索方法有模拟退火算法、爬山算法、禁忌搜索算法等。这里将介绍模拟退火算法和一种基于节点层、社区层、集群层的多层学习策略。
模拟退火算法不同于其他的局部搜索算法，它会以一定的概率保留较差的解，给解集带来多样性。其算法描述如表3.1所示。
表3.1 模拟退火算法描述
其中， T e 是初始温度，需要提前设置为一个较高的值； θ 是退火因子，用来控制该算法的退火速度，由表3.1可以看出，该值越大退火速度越慢； P best 表示输入解集中适应度值最高的解（染色体）； P' 表示输入解集的邻居解，在社区检测中，相当于新的社区划分，是与已有划分相似的邻居解； F 表示适应度函数，在基于分解的多目标遗传算法中， F 是子问题上的适应度函数。
多层学习策略是一种基于多层学习来改善个体解 x 的局部搜索方法。基于多层学习的局部搜索策略是根据网络节点、社区和集群结构的特定邻域知识而提出的，它由3个从低层次到高层次的学习策略组成。每一层次的学习策略都能够快速收敛到局部最优解。高层次学习策略能有效地帮助低层次学习策略跳出其所得到的局部最优解。
1）节点层学习策略
节点层学习策略作用在网络中的每一个节点上，其过程如表3.2所示，其中
x
a
表示一个染色体。给定一个
N
节点的网络
G
，节点层学习策略如下：首先生成一个随机序列
R
（{
r
1
，
r
2
，…，
r
N
}），然后根据序列中的顺序选择节点
，利用标签传播规则或其他融合策略更新该节点的标签
。重复上述过程直到每个节点的社区标签都不改变为止。节点层学习策略有助于遗传算法快速收敛到搜索空间的局部最优解，同时遗传算法也可以帮助节点层学习跳出局部最优，去搜索下一个更优的局部最优解。
表3.2 节点层学习算法流程
2）社区层学习策略
社区层学习策略作用在前一层的解
x
a
上。假设染色体
x
a
划分出了
个社区，命名为社区
C
1
，
C
2
，…
。把每个社区里的所有点看成是一个合在一起的新点，即社区
C
1
是个新节点
，由此构造的点称为超级节点，并由超级节点构成新网络
G'
。表3.3为社区层学习策略算法流程，其中函数表示进行节点层学习策略。需要注意的是超级节点间的连接问题，若
v
i
∈
C
a
，
v
j
∈
C
b
且
v
i
，
v
j
间有连接，则认为由
C
a
、
C
b
形成的超级节点
、
间有连接，且超级节点
C
a
、
C
b
间连接的权重为边数之和。
表3.3 社区层学习算法流程
社区层学习策略也用来帮助节点层学习策略跳出局部最优解，但是因为错误被合并在一个社区的节点，无法在该层学习中被分开，所以这两层的学习策略依然容易陷入局部最优解。
3）集群层学习策略
集群层学习策略的过程如表3.4所示。它作用在两个染色体
x
g
、
x
e
上，其中
是种群中的最优染色体，
是前一层社区层学习产生的解。集群层学习策略包含两个阶段。第一阶段为，对
x
g
中的每一个划分的社区
C
i
，
所对应的节点，根据下面两个原则重新分配到社区中。
（1）如果节点 v j 、 v k 在解 x g 、 x e 上被划分为同一社区内，则在新解上被分到该社区中；
（2）如果节点 v j 、 v k 在 x g 中被划分在同一社区，而在 x e 中被划分为不同社区，则在新解中也被划分到不同社区内。
定义第一阶段返回的解为
。第二个阶段是在
x
f
上使用前两层学习策略以便得到更好的社区划分。在表3.4中，函数NodeLearning（）和CommunityLearning（）分别表示节点层学习策略和社区层学习策略。最终集群层学习策略将返回一个新的染色体
x
l'
。
表3.4 集群层学习策略
集群层学习策略能够帮助前两层学习策略跳出局部最优解。首先，前两层学习策略陷入局部最优的主要原因在于被合并的多个节点和社区很难被再次分开 [29] 。而集群层学习策略就可以解决该问题，分开合并的节点和社区。同时重组的社区还可以获得更高的模块度。其次，集群层学习策略是作用于两个解上的集成聚类技术。新解将得到这两个解上相同的部分，不同的部分被分开。因此，集群层学习策略收集了来自两个或更多解的社区模式结构特性。
由上述两种局部搜索机制可以看出，局部搜索有助于在全局搜索过程中找到当前最优解的邻域内优于该个体的新解，加快了算法的收敛速度，同时优良的局部搜索机制还可以改善算法本身容易陷入局部最优解的情况，如上述提到的多层学习策略，多层机制增大了邻域搜索的能力，增加了新解的多样性，因此更有可能找到最优解。