复杂网络社区发现
发布时间：2020-07-07
点击次数：
背景：
社区发现指的是将复杂网络中的所有节点划分为多个节点集合，从而使得集合内部的节点连接紧密，而集合之间的节点连接疏松的过程，也被称为网络聚类。它对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为有着非常重要的理论意义，同时也可应用于各种社交网络个性化推荐系统的性能提升、传染病网络的风险预测等众多领域。社区发现问题在各个领域研究人员的持续探索下取得了一些发展，目前涌现了各式各样的社区发现算法。其中，基于智能优化算法的社区发现方法由于具有不需要提前给定网络中的社区个数，可以将专业领域的知识嵌入到算法的设计中等优点，近年来发展尤为迅速。然而，目前已有的基于智能优化算法的社区发现方法在求解精度和稳定性上仍然有待进一步提高，本研究目的是提出高精度、高稳定性的复杂网络社区发现方法，以满足实际社区发现任务的需要。
方法：
针对已有的社区发现算法在求解精度和稳定性上的不足，本研究提出了一种基于双层变换离散状态转移算法的复杂网络社区发现方法（MDSTA）。该算法主要包括种群初始化和进化、精英解种群的生成和局部搜索三个部分。为了保证算法的寻优性能，算法首先采用了基于标签传播的复杂网络社区结构初始化策略，接着利用离散状态变换算子对种群个体质量进行优化。具体地，算法分别设计了节点标签替换变换算子和社区标签替换变换算子这两种不同层次的社区发现算子进行全局寻优操作。同时，为增强算法的局部搜索寻优能力，该算法利用种群中质量较优的个体组成了精英种群集合，并通过在精英种群个体中进行交叉操作以产生更高质量的个体。
|
|
结果：
本算法与一些性能较好的社区发现算法，包括Louvain算法、GN算法、标签传播算法（LPA）、Danon算法、遗传算法（GA）、多目标遗传算法（MOGA）在GN人工生成复杂网络和多个现实世界复杂网络上进行了对比实验。下图是实验后所得的数据展示，其中指标值越接近于1表示算法效果越好。可以看出，本算法与其它对比算法相比具有更高的求解精度和稳定性。
|
|
|
下图是本算法对于大学生橄榄球比赛网络（Football）和美国政治家书籍网络（Polbooks）进行社区发现所得的可视化结果展示。
|
|
