论文部分内容阅读
随着信息技术的迅猛发展，复杂网络的研究引起了许多领域人员的关注。不论是自然环境还是人类社会，网络无处不在。任意对象间只要存在联系或具有相互作用就会形成网络。因此，通过复杂网络可以挖掘各种各样的复杂系统，这在诸多领域中都具有重要的意义。网络研究的急速发展使研究者们发现复杂网络具有社团结构，即复杂网络是由不同的社团组合而成，社团内部节点间联系紧密，社团间连接则相对稀疏。利用这一特性可以分析复杂网络的拓扑结构、网络发展规律信息以及预测行为，因此社团发现是复杂网络研究中一个重要的课题。 本文首先对经典的社团发现算法进行了详细的研究，并对每种算法进行仿真实现，进一步对四种经典算法对比总结。利用Matlab软件分别对快速社团发现算法（FN）、基于标号传播的社团发现算法（LPA）、基于种子扩散思想的社团发现算法（LFM）、马尔科夫聚类算法（MCL）进行了实现，将四种算法的划分结果进行对比，得到MCL算法在复杂网络中进行社团发现具有明显的优势的结论。 其次，在研究经典的模块度函数、划分密度及社团评价标准的基础上，提出了改进的评价标准，并总结了其相关性质。通过仿真对比，发现改进后的评价标准能够更合理地评价社团划分质量，且具有较高的灵敏度。 再次，鉴于传统的社团发现算法忽略了小社团与边缘社团存在的不合理性，本文以经典社团发现算法为基准点，将MCL算法进行改进，得到了改进的马尔科夫聚类算法（MCLp）。此算法在MCL算法的基础上分析是否存在小社团与边缘社团，通过对比判断值与阈值得到需要重新划分的节点集合，并对比重新划分前后的评价函数来得到最终的网络社团结构。在经典数据集上进行仿真实验，并与经典社团发现算法从多个角度对比，发现MCLp算法得到的社团结构与实际划分更为贴切，精确度高达92.8％。随着网络节点数目与连接边的增加，改进的MCLp算法在时间复杂度方面的增长并不显著。 最后，本文将改进的MCLp社团发现算法分别应用于包含1000个节点的基准网络、美国西部各州的电力网络以及科学家合作网，得到了合理的社团结构，进一步验证了改进的MCLp算法的通用性与稳定性。