面向二部图的内倾稠密子图搜索与分解

作     者：舒开元 

作者单位：广州大学 

学位级别：硕士

导师姓名：张帆

授予年度：2024年

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

主      题：二部图 子图搜索 稠密子图 图分解 内倾社群 

摘      要：随着信息技术的不断发展,对于大规模图数据信息的处理与挖掘也受到广泛关注。二部图作为表示两种不同类型实体之间关系的图结构,在许多领域都有着广泛的应用,如电子商务、推荐系统、网络安全等。稠密子图搜索通常返回一组连接紧密的节点集合,可以从图数据中挖掘具有稠密性的社团,同时对图结构进行稠密度分解,可以发现图结构潜藏的信息。然而,现有的二部图上稠密子图模型着重考虑子图内部的节点关联,缺乏对子图内部与外部之间的节点连接进行考量与约束。这导致稠密子图中可能存在内部节点与外部节点之间的大量连接,容易受到外部节点动态的影响。 因此,本文提出一种二部图上的新型稠密子图模型,即内倾稠密子图,其要求子图内部每个节点有一定比例的邻居节点存在于子图内部。这使得子图内部的节点具有内倾性,即节点倾向于子图内部的信息交互,且较难受到外部信息传播的影响。内倾稠密子图的研究对于各类网络中的信息传播优化、社团特性分析等方向有重要作用。本文将二部图上的内倾稠密子图定义为(α,β,p)-core,即一个极大子图,其中一组节点集合中每个节点内部度数不小于α,且内部度数占总度数比例不小于p;同时,另一组节点集合中每个节点内部度数不小于β。 在计算方法方面,论文首先提出了给定参数数值下的(α,β,p)-core在线搜索算法,以及基于不同参数数值的(α,β,p)-core的图结构多维度分解算法。在图数据分解的基础上,论文提出了新型索引机制,实现对于(α,β,p)-core的快速离线搜索。论文在8个真实二部图数据开展了实验评估:通过社团指标和搜索案例分析,本文同相关的(α,β)-core模型进行了对比,验证了本文所介绍的内倾稠密子图的有效性;实验结果表明了所提出算法对内倾稠密子图搜索与相应图数据分解的高效性。