第一章 引言
1.1 课题背景和意义
现实世界中，每个个体或事物都至少处于一个系统中，不同的个体之间通过各种方式进行着交互，如万维网[1]、交通运输系统[2,3]、电力系统[4]等。如果将系统中的每个个体看成一个节点，将个体间存在的交互关系看成边，进而将一个系统抽象为一个复杂网络，可以发现每个系统虽然都具有自身的特点，但是这些被抽象出来的网络却具有一些共有的特性：无标度[5]、自组织[6]、社区结构[7,8]等。随着各种新兴技术的高速发展，人与人、人与物、物与物之间的交互越来越频繁且复杂，个体接受的信息和数据量也随着所处系统的快速增长而越来越大，这些新兴技术的发展一方面使得人们对现有系统的认识与理解越来越深入，另一方面也促使人们对现有系统的完善与升级，从而形成了一个反馈，使得人们直接通过现实世界理解各类系统变得越发困难。复杂网络与现实世界的结合，使得人们对现实世界的理解更为容易，也便于学者们通过复杂网络模拟现实世界，一些无法在现实世界进行的实验可以通过模拟实验，从而发现一般性的规律并将他们应用于现实生活中，能够为经济、政策以及社会活动提供导向性的作用，例如网络的稳定性、博弈、传染病的传播、网络的同步等等[9-14]。
在过去的二十年里，复杂网络中的社区结构问题引起了人们的广泛关注，社区结构可以看成是社会关系网络中的朋友圈，位于同一社区内部的个体相似程度较大或者内部交互较频繁，位于不同社区间的个体相似程度较低或交互较少[7,8]。此外，在一个大的社区中，虽然整体上内部节点的相似程度较大，但是实际上它内部还可以划分出更多小的社区，简言之，大社区内部不同节点间有可能存在相似程度更高的小社区集合。对于社区结构的分析研究开始成为一个新热点是在Newman 提出模块度的概念之后[7,8]，他给出了社区结构的定义以及衡量社区质量的模块度计算公式，这些对于找到网络中的社区结构起着非常重要的作用。
研究复杂网络的社区结构对于理解复杂网络的功能以及分析节点间的相互作用关系，对于理解网络的拓扑结构以及网络的演化等都有着重要的意义。如在现代生物网络中[15-17]，研究者们通过对蛋白质间的相互关系，发现了蛋白质间组成的社区结构，进而推断出了具有相似功能的蛋白质；在万维网中[18,19]，通过对页面的关键信息进行提取，利用提取的信息构建不同页面间的相互关系网络，从而检测网络中的社区结构，为检测页面的相似性以及提供相关内容的推荐提供了更为可靠的结果。
..........................
1.2 论文主要内容
本文主要从优化检测结果和改进评价指标出发，提出适用于不同网络的社区检测算法，通过与一些具有代表性的算法在效率和准确性上进行比较，证明所提算法的正确性。主要内容可以包括以下四个方面：
1）提出了衡量节点相似性的节点相关强度指标，并由此提出无向无符号网络上的社区检测算法。社区结构表明内部节点具有较高的相似度，通过最大化网络的社区结构的质量可以达到社区检测的目的，但是却存在分辨率的问题[51]，也就是无法发现小社区结构。利用节点的相关强度，可以使得具有较大相关性的节点被划分为同一个社区中。通过仿真实验，验证了基于节点相关强度的社区检测算法能够给出合理的社区划分方案，同时，检测到的社区的数量也与实际的社区的数量相近。
2）为了解决数据来源较少的问题，提出了有向网络转换为无向网络的转换算法。现有的社区检测算法大多是针对无向网络，处理有向网络的能力不足，这主要是因为有向网络中根据与节点相连的边的权重很难将节点划分到适当的社区中，还需要考虑边的指向。此外，由程序生成的无向网络虽然具有现实世界网络的特性，但是没有考虑到边的指向问题。由此我们采用亲和力指标来表示节点在网络中的受欢迎程度，然后通过动态迭代的方式对网络进行演化，使得演化后的网络趋于稳定并将它转换成无向网络。
3）改进现有的符号模块度函数，提出了基于重构网络的无向符号网络上的社区检测算法。符号网络表示网络中可能同时存在着正权边和负权边，对应到现实世界中，则表示个体间的交互是带有情绪的，善意的情绪可以表示为正权边，
恶意的情绪可以表示为负权边。现有的用于评价无向符号网络上的社区结构的质量的指标中，它是单独对每部分计算后进行加权求和来表示社区的质量，这样可以保证社区的质量位于 0 到 1 之间，但是却没有考虑将符号网络的特性表现在结果中。因此，我们提出了改进的符号模块度函数，并通过重构网络的方式来检测网络社区，使得计算的结果可以显示网络的符号特性。实验结果显示，所提算法能够发现无向符号网络中的社区结构，并且符合实际的社区划分方案。
........................
第二章 复杂网络和社区检测算法概述
2.1 复杂网络简介
进入 21 世纪以来，复杂系统与复杂性科学开始成为了科学发展的前沿，它以研究各类系统中的特性和规律并将之应用于实际生活中为目的，如生态系统、电力系统、社交网络系统等等，而这也是系统科学与控制理论在新时代的基础研究中所面临的一个重大挑战[52]。复杂网络在我们日常生活中无处不在，因为任何一个系统都可以被抽象为复杂网络。复杂网络中的节点对应着现实中的个体，边对应着不同个体间的交互，对于一个加权网络而言，边的权重则说明了交互的强度、频率等数据[53]。
..........................
2.2 社区检测简介
复杂网络除了有上面提到的几个统计特性之外，社区结构也是复杂网络的重要特性之一，也是研究复杂网络的热门课题，特别是在 Newman 等人提出了模块度函数指标[7,8]之后。在现实的社会关系中，往往存在着朋友圈、熟人圈之类的结构，这些结构具有一个明显的特点：内部成员之间联系较为紧密，不同圈的成员之间联系较为稀疏。复杂网络中的社区结构最常用的定义就是这种基于频数的定义，
Newman 等人[7]给出了一个具有明显社区结构的网络，如图 2-3 所示。
............................
3.1 工作简介 ............................ 16
3.2 衡量指标 ............................... 17
第四章 基于亲和力指标的有向网络转换为无向网络的算法 ............... 28
4.1 工作简介 ............................ 28
4.2 衡量指标 ........................... 29
第五章 基于重构网络的无向符号网络社区检测算法 ..................... 34
5.1 工作简介 ...................... 34
5.2 衡量指标 ...................... 35
第六章 基于局部信息和动态扩展的无向网络社区检测算法
6.1 工作简介
在复杂网络的各种特性中，社区结构无疑是学者们关注的一个热点，因为无论是无符号网络（仅含正边）还是符号网络（含有正边和负边），隐藏在网络中的社区都表示了内部个体的相似性，而这些相似性在大数据时代对于预测、推荐有着较为重要的意义。然而，现有的多数算法都是基于全局信息来检测社区结构，也就是说，算法运行过程中考虑了全局信息对局部社区形成的影响。可是在一些情况下，获取全局信息是很难的甚至是不可能的，这就使得利用全局信息进行社区检测的算法无法有效且快速的进行社区检测。
由于全局数据无法获取的原因，有研究者提出了利用局部信息进行局部社区检测的算法，例如 Clauset[70]提出基于局部模块度的检测算法，
Luo 等人[71]提出了新的局部模块度的社区检测算法等等。但是它们检测的是一个局部社区，而不是全部，因为算法是从一个初始节点开始，检测网络中和初始节点位于同一个社区的节点，并且需要给定社区成员的最大数量，还是没有解决使用局部信息进行全局社区检测的问题。
........................
第七章 总结与展望
7.1 工作总结
挖掘复杂网络中的社区结构是一个意义重大的研究课题。通过从不同的角度来挖掘网络中的社区结构，能够跨学科交叉验证、发掘网络中相似的个体，对社区内部的节点的相似性进行分析，进而推断出个体在其他方面的相似程度。
目前，虽然研究者们已经提出了许多新颖且有效的社区检测算法，但是还存在着一些可以改进的方面。本文分别从节点的相似性、网络的符号特性以及局部信息角度出发，设计了不同的指标以及算法来进行社区检测。此外，为了充分利用现有的有向网络数据，提出了一种有向网络转换为无向网络的算法。 本文完成的工作主要包括：
（1）设计了节点相关强度的社区检测算法。根据节点的个体属性，我们利用概率统计的知识推导出了两个节点间的相关强度，通过该指标能够表示小社区内部的节点的相似性，进而挖掘出隐藏在复杂网络中的小社区结构。
（2）提出了有向网络转换为无向网络的算法。现实世界中的个体间的交互是存在方向的，并且这些交互可能存在着不同的情绪或者符号，利用交互的符号我们定义了个体的亲和力用于刻画个体在网络中的受欢迎程度。通过对网络进行演化，使得在不同的参数设置下，网络能够通过更新权重给出不同的演化结果。
（3）改进了符号模块度函数的基础上，提出了基于重构网络的社区检测算法。由于现有的模块度函数无法衡量符号网络上的社区结构的质量、现有的符号模块度函数计算的结果无法体现符号网络的特性，我们提出了改进的符号模块度函数，计算结果的符号可以显示网络中正权重的边较多，还是负权重的边较多。同时，将同一个社区的节点进行压缩后再构建网络将使得网络的规模被逐渐降低，从而加快算法的运行，由此提出了重构网络的社区检测算法。
（4）基于全局信息获取困难的原因，提出了利用局部信息来挖掘网络中的社区结构。当网络规模较大时，获取全局信息将会变得困难，使得利用局部信息进行社区挖掘成为研究的重点。现有的局部社区检测算法中需要考虑设置社区的最大成员数量来终止算法的运行，但是在通常情况下是无法明确知道社区的成员数量的，因此我们采用动态扩展的算法，使得社区的成员数量被逐步扩大，直到社区无法吸收邻居节点时将会生成新的社区，如此就能使得社区的数量、社区的成员数量被逐步扩展到合适的值。
参考文献（略）