科学家合作网络的聚类分析

文章编号:1672-3813(2005)02-0030-05

科学家合作网络的聚类分析

张　鹏1,李梦辉1,吴金闪2,狄增如1,樊　瑛1

(1.北京师范大学管理学院系统科学系,北京100875;2.Depart m ent of Physics&A str onomy,

University of B ritish Colu mbia,Vancouver,B.C.Canada,V6T1Z1)

摘要:在自建的经济物理学科学家合作网络的基础上,实现了层次聚类法和介数聚类法,并将他

们应用到对经济物理学科学家合作网络结构的聚类分析中,在理论层次对两种方法进行了比

较,同时将两种算法的计算结果与现实进行对照,发现介数聚类的结果与现实吻合得较好。在

充分理解Ne wman提出的Q函数的基础上,讨论了聚类过程中的最佳集团数。

关键词:复杂网络;集团结构;聚类;经济物理

中图分类号:N94;O414.2文献标识码:A

The Co mm un ity Structure of Sc i en ti f i c Coll abora ti on Network

Z HANG Peng1,L IMeng2hui1,WU J in2shan2,D I Zeng2ru1,F AN Ying1

(1.Depart m ent of Syste m s Science,School of Manage ment,Beijing Nor mal University,Beijing100875,China;

2.Depart m ent of Physics&A str onomy,University of B ritish Colu mbia,Vancouver,B.C.Canada,V6T1Z1)

Abstract:This paper uses a database of collaborati on recording bet w een Econophysics Scientists t o study the community structure of this collaborati on net w ork.H ierarchical clustering and the algorith m of Girvan and Ne wman are p resented t o an2 alyze the data.Comparing the results with facts,the result of G N is better.I n additi on,The best divisi ons of every algo2 rith m are got by functi on Q.

Key words:comp lex net w orks;community structure;clustering;Econophysics

1　引言

自从D.J.W atts和S.H.Str ogatz提出S mallWorld网络模型,并将统计物理学的方法应用于复杂网络研究以来[1,2],经过A lbert2LászlóBarabási[3],S.N.Dor og ovtsev与J.F.F.Mendes[4],M.E.J.Ne wman[5,6]等人前瞻性工作的推动,复杂网络已经成为科学研究特别是复杂性研究的一个重要领域[7,8]。

大量包含多个体和多个体相互作用的系统都可以抽象成为复杂网络,其中每一个个体对应于网络的顶点,个体之间的联系或相互作用对应于连接顶点的边。这种描述方法已被广泛应用于各种实际系统的研究,例如神经元网络、食物链网络、I nternet网络、WWW网络、各种社会关系网络、交通网等等,相关的研究加深了对这些具体系统的理解,并且提出了一系列新的概念和分析方法[3,4]。在这其中引起我们特别关注的一个问题就是网络的集团结构。

网络的集团结构是指顶点之间的连接程度各不相同而形成的结构。在集团的内部,顶点之间的连接程度明显高于不同集团之间的顶点之间的连接程度。集团结构是反映网络结构整体性质的重要特征[9]。近几年在实证研究中,人们已经发现多数的社会、生物网络都存在集团结构[10-12],这在实际中有重要意义。例

收稿日期:2005-02-27

基金项目:国家自然科学基金资助项目(70371072,70431002)

作者简介:张鹏(1981-),女,河北唐山人,硕士生,研究方向为系统理论及复杂网络。

第2卷第2期　　张　鹏,等:科学家合作网络的聚类分析如:在爵士音乐网中,集团反映的是音乐人的种族分类;合作网中,集团分别代表的是特定的研究兴趣领域;食物网中,集团代表的是生态系统中的子系统,等等。对于集团结构的深入研究可以帮助我们分析和了解实际系统的特性和结构。

寻找网络中潜在集团的思路与图论、计算机科学和社会学中对图的分割的思想十分近似。目前,研究人员对于网络中集团结构已经进行了初步的研究,提出了一些用于寻找网络中潜在集团的算法。如Spectral

bisecti on 算法[9]、the Kernighan 2L in 算法[9]、层次聚类法[9]和目前应用最为广泛的边介数(bet w eenness )聚类

法[13]。

2　经济物理科学家合作网络的聚类分析

本文对自建的经济物理学科学家合作网络进行结构分析。在文[14]中给出了关于这个网络的部分静态统计性质,此网络中节点代表科学家,边代表节点间的相互作用,即两位科学家合著过一篇或多篇文章则相应的两个节点之间就有边相连。对于经济物理学科学家合作网络的集团结构进行研究是必要的,这样可以使我们在整体上加深对该网络性质的认识,这也正是本文所关注的问题。本文采用的方法是聚类分析。抽取这个网络中的最大连通集团作为研究对象,这个集团中包含了271个点,371条边。分别实现了层次聚类和边介数聚类,从理论上将两种算法进行了比较,并将计算结果与现实进行了对照分析。

2.1　算法介绍

在对社会系统的研究过程中,研究人员发现社会统计分析中,依据顶点间被赋予的关联强度进行聚类的层次聚类法是一个用于探索集团结构的有力工具[9]。层次聚类法分为聚集法和分解法两种,其中聚集法是

首先把每个节点看成一类,先把距离最近的两类合并,然后重新计算类与类之间的距离,再把距离最近的两类合并,每一步减少一类,这个过程一直持续到所有的节点归为一类为止。分解法的过程则反之[15]。

介数聚类法是在原有网络的基础上依据各边边介数的大小依次断边分割的过程,这个算法的关键点在于确定每条边上的介数值。边介数指的是所有通过这条边的任意两节点间最短路径的和,显而易见连接集团间的边的介数会相对比较大。而这个算法的基本思想就是:每一轮通过删除可能连接任意两个集团的边(介数最大的边),逐步使得隐藏的集团显现出来。介数聚类算法的主要步骤如下[10]:计算网络中所有边的介数值;找到并删除介数值最大的边,如果介数值最大的边不止一条,那么随机选择其中一条删除;重新计算剩余边的介数值;重复第一步直至所有的边都被删除。

2.2　算法的实现和讨论

在层次聚类法中,核心问题是计算点与点、类与类之间的距离。本文定义了两种点与点间的距离:在无权网中,

1)d ij =1如果两点间有直接边相连

∞如果两点间无直接边相连

2)d ij 定义为i 点到j 点间最短路径上所通过的边的条数;在加权网中,

1)d ij =w ij 如果两点间有直接边相连

∞如果两点间无直接边相连

2)d ij 定义为i 点到j 点间最短路径上所有边的权重之和。类与类之间距离的定义本文选用的是最长距离法,即:D pq =max i ∈p,j ∈q d ij ,其中p,q 为任意两类[15]。在介

数聚类法中,搜索任意两点间最短路径时,我们采用的是广度优先搜索算法。对于无权网,最短路径定义为通过边的条数;加权网中的最短路径则为所通过边上的权重之和。上述两种算法中的权重定义为:w ij =1/tanh (t ij ),其中t ij 代表的是i,j 两位科学家间合作的次数(公式反映了合作次数的非线性饱和效应)。

本文实现了上述两种算法并得到了不同情况下的若干聚类结果,通过对这些结果的比较分析,并与现实

・13・

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学2005年4月进行对照,可以得出这些结果间是有差异的。本文自行设计了D 函数对聚类分析的不同结果进行了定量刻

画[16],D 值的范围在[0,1]之间,越大代表所要对比的结果间的差异越大。如:加权网中,层次聚类法和边介数聚类法的结果差异函数图(图1)。进一步从算法的角度分析产生这种差异的可能有:层次聚类的应用范围较广,但目标的探索性较强,即一旦给定聚类对象和对象间的距离测度,层次聚类就可以将所谓的类划分出,但类的现实意义有待商榷;介数聚类法是基于网络结构本身的性质设计出来的,其聚类结果可能与现实吻合得较好

。

图1　加权网中,层次聚类法和边介数聚类法结果差异D 函数图2.3　Q 函数

在聚类分析中,研究对象多为集团结构事

先不知道为何的实际系统。对应到算法分析中

就是网络被聚集或分割到何种程度效果最好,

在实际中更有意义?针对这个问题,Ne wman

曾给出了无权网最佳分类数的判定函数Q [13]:

Q =12m 6ij A ij -

k i k j 2m

d (c i ,c j )其中,A 是该网络的邻接矩阵;k i =6j A ij ,即i

点的度;m 是网络中的总边数;c 为任一集团。这

个函数定量的描述了算法每一步所分成的集团

内的边占总边数的百分比,与在相同集团分割下点之间随机连接后集团内的边占总边数的百

分比的差。以经济物理学科学家网络作为加权网进行分析时,为了寻找最佳分类数,我们对Q 函数进行了修正:A ij 表示为连接i,j 两点边上的权重,k i 也随之相应变换,其它量不变。这与Newm an 在文[17]中对Q 函数一般化后的形式相同。Q 值的范围在[0,1]间,Q 值越大代表所分的集团越好,在实际系统的分析中,Q 值的最高点一般出现在013～017之间。本文的经济物理学科学家合作网络的Q 值在[0,016]间。但是在对其它网络(包括自建的投入产出网和猴子网络)进行分析时,得到的Q 值有时会出现负值,这可能与网络的稀疏程度有关。这里的稀疏度定义为网络中的边数与具有相同节点数的完全图的边数的比值,经济物理学科学家网络的稀疏度为1%,而其它Q 函数出现负值的网络的稀疏度都在50%以上。

2.4　聚类结果

将不同算法在不同情况下得到的聚类过程全部记录下来,通过对记录的分析发现:首先不同算法得到的结果不同(图1);在同种算法下,不同条件下得到的结果不同,如:不同的权重赋予带来的聚类结果的差异(图2,3

),这说明权重是影响网络结构的重要量。本文由于篇幅所限,只能选择部分结果进行列举分析。图2　介数聚类中无权与加权结果差异D 函数图　　　　图3　层次聚类中无权与加权结果差异D 函数图

・23・

第2卷第2期　　张　鹏,等:科学家合作网络的聚类分析　　通过Q 函数本文得到加权网下,层次聚类法和介数聚类法分析经济物理学科学家合作网络得到的的最佳分类数(图4,5),每幅图中的数字代表(最佳分类数,Q 函数值)。从图中看出两种算法分别是在10个和23个集团时达到最优。将这两个结果分别与现实作比较,发现介数聚类得到的10个集团是按照地域或研究领域的不同而形成的,具有现实意义,而层次聚类得到的23个集团与现实对照时可解释性不强。为了对聚类结果有一个直观的了解,本文将介数聚类法得到的10个最佳分类集团用Netdra w 软件绘制出来(图6)。图6中1集团的成员大部分都是来自美国波士顿大学,其他的还有来自美国加州大学的4号集团、以色列耶路撒冷大学的10号集团等研究机构,图中9号集团的成员分别来自不同的地方,但他们所关注的领域都是金融市场。所以针对本文中的经济物理科学家合作网络,显然介数聚类法效果更好

。

图4　介数聚类法Q 函数图　　　图5　层次聚类法Q

函数图

图6　介数聚类法10个集团时的分类情况

3　展望

在自建的经济物理学科学家合作网络的基础上,运用层次聚类法和介数聚类法对该网络结构进行了聚类分析,并将得到的聚类结果与现实进行了对照分析。在充分理解Ne wman 提出的Q 函数的基础上,使用其讨论了经济物理学科学家合作网络聚类的最佳集团数。但在分析一些其它网络时Q 函数出现了负值,结果不是很理想,本文给出了对此现象的初步猜想,为此,今后的研究将对Q 函数进行部分修正或提出新的判别

・33・

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学2005年4月函数。在结果分析的过程中,发现权重是影响聚类结果的重要量,权重对网络结构影响是应进一步考虑的工作。

参考文献:

[1]W atts D J,Str ogatz S H.Collective dyna m ics of ‘s mall world ’net w orks[J ].Nature,1998,393:440-442.

[2]Str ogatz S H.Exp l oring comp lex net w orks[J ].Nature,2001,410:268-276.

[3]A lbert R,Barabasi A 2L.Statistical mechanics of net w orks[J ].RevMod Phys,2002,74:47-97.

[4]Dor ogovtsev S N,Mendes J F F .Evoluti on of net w orks[J ].Adv Phys,2002,51:1079-1187.

[5]Ne wman M E J,Str ogatz S H,W atts D J.Random graph with arbitrary degree distributi on and their app licati ons[J ].Phys Rev

E,2001,:02618.

[6]Ne wman M E J.M ixing patterns in net w orks[J ].Phys Rev E,2003,67:026126.

[7]戴汝为,操龙兵.I nternet ———一个开放的复杂巨系统[J ].中国科学(E 辑),2003,33(4):2-296.

[8]吴金闪,狄增如.从统计物理学看复杂网络研究[J ],物理学进展,2004,24(1):19-46.

[9]Ne wman M E J.Detecting community structure in net w orks[J ].Eur Phys J B,2004,38:321-330.

[10]Girvan M ,Ne wman M E J.Community structure in s ocial and bi ol ogical net w ork [J ].Pr oc Natl Acad Sci,2002,99:

7821-7826.

[11]Gleiser P M ,Danon L.Community structure in jazz[DB /OL ].ar Xiv:cond 2mat/0307434,2003.

[12]Ravasz E,Somera A L,et al .H ierarchical organizati on of modularity in metabolic net w orks [J ].Science,2002,297:

1551-1555.

[13]Ne wman M E J,Girvan M.Finding and evaluating community structure in net w orks[J ].Phys Rev E,2004,69:026113.

[14]Fan Ying,L iM enghui,et al .Net w ork of econophysicists:a weighted net w ork t o investigate the devel opment of econophysics[J ].

I nternati onal Journal of Modern Physics B,2004,18(17-19):2505-2511.

[15]郭志刚.社会统计分析方法———SPSS 软件应用[M ].北京:中国人民大学出版社,1999.

[16]Zhang Peng,L i Menghui,et al .The community structure of econophysicist collaborati on net w orks [DB /OL ].ar Xiv:physics/

05050,2005.

[17]Ne wman M E J.Analysis of weighted net w orks[J ].Phys Rev E,2004,70:056131.・43・