基于结构聚类挖掘社交网络图

摘要

当今的社会网络，己不再是狭义上社会学研究的内容，转而成为了集尖端的科研价值与巨大的商业潜质于一体的火热研究课题，吸引着愈来愈多各领域的研究人员的关注。随着时代的发展，互联网中的数据也以井喷式的速度急速增加，大数据时代中的网络已经变得异常复杂。随着逐步深入研究复杂网络的物理性质和数学特性，研究者发现许多真实世界的网络除了具备小世界性、无标度性这些特性外，还具有一个共同的特性，那就是社区结构，其由一系列点和边组成，具有社区内部的节点连接十分紧密，社区相互之间的节点连接松散的特征。从社区的角度能更好挖掘网络的功能和价值，且便于分析网络的结构和特性。因而，挖掘出复杂网络中的社区结构具有非常重要的意义。 由于缺乏将社交网络转化为数据的有效方法，有权网络和无权网络被当成了两种网络分别研究，大部分对无权网络的算法无法推及至权值网络，基于此，本文主要研究了社交网络转化为数据的方式，使得众多应用于数据的聚类方法可以应用在社交网络上。本文首先简单描述了论文研究的背景、当前的研究现状和本篇论文的组织结构。其次阐述了复杂网络的含义、相关特性、拓扑结构模型、社区的含义，并且描述了几种典型的社区发现算法。以前面的理论研究工作为基础，本文提出了伪邻接矩阵的概念。伪邻接矩阵的每一行代表一个节点。在伪邻接矩阵的对角元素上，设置α参数。这一参数保证了社交网络转化为数据的准确性，使数据能够更好的表示社交网络的结构。 在数据的基础上，本文介绍了K-means，层次聚类，FCM_种算法在社交网络上的应用。为了使K-means算法更好的应用于社交网络，本文提出了基于最大节点度的初始值选择方法。本文以模块值，规范化互信息、强弱社团数为指标，分别验证该数据转化方式的可行性。通过大量的对比实验，我们发现这种转化方法具有一定的优势。一定程度上提高了时间效率和社区划分精度。这种转化方式可以应用在权值和无权网络上，提高了K-means和层次聚类在社交网络上应用的泛化能力。

目录

第一个书签之前

ABSTRACT

摘要

List of Figures

List of Tables

List of Symbols

List of Abbreviations

Chapter 1Introduction

1.1Background

1.2Research status at home and abroad

1.3Research content

1.4Thesis Organization

Chapter 2Preliminaries

2.1Graph Theory

2.2Statistical properties of complex networks

2.2.1Degree

2.2.2Neighbors Node

2.2.3Clustering Coefficient

2.2.4Shortest Path Length

2.2.5Density

2.3The Topology of the Network

2.3.1Scale-free Network

2.3.2Small-world Network

2.3.3Community Structure

2.4Classic Algorithms

2.4.1CMP Algorithm

2.4.2Label Propagation Algorithm

2.4.3Spectral Clustering

2.4.4Louvain Algorithm

2.5Community Evaluation Indicators

2.5.1Modularity

2.5.2Normalized Mutual Information

2.5.3Community in a Strong Sense and in a Weak Sense

2.6Conclusion

Chapter 3Community Detection on Pseudo-Adjacency Matrix

3.1Problem Background and Solution

3.2K-means Based on Pseudo-adjacency Matrix

3.2.1The Maximum Degree of Initialization

3.2.2Basic Idea

3.3Hierarchical Clustering Based on Pseudo-adjacency Matrix

3.3.1Similarity Measure Function

3.3.2Basic Idea

3.4FCM Algorithm Based on Pseudo-adjacency Matrix

3.4.1Basic Knowledge

3.4.2Principle of Algorithm

3.5Conclusion

Chapter 4Experimental Results and Analysis

4.1DataSet

4.1.1Zachary Karate Club Network

4.1.2Dolphins Network

4.1.3Football League Network

4.1.4Lesmis Network

4.2K-means Experimental Results and Analysis

4.2.1Choice of Parameter

4.2.2Comparative Experiment of Unweighted Social Network

4.2.3The Experiment of K-means on Weighted Network

4.3Hierarchical Clustering Experimental Results and Analysis

4.3.1Choice of Parameter

4.3.2Comparative Experiment of Unweighted Social Network

4.3.3Experiment of Hierarchical Clustering on Weighted Network

4.4FCM Algorithm and Experimental Analysis

4.4.1Performance Analysis

4.5Conclusion

Chapter 5Conclusion and Future Work

5.1Conclusion

5.2Future Work

References

Acknowledgements

Biography