基于结构相似度的大规模社交网络聚类算法研究

摘要

社交网络为社交系统下个体之间的关系所组成的复杂网络结构。随着信息时代互联网科技的迅猛发展，社交网络，特别是在线社交网络，已成为人与人之间分享信息不可或缺的媒介。社交网络中个体之间的相互连接关系作为信息的传播途径，在很多方面有不可忽视的作用。如广告投递，潜在商机发现，效果预测以及危机预警。因此如何从这些庞大的网络中获取有价值的信息成为了目前重要的研究课题。网络结构分析也吸引了众多研究者的关注，其中的网络聚类即是一种有效的结构分析手段和途径。然而目前的网络聚类算法仍面临重大的挑战。首先，现有网络聚类算法没有充分考虑实际社交网络的特性。对社交网络的结构分析不同于一般网络聚类，社交网络中常常存在一些具有特殊作用的点，同时节点间的社交关系大多为有向的。其次，没有将大规模网络数据的处理作为目标。
　　 本文针对现有社交网络聚类中所面临的问题，提出了一种面向大规模有向网络的结构聚类算法。首先，提出了基于结构相似度的处理有向网络的聚类方法。本文对有向网络进行聚类操作提出了两种不同的方法：提出一种两阶段方法，首先将有向网络近似为无向网络，再使用结构相似度聚类算法进行结构分析；对现有的针对无向网络的方法进行改进使其能够直接对有向网络进行聚类。其次，针对社交网络的大规模特性，本文研究了如何将原本非并行的基于结构相似度的聚类算法进行并行化，使其能够处理大规模网络数据。算法中，针对社交网络数据特性，设计了合理的数据划分策略，各机器之间的数据交换策略。本文对算法进行了理论分析，证明采用这种高效率的并行编程框架实现的并行网络结构聚类算法的结果与原非并行算法的结果是一致的。最后，本文基于MapReduce并行架构实现了所提出的并行式网络聚类算法。大量实验结果表明本文提出的算法能够提高有向网络聚类算法的准确度，同时并行方法能够有效处理大规模的网络聚类问题。综上所述，本文在有向社交网络并行聚类问题上取得了一定的进展和效果，在社交网络的结构信息发现相关领域有很好的应用前景。

目录

声明

摘要

第一章 绪论

第一节 引言

第二节 研究背景

1．2．1 社交网络发展现状

1．2．2 网络聚类算法

第三节 选题意义

第四节 本文主要内容

第五节 论文组织结构

第二章 相关工作综述

第一节 网络聚类算法研究现状

2．1．1 图划分方法

2．1．2 基于模块度方法

2．1．3 谱聚类方法

2．1．4 网络聚类SCAN算法

第二节 有向网络聚类算法研究现状

2．2．1 无向网络聚类算法扩展为有向网络聚类算法

2．2．2 有向网络转化为无向网络再聚类

第三节 并行聚类算法研究现状

第四节 本章小结

第三章 基于结构相似度的有向网络聚类

第一节 有向网络转化为无向网络

3．1．1 采用文献计量对称化

3．1．2 采用度打折对称化

3．1．3 采用随机游走对称化

第二节 直接有向网络聚类

3．2．1 算法过程

3．2．2 算法复杂度分析

第三节 本章小结

第四章 基于结构相似度的并行网络聚类算法

第一节 并行实现ε邻居识别

4．1．1 对图进行划分处理

4．1．2 数据预处理

4．1．3 分布式ε邻居识别

第二节 并行ε邻居识别MapReduce实现

4．2．1 MapReduce并行平台简介

4．2．2 MapReduce上实现并行ε邻居识别

第三节 并行实现簇扩展

4．3．1 算法设计

4．3．2 保持标签一致性

4．3．3 改进的并行簇扩展过程

第四节 并行簇识别的MapReduce实现

第五节 并行算法正确性分析

第六节 算法复杂度分析

4．6．1 数据处理复杂度

4．6．2 总体复杂度分析

第七节 本章小结

第五章 社交网络聚类应用性研究

第一节 有向社交网络结构分析

5．1．1 实验数据

5．1．2 实验对比方法

5．1．3 评价指标介绍

5．1．4 参数的选择

5．1．5 结果分析

第二节 并行化社交网络分析

5．2．1 实验数据

5．2．2 评价指标介绍

5．2．3 结果分析

第三节 本章小结

第六章 总结与展望

第一节 工作总结

第二节 工作展望

参考文献

致谢

个人简历