一种新的重叠社区模块性函数

庄明明,王艺华

目前很多复杂网络算法都能够成功地发现社区,但是并不是每种划分都是最优结果,需要有一种定量的标准来判断何种划分是最好的.为解决这一问题,人们提出了模块性函数Q.同一算法的多种划分结果中,模块性函数值越高,则认为该划分越合理.但需要明确的是,一种划分是否优于另外一种划分存在不确定性,其中主要原因是社区的划分依赖于特定的社团概念及采用的模块性函数[1].本文基于已有的Q函数,提出一种新的重叠社区模块性函数,从理论和实验两个方面证明该函数复合Newman提出的模块性函数应该具备的基本性质.另外,利用复杂网络社团划分算法和经典实验数据,并与经典的EQ函数实验结果进行对比.

1 研究背景及现状

在社区发现算法的发展过程当中,Newman和Girvan[2]最先给出了模块性函数的定义:

其中矩阵e为k×k(将网络划分为k个社团)的对称矩阵,元素eij表示社区i中的节点与社区j中的节点相连接的边的数目在总的边数目里所占的比例;eii则表示社区i内部所有边占全部边的比例;表示连接社区i中的全部节点的边在总的边数里所占的比例;‖X‖ =.同时,Newman和Girvan指出如果所有的节点都在一个社区中,Q函数的值为0;Q越趋近于1,说明社区结果的模块化程度越高.

基于Newman和Girvan提出的Q函数,很多人进行了很多的改进,以使适应不同的网络及社区定义标准.Fortunato在文献[1]中综述了关于加权无向图、无权有向图、加权有向图的硬划分(每个节点只属于一个社区)下的模块性函数.Nicosia等人[3]首先将Newman等人定义的Q函数推广到有向图中,进而提出了评价有向网络重叠社区结构的Qov函数.尚明生等[4]提出关于重叠社区的模块性Qo函数.

当一个节点可能属于多个社区,即出现重叠社区时,这些定义就不适用了.基于此,人们在后续的研究当中,针对重叠社区提出了相应的模块性函数.Shen等[5]提出EAGLE算法的同时,为了能在树状图中选择某一层作为社区发现的结果,提出了一种能够评价重叠社区结构的Q函数的扩展,即EQ函数

其中Ov表示节点v所属社区的数目,A为邻接矩阵,kv为节点v的度,m表示网络中边的数目.

当社区结构是非重叠时(每个节点至多只属于一个社区),EQ的值和Q函数一致.另外,如果所有的节点都在一个社区中,EQ函数的值为0.Shen等[5]指出,较高的EQ值代表着较强的重叠社区结构.

2 一种新的重叠社区模块性函数

对于重叠社区,假设隶属度矩阵为Uk×n,其中k为社区数,n为节点数,Uij表示节点j属于社区i的强度,对任意节点j均有1.结合以上几个重叠社区模块性函数的定义,本文提出新的模块性函数

其中c为社区数,Ci表示第i个社区,ku为节点u的度,m为网络的边数.

文献[3]指出,Newman提出的模块性函数最重要的性质有如下两点:

1)当全部节点都属于同一个社团的时候,Q=0;

2)Q值越高,则所划分的社团结构越合理.

对于Qu,可以证明是满足以上两条性质的.首先,当全部节点都属于同一个社区的时候,对任意u有U1u=1,即有

在一个完全没有社区结构的网络中,一个节点u属于某个社区的隶属度(小于等于1)与同时属于同一个模块的其他邻近节点的隶属度相差是很大的,完全没有关联性,则产生的Q值也是非常小的.相反,若网络有很强的社区结构,若两个节点同时属于一个社区,可以预见的情况下是该两个节点的隶属度大小是相近的,从而产生的模块性函数应该是最大的.即该模块性函数也应该是满足模块性函数的第二个性质.

对于第二个性质,目前尚缺乏对模块性函数优劣进行评判的定性标准,其优劣只能通过实际网络的实验,人为地进行判断其优劣.通过使用比较多的基于非负矩阵分解的重叠社区发现算法[6]对Qu进行实验验证,实验数据为社会学家Zachary用两年的时间来观察美国一所大学中空手道俱乐部34名成员间的社会关系而构造的社会网络数据.他构造的成员之间的社会关系网是基于这些成员在俱乐部内部及外部的交往情况的,该网络包含34个结点78条边[7].该数据是社会网络分析领域中的经典数据集.忽略由于NMF分解造成的不稳定性问题,一次运行结果如图1.

图1 Qu值变化趋势图

从图1可以看出,Qu值在社区数为2时取得最大值,也即最佳划分为两个社区,其后Qu值总体上呈下降趋势,只有一个最大值,可知此模块性函数定义是符合要求的.

3 实验结果对比

目前存在许多真实网络数据,而且被广大的研究者作为实验数据进行相关实验,如Karate俱乐部网络、新西兰海豚网络、美国大学生足球比赛网络数据等.本文也采用这些数据作为实验数据,同时选用基于非负矩阵分解重叠社区发现算法(CNMF)和模糊C_均值重叠社区发现算法(FCMDA)对目标数据进行社区划分,分别计算相应的EQ值和Qu值.实验过程均在同等硬件、软件条件下使用Java语言实现.

3.1 新西兰海豚网络

Lusseau等在新西兰长时间地对62只宽吻海豚的生活习性进行了观察,构造了包含有62个结点的社会网络.他们研究发现这些海豚的交往呈现出特定的模式,网络中相应的两个结点之间有一条边存在,对应的是这两只海豚经常一起频繁活动[8].类似于人的社交网络,如Karate俱乐部网络,从而可以推知,该海豚网络也存在社区结构.新西兰海豚网络数据实验结果如表1.

表1 新西兰海豚网络数据实验Q值

表2 美国大学生足球比赛网络数据实验Q值

从表1可以看出,CNMF算法所取得的Qu值和EQ值均比FCMDA算法所取得的Qu值和EQ值高,从Qu值和EQ值可得到相同的结论:CNMF算法的实验结果优于FCMDA算法.另外,两种算法所得到的Qu值均比EQ值略低.

3.2 美国大学生足球比赛网络

美国大学生足球(橄榄球)比赛网络是2000年秋季美国高校橄榄球甲级常规赛季的关系数据.该网络中一个节点代表一个球队,节点之间的边代表两个球队之间有比赛.该网络共有115个节点、613条边.在比赛的过程当中,这些球队被随机分成12个小组,每个小组有8到12支球队组成.组内球队间比赛多于组间比赛次数,从而很自然地可以认为这些球队之间存在社区结构[9].美国大学生足球(橄榄球)比赛网络的实验结果如表2.从表2可以看出,CNMF算法所取得的Qu值0.226和EQ值0.252 668均比FCMDA算法所取得的Qu值0.146 235和EQ值0.166 858高,从Qu值和EQ值可得到相同的结论:CNMF算法的实验结果优于FCMDA算法.另外,两种算法所得到的Qu值均比EQ值略低.

4 结论

本文主要介绍重叠社区划分评价指标——模块性函数,根据已有的Q函数,提出一种新的重叠社区模块性函数,并从理论及实证两方面证明该函数的可行性.同时,通过复杂网络社区划分研究常用的实验数据和算法进行实验对比,以验证其可行性,本文实验结果中具有一定的可行性,但是其可行性还需要进行大量的实验对比才能够有更好的说服力,后续研究可以尝试从这方面进行.

参考文献:

[1]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486:75-174.

[2]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Phys.Rev.E,2004,69(2):026113.

[3]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanies:Theory and Experiment,2009(3):03024.

[4]Shang M S,Chen D B,Zhou T.Detecting Overlapping Communities Based on Community Cores in Complex Networks[J].Chinese Physics Letters,2010,27(5):058901.

[5]Shen H W,Cheng X Q,Cai K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A,2009,388:1706-1712.

[6]Zarei M,Izadi D,Samani K A.Detecting overlapping community structure of networks based on vertex–vertex correlationss[J].Journal of Statistical Mechanics:Theory and Experiment,2009(11):11013.

[7]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33:452-456.

[8]David Lusseau,Karsten Schneider,Oliver J.Boisseau,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54:396-405.

[9]Girvan M,Newman M.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.