Top-k中心度查询算法研究

发布时间：2017-08-19 02:08

  本文关键词：Top-k中心度查询算法研究

  更多相关文章： 中心度 拓扑排序 扩展顺序 广度优先遍历

【摘要】：如何快速地找出中心度最高的k个点是有关图模型研究的热点问题之一,在现实生活中有着广泛的应用,比如超市选址、城市规划、热点新闻报道、数据挖掘以及病毒营销策略等。通过对现有方法进行分析,发现现有方法的低效性主要是由于顶点处理顺序的代价过高和处理顶点数量过多造成的。本文针对现有中心度计算方法效率低的问题展开研究,具体内容如下。首先,针对顶点处理顺序的代价过高提出一种基于拓扑排序的top-k中心度查询算法。该算法采用拓扑顺序替代已有方法的顶点处理顺序,减少已有方法求解顶点处理顺序所带来的昂贵的时间代价。其优点是简单、高效,但是应用具有一定的局限性,对于结构比较复杂的图计算代价会很高。其次,针对处理顶点数量过多的问题,提出基于估算筛选的中心度查询算法。该算法通过一次广度优先遍历估算出每个点中心度的上界值,通过上界值的大小确定顶点的处理顺序。在计算过程中,通过维护top-k中心度的真实值,可以有效地过滤掉无需计算中心度真实值的点,使候选集需要计算真实中心度值的点变少,从而减少计算代价,提高了算法性能。最后,在不同类型特征和规模大小的图上进行实验对比分析,从时间消耗、k值变化等方面对本文方法的高效性进行了验证。
【关键词】：中心度 拓扑排序 扩展顺序 广度优先遍历
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6
【目录】：

• 摘要5-6
• Abstract6-9
• 第1章 绪论9-14
• 1.1 研究背景9-10
• 1.2 研究现状10-12
• 1.3 研究内容12
• 1.4 本文结构12-14
• 第2章 基础知识概述14-22
• 2.1 基本概念14-15
• 2.2 问题定义15-16
• 2.3 基本算法16-20
• 2.3.1 拓扑排序算法16-18
• 2.3.2 求top-k问题的堆排序算法18-20
• 2.4 本章小结20-22
• 第3章 基于拓扑排序的中心度查询算法22-32
• 3.1 问题分析22-27
• 3.2 基于拓扑排序的算法思想27-28
• 3.3 基于拓扑排序法的查询过程28-30
• 3.4 算法分析30-31
• 3.5 本章小结31-32
• 第4章 基于估算筛选的中心度查询算法32-44
• 4.1 问题分析32-33
• 4.2 基于估算筛选的算法思想33-34
• 4.3 基于估算筛选法的查询过程34-41
• 4.4 算法分析41-42
• 4.5 本章小结42-44
• 第5章 实验44-54
• 5.1 实验环境44
• 5.2 数据集和评价标准44-45
• 5.3 性能比较与分析45-52
• 5.3.1 不同类型的图45-48
• 5.3.2 查询时间的消耗48-50
• 5.3.3 k值的选取50-52
• 5.4 本章小结52-54
• 结论54-55
• 参考文献55-59
• 攻读硕士学位期间承担的科研任务与主要成果59-60
• 致谢60

【相似文献】

中国期刊全文数据库 前10条

1 张丽红;;查询算法的优化设计[J];职大学报;2009年02期

2 陈富强;奚建清;;商覆盖立方体中下掘与上卷操作的查询算法设计[J];信息技术;2011年04期

3 李英女,郑国雄;铁路客运信息查询算法[J];铁路计算机应用;2000年02期

4 徐红波;郝忠孝;;一种基于Z曲线近似k-最近对查询算法[J];计算机研究与发展;2008年02期

5 刘平;陈旭灿;李思昆;;嵌入式空间数据库综合查询算法[J];计算机工程;2008年17期

6 赵智慧;;基于对象方向方位的连续方向查询算法[J];齐齐哈尔大学学报(自然科学版);2010年04期

7 徐红波;韩启龙;潘海为;;空间数据库最优位置查询算法研究[J];计算机工程与应用;2011年18期

8 杜左强;基于对象的空间数据库的方位查询算法[J];信息技术;2004年07期

9 徐红波;郝忠孝;;一种采用Z曲线高维空间范围查询算法[J];小型微型计算机系统;2009年10期

10 高静波,李新友,唐泽圣,周晓辉;半动态矩形交查询算法[J];软件学报;1997年08期

中国重要会议论文全文数据库 前10条

1 洪润秋;金文;陈钢;王能斌;;迭代查询子查询算法的研究[A];第十一届全国数据库学术会议论文集[C];1993年

2 常珂;刘辰;杨正球;;基于树状结构的查询算法的设计与实现[A];中国通信学会第六届学术年会论文集（中）[C];2009年

3 孙焕良;刘江秀;许景科;;基于楔的时间序列流双向封装过滤查询算法[A];第二十五届中国数据库学术会议论文集（二）[C];2008年

4 李江波;周强;陈祖舜;;汉语词典快速查询算法研究[A];第二届全国学生计算语言学研讨会论文集[C];2004年

5 董科;王国仁;宁博;毛克明;赵相国;;基于压缩叶子流的XML Twig查询[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

6 刘旭辉;冯建华;洪亲;;一种支持更新的图可达性查询算法[A];第二十四届中国数据库学术会议论文集（技术报告篇）[C];2007年

7 刘怡;郝云飞;;一种有效的复调音乐查询算法[A];第三届和谐人机环境联合学术会议（HHME2007）论文集[C];2007年

8 黄海;侯颖;朱圣平;;一种多维向量并行查询算法[A];2010年全国开放式分布与并行计算机学术会议论文集[C];2010年

9 徐忠华;张剡;陈玲;柏文阳;;基于星型模型的轮廓连接查询算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

10 陈冬霞;吉根林;武志峰;;一种基于签名的XML查询算法[A];第二十一届中国数据库学术会议论文集（技术报告篇）[C];2004年

中国博士学位论文全文数据库 前7条

1 徐红波;基于空间填充曲线高维空间查询算法研究[D];哈尔滨理工大学;2010年

2 刘润涛;基于序的空间数据索引及查询算法研究[D];哈尔滨理工大学;2009年

3 季长清;云计算环境下的大规模空间近邻查询算法研究[D];大连海事大学;2014年

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

5 谢鲲;布鲁姆过滤器查询算法及其应用研究[D];湖南大学;2007年

6 刘艳;基于主存的高维空间连接及查询算法研究[D];哈尔滨理工大学;2011年

7 田小梅;多布鲁姆过滤器查询算法及其应用研究[D];湖南大学;2013年

中国硕士学位论文全文数据库 前10条

1 黄海龙;大规模图的图查询算法研究[D];燕山大学;2015年

2 李青;分布式计算环境下海量RDF数据的skyline查询研究[D];郑州大学;2015年

3 邓育;空间近似关键字反远邻查询方法研究[D];安徽工业大学;2015年

4 于世龙;信息物理融合系统资源索引与查询技术研究[D];国防科学技术大学;2013年

5 郭岩;实时数据流相似性查询算法的研究[D];华北电力大学;2015年

6 钟丽娟;时间序列数据相似性与聚合top-k查询算法研究与应用[D];浙江大学;2016年

7 李海莉;面向高速骨干网的网络流量测量关键技术研究[D];解放军信息工程大学;2014年

8 孟凡帅;基于HDFS的时空数据共享与查询隐私保护的研究与实现[D];东北大学;2014年

9 刘增兰;同构发布/订阅系统的系统最优化与并行查询算法的研究与实现[D];东北大学;2014年

10 叶向东;面向web规模RDF数据查询算法的研究与实现[D];东北大学;2014年

，

本文编号：698041