关键词：
复杂网络
社团检测
多目标优化
进化算法
蚁狮算法
摘要：
复杂网络社团检测在理解复杂系统的组织和结构、揭示复杂数据中的隐藏模式和规律、预测复杂系统行为等方面具有重要意义,在社交网络分析与推荐系统、生物信息学、交通网络规划、信息传播与病毒传播模型、网络安全与异常检测、市场研究与推广、物流与供应链优化、金融风险监控与管理等领域具有广泛的应用。在复杂网络社团检测的研究历史中,世界各国的专家学者们已经提出了众多优秀的算法。但如何在网络的先验知识匮乏甚至先验知识不存在的情况下,尽可能的在提高社团检测准确度的同时降低时间复杂度,仍然是社团检测领域需要突破的一个重点。进化算法在社团检测算法中扮演着重要的角色,在进化的过程中,如何精准的找到全局最优解,提高种群的收敛速度,仍然是困扰着该领域研究者的一大难题。本文主要研究工作如下:
1.提出了一种基于蚁狮算法的多目标静态网络社团检测算法。社团检测问题可以看成优化问题,而且是NP难问题。在某些应用中,希望在社团检测中同时考虑多个冲突的目标,如果简单地将多个目标函数根据加权系数进行加权求和构成单目标优化问题,各个目标解线性组合的参数可能会很敏感,稍有不慎就会错失全局最优解。本文采用核k均值和比率切割作为优化目标,提出一种基于蚁狮算法的多目标静态网络社团检测算法。为了解决现有静态网络社团检测算法存在易过早收敛而陷入局部最优解、需要过多先验知识的问题,本文引入蚁狮算法。蚁狮算法具有参数少、实现简单、全局搜索能力强、不易陷入局部最优解、可并行化等优点,被广泛的应用于工程领域。但是原始的蚁狮算法适用于优化连续函数,为了将其应用于社团检测领域,本文将蚁狮算法的算子进行离散化。先使用标签传播算法对种群进行初始化,再利用离散化后的蚁狮算法算子对种群个体进行多目标优化得到最优个体,从而完成网络的社团划分。最后将该算法与对比算法在人工合成网络和真实世界网络上进行实验,实验结果表明该算法比对比算法的社团划分指标NMI值更高,这表明该算法比对比算法更具有竞争优势。。
2.提出了一种基于蚁狮算法和共识社团的多目标动态网络社团检测算法。现实中的网络往往都是随着时间而不断变化的,动态网络的社团检测就是要分析出社团结构随时间变化的规律。动态网络的社团检测不仅要精确地找到当前时刻网络的社团划分,还要保证前后时刻网络的划分结果漂移量较小。为了解决现有动态网络社团检测算法忽略前后时刻网络中社团结构变化量的问题,本文引入了种群内共识和种群间共识。从第一时刻的网络开始,对于一个初始化后的种群,用离散化后的蚁狮算法算子对其进行迭代。在种群迭代的过程中,计算出当前时刻网络的种群内共识,下一时刻的种群对种群内共识进行投票,支持率高于阈值的种群内共识作为不同时刻间的知识传递到下一时刻的种群中。这样当前时刻的种群就会沿着上一时刻种群的进化方向进化,尽可能的减小时刻间结果的漂移量。将该算法与对比算法在人工合成动态网络和真实世界动态网络上进行实验,实验结果表明该算法比对比算法的社团划分指标NMI值更好,这表明该算法解决了现有算法存在问题,更具有竞争优势。
欢迎来到三峡大学图书馆！
