基于图数据的Steiner分量发现方法研究

摘要

给定数据图G,G的最大连通Steiner分量(SMCC)是G中连通度最大且包含顶点数目最多的子图。查找包含q的SMCC可以应用在现实生活中的很多领域，如在社交网络中，可以找出联系最紧密的社交团体；在电子商务中，可以为联系紧密的用户推荐产品；在协作网络中，可以找到联系紧密并且能够很好合作的小组。本文从以下几个方面对最大连通Steiner分量SMCC的查询问题进行研究，具体研究内容如下。
　　首先，通过对现有算法进行分析，发现现有方法存在构建索引时间长，索引规模大，查询效率低的问题。
　　其次，基于k-edge连通分量的性质，提出高效的ST(Set Tree)索引结构。对无向图的(k-1)-edge连通分量中包含的k-edge连通分量和非k-edge连通分量建立分层树形索引，其中以每一个结点为根的子树都对应一个k-edge连通分量。和现有的生成树索引相比，ST索引减少了索引结点的个数，缩短了索引构建时间。
　　再次，基于ST索引结构提出了计算SMCC的算法SMCC-ST，以及计算有顶点个数限制的SMCCL-ST算法。其优点在于使用较小的索引，同时减少了求解SMCC， SMCCL和连通度时需要访问的顶点个数，从而提高查询效率。
　　最后，基于9个真实的数据集进行测试，实验结果从索引构建时间，索引大小，查询时间，处理顶点数量等方面验证了本文所提方法的高效性。

目录

声明

第1章 绪 论

1.1 研究背景和意义

1.2 研究现状

1.3 本文研究内容

1.4 本文组织结构

第2章 基础知识概述

2.1 相关概念

2.2 相关算法

2.3 本章小结

第3章 ST索引结构

3.1 问题分析

3.2 ST索引

3.3 ST索引的构建

3.4 本章小结

第4章 基于ST索引的SMCC算法

4.1 问题分析

4.2 SMCC-ST算法

4.3 SMCCL-ST算法

4.4 基于ST和基于MST-MST*算法的总结

4.5 本章小结

第5章 实验结果分析

5.1 引言

5.2 实验环境和数据集

5.3 实验所用查询和评价标准

5.4 性能比较和分析

5.5 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢