顶点加权图的最密集子图算法设计与实现

发布时间：2020-05-27 21:02

【摘要】：图作为一种能有效描述现实世界中各类实体之间复杂关系的数据结构,被广泛地应用于社会关系网络、合著者网络、通信网络、生物信息网络等实际领域。随着这些新兴大规模网络的快速发展,相关的各类应用不断地涌现和丰富,图数据也急剧地增长和频繁地更新,使得对大规模图的处理需求也愈加迫切。密集子图查询是图数据处理中的热点研究问题,在复杂网络分析中扮演着非常重要的角色。给定一个图,密集子图查询旨在寻找到有一定联系紧密程度的子图。然而,大部分现有的密集子图查询方法没有考虑顶点的权值的影响,在许多现实图中,顶点有不同重要性。例如,目前社交网络中,有很多QQ群,微信群等等,如何计算一定范围内平均联系最密集的群可以转化为顶点加权图的最密集子图问题。而一个群的人数可以作为一个图的顶点的权值。本文引进了顶点加权图的最密集子图问题,并提出计算顶点加权图的最密集子图的多项式时间算法。提出的算法的基本思想是:给定一个顶点加权图G,假设最密集子图的密度为D,给D一个猜测的值为g,然后构建一个无向图,并且建立这个g值与该图一个最小割值的关系,然后通过二分法查找逐步求解D的值,最终找到顶点加权图G的最密集子图。进一步分析了该算法的时间复杂度和证明了该算法是正确的。然后通过仿真实验和实际图数据的实验来验证算法的有效性,得到相关结论。并且针对数据量比较大的顶点加权图的最密集子图问题,提出了一种基于贪心策略的近似算法,该算法通过不断的迭代删除掉平均最小值的顶点,以得到近似的密集子图,并且证明了这个近似算法的近似比。
【图文】：

图 1-1 中国网民规模和互联网普及率[1]ig.1-1 The scale of Chinese netizens and Internet penetration[1]

1图 1-2 中国手机网民规模及其占网民比例[1]Fig.1-2 The scale and proportion of mobile netizens[1]
【学位授予单位】：广州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 苑春佼;;《吉祥多子图》临摹[J];大众文艺;2018年10期

2 鲁宗贵;;吉祥多子图页[J];中国书画;2018年09期

3 印安涛;钱钢;施欢欢;;在复杂网络中查找k个有限重叠的密集子图[J];计算机应用与软件;2016年12期

4 鲁宗贵;;吉祥多子图[J];文艺研究;2017年03期

5 梁瑶;;吉祥多子图[J];美与时代(中);2017年06期

6 鲁宗贵;;《吉祥多子图》[J];老年教育(书画艺术);2016年01期

7 王苗苗;;《吉祥多子图》[J];明日风尚;2016年08期

8 周姗;;《吉祥多子图》[J];参花(上);2016年06期

9 杨利民;图K_n~k和C_n~t的理想子图的计数[J];大理师专学报(自然科学版);1995年01期

10 陈赐平;;带亏数的[1,n]-子图[J];北京农业工程大学学报;1987年03期

相关会议论文 前9条

1 刘桂珍;徐周波;;最大公共子图问题的约束符号求解技术[A];广西计算机学会2016年学术年会论文集[C];2016年

2 徐以凡;;层分解和子图识别问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

3 吴卫江;李国和;;Apriori算法思想在频繁子图挖掘中应用的研究[A];第六届全国信息获取与处理学术会议论文集（2）[C];2008年

4 陶剑文;丁佩芬;赵杰煜;;csgIndex:一种可扩展的对比子图索引模型[A];第二十七届中国控制会议论文集[C];2008年

5 陈荣斯;;非正则冠状系统[A];面向21世纪的科技进步与社会经济发展（上册）[C];1999年

6 吴颖华;周皓峰;袁晴晴;洪铭胜;汪卫;施伯乐;;Topology:一个快速的频繁连通子图的挖掘算法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

7 韩璐;王朝坤;阮文静;欧晓平;仇萍;;基于MapReduce的不确定子图查询处理[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

8 周杨;王峰;;FSM——基于子图同构和结构同构的频繁子图挖掘算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

9 张丽丽;殷兆麟;张爱娟;王竹晓;;以结点为中心的WordNet子图的可视化[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

相关重要报纸文章 前1条

1 王圣立;“五子图”罐再现成化风彩[N];中国商报;2003年

相关博士学位论文 前10条

1 蔺厚元;禁用子图与图的哈密尔顿性[D];华中师范大学;2012年

2 李斌龙;重子图条件下图的Hamilton性及相关问题[D];西北工业大学;2016年

3 毛玲;基于层次因子图的心电图自动诊断方法研究[D];国防科学技术大学;2009年

4 崔庆;Tutte子图方法及其应用[D];南开大学;2009年

5 邹磊;图数据库中的子图查询算法研究[D];华中科技大学;2009年

6 崔耀祖;基于复杂网络边的密度探索社团结构算法研究[D];大连理工大学;2016年

7 吴云建;一致星因子图与笼的连通性[D];南开大学;2009年

8 马登举;曲面的极小禁用子图与图的亏格[D];华东师范大学;2011年

9 石海佳;基于复杂网络的产业生态系统结构复杂性研究[D];清华大学;2015年

10 洪艳梅;图连通度与非分离子图[D];上海大学;2012年

相关硕士学位论文 前10条

1 邹艳梅;关于图的Hamilton性的禁用子图条件[D];华东师范大学;2018年

2 闫靓;稳定频繁子图挖掘算法研究[D];辽宁大学;2018年

3 姜丽雁;大规模动态有向标签图子图查询方法研究[D];辽宁大学;2018年

4 刘钟凌;顶点加权图的最密集子图算法设计与实现[D];广州大学;2018年

5 陈科第;基于频繁子图模式挖掘的群体性抗议事件检测技术研究[D];国防科学技术大学;2016年

6 张迎;面向大图数据的子图相似匹配算法研究与实现[D];东北大学;2015年

7 王凯;基于MapReduce的图数据库频繁子图挖掘[D];华中科技大学;2016年

8 贾俊;不确定图数据库上基于预裁剪的频繁子图挖掘[D];华中科技大学;2016年

9 刘文艳;基于深度优先策略的频繁导出子图挖掘算法[D];西安电子科技大学;2009年

10 朱杰;k核心子图查询算法研究[D];燕山大学;2016年

，

本文编号：2684136