节点间依赖度的社团结构划分范文

《物理学报》2014年第十二期

1方法的描述

1.1主要思想在大量的实验和观察中发现,在划分社团结构的过程中,一个节点的划分往往依赖于和它有最多公共邻居的邻居节点,或者依赖于它的大多数邻居节点的划分.

1.2基本概念1)节点对节点的依赖度节点a对它的邻居点b的依赖度Da,b定义为其中na,b表示节点a和节点b的共同邻居的数目,ka表示节点a的度.称节点a为起始节点,节点b为终止节点.2)节点对社团的依赖度节点a对社团C的依赖度Da,C定义为其中na,C表示社团C中节点a的邻居的数目.3)依赖节点如果节点b是节点a的一个邻居节点,并且节点a对节点b的依赖度不小于节点a对它的其他邻居节点的依赖度,则称节点b是节点a的一个依赖节点,称a对b的依赖度为节点a的最大依赖度.4)节点对社团的条件依赖度节点a对社团C的条件依赖度Dam,C定义为5)社团的公共节点如果一个节点对几个社团有着相同的依赖度和条件依赖度,那么称这个节点是这几个社团的公共节点.

1.3实现步骤以下结合对著名的Zachary空手道俱乐部人际关系网络[29](图3显示了该网络的原始状态)的社团划分过程来说明本文的社团划分方法.1)去除复杂网络中度为1的节点,并将它们邻居的度减1,直到该复杂网络中不再存在度为1的节点.在复杂网络中划分社团结构时,度为1的节点必然和它的惟一邻居归于同一社团,而它的存在对它的邻居的归属没有任何影响,因此,在划分社团之前可先将这类节点去除.在空手道俱乐部网络中,去掉度为1的节点12,并将节点1的度减1。2)计算复杂网络中所有节点的最大依赖度,并在这些最大依赖度中找到最大值Dm.找到这个最大值Dm所对应的所有起始节点(这些节点须具有惟一的依赖节点),将它们分别和各自的依赖节点组成小的社团.这些依赖节点称为社团的初始节点.表1给出了空手道俱乐部网络中各节点的最大依赖度,在本步中Dm的值为1,表2显示了这本步得到的2个社团.3)对于社团的初始节点或者未划分到社团的节点s,如果s对现存的某个社团的依赖度大于0.5,则将节点s吸收进这个社团;如果节点s对它的邻居的最大依赖度不小于上步中的Dm,且s对于某个社团的条件依赖度大于0.5,则将节点s吸收进这个社团.如果节点s是某个社团的初始节点,则将节点s所在社团中的所有节点吸收进这个社团中.表3显示了经过本步骤得到的社团的结果,13和27两个节点对两个社团的依赖度分别大于0.5,被吸收进对应社团.4)重复步骤3),直到没有节点被吸收进社团.此时,从未划分到社团的节点和社团的初始节点的依赖度中找到最大值,将对应于该最大依赖度的具有惟一依赖节点的起始节点s吸收进社团(如果终止节点属于这个社团),或者将节点s和终止节点组成一个小的社团(终止节点不在一个社团中).在对空手道俱乐部网络的划分中,本步骤的最大依赖度为0.917,对应于节点33对节点34的依赖度,将节点33吸收进社团2.5)重复步骤4),直到没有节点被吸收进社团并且没有新的社团成立.6)此时社团外的节点与它们的邻居关系不够紧密或者具有一定的歧义性.在空手道俱乐部网络中,此时社团外的节点为6,7,10,17.计算社团外节点对现存社团的依赖度和条件依赖度,并从这些依赖度和条件依赖度中找到最大值,将对应的节点(这些节点须具有对应于该最大值的惟一的社团)吸收进相应的社团中.如果有节点满足步骤3)的条件,则执行步骤3).直到没有节点被吸收进社团为止.表4显示了本步骤后空手道俱乐部社团的结果.7)对于现存的社团,如果社团规模过小(例如社团中节点数目少于网络中节点总数目的5%),则将该社团中的节点依照上述步骤重新划分入现存的满足条件的其他社团.在对空手道俱乐部网络的划分过程中,没有出现规模过小的社团.8)对于未划分到社团的节点,根据步骤5)可知它们满足公共节点的定义,属于与它们相连的社团的公共节点.在空手道俱乐部网络中,节点10作为社团1和社团2的公共节点而存在.重新计算所有节点对现存社团的依赖度和条件依赖度,确保所有节点对它所处的社团的依赖度大于对其他社团的依赖度,或者在依赖度相等的情况下有最大的条件依赖度,否则,将不满足条件的节点以及受它归属影响的节点重新划分到合适的社团.经过以上步骤,再将步骤1)中的度为1的节点划归它们邻居所在的社团中,即可得到该复杂网络的一种社团划分.对空手道俱乐部网络,度为1的节点12属于社团1,其他节点的划分与表4保持一致,节点10是两个社团的公共节点.

1.4复杂度分析对于一个包含n个节点和m条边的复杂网络,本文算法在实现过程中,步骤1)所需的时间复杂度为O(n).步骤2)计算节点的最大依赖度所需的时间复杂度为O(mn),为便于步骤2)和步骤4)从大到小取用,将网络中所有节点的最大依赖度排序,所需时间复杂度为O(nlog2n).将一个度为k的节点吸收进社团最多需要计算k次节点对社团的依赖度,每次计算的时间复杂度为O(k),故总的时间复杂度为O(k2),将所有节点吸收进社团的时间复杂度为O(nk2).网络中节点的平均度为2m/n,而对于稀疏网络,O(m)等价于O(n),故本文算法的时间复杂度为O(n2).

2实验结果与分析

在对Zachary空手道俱乐部人际关系网络的实验中,本算法得到了和实际情况完全一致的两个社团,如图4所示.而由于节点10和两个社团都分别有一条边相连,符合关于社团公共节点的定义,将它划分为这两个社团的公共节点.Lusseau等在新西兰对62只宽吻海豚的生活习性进行了长时间的观察,他们研究发现这些海豚的交往呈现出特定的模式,并构造了包含有62个结点的社会网络[30].如果某两只海豚经常一起频繁活动,那么网络中相应的两个结点之间就会有一条边存在.本文算法将海豚社会网络划分为4个社团,如图5所示,节点39为它所连接的两个社团的公共节点.美国足球队网络(文献[5]中的一个例子)中,每个节点代表了参加美国2000年橄榄球赛季的高校代表队,连接两个节点的边表示对应的两支球队之间至少曾有过一场比赛.美国足球队网络包含了115个节点和614条边.本文算法将该网络划分为7个社团,如图6所示,红色线条将网络划分为7个部分.在对空手道俱乐部网络的划分中,前文提到的谱平分法[10,11],GN算法[14],Tyler等在GN算法基础上提出的新算法[31]等,都将节点3作为争议节点划分到了错误的社团中.表面上看,节点3和两边的社团都有同样数目的边相连,但是实际上,以节点1为中心的社团中节点3的邻居间的联系更为紧密,节点3对节点1的依赖度更高,故将节点3划分到节点1的社团中.节点10和两个社团分别有一条边相连而被划分为公共节点,本文所得的结果更加符合实际情况和社团结构的定义.在文献[14]中提出了一种得到普遍认同的、对社团结构划分质量的评价标准:模块度Q值,Q值较大,表明该算法所做划分较好.表5是本算法和其他一些算法对海豚社会网络和美国足球队网络所做划分的Q值的比较.从表5可以看出,本文算法在这些复杂网络尤其是节点层次明显的网络的社团划分上有相当不错的表现。

3结论

本文提出了一种新的基于节点间依赖度的在复杂网络中划分社团结构的方法,定义了节点对它的邻居的依赖度以及节点对社团的依赖度和条件依赖度.首先找到具有惟一依赖节点且最大依赖度不小于其它节点的节点,将它和它的依赖节点组成社团,然后对社团的依赖度和条件依赖度满足要求的节点吸收进社团或者继续组成新的社团,直到所有节点都被划分到社团.算法的设计使得划分得到的社团中,每个节点对它所在社团的依赖度都不会小于它对其他社团的依赖度,也就是说,任何节点都和它的尽可能多的邻居划分到同一个社团,和任何节点相连的边都尽可能多的成为社团内部的边,使得结果更符合社团结构的定义.通过对3个经典实际网络的测试,本文算法都取得了不错的结果,而算法的时间复杂度为O(n2),达到了较高的水准。

作者：王兴元赵仲祥单位：大连理工大学电子信息与电气工程学部