论文部分内容阅读
自然界中存在的大量复杂系统都可以通过复杂网络加以描述,而社团结构是继小世界特性和无标度特性之后发现的最为重要的复杂网络特性。社团是网络中关联紧密的一群节点,往往具有某些共同特征,具有一定的实际物理意义。互联网是典型的复杂网络,深入研究互联网的社团结构可以帮助我们以分而治之的方式研究网络的功能及演化过程,更加准确的理解互联网的组织原则、拓扑结构等。目前针对互联网网络特性的社团发现研究还不足,传统社团发现算法并不能很好的反映互联网独有的特性。同时传统的社团发现算法大多数不能同时发现社团的重叠性和层次性。本文在局部适应度值最优化算法(LFM)思想的基础上,提出了基于共同邻居加权的社团发现算法(称之为CNW-LFM算法)。算法中通过共同邻居信息对边进行加权,其权值大小表示节点之间的紧密程度,并将适应度函数以网络中边的权值重新定义。然后在多个不同类型和不同规模的真实网络进行实验,发现CNW-LFM算法的重叠模块度高于原LFM算法,说明CNW-LFM算法优于原算法,使得社团划分结果更加合理,而且该算法可以同时发现社团的重叠性以及层次性。从而证明了结合网络特性进行加权的方法是可以提高社团结构发现的准确度以及合理性,为本文重点研究互联网社团结构打下了坚实的基础。针对互联网的宏观拓扑结构下的社团研究,在CNW-LFM算法的基础上,本文提出了基于地理位置加权的社团发现算法(称之为BGW-LFM算法)。针对互联网数据量庞大的问题,算法中提出了网络规模的缩减方法,从而明显地提高了时间效率。同时该算法充分考虑了互联网的地理特性,将地理位置信息和共同邻居信息相结合对边进行加权,边的权值依然表示节点之间联系的紧密程度。然后在多个不同规模的互联网网络进行实验,总结了算法中参数对社团划分结果的影响规律。对比实验中发现BGW-LFM算法的重叠模块度最高,其次是CNW-LFM算法,说明BGW-LFM算法使得社团划分结果更加合理。最后对比分析了社团结构的地理分布情况,发现BGW-LFM算法使得社团结构的地理分布更为紧凑。通过两方面的对比说明BGW-LFM算法使得对于互联网的社团结构发现更加准确,地理分布更为合理。而且该算法可以同时发现社团的重叠性以及层次性。