基于k核与k桁架的稠密子图最大化算法研究

作     者：孙新 

作者单位：天津大学 

学位级别：硕士

导师姓名：金弟;孙提

授予年度：2022年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：k核 k桁架 子图最大化 启发式搜索 

摘      要：稠密子图挖掘是图分析领域的一个重要环节,人们可以利用稠密子图来分析图的连通性、中心性、鲁棒性等重要性质。在众多稠密子图模型中,k核(k-core)和k桁架(k-truss)模型是目前的研究热点,这主要得益于它们可以在多项式时间内将图降解为层次结构。近年来,稠密子图最大化问题在现实生活中展现出了广泛的应用前景,譬如:增强社交网络的活跃度,识别军事网络中缺失的防御结点或链接,提高P2P(Peer-to-Peer)网络中资源交换的稳定性等。其中,k-core子图最大化问题主要是向图中插入一些有益的新边来增广k-core子图,然而已有启发式方法存在效率低的问题,难以在大规模图数据上应用;k-truss最大化问题目前尚未被研究过,然而我们发现该问题在很多现实应用中非常具有价值。因此,本文针对上述问题围绕k-core和k-truss这两个稠密图模型展开研究。首先,本文针对k-core最大化算法效率低的问题,提出了一种基于图划分和快速搜索策略的新算法命名为FactCM+。该算法的核心思想为:首先使用图划分算法将图中的重要节点划分为不同的连通分量,然后独立考虑每个分量,以完全转换和部分转换两种方式将不同的分层顶点转换到k-core中,最后针对不同分量设计动态规划算法来合理选择最合适的增广新边。进一步,本文从理论上给出了 FactCM+算法的时间复杂度为O(n(m+b)),比时间复杂度为O(bmn2)的当前最好算法EKC具有明显优势,其中n、m、b分别表示图中的顶点数、边数和插入边的数量。最后在十一个大规模图数据集上进行实验比较,结果表明本文算法FactCM+在大图上的运行速度比已有最好算法EKC快74,000倍,同时求得的插入边也能更好地增广k-core。进而,本文首次提出并研究了 k-truss最大化问题。由于该问题目前尚未被研究过,所以本文首先从两个真实世界应用(包含飞机航线网络连接性增强和社交网络参与度提升)中揭示了该问题具有丰富的应用场景和价值。接下来从理论上证明了 k-truss最大化是NP难问题,并继续分析了 k-truss新来者函数不具有子模性,进而设计了高效的启发式算法。本文首先识别图结构中高效的候选边,提出一种使用单边插入的贪心算法,进而通过精简候选边来提升效率。最后,提出一种基于分量的动态规划算法,它可以平衡预算分配并向所有分量同时插入多条边。通过在九个大规模真实世界图数据上的实验验证了本文提出算法的有效性、高效性和实用性。本文通过上述两个研究提升了目前子图最大化问题的求解效率、增广了其应用范围和解决方案,也为其他稠密子图最大化算法的设计与应用提供了一条新途径。