论文部分内容阅读
现实世界中,许多复杂系统可以用复杂网络来表示,蛋白质相互作用网络、航空航线网、万维网、电话通讯网、人际关系网等。复杂网络研究作为一个新兴的学科方向,吸引了来自不同学科领域研究人员的关注。对复杂网络的研究有助于揭示复杂网络表示下的不同复杂系统中存在的一般规律,在生物学、社会科学等诸多学科中具有重要意义,同时对于理解网络的结构和行为也至关重要。传统方法通常寻找的是彼此分割的社区,但实际当中,有的个体可能同时属于多个社区,也即重叠的社区结构。以往社区结构分析的研究主要集中在无向无权网络上,实际网络中,边通常是带有权重和方向的。当前对有向、加权网络社区结构划分的普遍做法是简单地忽略边的方向和权重。但这样会损失掉其中包含的重要拓扑结构信息,从而无法正确有效地划分网络的社区结构。本文在介绍了复杂网络研究中社区结构的定义和相关指标以及用于复杂网络社区结构发现的几种经典算法的基础上,提出了两种复杂网络社区发现算法,具体如下:(1)针对无向无权网络中的非重叠社区及重叠社区发现问题,提出了一种基于高斯核相似矩阵的复杂网络社区发现算法。根据谱平分法的步骤,基于高斯核相似矩阵来寻找网络社区。首先,通过调节高斯核参数来改变相似性尺度,寻找对应模块度值最大情况下的网络划分,得到非重叠社区。又由于高斯核参数的改变会导致社区结构关系不稳定的节点发生跳离,因而对非重叠社区发现算法稍作处理即可发现重叠节点。最后,分别利用人工合成数据、空手道俱乐部网络数据和政治书籍网络数据进行了测试,说明了本文算法的可行性和有效性。另外,对加权网络的带权邻接矩阵稍作处理,即可将本文算法用到加权网络中,网络数据的测试结果表明该算法同样是可行的。(2)针对有向网络中的重叠社区发现问题,提出了一种基于PageRank算法的复杂网络社区发现算法。该算法用节点的PageRank值来近似地描述节点在网络中的重要性程度,帮助寻找中心节点。再依次以中心节点为核心逐层向外扩展,达到设定的终止条件后形成以该中心节点为核心的局部社区,然后对不同的局部社区进行合并,观察模块度值的变化,取模块度值最大的划分为最终结果。由于节点可以属于不同的局部社区,所以该算法对于寻找重叠社区同样适用。最后,分别对人工合成数据和犯人网络数据进行了测试,结果也表明了本文算法的可行性及有效性。