第 1 章 绪论
1.1 研究背景及意义
随着人与人之间的联系不断增强，现实中的社交网络结构也变得规模日渐增加，对于复杂的社交网络的分析工作也涉及到了各种跨学科的理论和方法，为理解人类各种社交关系、行为特征以及信息传播过程提供了量化的分析。兴趣、话题、行为等相同的人更容易形成密集的群体，而不同群体之间的相似性就会小很多，所以这也就是社区结构的概念，社区内的连接较为紧密，社区之间的连接较为稀疏。
随着研究者对社会网络分析的日益深入，社交网络分析中形成的理论、方法和技术已经成为了一种重要的社会结构研究范式[1, 2]。其一是“小世界现象”理论，有的研究者提出了“小世界现象”的论断，认为地球上的任何两个人都可以平均地通过一条由 5 位联系人组成的连接而联系起来[3-5]。后来美国心理学教授通过设计一个连锁信件实验，提出了著名的“六度分割（Six Degrees of Separation）理论” [6-8]。另一个是幂律分布理论，现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，简而言之称之为 Zipf 定律，即马太定律[9, 10]。将度分布符合幂律分布的复杂网络称为无标度网络，并且无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的攻击性。
1.1 研究背景及意义
随着人与人之间的联系不断增强，现实中的社交网络结构也变得规模日渐增加，对于复杂的社交网络的分析工作也涉及到了各种跨学科的理论和方法，为理解人类各种社交关系、行为特征以及信息传播过程提供了量化的分析。兴趣、话题、行为等相同的人更容易形成密集的群体，而不同群体之间的相似性就会小很多，所以这也就是社区结构的概念，社区内的连接较为紧密，社区之间的连接较为稀疏。
随着研究者对社会网络分析的日益深入，社交网络分析中形成的理论、方法和技术已经成为了一种重要的社会结构研究范式[1, 2]。其一是“小世界现象”理论，有的研究者提出了“小世界现象”的论断，认为地球上的任何两个人都可以平均地通过一条由 5 位联系人组成的连接而联系起来[3-5]。后来美国心理学教授通过设计一个连锁信件实验，提出了著名的“六度分割（Six Degrees of Separation）理论” [6-8]。另一个是幂律分布理论，现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，简而言之称之为 Zipf 定律，即马太定律[9, 10]。将度分布符合幂律分布的复杂网络称为无标度网络，并且无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的攻击性。
“社区”的定义，从直观上讲，社区是网络的一个子集，可以形成一个独立的、连通的子网络结构。所以社区结构作为复杂网络的共同拓扑属性之一，引起了各个领域的广泛关注[14, 15]。社区检测的一个常见的思路是，社区内的连接紧密、社区之间的连接稀疏[16-18]。这一想法是由模块化的指标进行捕获的，对于一个网络结构，可以将其划分为多个社区，从而实现最佳的模块化。优化社区结构的质量功能是一种流行的社区检测策略，例如模块度优化[19-21]。正像一个社交网络图由成千上万个节点及其连边组成一样，社区也有一系列的节点和连边组成，故节点和社区之间存在多对多的关系，一个节点可以存在多个社区中，一个社区包含了多个节点。因此研究者经常把一个社区看作一个抽象的节点，只不过该抽象节点表示的信息更加丰富，规模比普通节点要大很多，这样一来对于社区结构的处理就方便了很多[22, 23]。一旦我们将一个网络划分称为社区，就可以根据它们的社区给节点进行着色，并选择一个能够体现社区结构的网络布局。
..........................
..........................
1.2 相关工作研究现状
本章节将主要从三个方面来分析国内外的相关工作现状，包括图神经网络模型、静态社区检测算法、动态社区检测算法三个方面。
1.2.1 图神经网络模型研究现状
图表示一种离散的网络数据结构，而图网络结构由一系列节点和边的集合组成。随着深度学习技术的不断成熟，深度学习在图像处理、机器翻译、自言语言处理等领域都表现出了很好的应用价值，但是离散的网络图数据对机器学习模型表现得并不友好，因此，图神经网络技术[40-42]便应运而生。图神经网络（GNN）通过网络图中节点之间的联系来提取语义化的信息，存储网络图结构中的节点信息和边的信息。为了更好的理解图神经网络的原理，我们将从原始的图神经网络、图神经网络的变体、图神经网络在社区检测方面的应用共三个方面来了解图神经网络。
原始图神经网络，Scarselli 等人[43]第一次提出图神经网络的概念，被认为是原始的 GNN，将该有监督学习模型分为映射和输出两部分，映射部分为主要提取所有节点的邻居信息，输出部分将节点用等维度的向量来表示，通过 softmax归一化进行多分类预测。原始图神经网络模型在更新节点状态时比较依赖于周围邻居节点的状态，造成了原始图神经网络存在较大的局限性。
本章节将主要从三个方面来分析国内外的相关工作现状，包括图神经网络模型、静态社区检测算法、动态社区检测算法三个方面。
1.2.1 图神经网络模型研究现状
图表示一种离散的网络数据结构，而图网络结构由一系列节点和边的集合组成。随着深度学习技术的不断成熟，深度学习在图像处理、机器翻译、自言语言处理等领域都表现出了很好的应用价值，但是离散的网络图数据对机器学习模型表现得并不友好，因此，图神经网络技术[40-42]便应运而生。图神经网络（GNN）通过网络图中节点之间的联系来提取语义化的信息，存储网络图结构中的节点信息和边的信息。为了更好的理解图神经网络的原理，我们将从原始的图神经网络、图神经网络的变体、图神经网络在社区检测方面的应用共三个方面来了解图神经网络。
原始图神经网络，Scarselli 等人[43]第一次提出图神经网络的概念，被认为是原始的 GNN，将该有监督学习模型分为映射和输出两部分，映射部分为主要提取所有节点的邻居信息，输出部分将节点用等维度的向量来表示，通过 softmax归一化进行多分类预测。原始图神经网络模型在更新节点状态时比较依赖于周围邻居节点的状态，造成了原始图神经网络存在较大的局限性。
..........................
第 2 章 相关技术和理论
2.1 常见的节点表示技术介绍
目前比较常见的节点表示学习技术可以分为以下几种：基于图神经网络的静态社区检测技术和基于增量的动态社区检测技术。
1) 基于图神经网络的静态社区检测技术
第 3 章 基于节点影响力的社区检测算法 .............................. 20第 2 章 相关技术和理论
2.1 常见的节点表示技术介绍
目前比较常见的节点表示学习技术可以分为以下几种：基于图神经网络的静态社区检测技术和基于增量的动态社区检测技术。
1) 基于图神经网络的静态社区检测技术
图神经网络模型通常用于将网络图中的节点映射到低维的向量空间中，即用低维度的向量形式来表示网络中的节点。通过学习网络中节点之间的相似性，包括距离相似性、属性相似性等，得到包含节点信息的向量表示，其中相似性越高的节点之间在向量空间中的距离会更加接近。这充分结合了自然语言领域中处理文本内容的 word2vec 技术，其主要思想就是通过一定规则的学习，将文本单词表示成向量形式，之后利用深度学习中的聚类算法将文本单词进行分类，有利于之后对文本中有价值的信息进行提取。而图神经网络模型就是 word2vec 技术在离散的图结构中的完美应用，既然网络中的节点可以量化为向量的形式，故也可顺理成章的使用聚类技术，对节点向量进行聚类，将相似度高的一系列节点归为一类，也就达到了社区检测的效果。但是基于传统的基于图神经网络的静态社区算法没有现成的图语料库，需要通过遍历节点形成语料库来构造图语料库，然而现有的游走策略，如深度优先、广度优先搜索策略，或者是基于深度优先和广度优先搜索策略的改进，都是基于网络边的拓扑结构的搜索策略，构造的图语料库质量不高，因此基于质量不高的语料库训练得到的节点向量也需要改善，所以在此基础上聚类检测到的社区结构结果也有很大的误差。在 2.2 节本文主要框架中，左边虚线部分表示基于影响力信息的节点表示的社区检测算法，该算法通过定义新的搜索策略，提高了语料库质量；同时保留了网络拓扑结构信息和节点本身的影响力属性信息，提高了社区检测的准确度。
.......................
2.2 本文研究思路及框架
本文在第三章提出了一种基于影响力信息的节点表示方式，提高了节点向量表示的质量，使其语义化丰富，基于该融合影响力信息的节点表示方式进行社区检测会提高检测结果的准确度，按照提出的方式检测到的社区结构随着时间的推移是不断演化的，将检测到的社区结构作为初始时刻的网络社区结构，为了提高最终时刻社区结构结果的准确度，本文提出采用根据模块度粗粒度定位和增量式训练向量细粒度调整的方式计算社区归属，其中增量式训练向量的方式采用第三章提出的融合影响力信息的节点表示方式。显然，在每个时刻检测动态社区时，如果没有采用第三章提出的融合影响力信息的节点表示方式，则节点表示的质量较低，导致计算社区归属概率时不准确，给每个时刻检测社区结果带来误差，使检测结果不准确。
具体来讲，本文在第三章中提出了基于节点影响力的社区检测算法，主要综合保留了网络的拓扑结构信息和节点本身的影响力属性信息，同时融合了节点和社区之间多对多的关系。在随机游走生成语料库阶段通过定义新的搜索策略，既保留了网络的拓扑结构，实现了深度优先和广度优先搜索策略的平衡，又保留了节点本身的影响力属性信息，按照新定义的搜索策略遍历节点得到的游走序列构成的语料库，质量明显提到改善。基于此语料库对网络中的节点进行学习，并通过已知中心节点所属的社区来预测其邻居节点的归属社区情况，
本文在第三章提出了一种基于影响力信息的节点表示方式，提高了节点向量表示的质量，使其语义化丰富，基于该融合影响力信息的节点表示方式进行社区检测会提高检测结果的准确度，按照提出的方式检测到的社区结构随着时间的推移是不断演化的，将检测到的社区结构作为初始时刻的网络社区结构，为了提高最终时刻社区结构结果的准确度，本文提出采用根据模块度粗粒度定位和增量式训练向量细粒度调整的方式计算社区归属，其中增量式训练向量的方式采用第三章提出的融合影响力信息的节点表示方式。显然，在每个时刻检测动态社区时，如果没有采用第三章提出的融合影响力信息的节点表示方式，则节点表示的质量较低，导致计算社区归属概率时不准确，给每个时刻检测社区结果带来误差，使检测结果不准确。
具体来讲，本文在第三章中提出了基于节点影响力的社区检测算法，主要综合保留了网络的拓扑结构信息和节点本身的影响力属性信息，同时融合了节点和社区之间多对多的关系。在随机游走生成语料库阶段通过定义新的搜索策略，既保留了网络的拓扑结构，实现了深度优先和广度优先搜索策略的平衡，又保留了节点本身的影响力属性信息，按照新定义的搜索策略遍历节点得到的游走序列构成的语料库，质量明显提到改善。基于此语料库对网络中的节点进行学习，并通过已知中心节点所属的社区来预测其邻居节点的归属社区情况，
将得到的社区检测结果作为第四章的初始社区结构，接下来第四章提出了基于模块度的增量式动态社区检测模型，通过根据模块度增量进行粗粒度定位变化的社区结构，然后按照不同的情况分别进行增量式向量训练，最后得到所有节点的细粒度社区归属调整，提高了动态社区检测准确度，还原了真实复杂网络的社区结构。
...............................
3.1 基于节点影响力的社区检测算法概述 ........................... 20
3.2 随机游走生成语料库 ......................................... 22
第 4 章 基于模块度的增量式动态社区检测模型 ........................ 36
4.1 基于模块度的增量式动态社区检测模型概述 ..................... 38
4.2 根据模块度增量定位变化的社区结构 ........................... 40
第 5 章 实验 ............................. 55
5.1 实验环境简介 ............................. 55
5.2 实验数据集介绍 ............................. 55
第 5 章 实验
5.1 实验环境简介
本课题进行实验的平台环境简单介绍如下，
本课题进行实验的平台环境简单介绍如下，
1) 硬件配置
CPU 处理器：Intel(R) Core(TM) i5-8300H CPU @2.30GHz 2.30 GHz
内存：8.00GB
硬盘：512GB
2) 软件配置
操作系统：Windows 10, 64 位操作系统
开发工具：JetBrainsPyCharm Community Edition 2019.2, Visual Studio Code Python 版本：Python 3.7.3 Anaconda 版本：Anaconda Command line client (version 1.7.2)
........................CPU 处理器：Intel(R) Core(TM) i5-8300H CPU @2.30GHz 2.30 GHz
内存：8.00GB
硬盘：512GB
2) 软件配置
操作系统：Windows 10, 64 位操作系统
开发工具：JetBrainsPyCharm Community Edition 2019.2, Visual Studio Code Python 版本：Python 3.7.3 Anaconda 版本：Anaconda Command line client (version 1.7.2)
第 6 章 总结与展望
6.1 总结
随着人际关系复杂性的提高，社交网络结构的复杂度和规模也在发生变化，对复杂网络的社区结构的研究也变得尤为重要，又由于深度学习技术的发展，基于图神经网络的社区检测方法越来越受到人们的关注。然而会出现语料库质量不足、学习到的节点向量语义信息不丰富，进而导致社区检测的结果不准确的问题，也是迫在眉睫的。在动态社区检测过程中，对于每次结果误差的消除，提高最终检测结果的准确度，还原真实网络中的社区结构，是现有研究工作面临的又一个挑战。
为了解决上述两个挑战，本文首先对现有的基于图神经网络的社区检测算法进行分类总结和分析，并指出现有算法中的不足之处，并在目前已有的研究工作的基础上进行了改进，提出了基于节点影响力的社区检测算法。随后，对于动态演化的社区检测进行了详细的分析，并提出了基于模块度的增量式动态社区检测模型。本文详细说明了在基于节点影响力的社区检测算法中如何进行随机游走生成语料库，基于影响力信息的节点的表示学习以及如何进行静态社区检测。在基于模块度的增量式动态社区检测模型中，本文详细说明了如何根据改进的模块度对动态社区结构进行粗粒度提取和划分，如何采用新增节点的动态社区检测和移除旧节点的动态社区检测来对上一步的划分结果进行细粒度的调整，最终得到当前时刻的动态社区检测情况。
参考文献（略）
6.1 总结
随着人际关系复杂性的提高，社交网络结构的复杂度和规模也在发生变化，对复杂网络的社区结构的研究也变得尤为重要，又由于深度学习技术的发展，基于图神经网络的社区检测方法越来越受到人们的关注。然而会出现语料库质量不足、学习到的节点向量语义信息不丰富，进而导致社区检测的结果不准确的问题，也是迫在眉睫的。在动态社区检测过程中，对于每次结果误差的消除，提高最终检测结果的准确度，还原真实网络中的社区结构，是现有研究工作面临的又一个挑战。
为了解决上述两个挑战，本文首先对现有的基于图神经网络的社区检测算法进行分类总结和分析，并指出现有算法中的不足之处，并在目前已有的研究工作的基础上进行了改进，提出了基于节点影响力的社区检测算法。随后，对于动态演化的社区检测进行了详细的分析，并提出了基于模块度的增量式动态社区检测模型。本文详细说明了在基于节点影响力的社区检测算法中如何进行随机游走生成语料库，基于影响力信息的节点的表示学习以及如何进行静态社区检测。在基于模块度的增量式动态社区检测模型中，本文详细说明了如何根据改进的模块度对动态社区结构进行粗粒度提取和划分，如何采用新增节点的动态社区检测和移除旧节点的动态社区检测来对上一步的划分结果进行细粒度的调整，最终得到当前时刻的动态社区检测情况。
参考文献（略）