论文部分内容阅读
复杂网络中社区结构的检测对理解网络功能有着十分重要的意义，被广泛用于恐怖组织识别、社交网络分析等实际问题。但随着网络结构的愈加复杂，单纯依靠拓扑信息的社区检测很难获得令人满意的效果。近年来，已提出了一些通过融合各类背景信息的半监督社区发现方法。根据监督信息的类别，这些半监督算法可以分为基于节点监督信息的半监督算法和基于成对关系信息的半监督算法。由于成对监督信息的易获取性和普遍统一性，其成为时下半监督社区发现算法的研究热点。但这些方法在融合效率和自动确定社区个数等方面存在较大的不足，从而限制了他们的实际应用。为了使半监督社区发现方法在现实场景中有着更广的适用范围和更好的性能，论文拟从如何提升半监督社区发现的高效性和自动性这两个方面开展研究，旨在开发能够高效利用监督信息进行自动化（同时检测社区结构和确定社区个数）精确社区发现的算法。具体的说，我们从被动高效监督信息的利用和主动待标注监督信息的选取两个方面提升监督信息的利用率，并通过将非负矩阵分解改进为能自动确定社区个数的模型使采用其作为主要部分的半监督社区发现算法能够实现社区检测的自动化。 本论文主要包括以下三个部分: 1.高效的监督信息嵌入策略。这里，我们首先对一些被广泛使用的基于矩阵的社区发现算法（非负矩阵分析、谱聚类方法及其变种）给出一种全新的统一化解释。此类方法以表示网络拓扑结构的邻接矩阵作为输入，通过优化不同的目标函数获得节点在隐空间中的全新表达，并针对这些新的表达进行聚类操作。之后，基于这个统一化解释，我们提出一个统一的半监督社区发现框架。基于我们的统一解释，节点是根据隐空间中的全新表达进行聚类的。因此只有具有相似隐空间表达的节点才会被分到同一个社区中。如果我们有先验信息指出一对节点属于同一个社区，那么我们应该使这两个节点有着尽量相似的隐空间表达。这里，我们通过在原有待优化的目标函数中引入隐空间图正则来将先验信息与原有拓扑信息相融合。由于我们用目标函数中不同的项来刻画不同信息的作用，这个框架主要有以下两个方面的优点。一方面我们将半监督社区发现当做一个全新的问题进行处理，而不是简单的将其当做传统社区发现算法的前处理过程。另一方面它可以根据先验信息的可信度来平衡拓扑结构信息和先验信息对最终结果的影响。此外，虽然我们引入了监督信息，但是我们提出的框架并没有大幅增加原有算法的时间复杂度。 2.高效的主动链接选择策略。受到主动学习的启发，为了减少对监督信息的需求量，我们提出了一种可以主动选择对性能影响最为明显的链接供人工标注的链接选择框架。通过对现有的社区发现算法的研究，我们发现在传统社区发现算法得到的网络的社区结构中，社区边界上的点是最不确定且最容易被分错的节点。而且要确定一个社区，最主要的就是要确定其明确的边界。因此我们的主要想法是通过传统的社区发现方法（以非负矩阵分解为例）先找出网络中处于社区边界上的节点，并通过人工标注将这些节点与其所属的社区核心节点相连接（连接策略），同时通过进一步分析所获得的监督信息将最有可能是社区间的链接断开（断链策略）。通过以上的两步对网络拓扑结构的操作我们可以比添加随机成对监督信息更加高效地使邻接矩阵的块结构变得清晰。通过迭代上述过程来改善社区发现的算法（以非负矩阵分解为例）的性能。进一步，由于非负矩阵分解算法是初值依赖的，并且在主动链接选择过程中需要迭代的运行多次不同的非负矩阵分解，整个过程需要较长的时间。为了解决这个问题，我们提出了一种加速的策略。由于连续两次迭代过程中的邻接矩阵变化不大，因此我们将上一步非负矩阵分解的结果作为下一步的初始值。这就使得最终的运行速度是原始算法的二十分之一。另外，我们的算法的时间复杂度近线性与网络的规模，并且可以容易的被并行化和分布式。因此我们的算法适用于较大规模的网络。 3.自动化社区发现算法（模型选择）。我们提出了一种自动加权低秩约束的非负矩阵分解算法来进行自动的社区发现（即同时确定社区结构和社区个数）。一种自然的想法是初始化较多的社区数目，再逐步的将这些社区进行合并。主要的想法是首先将分解后的矩阵列数初始化为远大于社区个数，并通过加权的低秩约束将其中的一些列压缩为零。具体的说，我们首先证明通常低秩正则项，即核模，等价于同时地同等程度的将分解后的矩阵的每列压缩到零。因此，为了使一部分列被压缩到零，我们就需要加入一个自适应加权的低秩约束。这就等价于在不同的列加入不同的压缩权重。如果权重较大，相应的列更容易被压缩到零，反之亦然。那么剩下的问题就是如何确定这些权重。这里我们并不是通过人工的方式设定这些参数，而是在这些参数的分布上加入了两个约束。1）不能每个权重都很小，否则加权的低秩约束就起不到应有的作用。2）只能保留一部分的权重很大，因为我们只希望将部分列压缩到零。最后的优化函数是组合了非负矩阵分解的重构误差、加权低秩约束和在权重上的约束。通过最小化目标函数，我们可以使分解后的矩阵具有列稀疏的性质。最终非零列的个数即为社区的个数，且可以使用非零列将节点分到不同的社区中。我们的算法有两大优势。1）我们可以在不增加非负矩阵分解算法复杂度的同时确定社区个数。2)系统中之后一个容易调节的参数。通常情况下这个参数并不需要调节，如果要将网络划分为具有层次结构的社区，则可以适当的逐步增大这个参数。 在人工及真实网络上的性能充分说明了，相比于之前的方法，我们的算法在嵌入监督信息的性能和效率方面方面都有着显著的提升，并在自动性方面有了明显的改善。这些都使半监督社区发现有了更广阔的应用场景。