中文题名: | 大规模图上的K-Truss社群在线查询 |
姓名: | |
学生类型: | 学士 |
学位名称: | 工学学士 |
学校: | 中国人民大学 |
院系: | |
专业: | |
第一导师姓名: | |
完成日期: | 2015 |
中文关键词: | |
中文摘要: |
在社群检测领域中,在线查询是广泛关注的问题。例如寻找社交网络中同一学校的同学,寻找网页中同一主题的网页集合等。很多社会网络模型需要寻找属于同一类型的点集,在线查询社群的方法能够很好地解决这一问题。
很多模型被用来处理社群的查询问题,包括密集度模型,K-Core模型,K-Truss模型和团重叠模型等等
本文主要运用K-Truss结构描述社群。通过构建索引的方法来实现在线查找。本文首先总结了两种重要的K-Truss社群在线查找方法,其一是基于Truss分解算法的索引,其二是TCP索引。本文提出了一种新的三角连通性优先索引实现K-Truss社群的在线查询。该算法查询复杂度达到理论极限。针对现实生活中的数据,三角连通性优先索引的试验结果比TCP索引和基于Truss分解算法的索引效率更好。针对点度非常大的极限数据,三角连通性优先索引拥有和TCP索引相近的高效率。
﹀
|
开放日期: | 2016-03-21 |