英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

距离，相异指数和网络社团结构

周海军

（2003年二月13日收到，出版于2003年6月10日）

我们要解决的问题是发现一个复杂网络中的社团结构，在早期，我们介绍了网络随机行走的概念并定义了距离测度，根据这个距离测度，我们计算一个网络中最近邻节点的相异指数并设计一个算法来把这些节点划分到社团分层组织。每个社团的特点是有一个上限和下限的相异性阈值。这个算法被应用到几个人工和真实世界的网络中，并取得了优异的成绩。对于人工生成的随机模块化网络，该方法优于基于边介数概念的算法。就像对于酵母中蛋白质-蛋白质互相作用网络，我们通过他们具有的明确定义的生物功能能识别很多集群。

I.引言

一个节点和边组成的网络图是很有用的工具来描述一个复杂系统中不同作用者之间的相互影响。举个例子，如果我们想要分析酿酒酵母[1]中蛋白质与蛋白质之间的相互作用，我们能将每一个蛋白质表示为图的一个不同节点，如果相应的蛋白质有直接的物质相互作用关系，就在这两个点之间设置一条边，许多这样的网络在社会学、生物学和科技领域中被构成，而且它们通常有结构非常复杂的连接模式。我们需要的是一个能够将复杂网络的节点分类成不同的簇群（社团）的方法。如果一个网络能被适当地分解成一系列功能单元，（a）网络的结构能被更好的理解，网络的不同组成要素之间的关系会变得清晰，（b）能从集群的成员们的功能来推断每个集群的主要功能，（c）通过比较其他成员的功能能启示集群内成员潜在的功能。网络聚类技术因此在生物信息学和蛋白质组学新兴领域的研究中非常重要。

一个好的聚类方法需要满足两个条件：第一，网络的固有结构应被保留；第二，它应该提供一个量化的分辨参数，来记录划分过程中每一级的意义。网络的全球结构应该已经被低程度的分解辨认，并且越来越多精细组织结构随着分解能力的提高而增加。

许多现有的方法[2,3]只考虑每个节点的局部信息，如与其他节点共享的最近邻数量，与其他节点的独立途径数量等等。最近，Girvan和Newman[4]提出了一个简洁的全局算法就是拓展节点自由人中心介数的概念到边。他们的算法运行迭代通过排除中介中心度最高的边。当应用到一个集合的随机模块化网络时，该算法大大的优于一些平常算法[4]。另一方面，它没有提供一个参数来量化社团之间的差异；此外，边介数中心度的概念对未加权网络是最适合的。

在REF[6]中，布朗粒子被引入来测量节点之间的距离。在目前的工作中，我们基于这个距离矩阵延伸REF[6]中的基本思想，定义一个最近邻节点之间的量叫做相异性指数。相异性指数表示两个最近邻节点在同一社团中的差异达到何种程度。由此，一个按层次划分的算法就出现了，它利用相异性指数给出的信息，把一个网络分解成一序列按层次的簇群。每个社团的特点是有一个上限和一个下限的相异性阈值。

这个既能用在加权网络也能用在未加权网络的方法，被应用到几个人工和真实网络，获得了非常令人满意的结果。对于随机的模块化网络，本算法优于Girvan和Newman[4]的方法。当把这个算法应用于酵母蛋白质-蛋白质相互作用网络，我们能识别出许多具有明确生物功能的蛋白质簇群。

在Sec.II，我们回顾REF[6]中的距离测度，并给每对最近邻节点定义一个相异性指数。Sec.III概述了一个以相异性指数为基础的分层次算法，在Sec.IV，该算法被应用于两种人工生成网络和四个真实世界网络。在Sec.V，我们结束我们的工作并做出一个简短的论述。

II.距离测度和相异性指数

在Flake、Lawrence和Giles[7]看来，图中的社团应该满足社团内的节点之间总的相互影响作用比与图中其他节点总的相互影响作用要强这个要求。这是一个非常强的约束。在这项工作中，我们弱化了这个条件，只要求一个节点与它自己社团内节点们的总相互影响作用比与图中任何其他社团节点们的总相互影响作用要强。

我们考虑一个连贯的网络有N个节点，M条边。这个网络的连接图案由广义邻接矩阵A详述。我们假设矩阵A的每个非零元素A_ij的值表示节点i和j之间相互作用强度。节点i到节点j的距离d_ij由从网络上的一个布朗粒子从节点i移动到节点j所需要步数的平均数来定义[6]。在每个节点k这个布朗粒子将在下一步跳到最近邻点l的概率是P_kl=A_kl/sum;^N_m=1A_km。这样定义的距离矩阵是不对称的（一般来说，d_ijne;d_ji）,它是通过求解N阶线性代数方程组获得的[6]。

以任意节点i作为网络的起点，这个集﹛d_i1,hellip;,d_i,i-1,d_{i,i 1},hellip;,d_iN﹜衡量了其他节点们位于距离起点多远的位置。因此，它其实是一个从节点i角度观看的透视的全局网络。假设节点i和节点j是最近邻节点（A_ijgt;0）,从他们的视角观看到的整个网络的差异是能被定量衡量的。我们用下列表达式来定义相异性指数and;(i,j)：

(1)

如果两个最近邻节点i和j属于同一个社团，从i到其他任意节点k(kne;i,j)的平均距离d_ik将会与从j到其他任意节点k(kne;i,j)的平均距离d_jk 非常近似，因此分别基于i和j的两个网络视角将会非常近似。因此，如果i和j属于同一个社团，and;(i,j)就小，如果i和j属于不同社团，and;(i,j)就大。

III.算法

我们用相异性指数来破译网络的社团结构。在求得距离矩阵﹛d_ij﹜和所有最近邻节点的相异性指数﹛and;(i,j)﹜后，算法如下运行。

（1）最初整个网络只是一个单一的社团。这个社团被赋予不同的高阈值theta;_upp也就是所有不同相异性指数的最大值。

（2）每个社团都会介绍一个分辨阈值参数theta;并赋予这个社团最初的值 theta;_upp 。当and;(i,j)≦theta;时，这个算法不能区分最近邻节点i和j，如果出现这种情况，i和j就被标记为朋友。

（3）theta;的值是差异性下降的。社团内所有边都将被检查，由此来判定两个最近邻节点是不是朋友，然后形成社团内不同的朋友集合，每一个集合都包含集合中所有的节点朋友。也可能有节点在社团内没有任何朋友。这些节点中的每一个都根据广义邻接矩阵被移动到与它有最强相互影响作用的集内。在这个操作之后，社团内的节点都被分成一些不相交的集合（这个数字可能是一致的）。

（4）每一个分组中的节点与同组节点间的相互作用要比与社团内其他分组的节点之间的相互作用强烈。为了满足这一要求，我们做了一个局部的调整，把每一个不能满足要求的节点移动到与它有最强总相互作用的朋友集内。这个调整是对所有不稳定的节点一齐进行，并且重复执行到没有不稳定的节点存在为止。

（5）如果社团内的节点仍保留在一起，该算法返回步骤（3）。如果它们被分成两个或更多的组，这个被处理过的社团就赋予一个低的相异阈值theta;_low 等于现在的theta;值并且不再被考虑。这个社团每一个被辨认的子集被视为一个（低等级）社团，它的上相异阈值theta;_upp就是现在的theta;值。当处理另一个被辨认的社团时，这个算法返回步骤（2）。

（6）当所有的社团都被处理后，我们能画出一个树状图来演示不同社团之间的关系和每个社团的上、下相异性阈值。每个社团的节点集合也被显示出来。

上面的程序能被C 语言编程轻松实现。源代码以及下列被研究过的例子的资料[8]将是公开可用的。

IV.应用

我们测试了上述算法的性能，通过将其应用到2种人工网络和三个真实世界的网络。

A.人工随机组合网络

为了与Girvan和Newman[4]的工作定量的比较，该算法首先被应用在人工随机组合网络。这个网络有128个节点，被分成4个32个节点的模块。每个节点平均有16条边连接其他节点，每个节点的边平均被其他模块的节点连接Z_out次。所有的边都被随机设置了2个固定的期望值。本方法能够在Z_out asymp;7的时候恢复网络的模块结构。它在性能上稍优于Girvan和Newman[4]的方法。举个例子，将本方法应用于一个随机图的集合，当Z_out =6.0时，平均只有4.5个节点被错误分类，这些节点每一个都被分配到一个模块内大部分节点的分类识别不同于它的簇群；而用Girvan和Newman[4]的方法平均有13个节点被错误分类。

图1是128个节点和1067条无加权边组成的随机网络模块的社团结构（见主文本如何生成这样一个网络的规则）。在xx—yy模式中，下面的数字中连字符后面的yy数值表示节点xx根据其它来源的群身份。在图1中，一个随机生成的模块化网络的社团结构在Z_out =6.0时被确认，当该分辨阈值超过0.323的时候，整个网络可视为一个巨大的社团。然而在分辨阈值为0.323时，3个大小为32，32,64的子群突然出现。前两个社团对应于网络的两个模块，最后一个是另两个的组合。在分辨阈值为0.319时，这个后来的社团又被分割为两个有32个节点的社团，对应剩下的两个模块。在分辨阈值为0.258时，网络的一个模块被发现分裂成为大小14和18的两个社团。在这个例子中，所设计网络的四个模块对应从0.258到0.319的分辨阈值。

如何像图1所示的那样在聚类分析中体现分辨界限？取模块2、模块3为例，图1显示这两个模块的边之间的相异性指数大于0.323，然而在这些模块内的边的相异性指数约等于0.227，由此可见模块内的边和模块间的边有一个大约0.1的相异性缺口。

很明显通过目前的算法，每一个社团有确定的稳定范围。只有当分辨阈值降低到已确定的水平之下时，亚群才会突然地出现。

B．规则层次网络

这里我们分析Ravasz和同事们[3]研究过的典型层次网络的社团结构，这个网络由几步构成[3]。在n为0级时，生成一个四个节点的完全连通单元。在n为1级时，添加三个这个单元的复制品，这些复杂品的外部节点连接到n为0级单元的中心节点，这些复制品的中心节点则彼此互相连接。这个复制连接过程能被继续到任何想要的n级为止。在图2（a）中展示了一个n为2级的网络。我们注意到[3]传统的网络聚类方法无法发现这样一个网络的层次结构。而目前的方法就能处理的很好，图2（b）中演示了所获得的图2（a）中网络的社团结构。图2（b）中网络中节点的层次结构基本都被保留了。在分辨阈值为1.95时，这个网络被分成四个大小为3的亚群，和一个巨大的62的组成部分。然后再分辨阈值为1.89时，这个巨大的组成部分再次分裂成两部分：一部分有12个节点，并且在分辨阈值为1.52时被进一步分成三个大小为4的亚群；另一部分有50个节点，它在分辨阈值为1.53时被进一步分解成大小为13，13和14的三个亚群。在分辨阈值为0.91时，这三个亚群的每一个又被再分成三个子群。

C．空手道俱乐部网络

在Refs[4,6]中被检查过的空手道俱乐部数据[9]在这里被重新评估。这个网络是加权的，每一条边被赋予不同的力度。目前的算法测出了图3中的社团结构。在分辨阈值1.67时，这个网络分裂成一个有五个节点的小组成部分A和一个有29个节点的大组成部分。在分辨阈值为0.87时，这个大的部分进一步分解成两个亚群，一部分（B）有11个节点，另一部分(C)有18个节点。图3中给出了于实际裂变模式的比较。根据Ref[6]图1（a），这三个组成部分的连接模式是A-B-C的线性连接（A和C之间没有边）。Ref[4]中的算法先剪断了B、C间的边，然后剪断了A、B之间的边；在图3中，这个次序是相反的。当一些组成部分是线性连接时，它们的分层组织可能有一点点的乱。

D．足球队网络

由Girvan和Newman[4]编译，Refs[4,6]中研究的足球队网络在这里被重新调查。用目前方法作用在图4的社团结构。每个节点的实际群身份都被比较演示。根据目前的算法，在0.41到0.64的分辨区域有12个社团。这12个实际群体中，只有第12个群体中的成员分配到其他群体（有很好的理由，因为实际这个群体内的五个成员之间有很少的直接相互作用）。节点111被归类到11组的成员一起，我们已经检查了这个节点有八条边和11组相连而只有三条边连向其他组。节点59被归类到9组的成员一起，我们已经检查到它与9组的相互作用比与其他组的相互作用强。用目前算法显示不同团队的组织结构比传统算法显示的组织结构要好。

E．科学合作网络

Girvan和Newman[4]编译，Refs[4,6]检查过的科学合作网络也被重新检查。这个网络也是加权的[见图5（a）]。目前的算法显示了一个社团结构在图5（b）中。根据实际情况，在全球范围内，这个网络有三个巨大的可比较规模大小的社团。当分辨能力提高时，这些社团中的每一个都被进一步的分解成一些亚社团。

F．酵母蛋白质相互作用网络

酵母蛋白质相互作用网络是在Refs[10,11]中报告的数据基础上构建的，它包含了1471个蛋白质和2770条边（蛋白质-蛋白质的物理相互作用）。这个网络也已经在Ref[6]中被研究过了，这里我们构建了一个比起原来那个削弱了相互影响的网络。首先,自连接被移除了；其次，移除了只有一条边连向网络的蛋白质。第二步持续到没有一阶度蛋白质留下。移除所有一阶度蛋白质的原因是根据Girvan和Newman[4]的思想，只通过一条边连接网络的节点应该和它的最近邻节点属于同一个社团，因此它的情况不用被单独考虑。当然我们已经检查过了当没有执行网络简化过程时结果一样。这个削减过的网络包含871个蛋白质，2043条未加权相互作用（边）。

V. 结论与讨论

在我们早

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[147555]，资料为PDF文档或Word文档，PDF文档可免费转换为Word