社交网络中的社团发现与度量研究

摘要

社交网络现已经成为人们工作和生活中不可或缺的工具，社交网络结构分析是社会计算研究领域的重要课题。社交网络中的社团结构是指整个网络由几个相对独立的节点集合构成，节点集合称为社团，社团内部的节点连接紧密，而社团间的连接相对稀疏。社团结构的研究能够使人们深入直观地理解网络内部结构，为其在社会生活的各方面提供决策支持。另一方面，通过分析网络中的社团结构，能够减小目标网络的规模，为人们处理与分析海量数据提供技术支持。
　　社交网络中的社团结构度量是一项重要研究内容，将直接反映所发现社团结构的质量。现实网络中，节点的社团归属通常不是唯一且节点间的关系也是强弱不一的，即加权网络中的重叠社团结构。而现有的社团度量方法，如基于模块度的方法等，都不能用于度量加权的重叠社团结构。针对上述问题，本文提出一种扩展的加权模块度计算方法EWQ，并结合随机图及多边图模型对扩展模块度EQ及EWQ的正确性进行数学验证。在标准人工网络上对所提出的扩展加权模块度有效性进行验证，由于人工网络与现实网络具有类似的特性，其节点的度数满足幂率分布，对其中的社团结构进行度量能够反映度量方法的客观性。实验结果显示，扩展的加权模块度能够更好地结合节点间连接权重对社团结构进行度量。
　　现有的社团发现算法依据是否允许节点同时属于多个社团分为重叠或非重叠社团发现算法，然而这些算法在进行社团发现时，很少考虑节点的属性信息。由于节点的属性信息是社交网络用户特征的真实反映，忽略节点属性信息进行社团发现必然会对社团结果产生影响。针对上述问题，本文提出一种改进的基于随机游走模型的社团发现算法。整合社交网络中节点的连接关系与节点属性信息，利用随机游走模型并结合节点属性对节点进行重要度评分，得到网络中的重要节点;基于随机游走模型定义节点间紧密度;以重要节点作为种子节点进行聚类，发现其中的社团结构。通过一定的图形构造，本文方法能够解决重叠和非重叠社团发现问题。实验结果显示，相对于未考虑节点属性的方法以及随机选择种子节点的聚类方法，本文方法更为高效，社团度量结果也更为合理。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 问题描述

1．3 本文工作

1．4 论文结构

第二章 相关工作

2．1 基本概念

2．2 社团度量

2．2．1 非重叠社团度量

2．2．2 重叠社团度量

2．2．3 其他度量方法

2．3 社团发现算法

2．3．1 非重叠社团发现算法

2．3．2 重叠社团发现算法

2．3．3 其他社团发现算法

2．4 本章小结

第三章 面向赋权网络的重叠社团结构度量

3．1 模块度的随机图解释

3．2 赋权模块度

3．3 面向重叠社团结构的扩展模块度

3．4 实验

3．4．1 LF标准人工网络

3．4．2 人工网络社团度量

3．5 本章小结

第四章 基于随机游走和节点属性的社团发现

4．1 整体框架

4．2 重要节点发现

4．3 社团发现

4．4 实验

4．4．1 数据集

4．4．2 参数选择与社团划分

4．4．3 不同方法对比

4．4．4 种子节点选取对算法效率的影响分析

4．5 本章小结

第五章 总结与展望

5．1 本文总结

5．2 未来展望

参考文献

致谢

攻读硕士学位期间发表的学术论文目录

攻读硕士学位期间参与的项目