基于Louvain算法的社团结构划分

发布时间：2020-08-06 18:14

【摘要】：迅猛发展的网络科学为人们分析和研究复杂系统提供了重要工具,已经成为一个跨学科的研究平台。复杂网络中的社团结构与系统的功能与动力学特性紧密相关,是对网络进行分析研究的重要切入点和研究对象。对社团划分算法的研究经历了十余年的发展,尽管取得了许多研究成果,但对其实际应用的研究仍存在一定缺陷,主要体现在以下两个方面:1)缺乏对算法实际应用效率的评价方法。对算法进行性能评价时往往采用多次实验取平均值的方法,平均值虽能体现算法的平均性能,但无法体现算法在实际应用中的效率;2)社团划分算法的结果带有随机性,多次实验得到的多个结果之间存在差异性,如何从带有差异性的多个结果中找到准确、合理的划分结果,以便进行后续研究工作,依然缺乏一种合理的解释和快速有效的算法。围绕这些问题,本文依据算法在实际应用中的情况提出了新的评价指标,提出了实际应用效率更高的社团划分算法,分析了社团划分结果差异性的成因,提出了从多个划分结果中找到准确、合理的划分结果的算法。本文的主要研究成果和学术贡献如下:1)提出了基于小概率事件原理的自适应随机邻居Louvain算法。本文以经典Louvain算法为基础,借鉴随机邻居Louvain算法降低模块度增益计算次数的改进思想,提出了基于小概率事件原理的自适应随机邻居Louvain算法。算法随机抽取部分邻居节点计算模块度增益,从而降低模块度增益计算次数,提高运算速度;邻居节点抽取数量通过小概率事件原理推导获得。算法从划分的中间结果中获取网络的社团结构信息,对计算所使用的物理量进行估计。利用LFR人工基准图和实证网络对该算法进行测试,并与经典Louvain算法和随机邻居Louvain算法进行对比,发现本文所提算法可以在保证划分结果的模块度的大小和稳定的同时,有效提高算法的运行速度,在110万节点的Youtube网络上提速比例超过 100%。2)提出了等效运算时间指标。基于社团划分算法在实际应用中的情况,本文提出了等效运算时间指标,作为评价社团划分算法实际应用效率的标准。利用该指标对自适应随机邻居Louvain算法进行了测试,该算法可以有效提高实际应用效率,在多数网络中具有最佳的表现,在实证网络中,与经典Louvain算法相比,本文算法的提速比例最高可达4倍以上。3)提出了带噪声的社团结构模型。针对社团划分算法结果不稳定的问题,本文提出了带噪声的社团结构模型,将网络中的连边分为信息边和噪声边,指出信息边可以帮助社团划分算法找到网络中的真实社团结构,而噪声边会对社团划分算法产生干扰,使其无法准确、稳定地找到网络中的真实社团结构。4)提出了利用社团划分的网络去噪算法。依据带噪声的社团结构模型,本文提出了一种网络去噪算法。算法利用一组社团划分结果,通过统计连边两端点的同社团关系出现概率,对连边的权值进行计算、更新,对网络中的信息边和噪声边进行区分,并对噪声边进行滤除,从而得到仅包含有信息边的网络结构。通过将去噪算法与自适应随机邻居Louvain算法进行结合,在LFR人工基准图和实证网络上进行验证,结果表明本文所提去噪算法可以有效提高划分结果的准确性。与共识算法进行对比,去噪算法不仅可使划分结果的准确度有所提升,算法的运算时间也显著降低,时间复杂度仅为O(m),显著低于共识算法的时间复杂度O(n~2)。
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】