基于密度和进化的社区结构检测方法

摘要

近年来网络社区结构检测受到越来越多的关注。社区结构是复杂网络的一个重要属性。网络社区结构就是网络中某些特定节点的子集,其内部节点之间的联系比较紧密,而和网络中其它节点的联系相对稀疏。网络社区结构分析对于理解网络子结构的功能、发现网络中的隐藏规律以及预测网络的行为不仅有十分重要的理论意义,而且有广泛的应用前景。
　　基于密度的方法在社区结构检测领域的研究热度越来越高。这类方法依赖于两个参数,因此对输入的参数极为敏感,导致难以选择合适的全局参数。正因为这些参数非常敏感而且具有全局作用,我们并没有采用常规的选择参数的做法,而是利用了参数的上述特性,提出了一种全新的从社区层面对网络结构进行深入分析的思路,同时提出了一种启发式的基于密度的社区结构检测方法。在所提出的方法中,首先,利用参数的阈值作用本质,找出所有可能的输入参数情况。这些参数按照经典方法将产生多种多样的网络结构划分。其次,我们提出了包括划分、融合、分解、重组的策略对这些划分进行社区层面的处理。尤其在重组步骤中,我们用到了进化算法的思想,利用模块度搜索出了最好的结果。当这些策略处理完毕之后,我们将可以获得一个高质量的社区划分。在虚拟网络和实际网络上的实验证明了我们方法的有效性。
　　网络的动态特征是另一个持续受到关注的网络属性。现实世界中的网络多数都是动态网络,动态网络的社区结构会随着时间不断演化,因此它比静态网络社区检测更富有挑战性。在动态网络中,我们仍然需要考虑每个时间点的静态网络划分质量,同时也要兼顾各时间点之间的动态联系。在时间光滑的假设下,这种动态联系被数学化为相邻两时间节点间结构的相似性,与多目标进化算法的框架不谋而合。在先前的工作中,一种基于分解的多目标社区结构检测进化算法已经被提出。在此基础上,为了进一步提高算法性能,我们试验了一种局部搜索策略。这种局部搜索策略利用标签传播的思想,对每个时间点的结构都起着微调的作用。在动态网络上进行的一系列实验体现了该局部算子对算法性能的提高。
　　总结本文贡献如下:
　　(1)解决了基于密度的社区结构检测方法中参数的选择问题。我们的方法不仅克服了参数敏感以及难以选择的问题,而且找到了所有可能的参数,以参数为工具,对网络结构进行分析,最终结合进化算法,形成了一个完整的处理社区结构检测问题的新方法,在与其他算法结果对比中占优。
　　(2)在基于分解的多目标优化算法的框架下,我们提高了其解决动态社区结构检测的能力。在大量实验的基础上,基于标签传播思想的局部搜索策略确实提高了目标算法的性能,达到了预期效果,另外通过实验,假设合理性与框架合理性得到一定程度的验证。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 社区结构问题的背景和意义

1.2 研究现状

第二章 相关理论

2.1 社区的数学描述

2.2 多目标算法

2.3 评价函数

第三章 新型启发式基于密度的社区结构检测方法

3.1 背景介绍

3.2 相关研究

3.3 方法描述

3.4 实验结果及分析

3.5 结论

第四章 基于分解的多目标动态社区结构探索

4.1背景介绍

4.2 方法描述

4.3 实验结果与分析

4.4 结论

第五章 总结与展望

附录A

致谢

参考文献

硕士期间成果