应用特征值判别二部图的方法

2022-09-11

复杂网络是一类既非完全规则又非完全随机的网络[1,2]。这种网络广泛存在于物理, 化学, 生物及社会系统当中。模块是许多复杂网络的最突出的属性之一。目前很多关于模块划分的一般算法对具有二部图拓扑结构的网络都不适用, 因为他们大多是将二部图投影到单模式网络后再划分, 这样丢失了很多信息, 为此一些科学家开始探索有关二部图模块划分的算法, 也有科学家开始探索网络的二分性, 并定义了一些定量测量指标。

本文设计了一个基于邻接矩阵特征向量来判定二部图的方法。文章第二部分中, 介绍二部图及其性质;第三部分中介绍判定算法;最后通过实例来验证算法的有效性。

1 二部图

定理:图G是二部图当且仅当图G不含奇圈。

本文考虑的是一类简单无向连通图G, 对于非连通图, 只要将本文方法作用于其不同连通子图即可。设矩阵A= (a ij) n×n为图G的邻接矩阵, 则当图G为二分图时, 其邻接矩阵可通过置换表示成如下形式:

其中B的元素由0, 1组成。设λ为邻接矩阵A的特征值, 则矩阵A的特征方程

由 (1) 、 (2) 、 (3) 式可得:

其中x= (x, 1x2) T, 向量xi是维数为ni的非零列向量 (i=1, 2) 。

A为实对称矩阵, 其可达矩阵A2的第i行, 第j列的元素代表节vi点vj与与同一节点连接的数目。对于无向图, 可达矩阵A2其分块矩阵BBT, BTB亦为实对称矩阵。

现在来证明BBT, BTB为不可约矩阵。先证BBT为不可约矩阵。

证明:设BBT为可约矩阵, 则:

这表明集合V1中存在某些节点与其它节点没有共同的邻接点, 即图G是不连通的, 与G是连通二部图相矛盾, 所以矩阵BBT必为不可约矩阵。同理可证矩阵BTB亦为不可约矩阵。

由非负不可约矩阵的PerronFrobenius定理可知矩阵BBT, BTB具有单一最大特征值λmax, 且其对应的特征向量的各分量都大于0。由于矩阵BBT, BTB的特征值对应于矩阵A特征值的平方, 所以矩阵A具有一个最小特征值。对于特征方程Dx=λx, 如向量y满足该方程, 则向量-y亦满足。

由公式 (4) 、 (5) 可知邻接矩阵A的最小特征值对应的特征向量x的分量1x、x2必须是一个为正向量, 一个为负向量。

2 判定方法

置换是一种可逆变换, 它并不会改变矩阵的特征值, 只会变换矩阵及其特征向量元素的排列方式。所以, 只要图G是一个二部图, 我们一定可以依据图G的邻接矩阵的最小特征值所对应的特征向量的分量的符号来将图的节点集划分成两个不相交集合。

当然, 若图G不是二部图, 其邻接矩阵的最小特征值对应的特征向量也有可能同时具有负的分量和正的分量, 所以不能仅依靠特征向量的符号来判断图是否为二部图。为此还要判断依据这两种分量划分的两个节点集间存在的边数是否等于图G的总边数。

Newman定义了变量R来计算两个模块间边数。具体方法是, 对于图G, 假设可将其分成两个顶点集g1, g2。则连接这两个集合的边数为

为了便于计算他定义了一索引向量S, 其分量

则:。其中m为图的边数。

由上一小节可知, 若据图G的邻接矩阵的最小特征向量所对应的特征向量的符号来将节点划分成两个节点集时, 则索引向量S可依据图G的邻接矩阵的最小特征向量所对应的特征向量的符号写出, 当由此产生的索引向量S, 使R=m (为m图的边的数目) 时, 则所研究图G必是二部图。

3 实例分析

现在用上述方法来对一个实例进行分析, 判断其是否为二部图。边数m=11图G1如图1所示。运用上述算法, 求得该邻接矩阵最小特征值为λmin=-3.2278。其对应特征向量

然后依据v各分量的符号写出索引向量

将S, A代入公式 (6) , 求得R=11=m。所以, 该图可划分为顶点集v1={, 2, 45}, v2={, 1, 3, 67}。实例分析表明本文的判定方法能对图是否为二部图进行很好的判定。

4 结语

本文提出了一种判定二部图的新方法, 该方法主要利用了二部图的邻接矩阵的特征向量的性质。研究发现, 二部图邻接矩阵的最小特征值所对应的特征向量v0的分量符号与节点所属的集合有关, 可以依据v0的分量的符号来对节点进行划分。但是, 对于非二部图, 其最小特征值所对应的特征向量也有可能存在正负分量, 为此还要利用两模块间边数测量参数R。根据图的邻接矩阵的最小特征值所对应的特征向量的分量符号划分节点集后, 再计算R, 若R=m则图G定为二部图。实例分析表明本文所提的方法是有效的。

摘要：本文应用邻接矩阵的特征向量对二部图进行判别。该方法的核心是证明任意连通二部图的邻接矩阵最小特征值所对应的特征向量的各分量非零, 且同号分量对应于同类节点。最后, 将该方法应用于两个实例图, 实验结果表明, 该方法是有效的。

关键词：复杂网络,二部图,邻接矩阵