学位论文 > 优秀研究生学位论文题录展示

基于社交网络好友关系的图查询算法研究与应用

作 者: 史岭峰
导 师: 王树梅
学 校: 南京理工大学
专 业: 计算机应用技术
关键词: 社会网络数据 图查询优化 双曲空间 图的分离指标
分类号: TP391.3
类 型: 硕士论文
年 份: 2012年
下 载: 275次
引 用: 0次
阅 读: 论文下载
 

内容摘要


近年来,社会网络数据逐渐成为一种新颖的、日益重要的数据类型。相对于传统的数据类型,社会网络数据更加复杂,表达的语义更加丰富。体现在:一、社会网络的实体规模往往数以百万计,有时甚至千万或者上亿,实体间的关系在最坏情况下与实体规模成平方关系,更加大了数据规模;二、社会网络中的关系往往存在不确定性,比如关系的强弱、方向、类型等,这样就对社会网络数据的查询增加了难度。针对如此复杂的数据类型,寻找到有效的数据组织方式以及高效的查询处理方法,对于提高社会网络数据的质量和效率分析是非常必要的。本文以社交网络好友关系为研究对象,为其建立图模型;在此基础上设计和使用图查询优化技术进行好友关系的最短路径查询。首先介绍了已有的最短路径查询算法,然后设计了基于双曲空间的最短路径查询算法。该算法将社交网络图映射到双曲坐标系统中,社交网络图中节点间最短路径长度的查询就转化成坐标系统中节点间距离的计算,从而有效地将使用广度优先搜索(BFS)的计算开销O(n+m)降低为O(1)。实验表明,基于双曲空间的最短路径查询算法的效率和准确性都比较高。最后将该算法应用于图的分离指标的计算、图的中心势的计算和按距离排名的社交搜索三个实际需求,进一步验证了算法的实用性和准确性。

全文目录


摘要  3-4
Abstract  4-7
1 绪论  7-13
  1.1 课题背景与研究意义  7-8
  1.2 国内外研究现状  8-11
    1.2.1 国外研究现状  8-10
    1.2.2 国内研究现状  10-11
  1.3 论文主要工作  11-12
  1.4 论文组织结构  12-13
2 社交网络理论与模型  13-22
  2.1 社交网络的概念  13
  2.2 社交网络的组成  13-14
  2.3 社交网络的理论基础  14-17
  2.4 社交网络的研究问题  17-19
  2.5 社交网络模型  19-21
  2.6 本章小结  21-22
3 最短路径算法分析  22-36
  3.1 可达性查询算法  22-26
    3.1.1 路径分解方法  23
    3.1.2 生成树算法  23-24
    3.1.3 生成树的衍生算法  24-25
    3.1.4 2-hop标签算法  25
    3.1.5 可达性算法比较分析  25-26
  3.2 最短路径算法  26-35
    3.2.1 最短路径算法分类  27-29
    3.2.2 基本的最短路径算法  29-31
    3.2.3 最短路径查询优化算法  31-33
    3.2.4 基于图坐标系统的最短路径算法  33-35
  3.3 本章小结  35-36
4 基于双曲空间的最短路径查询  36-48
  4.1 社交网络数据集  37
  4.2 双曲坐标系统的设计  37-44
    4.2.1 图坐标系统  38
    4.2.2 双曲坐标系统中的距离计算  38-39
    4.2.3 图到双曲空间的映射  39-40
    4.2.4 双曲坐标系统参数选择  40-44
  4.3 基于双曲空间的最短路径查询方法  44-47
    4.3.1 利用双曲空间查询最短路径  44-45
    4.3.2 最短路径查询的准确性检测  45-47
  4.4 本章小结  47-48
5 基于双曲空间最短路径算法的应用  48-56
  5.1 图的分离指标的计算  49-50
  5.2 图的中心势的计算  50-53
  5.3 按距离排名的社交搜索  53-55
  5.4 本章小结  55-56
6 总结与展望  56-58
  6.1 总结  56-57
  6.2 展望  57-58
致谢  58-59
参考文献  59-62

相似论文

  1. 高维四元数双曲空间上的Jφrgenson不等式,O178
  2. 关于常曲率空间中基本凸体的几何不等式理论及应用,O178
  3. 面向社会化媒体的社会网络挖掘与分析,TP393.09
  4. H~2×R中的Weierstrass表示公式,O186.1
  5. 三维双曲空间中非类光曲线的球面达布像集,O186.12
  6. 双曲等距群的离散性,O174.5
  7. M(?)bius变换和圆锥曲线,O186.1
  8. 基于双曲空间的层次信息可视化方法研究,TP393.09
  9. 平行平均曲率子流形的间隙定理和刚性定理,O186.1
  10. 关于单位球面及双曲空间中子流形的一些结果,O186.1
  11. PU(2,1)的Kleinian子群的正规化子及高维M(?)bius群的离散准则,O152
  12. 关于双曲空间中子流形若干问题的研究,O186.1
  13. 常中曲率曲面的Flux,O186.11
  14. 关于螺旋抛物元素的Shimizu引理,O174.5
  15. 双曲空间中的曲面论,O186.1
  16. 复双曲离散群中的极限点,O174.5
  17. 社会网络分析与挖掘的若干关键问题研究,TP311.13
  18. 关于双曲几何与Klein群相关性质的研究,O186.11
  19. 调和映射边界正则性和曲面上归一化的Ricci Flow,O174.5
  20. 基于FPGA的数字图像处理基本算法研究与实现,TP391.41
  21. 用于检索的人脸特征提取与匹配算法研究,TP391.41

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理(信息加工) > 检索机
© 2012 www.xueweilunwen.com