面向符号图数据的符号团搜索算法研究

论文摘要

现实应用中存在很多各种各样的图数据,例如蛋白质-蛋白质相互作用网络,社交网络和合作网络等都是常见的图数据。在这些图中,通常都存在连接稠密的社区子图结构,从图数据中挖掘稠密子图结构是网络分析中的一个基本问题,其在社区探测、蛋白质络合物挖掘、检测垃圾邮件等都具有广泛的应用。在各种图数据应用中,存在一种图,它的边上包含有正负的信息,其中正边表示“朋友”,负边表示“敌人”。近年来,符号图数据的分析处理已经得到了学术界的广泛关注,但是大多数现有的稠密子图模型是专门为传统的无符号图设计的,因此迫切需要针对符号图数据定义新的稠密子图模型。首先,本文在符号图中定义了一种新的稠密子图模型,称之为极大（α,k）-团模型。具体来说,一个极大（α,k）-团是一个团,而且每个节点至多有k个负邻居并且至少存在?αk???个正邻居,其中α≥1。基于这一模型,本文研究了两个基本问题:（1）枚举所有的极大（α,k）-团;（2）枚举top-r（大小前r）的极大（α,k）-团。为了高效枚举所有的极大（α,k）-团,本文提出了一种高效的剪枝策略以削减符号网络的规模,其中包括一个基本剪枝方法MCCore（极大约束?αk???-核）和一个新的剪枝方法MCNew（新的极大约束?αk???-核）。MCNew算法能够保证最坏的时间复杂度为O（m）δ,其中m表示图中边的个数,δ表示图的荫度,其上界为O（m）,但是在现实生活中的图,δ往往远小于上界。然后本文提出了一种高效的分支定界算法和一些精心设计的剪枝规则,在被削减的符号图中枚举所有的极大（α,k）-团。为了枚举top-r的极大（α,k）-团,本文提出了几种新的剪枝规则,极大提高了枚举top-r极大（α,k）-团的性能。最后在5个真实的数据集中进行了大规模测试。实验结果验证了本文算法的高效性,可扩展性以及高性能。其中最显著的结果是,在规模为160万个节点数,3060万条边的图中,在大多数参数情况下,本文的算法可以在不超过1000秒的时间内枚举出所有的极大（α,k）-团。为了衡量聚类质量,本文提出了一种符号Conductance聚类度量,在该度量下,本文的算法要显著优于其他的算法。而且本文还通过一个具体的案例分析来评估符号团模型的有效性,实验结果验证了本文所提模型的优越性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究的背景与意义
•   1.2 研究现状
•   1.3 研究内容
•   1.4 组织结构
• 第2章 符号网络及符号团的定义
•   2.1 符号网络的定义
•   2.2 符号团的定义及问题
•   2.3 难点与挑战
•   2.4 本章小结
• 第3章 符号团剪枝方法
•   3.1 极大约束核剪枝规则
•   3.2 基本的剪枝方法
•   3.3 新的剪枝方法
•   3.4 本章小结
• 第4章 符号团枚举算法
•   4.1 分支定界枚举
•   4.2 极大符号团枚举算法
•   4.3 Top-r极大符号团枚举
•   4.4 本章小结
• 第5章 实验结果及分析
•   5.1 效率测试
•   5.2 效果测试
•   5.3 本章小结
• 第6章 总结与展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果

文章来源

类型: 硕士论文

作者: 代强强

导师: 李荣华

关键词: 符号网络,极大,分支定界枚举

来源: 深圳大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 深圳大学

分类号: O157.5

DOI: 10.27321/d.cnki.gszdu.2019.000368

总页数: 59

文件大小: 2305k

下载量: 8