（理论物理专业论文）复杂网络的点强度相关研究及其复杂网络在生物领域的应用研究.pdf

扬州大学硕士学位论文 摘要 复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个 方面：( 1 ) 结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。( 2 ) 网 络进化：表现在节点或连接的产生与消失。( 3 ) 连接多样性：节点之间的连接权重 存在诧异，且有可能存在方向性。( 4 ) 动力学复杂性：节点集可能属于非线性动力 学系统。( 5 ) 节点多样性：复杂网络中的节点可以代表任何事物。( 6 ) 多重复杂性 融合：即以上多重复杂性相互影响，导致更为难以预料的结果。 复杂网络可以描述广泛多样的实际系统。十年以来，各种领域的科学工作者 进行了大量的实际复杂系统的网络描述及其实证统计的研究。这里，我们的兴趣 主要集中在所谓的“合作竞争网”的含权情形实证统计研究，并且建议把每个参 与者在每个合作竞争项目中争得的资源定义为它在此项目中的节点权。定义参与 者在项目中的合作关系为它们之间的边。这样，一个项目就可以用一个它包含的 参与者两两连边所构成的完全图来表示。这样的网络不一定是社会网络，也可以 包含其他许多类网络，但是由于拓扑结构具有共同特征，它们的统计性质和动力 学特性也具有共同特征。在我们实证地研究过的实际网络中，我们发现2 0 0 4 雅典 奥运会网、i t 产品销售网、混合饮料网、中学自主招生网、蛋白域相互作用网络 等都可以用广义合作网络来描述。 我们对这些社会以及非社会的系统进行了统计分析：首先，传统的二分图投 影方法丢掉了一些二分图的信息。为了更多地保留二分图的信息，周涛等人在2 0 0 7 年建议了“平均资源分配法”。这种方法假设了平均分配，其边权定义可以运用在 实际上不知道资源信息的情况。其次，我们建议调研一些竞争资源信息可以被获 得的二分图网络，从而更好地描述了真实世界的系统。继而，我们通过含权资源 分配法定义了网络节点的点强度为节点对其邻居的总的竞争影响，以2 0 0 4 雅典奥 运会网、i t 产品销售网、混合饮料网、中学自主招生网为依托，讨论了该点强度 与节点度、多重边点强度等传统的统计性质之间的关系，近一步论证了含权资源 分配法的优越性。 2 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 蛋白域之间的相互作用可以通过网络来描述。目前，复杂网络在生物领域的 应用研究已激发了许多复杂网络以及生物领域的研究人员的兴趣。 复杂系统的网络结构被认为是演化的结果。这里，我们尝试从生物物种中根 本的进化关系来理解复杂网络的演化。为此目的，首先，在4 7 0 个完全序列的物 种中，我们对每一个物种构建蛋白域相互作用网络，因此每一个物种对映一个蛋白 域相互作用网络；其次，我们用最近邻连接思想推断这些物种的进化关系；再次， 在第二步构建的物种中的进化关系被用于第一步中构建的蛋白域相互作用网络的 进化过程。我们分析、观察进化过程：( 1 ) 在网络演化过程中有一个保守的子网结 构。在这个子网中，有较低的度值的节点倾向于保持它们的连接不变，并且枢纽 点倾向优先连接新加入的节点维持其枢纽作用：( i i ) 少数的节点是保守的作为枢 纽点，大多数节点属于有较低度值一类( i i i ) 在网络演化过程中，在许多情况下， 新节点以个体加入网络中。 我们聚焦于合作一竞争网络研究及其在生物领域的应用研究，实证地统计分析 了几个实际系统，从其中得到了一些有趣的结果。但这个工作仍然是浅陋的，期 望相关的工作能够作为一个引子，能够激起研究者们对合作竞争网络及其生物网 络作更深入的研究。 关键词 ：复杂网络，合作一竞争网，平均资源分配法，含权资源分配法，蛋白域， 演化 扬州大学硕士学位论文 3 a b s t r a c t c o n l p l e xn 娟阳r k sm a ti ss h o r to f ah i g l l l yc o m p l c x 时n e t 、加r k a s 廿1 ef o l l o w 吨 1 i s to fp o s s i b l ec 0 m p l i c 撕o n si l l u s 缸砒e s ：( 1 ) s b l j c t l 面c o m p l e x i 够：t h cw i r i n gd i a 鲫n c o u l db e 觚i n t r i c a t et a i l 哲e ( 2 ) n 印釉r ke v o l u t i o n ：m ew i r i n gd i a 莎锄c o u l dc h a i l g e o v c rt i m e ( 3 ) c o i l n e c t i o nd i v e r s i 哆：吐l cl i l l l ( sb e 附c e i ln o d e sc o u l dh a v ed i 侬胱n t w e i g h t s ，d i r e c t i o n s 孤ds i 目琏( 4 ) d y n a n l i c a lc o r 如【p l e x i t ) r ：1 en o d e sc o u l db e n o i l l i n e a r d y i l a m i c a ls y s t 啪s ( 5 ) n o d ed i v e r s i t ) r ：m e r ec o u l db em a n yd i 邪e r e ml 【i n d so fn o d e s ( 6 ) m e 协c o m p l i c a t i o n ：t l l ev 耐o i l sc o m p l i c a t i o n sc a l lh n u c ee a c ho m c r t h ec o m p l e xn e t 、) l ，o r kc a l ld e s 谢b ev 缸e t yd i f c e r e n tp r a c t i c a ls y s 蛔【i l s d e c a d 鼯， s c i e n t i s t si 1 1v a r i o u sf i e l d s 锄p i r i c a ls t u m e sal 踟售em 】i i l b e ro f 廿1 er e a lw o d dc o m p l e x n e t w o r ks ，r s t e m s h e r e ，w e 南c u so nm ei i l t e r e s ti nt h ee m 【p i “c a ls t a t i s t i c a ls t u d i e so f s o - c a l l e d ”c o 叩e r a t i o n c o m p e t i t i o n ，w e i 曲t e dn e t 、o r k s ，a n ds u g g e s t e dt 1 1 a te a c ha c t o r 丘o me a c ho fc o o p 训o n - c o m p e t i t i 伽a c t9 0 tr e s o u r c e si sd e 助e d 鹤m en o d e sw e i 曲t w ep r o p o s ed e 6 n ea c t o r sc o o p e r a t i o n0 rc 0 i n p c t i t i o nr e l a t i o ni i lm l ea c t s 嬲e d g 器i n t h i sw a y ，o n ea c tc a nb ed e s c r i b e db yac o m p l e t e 粤a p hc c i m p o s e db ym ea c t o r sw h e r e e v e r yp a i ro fm 锄a r ec o n n e 曲e dw 油e d g e s s u c han e t 、釉d 【m a yn o tb ea s o c i a l n e 细o r k ，i tc 锄b e l o n gt 0m a i l yo t l l e rk i i l d so fn e t 、阳f k st o o ，b u tb e c a u s et 1 1 et 叩0 1 0 西c a l s 仇l c t u r eh 勰c 0 m m o nc h a r a c t 耐s t i c s ，n l e i rs 嘶s t i c s p r o p e r t i 豁 h a v ec o m 埘l o n c h 锄c t e r i s t i c s 1 1 1o u rs t u d i e d 廿l ea c t u mn e t w o r k s ，w ef o u n dm a ti 1 12 0 0 4a t l l e 璐 o l y m p i cg 锄e sn e t 、) l r o r k ，1 1 rp r o d u c t ss e l l i n gn e t w o r k ，f n j x e dd 血1 1 【sn e 俩o r l ( ，u i l i v e r s 时 i 1 1 d 印e l l d e n tr e c r u i 协1 饥tn e t w o r k ，p r o t e i nd o m a i ni n t e r a c t i o nn e t w o 永c a nb ed 船c r i b e d b y t l l en e t 、r k s w el l a 、，er c s e a r c h e ds o c i a la n dn o n s o c i a ls y s t e m ：f i i 吼o fa l l ，雏l o s i i 唱s 0 m e i 1 1 f o 册a t i o no ft 1 1 e 仃a d i t i o n a lp r o j e ( 姬o nm eb i p a r t i t eg r a p hm c t h o d r bb e t t e rr e t a i l l l e b i p 枷t eg r a p hi i l f o n i l a t i o i l ，z i l o ue ta 1 p r o p o s 。dar e s o u r c 争a 1 1 0 洲0 np r o j e c 廿o nm e l o d u i l d e r 廿l i sa v e r a j 驴r e s o u r c e - a l l o c a 矗o n 私s u i m 砸。玛l eb i p a n i t cg m p hp r o j 剃o nm e 廿1 0 d 4 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 c 姐b ca p p l i e di n 廿1 en c 啪d ( s 、) l ，h c 髓a c n l a l l y 豫舢r c em 如册撕0 ni su i l a v a i l a b l e s o n d l 弘t ob e 往e fd e s c f i b e 也er e a lw o r l ds y s 细玛w ep f o p o s e 遮y 馏t i g 弛gs o m e c o m p e t i r 喀b i p a r t i t e 玳；出sw t 卫e r e h e 他s o u r c ei i i f o 锄撕o ni sa v a i la ：b l e t h e i l ，w e d e f i l l e d l en o d es 慨g t l l 酗t l et o t a lc o m p e t i t i o ni 1 1 f l u e 芏l c eo fa c t o rt 0i t sn e i 曲b o 随 r e l ) ，i n go n2 0 0 4a t l l e 粥0 l y m 】) i cg 锄en 咖o r k 、r rp r o d u c t ss e l l i n gn 帆o d ( ，m i x 酣 d i 证k sn e t w o 比u l l i v i e 鹉i 秒i n d e p e n d e l l tr e c r t l i 锄锄tn e 如，0 r k ，t 0d i s a l s st l l e 心妇t i o no f n o d es m m g t l lc 0 皿e c t i 啊够c 0 删a t i o nw i 廿ln o d ed e 粤优、n m l t i p l ee d g en o d es t r c l l g me t 缸t 0 如砷e rd 即1 0 n s 缸a t e sm es u p 嘶o r i t yo f 廿l er e s 0 w a l l o c a t i o nm e t h o d i | m 瓢以o n sb 酶嗍lp r o t e i nd o m a i 璐c 蠲b ed e s c 曲e db y 也en 酶r k a tp r e s e n t ， 血ec o m p i e xn e 晰o r k 印p l i c 鲥。瑚r e s e 疵hi i lb i o l o 百c a ih a si i l s p i r e dm a n yc o m p l e x n e t w o f i 【s ，a sw e l la sr e s e 卸c h e r si 1 1m ef i e l do f b i o i o 西c a li n t e r e s t t h en e t 、r ks t r i l c t u r e so fc o m p l e xs y s t e m sa r eb e l i e v e dt 0b em er e s u l t so f e v o l u t i o n ht h i sp a p e r ，w ea t t e m i p tt 0u n d e r s t a n dc o n l p l e xn e t 、o r ke v o l u t i o n 舶mt h e u n d 谢y i n ge v 0 l u t i o n a r ) rr c i a t i o n s h i p 锄o n gb i o l o 百c a io 玛a n i s m s f 0 rt h i sp u 印o s e ， 五r s t l y ，w ec o l l s t n l 曲阳p f 抽d o m a i l li n t e r a c t i o nn e 铆o r kf o re a c ho ft 1 1 e4 7 0c o m p l e t e l y s e q u e n c e d0 r g a l l i s m s ，t l l e r e f o r ee a c ho r g a m s mw 鹤1 1 r e l a 嘲诚n 1as p e c i f i cp f 抽 d o m a i ni n t e r a c t i o nn e t w o r k ；s e c o n d l y ，w ei i l f e 盯i e dm e r o l u t i o n a r yr e l a t i o n s h i po fm e s e o 唱血s m s 而ln e a r e s tn e i g h b o rj o i l l i n gm e m o d ；t h i r d l y ，t l l ee v 0 l u t i o n a 巧r e l a t i o l l s l l i p 卸的n go r g a i l i 锄sc 0 i l s m i 甜i nt l l es e c o n ds t 印w 勰u s c d 勰t l l ee y o l u t i o n a 巧c o u 硌eo f p f 锄d o m 咖i n t e m c t i o nn e 附o r kc 0 i l s 讯i c t e di nm ef i r s ts t 印0 1 1 r 觚a l y s i sa b o u tm i s e 、，o l 砸o n a r yc o u r s es h o w s ：( i ) 廿1 e r ei s ac o n s e r y c d 眦k n e t 、) i ，o r ks 虮l c t u r ei i ln 吣 ，o r k e v 0 1 u t i o n i i l l i ss l l b - n e t w o r ：k n o d e sw i m1 0 w e rd e 粤ep r e f 醯t 0m a i n 协i nt l l e i r c o n n e c t i v i 够i n 硼d a 芏l t a n dn b st 髓dt 0m a i l l t a i l lt l l e i r l ea sk l bb ya ：t ! 【a c h e d p r e f ：僦a l l yw 池n c wa d d e dn o d c s ；( i i ) f i e wn o d 嚣a r ec o n s e r v e da sh u b s ，m o s to fm e o t l l e rn o d 鹤a r ec o l l s e r v e d 嬲t l l eo n ew i t l lv e 巧l o wd e 伊e e ；( i i i ) i n l ec o u r s eo f n 酏w o r k e v o l u t i o 玛n e wn o d e sw e r ea d d e dt o 也e n e t w o r ke i m e ri i l d i 啊d u 采l yi l lm o s tc a s 髓o r 勰 c l u s t e 鹤谢廿lr e l 撕v el l i g l lc l 似嘶n gc 0 e 伍c i 饥ti nv e 巧f e wc a s e s 扬州大学硕士学位论文 5 w ef 0 c u so nc o o p e r a t i o n - c o m p e t i t i o nn 咖o r ：| ( sr e s e 砌a 1 1 di t sa p p l i c a t i o 璐i n b i o l o 舀c a l ，e m p i r i c a l 锄ds t 撕s t i c a la 1 1 a l y s i so fs c v e r a lr e a ls y s t 锄s ，丘o m 、】l ，：i l i c h a n u n l b e ro fm e r e s 恤g 嗽；u l t s 、) l r e 坞o b t a i n e d t h er e s e a r c hi sr o u 曲h o w e v 、阳e x p e c t 弱ab e 百n 1 1 i n g ，t l l ew o r kc o u l di n s p i r ep e o p l et 0r e s e a r c hn l ec o o p e r a t i o n c o m p 舐t i 蚰 n e m o r k s 锄db i o l o 百c a ln e t 、) l ，o r k sd e 印l y i k e y w o r d s l ：c o m p l e x n e 附o r k ，c 0 0 p 训i o n c o m p e t i t i o nn e 附o r k s ，a v e r a g e r 器o u r c e a l l o c a t i o n ，w e i g l l t e dr e s o u r c e a l l o c a d o n ，p f i a md o m a i l l e 、r o l u t i o n 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体己经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名： 签字日期：巧年月3 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名：瓣 签字日期： 哆年厂月乡日 导师签名： 签字日期： 鼢掺 q 年毛其户日 6 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 1 1 复杂网络简介 第一章引言 同图论一样，复杂网络的理论源头要追溯到著名的“七桥问题 ( k o n i g s b e r g s e v e n - b r i d g ep r o b l e m ) 。1 7 3 6 年，e u l e r 研究了这一问题并将其抽象为一笔画问 题，从而成为图论研究的滥觞。1 9 6 0 年，杰出的数学家e r d 6 s 和r 6 n y i 提出了随 机图模型，大大地推动了图论的发展。e r 随机图模型是非常优美的模型，这个模 型有个非常优良的性质：对于任意给定的概率p ，要么几乎每一个图都具有某个性 质q ( 例如图的连通性) ，要么几乎每一个图都不具有该性质。然而2 0 世纪以来， 以i n t e r n e t 为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。大量 的实证工作表明，真实网络既不是纯粹随机，也不是完全规则的，e r 随机图模型 已经不能较好地解释真实网络的拓扑特性和统计特征。 在二十世纪末，两个开创性的工作揭开了复杂网络研究的新纪元。一是 c o r n e l l 大学的w a t t s 和s t r o g a t z 在1 9 9 8 年6 月发表在n a t u r e 的小世界网络 的集体动力学；另外一个是n o t r ed a m e 大学的b a r a b 6 s i 和a 1 b e r t 在1 9 9 9 年 1 0 月发表在s c i e n c e 上的随机网络中标度的涌现，这两个工作分别揭示了复 杂网络的小世界效应( s m a l l w o r l de f f e c t ) 和无标度特性( s c a l e f r e e p r o p e r t y ) ，并建立了相应的模型以解释上述特性的产生机理。当然除了小世界效 应和无标度特性外，真实网络还有很多统计上的特征，例如混合模式，度相关特 性，超小世界性质等等。 上述两个重要工作引起了广泛的关注，大量的研究随之跟进，目前复杂网络 的研究主要集中于： 1 、 揭示和刻画复杂网络的统计特性和相应的度量方法； 2 、建立相应的网络模型以理解复杂网络的这些统计特性的意义和产生机制： 3 、通过分析节点特性和网络拓扑，预测和控制整个网络的行为； 4 、优化已有网络的性能和设计新的鲁棒的和稳定的网络，实现网络的同步。 扬州大学硕士学位论文 7 复杂网络研究的重要性在于：首先，它是大量真实复杂系统的拓扑抽象，是 大量复杂系统的复杂性分析的拓扑基础，因此对它的研究被认为有助于理解复杂 系统的复杂性来源及其复杂程度等重要问题；其次，它揭示并解释了真实网络的 统计特征，其研究结果可以解决大量的科学的和工程的实际问题；最后，它有力 地结合了图论、控制论、计算机网络、社会学、经济学等许多过去被条块分割的 不同领域，找出了隐含在这些不同学科后的共同特性，从而提供了多学科、跨平 台的科研合作平台，它的研究结果反过来也必将推动上述学科自身的进步。 1 2 复杂网络一些统计性质 度分布：节点的度岛指的是与f 连接的边数，度分布则表示节点度的概率分 布函数p ( k ) ，它指的是节点有绦边连接的概率。近些年来的大量研究表明，许多 实际网络的度分布遵循以下四种函数：幂律分布( 也称为无标度( s c a l e f r e e ) 分 布) 、指数分布、介于幂律分布和指数分布中间的“漂移幂律”分布( s h i f t e dp o w e r l a w ，简称s p l ) 、正态分布) 【1 - 5 1 。为了减小实际数据显示的统计涨落，常使用累计 分布方法。容易解析地证明：在数据量很大，以至于可以认为趋于无穷，并且数 据不显示明显的跳跃，可以认为准连续时，这四种度分布的累计分布和不累计分 布具有下列对应关系： ( 1 ) 如果度分布为幂律分布，不累计度分布为p ( 七) 露，累计度分布为 p ( 后i ) o c 羔p ( 后) ，则p ( 七) 芘兰七一，茂f j | 一7 出芘七嘶i ) ，即累计后的度分布仍然是 幂律分布，幂指数比不累计分布少l 。 ( 2 ) 如果度分布为指数分布，不累计度分布为p ( 尼) 虻p 终，其中r 0 是一常数， 累计度分布期m 薹m ) ，贝| j 雕) 虻争形p 形擞打，即累计后的 度分布仍然是指数分布，指数不变。 ( 3 ) 如果度分布为s p l 分布，不累计度分布为只七) ( 七+ 口) 一，当口2 0 ，s p l 分布为 互建军：复杂网络点强度袒关研究及其复鍪盟络在生物领域的应用研究 幂函数，当口专，容易证明s p l 趋于指数函数) ，累计度分布为p ( j | a c p ( 七) ， 量i 上。 则，尸( 七) 芘( 七十口) 叼f ( 七+ 口) 一9 掀虻( 七t + 口) 一俨n ，即累计后的度分布仍然是 七= 七 s p l 分布，关键参数a 不变，幂指数少l 。 ( 4 ) 如果度分布为正态分布，不累计度分布也近似为正态分布【4 】。本文后面的所有 相关统计均采用了累计的处理方式 集群系数：对于网络中的某一个节点f 来说，其集群系数q 表示f 的邻点两两互相 链接的概率。c j 的定义如下：若f 的度为岛，则在这岛个邻点之间最多存在生咚 条边，若其中实际存在的边的数目为局，则节点i 的集群系数色被定义为： 弘兰星 t ( t 1 ) 网络的集群系数c 则被定义为网络所有点的群集系数的平均值： y q _ 一， c = l n 点强度：考虑到该节点与近邻节点的边的权重，定义节点的点强度毛，其定义 式为：毛= ，其中嘞其表示两个节点( 忉之间上的边权，r ，是节点f 的邻近 扣l 节点集合。 1 3 生物蛋白质相互作用网络 蛋白质之间的相互作用是很多生物功能实现的基础。在蛋白质相互作用关系 的网络模型中，结点表示蛋白质，节点之间的无向边表示蛋白质之间存在物理的 或生物功能上的相互作用。d i p 【6 】、i n t a c t 同、s t r i n g 网等数据库中集中收录了蛋白 质相互作关系数据。其中d i p 和i n t a c t 数据库收集的是通过生物实验获得的关于 蛋白质之间物理相互作用关系的数据；s t r i n g 数据库不仅包括实验获得的蛋白质 扬州大学硕士学位论文 9 之间物理相互作用关系数据，而且包括通过理论研究预测的蛋白质之间的功能相 互关系数据。和代谢网络相似，在蛋白质相互作用网络中，同样发现了节点度分 布的无标度规律、节点间最短路径的小世界性质，和网络的模块化结构等统计性 质【9 - 1 2 】( 图9 1 3 ) 。 图9 1 3( a ) 不同实验获得的蛋白质相互作用网络的节点度分布；( b ) 节点集群系数与 节点度的关系。图中拟合直线的斜率都是一2 ( 摘自文献【lo 】) 。 蛋白质相互作用网络的无标度性质显示，一些蛋白质在蛋白质相互作用网络中 拥有非常多的相互作用边，处于枢纽的地位；而大多数蛋白质只和少数几个固定 的蛋白质发生相互作用。处于枢纽地位的节点，对网络的结构具有重要意义。对 枢纽节点的破坏，通常导致网络结构的破坏。郑夏雄等人的研究发现【9 ，l 孔，蛋白质 的节点度与蛋白质的生物功能的重要性之间存在相关性。大多数节点度大的蛋白 质，在生命活动中都具有非常重要的生物功能；节点度很小的蛋白质，只有极少 数具有非常重要的生物功能。由于无标度网络中，具有比较大节点度的节点只占 网络很小一部分，因而，由于随机因素导致的破坏只有很小的概率发生在对生物 具有至关重要作用的节点上。蛋白质网络结构的这种性质，使它在进化过程中具 有很好的鲁棒性( r o b u s t ) 。 通过对蛋白质结构和序列的分析，人们发现蛋白质由蛋白域( p r o t e i nd o m a i n ) 构成。蛋白域既是蛋白质的构成单位( b u i l d i n gb l o c k ) ，也是蛋白质的进化单位 ( u n i to fe v o l u t i o n ) ，在进化过程中表现出保守性( 不同物种中的同一个蛋白域， 在组成蛋白域的氨基酸序列和蛋白域的功能上具有相似性) 。虽然目前收录的蛋白 质序列有五百多万条，但发现的各种蛋白域只有1 4 7 5 5 个( i n t e r p r o 数据库【1 1 】， 2 0 0 7 年1 2 月1 6 日) 。这说明，蛋白域之间的重组构成了不同的蛋白质，并且已经 l o 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 知道，具有进化关系的蛋白质拥有共同的蛋白域，蛋白域相互作用关系是蛋白质 相互作用关系的重要反映。通过蛋白域相互作用关系，能够预测蛋白质之间的相 互作用关系。在蛋白域相互作用关系的网络模型中，网络节点表示蛋白域，节点 之间的无向边表示蛋白域之间存在物理的或生物功能上的相互作用。d i m a 【1 5 】和 d o m i n e 【1 6 】两个数据库集中收录了蛋白域相互作用关系数据，包括物理的以及预测 的相互作用。对蛋白域相互作用网络结构的研究，发现了无标度、小世界和高集 群系数等统计性质【l 。 参考文献 【l 】黼dj 觚ds 昀g a t zsh c o l l 鳅i v ed y n 锄i c so fs 撇i lw o r l dn 咖o r k s n 籼e ， 3 9 3 4 4 0 4 4 2l9 9 8 2 b 础a s ia - la n da l b e r tr e m e 昭e 1 1 c eo fs c a l i n gi nr a n d o mn e t w o r k s s c i e n c e ， 5 0 9 5 1 2 ，2 8 6 ，1 9 9 9 【3 】a m a r a l ，lan ，s c a l aa ，b a r t h e l 锄ym ，a n ds t a l l l e yh e c l 嬲s 懿o fs m a l l - w o d d n e t w o r k s ，p r o c n a t l a c a d s c i u s a ，9 7 ：1 1l4 9 ”c1 1l5 2 ，2 0 0 0 【4 】z h 锄gpp ，c h e i lkh ey 踟ut s ubb ，j i nyc h 锄gh ，z h o uy i p ，s 眦 l c ，w a n gb h ，h ed - r m o d e la l l da n p i r i c a ls t u d yo ns o m ec o l l a t 岫r a t i o nn 哪o r k s 5 9 9 ”c 616 p h y s i c aa ，3 6 0 ，2 0 0 6 【5 c h 锄gh ，s ubb ，z h o uy p h ed r a s s o r t a t i v i 锣锄da c td e 蓼d i s t r i b u t i o no f 6 8 7 7 0 2s o m ec o l l a b o r a t i o nn 咖o r l ! 【s p h s i c aa ，3 8 3 ，2 0 0 7 【6 】h 婶：d i p d o e - m b i u c l 乱o d u 【7 h t t p ：肌m n e b i a c u k 恤t a 洲 【8 】h t t p ：s 缸培朋而1 d e ， 9 】h j e o n 吕s p m a s o n ，a - l b a r a b 缸i ，z n o l t v a i ，n a ：t u 4 1 1 ，4 1 ，2 0 0 1 【1o 】s 一h y - 0 咄z n o l 慨i ，a 一lb a r a b 扳，p r o t e 0 i i l i c s4 ，9 2 8 ，2 0 0 4 【1 l 】a w a 印m 0 1 b i 0 1 e v 0 1 1 8 ，1 2 8 3 ，2 0 0 1 扬州大学硕士学位论文 l l 【12 l e a ( i o t s c i e n c e3 0 2 ，17 2 7 ，2 0 0 3 【l3 r a l b e n h j e 0 i 培a n da 一l b a r a b 嬲i n a t u r 岛4 0 6 ，3 7 8 ，2 0 0 0 【14 】h t t p ：肌哪w e b i a c u m n t e 叩1 1 0 15 】 p p a g e l ， m o e s t e r h e l d ， vs 缅n p f l e i l ， d f r i s h m a i l ，b i o i i l f o m a t i c s ， 2 2 ( 8 ) ，9 9 7 ，2 0 0 6 【16 】b r a 曲a v a c h 撕，a 1 b n e e i l l ，t p 硒，t y c k a 肌dr j o n l i ，n u c l e i ca c i d sr e s 锄c h 2 0 0 7 【1 7 】s w u c h 鸭m 0 1 b i 0 1 e v 0 1 ，1 8 ，1 6 9 4 ，2 0 0 1 1 2 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 第二章二分图投影的资源分配方法 2 1 二分图及其投影 二分图是复杂网络中倍受关注的一类，它的主要特点是包含两类节点。我们一 直有兴趣于二分图中被称为“隶属网 的一种。隶属网中的一类节点是在参与某 种活动、事件或者组织的“参与者”；而另一类就是它们参与的活动、事件或者组 织，称为“项目”。在图论中只考虑不同类节点之间的连边。如果关心参与者之 间的关系，可以把二分图向参与者节点按照几何方法直观地投影，得到所谓“单 模式网络，【1 1 。例如，可以用二分图描述电影演员之间的合作关系，其中参与者定 义为演员，项目定义为影片。一条二分图边表示一个演员参加一部影片的演出。 在演员投影图中，一条边则表示两个演员至少合演过一部影片( 也就是相应的两条 二分图边合并为一条投影图边) 。通常的图是所谓的“简单图”，其中的边表示上述 的互相作用存在关系，不能表示作用的频率或强度。合演过二十部影片或一部影 片都表示为一条边。如果把合演的影片数，也就是所谓的“重复边数”定义为边 的“权，就称为“含权网”，可以表述更多的信息。这样定义的边权被广泛地接 受，可以称为“多重边边权 。 a 出： a c i o r s x ，x 3x 气x 、 b i p a m t e a c t o r s p r o j e 删o n 图2 1 1 二分图和其x 方向投影示意图 扬州大学硕士学位论文 1 3 2 2 平均资源分配法 二分图及其投影的描述方法不但适用于合作网络，也适用于其它一些网络。 然而，一般而言，二分图投影以及投影得到的单模式图中的边权定义丢掉了一些二 分图的信息。例如，两个参与者在同一个项目中的互相竞争的剧烈程度取决于参 加这个项目的人数，即所谓的“项目大小”f ，= ，对应二分图邻接矩阵元6 = 1 ， f 否则6 f = o 。一般说人数越少竞争越激烈。另外，这种相互作用关系通常是不对称 的，这取决于每个参与者参加的项目数，即“项目度”呜= 。一般来说，参 7 “ 加项目越少参与者投入的竞争力度越大。实际上，和鹿正是项目，和参与者f 在 二分图中分别对映于两类节点的度，因此这两个量的重要性是很明显的。然而， 在投影图中，这些信息大部分都丢失了。 图2 2 1 ( 引自文献【2 3 】) 二分图资源分配投影方法的图示 出于以上考虑，文献【5 】的作者们建议了一种把二分图投影为单模式图的新方 法。他们不失一般性地假设每个参与者和每个项目都分配有一定的“资源 ( 例如 研究经费、影片片酬等) ，而边权表示参与者，通过这次合作( 边) 传递给f 的 资源所占比例。认为每个项目所有的资源开始都平均地分配给了它的每个参与 者。反过来，每个参与者这样分配到的权也应该再通过通向它们参加的项目的二 分图边再平均分配给项目。这正像每个火车站上的旅客一开始平均地登上每列停 1 4 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 靠的火车，然后每列火车上的旅客又平均地下到每个停靠的火车站。图2 2 1 表述 了这样的一个权分配过程。其中上面的圆点表示项目，下面的圆点表示参与者，x ， y ，z 表示资源。 对于图1 0 1 3 ，最后的资源分配可以由下面的公式得到 巍狲 对于一般的一个二分图，可以有公式 厂( 而) = 嘞厂( o ) ， = l 蛾：上争丝， 2 丽备蒜 ( 2 ) 其中，厂( 工j ) 表示参与者节点在上述第一步分配到的资源，厂( 而) 表示参与者节点 f 最后分配到的资源，蠡( x ，) 表示参与者节点，的度，露( y ，) 表示项目节点，的度。 这样定义的边权分配解决了上述的各种传统投影具有的问题。以科研合作网为 例，由于南2 急，所以对于一条合作边，度大的节点赋的权小，而度j 、的节 点赋的权大。而且由于上面公式表示的运算矩阵的对角元不为零，所以仅仅有一 条二分图边的项目在投影后仍旧会保持信息。文献【习讨论了这种投影方法在推荐网 中的应用。这种投影方法还可能有更多的应用。 2 3 考虑实际资源信息的资源分配法 在知道资源信息的情况下，每一个项目有一定量的竞争资源，如果q 是项目f 的总资源，并且略是参与者节点f 在项目z 中获得的一部分，那么有哆：圭( ) 。 参与者节点f 对项目节点，的“竞争影响力 为： 小何煅 n l 5 ，。k = ， ， ， 工 y z ，。一 扬州大学硕士学位论文 1 5 驴羔 这个定义意味着当参与者节点f 获得较大部分的竞争资源时，参与者节点f 对项目 节点z 的竞争影响将增大。参与者节点j 对项目节点z 的“竞争影响力为： 易：乒 ( 4 ) ( ) 这个定义意味着参与者节点在项目，中获得竞争资源越大( 比较参与者节点_ ，获得 所有的资源) ，项目节点，对参与者节点，的竞争影响力将越大。 资源不一定是乘客或者货物：它能够被理解为影响、重要性、强度、财富等 等。例如，对于推荐系统【2 4 1 ，在用户和商品之间的资源可以被认为是一种推荐能 力。这里，竞争影响流从参与者节点流向项目，然后由项目流向另外的属于这个 项目的参与者节点。参与者节点f 将对和它参与共同参与的项目的节点施加竞争 影响。通过类似于周的思想【5 1 ，这里给出了我们的二分图投影方法。我们定义投影 后的单模式网络中一条边上的权重为： 嵋：厶厶= _ 堂掣l ( 5 ) ( ) f l l，= l 当参与者节点f 和_ ，被多重边连接时，在他们之间的权重可定义为： 嘞：# 学 7 嘞匆，艺 这里的边权是有向的。如果资源分配是均匀的，例如= = ( 一个常数) 对 于任意的矗j f 和l 边权变为= 古军竽，这正和文献【5 】中用到的边权是 样的。因此，我们可以说在文献【习中用到的边权是我们当前定义的种特殊的情 形。在普遍的资源分配不均匀的情形下，我们的边权相对文献【习所用到的边权而言， 1 6 石建军：复杂网络点强度相关研究及其复杂网络在生物领域的应用研究 将包含更多的资源信息。 2 4 点强度的定义 因为新的边权是有向的，所以存在两种不同的点强度定义：“出点强度”和“入 点强度”。参与者节点f 对它的邻居的总的竞争影响，即出点强度的定义为： 筇：；牛 ( 7 ) 77 7 唧 f j i，= i 那么，后一种情形则为f 的邻居对它的总的竞争影响，即入点强度定义为： 彰：# 学 j 艺j l b j 概 ( 8 ) 当用点强度来标志一个节点的特性( 例如意义) ，或者讨论点强度和其它统计 性质之间的关系( 例如节点度) 时，很显然，我们应选择出点强度。 类似地，我们能够根据文献【5 1 的边权定义一个点强度： 2 手咏2 手古军竽 现在，我们有三个点强度的定义：考虑资源信息的出点强度定义( 7 式) ；基 于周的资源分配的定义的点强度( 9 式) ；以及传统的重复边点强度定义： 墨= 嘞。对于任意的f ，_ ，嘞= = ( 一常数) 以及 和f 也为常数时，有： 影= 军莩警= 莩莩警= = 差o c ， 川哆，川 “。 一般而言，资源分配或者网络的拓扑性质不均匀，则点强度应该展示出非常不同 的行为。 一个问题是：如果我们