论文部分内容阅读
现实世界中充满着各种各样的复杂网络。复杂网络所拥有的一个最普遍和最重要的拓扑属性是社区结构，即网络是由若干个社区组成的。在同一个社区内部，节点与节点的连接紧密，而不同社区的节点之间相互连接却相对稀疏。社区发现的任务是利用网络的拓扑结构以及节点的信息，通过特定有效的算法，发现复杂网络中的社区结构以及每个节点所属的社区。社区发现算法对分析复杂网络的拓扑结构，发现网络的某种隐含模式，预测其行为都有十分重要的理论意义，在实际应用中也非常广泛。 基于标签传播的社区发现算法由Raghavan等人于2007年提出后，因为简单高效的特点，迅速成为社区发现算法中的重要发现算法，但此类算法的一个缺陷是算法结果不稳定。本文在认真研究基于标签传播的社区发现算法和其它社区发现算法后，提出一种改进的标签传播算法，最小极大团的标签初始化社区发现算法，即MMCLPA(Minimal Maximal Clique Label Propagation Algorithm)算法。基于标签传播的社区发现算法分为三个过程，分别是:(1)标签初始化;(2)多轮标签传播;(3)后期处理。在标签初始化过程中，之前的算法都是简单的让网络中的每一个节点拥有一个唯一的标签，而MMCLPA算法则考虑网络中的拓扑结构，通过寻找最小极大团，让团中的每一个节点拥有相同的标签。在寻找最小极大团的时候，同时考虑节点度，优先寻找度数较大的节点的极大团。在标签传播过程中，每一个节点在一轮迭代的过程中，并不是接受邻居的所有标签，而是以权重为概率随机的选择一个标签。后期处理包括删除子社区，拆分不相连的社区，为度为1的节点重新划分社区等。 本文实验数据包括人工网络数据和真实网络数据。对于人工网络数据，由于社区已知，通过标准互信息(Normalized Mutual Information，简称NMI)来衡量社区发现的质量。对于真实网络数据，由于社区未知，通过模块度来衡量社区发现的质量。而算法的稳定性则通过计算算法多次运行结果的方差来衡量。实验结果表明，由于考虑了网络的拓扑结构，减少了无用的标签，MMCLPA算法可以提高社区发现的稳定性，并在一定程度上提高了算法的运行效率，同时该算法能够应用于社区结构相对不明显的复杂网络。 另外，在大数据时代背景下，本文利用MapReduce编程模型和Hadoop云平台，提出了标签传播算法的并行化实现，从而使得在超大规模的复杂网络中进行社区发现成为可能。