关键词：
复杂网络
社团检测
图正则化
矩阵分解
子空间学习
摘要：
复杂网络广泛存在于现实世界当中,如社交网络、生物网络、脑网络、信息网络等。在复杂网络中,社团结构是一种非常重要的组织结构,它既表现为内部连接紧密,与外部连接相对稀疏的局部拓扑特征,又体现出网络中个体属性的一致性。社团结构与复杂网络的功能、属性、组织结构、动力学行为等方面密切相关。因此,从错综复杂的网络中检测社团结构,对于网络的拓扑结构分析、功能分析和行为预测具有至关重要的意义。近年来,伴随着复杂网络研究的兴起,社团检测已成为多学科交叉的热点研究领域,涌现了一大批社团检测方法。然而,受制于复杂网络本身的复杂性,当前的社团检测仍然存在许多公认的难题。首先,在真实的复杂网络中,各种缺失、冗余、甚至错误的连接几乎无处不在,这些扰动使得真实世界网络的社团结构变得非常模糊,因而难以被准确发现。其次,现实环境中的复杂网络可能同时拥有拓扑结构与节点属性信息,但二者可能并不一致。如何将这两种信息有机、互补地结合来提高社团检测的性能也是一项亟需解决的难题。最后,现实中复杂网络的连接往往十分稀疏,且含有较多扰动和噪声,添加先验信息是一种有效的解决思路。然而,现有的半监督方法大都需要大量的先验信息,代价高昂却并不能被充分有效地利用。因此,如何发掘并高效利用先验信息是另一项重要的技术难题。从上述分析可见,网络的扰动、拓扑结构与节点属性的融合、先验信息的有效利用是当前社团检测中存在三个主要问题。而解决这三个问题的关键就在于如何挖掘额外信息(对网络扰动的鲁棒结构)或利用现有信息(节点属性、先验成对约束),并将其融合到复杂网络的社团检测问题中。图的正则化恰好提供了一种有效的信息融合工具。将图的正则化与基于几何空间的社团检测方法相结合,可以依据不同的额外信息,从不同角度约束网络节点在潜在空间的分布,从而获取鲁棒的社团检测结果。基于上述分析,本文专注于复杂网络的社团检测研究,通过图正则化的学习框架分别提出相关方法以解决上述问题,具体包括以下几个方面内容。(1)针对复杂网络中广泛存在扰动、社团结构模糊不清晰的难题,本文首次尝试将低秩学习方法应用于社团检测问题,提出了一种基于低秩子空间学习的社团检测方法。该方法利用低秩分解获取几何空间中的节点低秩系数矩阵,以精确、鲁棒地描述节点的子空间分布,再将低秩系数矩阵转化为子空间关联图并将其作为图正则化项融入非负矩阵分解框架中,从而同时考虑了原始的邻接矩阵信息和节点的子空间分布信息。实验结果表明,基于低秩子空间学习的社团检测方法优于其他代表性的社团检测方法,其结果更加接近真实的网络划分。(2)针对属性网络中的网络拓扑信息与节点属性信息不一致,多信息有效融合的问题,本文提出了一种基于双图正则化的鲁棒属性网络社团检测方法。该方法充分利用了节点属性和网络拓扑互为补充的优势,将节点属性、拓扑结构、属性相关性三方面的因素同时融入非负矩阵分解的框架之中,并采用L2,1范数抑制网络连接中的噪声与节点属性中的异常值,从而形成新型的双图正则化的鲁棒非负矩阵三分解模型。该模型在非负矩阵分解领域尚属首创。论文推导出了一整套求解方法与迭代更新规则。实验证明,该方法成功融合了网络的拓扑信息与节点属性信息,获取了一致性的社团结构,具有较高的社团检测质量。(3)针对现实中的复杂网络连接往往较为稀疏,且含有较多扰动和噪声,而先验信息的利用却又不充分的问题,本文提出了一种基于链接约束置信度学习的半监督社团检测算法。在半监督社团检测问题中,本文首次结合给定的约束信息和网络拓扑结构信息,通过流形排序的方法对网络中所有链接的置信度水平进行评估,从而派生出更多潜在有用的成对约束信息,来指导社团结构的检测。具体指导过程如下:将获得的Must-Link正先验约束和Cannot-Link负先验约束同时作为图的正则化项融入非负矩阵分解的框架之中。实验结果表明,利用少量先验种子派生出的先验约束在检测社团时表现出明显的优势,使得有限的先验约束在社团检测过程中发挥了巨大的作用。
欢迎来到三峡大学图书馆！
