不确定图中紧密子图挖掘算法研究

论文摘要

随着社会科学技术的快速发展,各行业中积累了众多以图形式存储的数据。如在生物蛋白质网络、社交网络以及无线传感器网络中产生了大量的数据,其中包含了许多有用的知识和具有潜在价值的信息,因此以图结构为基础的挖掘技术应运而生。图挖掘是指从这些图数据中发现有价值的信息的过程。迄今为止,国内外学者对图挖掘的问题进行了广泛的研究,但是由于图结点之间存在连接不确定性、图中边的稀疏度和图结点个数的影响导致很难通过常用的数据结构进行分析,因此为了满足在各种网络中挖掘知识的需求,给出如下算法。首先,针对不确定图稠密子图中紧密子图快速挖掘算法,依靠子图中边个数与结点个数比值的函数和子图中各结点期望度数来衡量其紧密程度。由于该算法过程通过迭代实现,每次都需要删除一个结点和相连的边,导致存在算法时间冗余问题。因此为了减少算法时间开销,根据判定结点连接的关系和结点度数的计算,给出最小结点度数非唯一的ImproveALKS算法。其次,针对在大图中得到密切关联且存在概率较高的多个子图区域的问题,根据不同图中结点的连接情况,调整紧密子图阈值参数的输入,然后得到GC-ImproveALKS算法。该算法以贪心迭代的思想得到Top-k不重叠的紧密子图,删除该子图的所有结点与边,再去计算剩余结点的紧密子图,循环计算直到满足k值停止,输出Top-k最紧密子图。最后,通过多组数据的对比实验对紧密子图挖掘算法和Top-k紧密子图挖掘算法的时间效率进行了验证。

论文目录

文章来源

类型: 硕士论文

作者: 孙延贞

导师: 邹晓红,曹国栋

关键词: 紧密子图,结点期望度数,不重叠子图,期望密度

来源: 燕山大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 燕山大学

分类号: O157.5

DOI: 10.27440/d.cnki.gysdu.2019.001456

总页数: 58

文件大小: 1133K

下载量: 39

相关论文文献

• [1].单图中的近似频繁子图挖掘算法[J]. 华东师范大学学报(自然科学版) 2019(06)
• [2].《吉祥多子图》临摹[J]. 大众文艺 2018(10)
• [3].吉祥多子图页[J]. 中国书画 2018(09)
• [4].在复杂网络中查找k个有限重叠的密集子图[J]. 计算机应用与软件 2016(12)
• [5].吉祥多子图[J]. 文艺研究 2017(03)
• [6].吉祥多子图[J]. 美与时代(中) 2017(06)
• [7].《吉祥多子图》[J]. 老年教育(书画艺术) 2016(01)
• [8].《吉祥多子图》[J]. 明日风尚 2016(08)
• [9].《吉祥多子图》[J]. 参花(上) 2016(06)
• [10].最大公共子图的约束符号求解方法[J]. 广西科学院学报 2017(01)
• [11].基于改进完全子图模型的关注对象多社区发现研究[J]. 南京理工大学学报 2016(06)
• [12].一种基于特征子图的不确定图分类算法[J]. 陕西师范大学学报(自然科学版) 2014(05)
• [13].指令扩展中相关子图的分析与处理[J]. 计算机辅助设计与图形学学报 2009(10)
• [14].因子图发展及其在定位与导航的应用技术[J]. 全球定位系统 2020(01)
• [15].具有最多与最少连通子图的单圈图[J]. 宜春学院学报 2015(03)
• [16].单圈图的连通子图的数目[J]. 南开大学学报(自然科学版) 2011(03)
• [17].改进的最大频繁子图挖掘算法[J]. 信息与电脑(理论版) 2017(18)
• [18].从不确定图中发现K紧密子图[J]. 计算机科学与探索 2011(09)
• [19].频繁子图挖掘研究综述[J]. 微电子学与计算机 2009(03)
• [20].频繁子图挖掘算法的应用分类[J]. 电脑知识与技术 2020(29)
• [21].加权最大频繁子图挖掘算法的研究[J]. 计算机工程与应用 2009(20)
• [22].一种挖掘最大频繁子图的新算法[J]. 系统仿真学报 2008(18)
• [23].基于子图模式的反恐情报关联图集分析[J]. 现代情报 2019(07)
• [24].具有结果多样性的近似子图查询算法[J]. 南京大学学报(自然科学) 2019(06)
• [25].频繁子图挖掘算法的若干问题[J]. 采矿技术 2011(05)
• [26].基于近似子图的规则空间压缩算法[J]. 自动化学报 2019(08)
• [27].一个复杂网络中完全子图的搜索算法[J]. 数学理论与应用 2013(03)
• [28].标签零模型及子图分布算法应用研究[J]. 小型微型计算机系统 2018(05)
• [29].特殊子图的计数[J]. 淮南职业技术学院学报 2011(03)
• [30].基于包含度的子图匹配方法[J]. 软件学报 2018(06)

标签：紧密子图论文;  结点期望度数论文;  不重叠子图论文;  期望密度论文;