社会关系网络社区结构识别

摘要

近年来随着Web2.0的流行和普及，对社会关系网络(SNS)的研究和应用逐渐成为关注热点。社区结构是一种在社会关系网络数据中的特有结构，在诸如在线博客和论文引用等社会关系网络中，社区结构是人类交流和交际的固有特征。社区结构的发现和识别有助于得出有意义的个体间活动模式和社会发展规律，在客户行为分析和社会安全等多方面具有现实意义。
　　然而，社会关系网络中个体的兴趣和社会角色会随时间发生改变，传统的用聚合的网络数据分析社会关系网络会丢失网络变化中所包含的重要信息。目前对动态社会关系网络中社区结构描述和识别的研究还比较少，已有方法存在可扩展性差的缺点，无法在可接受时间内对大规模网络进行识别。本文提出动态社会关系网络中发现社区结构的增量式新方法IC算法。利用动态网络时间局部性即相邻采样时刻网络变化不大的特点，通过增量分析避免对整个网络中的个体全部重新划分，达到较高的算法效率。实验结果表明，IC算法效率高于现有方法，在大规模网络上效率提升在一个数量级以上；发现的社区结构很好的反映出社会关系网络的本质结构；IC算法适合在大规模动态社会关系网络上(105结点量级)有效地进行社区结构识别。
　　传统社区结构模型的一个弊端是顶点只能存在于一个社区之中，现实数据表明个体可能具有多重身份、参与多个活动团体，而传统的单一归属社区结构模型不能够解释这一现象。本文提出了多重归属的社区结构模型，并给出了能够识别社会关系网络的多重归属社区结构的算法MIC算法。实验结果表明，MIC算法可以找到有意义的社区结构，多重归属的社区结构往往具有比单一归属的社区结构更高的社区质量，能更好的解释个体在网络中的地位和作用，展示社会关系网络的真实拓扑结构和顶点之间的本质联系模式。

目录

社会关系网络社区结构识别

COMMUNITY STRUCTURE IDENTIFICATION IN SOCIAL NETWORKS

摘要

Abstract

第1章 绪论

1.1 研究背景

1.2 研究历史和现状

1.3 研究意义

1.4 本文的贡献

1.5 本文的结构

第2章 模型构建与分析

2.1 社会关系网络研究中的术语简介

2.2 静态社会关系网络模型

2.3 动态社会关系网络模型

2.4 动态社会关系网络社区结构识别方法简介

2.5 本章小结

第3章 动态社会关系网络社区结构增量识别算法

3.1 研究动机

3.2 数据模型准备

3.3 IC算法的提出

3.4 实验

3.5 本章小结

第4章 多重归属的社区结构识别

4.1 单一归属的社区结构识别

4.2 多重归属的社区结构

4.3 MIC:多重归属的社区结构识别算法

4.4 实验

4.5 本章小结

结论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性说明

哈尔滨工业大学硕士硕士学位论文使用授权书

致谢

个人简历