论文部分内容阅读
复杂网络普遍呈现出社团结构特征。直观上，这意味着复杂网络可能包含一些局部结构模块（即社团），使得每个模块内部联系紧密且与外部联系较为松散。每个节点仅归属于一个社团的社团结构为非重叠社团结构，反之为重叠社团结构。发现社团结构对理解复杂网络的结构和行为、预测其演化都是非常重要的，并且有很强的应用前景。社团挖掘技术的研究已经成为社交网络分析、数据挖掘、信息检索等领域日益关注的焦点。 复杂网络发展十多年来，非重叠社团结构的研究十分活跃，代表性成果有Newman提出用以度量社团结构的模块度概念以及一系列基于模块度优化的社团挖掘方法。由于复杂网络呈现重叠社团结构通常更符合客观实际，近年来人们把非重叠社团结构的模块度概念和相应的社团挖掘方法进行推广用来处理重叠社团结构问题。这其中有一类方法称作谱聚类方法，其基本思路是首先计算网络拓扑图的特定图矩阵的若干个特征向量，然后用FCM等方法来发现重叠社团结构。谱聚类方法有明显的局限性:需要计算多个特征向量、时间复杂度高;使用定量方法描述节点的社团归属问题等。 针对谱聚类方法的局限性，本文对重叠社团挖掘的谱方法作了进一步探索研究，提出了基于Fiedler向量的重叠社团挖掘算法，主要工作包括两个部分。 一、基于网络拓扑图的Laplace矩阵的Fiedler向量的物理意义和Fiedler向量划分图的合理性，提出了仅计算一个特征向量即Fiedler向量的重叠社团挖掘算法(FVOC算法)。对于事先设定的社团个数k，该算法首先对Fiedler向量用k-means方法将图中节点粗略划分成k个非重叠社团，然后采用一种模糊化策略来确定每个节点的社团归属问题。相比于传统谱聚类算法需要计算多个特征向量的情形，我们的重叠社团挖掘算法是高效的。测试算例验证了该算法的准确性。 二、我们的重叠社团挖掘算法需要事先设定社团个数k，但通常复杂网络中社团个数事先并不清楚。针对这种情况，本文设计了一种启发式策略来快速地确定社团划分的合理个数。基于该策略的重叠社团挖掘算法能适用于复杂网络社团个数未事先确定的一般情形。测试算例验证了一般情形下该策略的有效性。