生物分子網(wǎng)絡(luò)基礎(chǔ)

第一章生物分子網(wǎng)絡(luò)根底教師：崔穎辦公室：外語學(xué)館412室上節(jié)回憶一、網(wǎng)絡(luò)與網(wǎng)絡(luò)科學(xué)的定義二、網(wǎng)絡(luò)科學(xué)歷史三、網(wǎng)絡(luò)科學(xué)與多學(xué)科的交叉融合四、網(wǎng)絡(luò)科學(xué)研究方法及體系結(jié)構(gòu)框架〔※〕五、網(wǎng)絡(luò)科學(xué)的子學(xué)科〔※〕六、網(wǎng)絡(luò)的分類方法〔※〕七、分子生物網(wǎng)絡(luò)根底理論〔※〕1分子生物網(wǎng)絡(luò)的根本概念(※)分子生物網(wǎng)絡(luò);分子生物網(wǎng)絡(luò)分析2分子生物網(wǎng)絡(luò)的分類(▲)〔信號轉(zhuǎn)導(dǎo)網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)、疾病基因網(wǎng)絡(luò)、代謝網(wǎng)絡(luò)、表觀遺傳調(diào)控網(wǎng)絡(luò)〕主要內(nèi)容1.1復(fù)雜網(wǎng)絡(luò)的根本概念1.2復(fù)雜網(wǎng)絡(luò)研究簡史1.3網(wǎng)絡(luò)的根本概念1.4復(fù)雜網(wǎng)絡(luò)的拓?fù)涮匦?.5拓?fù)鋵傩缘难a(bǔ)充定義1.1復(fù)雜網(wǎng)絡(luò)的根本概念復(fù)雜網(wǎng)絡(luò)定義復(fù)雜性的主要表現(xiàn)復(fù)雜網(wǎng)絡(luò)定義錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個(gè)較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界、無標(biāo)度中局部或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。在網(wǎng)絡(luò)理論的研究中，復(fù)雜網(wǎng)絡(luò)是由數(shù)量巨大的節(jié)點(diǎn)和節(jié)點(diǎn)之間錯(cuò)綜復(fù)雜的關(guān)系共同構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)。用數(shù)學(xué)的語言來說，就是一個(gè)有著足夠復(fù)雜的拓?fù)浣Y(jié)構(gòu)特征的圖。復(fù)雜網(wǎng)絡(luò)的研究是現(xiàn)今科學(xué)研究中的一個(gè)熱點(diǎn)，與現(xiàn)實(shí)中各類高復(fù)雜性系統(tǒng)，如互聯(lián)網(wǎng)網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)和社會網(wǎng)絡(luò)的研究有密切關(guān)系。復(fù)雜性的主要表現(xiàn)結(jié)構(gòu)復(fù)雜性節(jié)點(diǎn)復(fù)雜性網(wǎng)絡(luò)進(jìn)化性連接多樣性動(dòng)力學(xué)復(fù)雜性多重復(fù)雜性融合復(fù)雜性的主要表現(xiàn)(1)結(jié)構(gòu)復(fù)雜性:表現(xiàn)在節(jié)點(diǎn)數(shù)目巨大，網(wǎng)絡(luò)結(jié)構(gòu)呈現(xiàn)多種不同特征。(2)節(jié)點(diǎn)復(fù)雜性:表現(xiàn)在網(wǎng)絡(luò)節(jié)點(diǎn)的多樣性。復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)可以代表任何事物，例如，人際關(guān)系構(gòu)成的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)代表單獨(dú)個(gè)體，萬維網(wǎng)組成的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)可以表示不同網(wǎng)頁。復(fù)雜性的主要表現(xiàn)復(fù)雜性的主要表現(xiàn)復(fù)雜性的主要表現(xiàn)(3)網(wǎng)絡(luò)進(jìn)化性:表現(xiàn)在節(jié)點(diǎn)或連接的產(chǎn)生與消失。例如world-widenetwork，網(wǎng)頁或鏈接隨時(shí)可能出現(xiàn)或斷開，導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)不斷發(fā)生變化。(4)連接多樣性:節(jié)點(diǎn)之間的連接權(quán)重存在差異，且有可能存在方向性。復(fù)雜性的主要表現(xiàn)復(fù)雜性的主要表現(xiàn)復(fù)雜性的主要表現(xiàn)(5)動(dòng)力學(xué)復(fù)雜性：節(jié)點(diǎn)集可能屬于非線性動(dòng)力學(xué)系統(tǒng)，例如節(jié)點(diǎn)狀態(tài)隨時(shí)間發(fā)生復(fù)雜變化。(6)多重復(fù)雜性融合：即以上多重復(fù)雜性相互影響，導(dǎo)致更為難以預(yù)料的結(jié)果。例如，設(shè)計(jì)一個(gè)電力供給網(wǎng)絡(luò)需要考慮此網(wǎng)絡(luò)的進(jìn)化過程，其進(jìn)化過程決定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。當(dāng)兩個(gè)節(jié)點(diǎn)之間頻繁進(jìn)行能量傳輸時(shí)，他們之間的連接權(quán)重會隨之增加，通過不斷的學(xué)習(xí)與記憶逐步改善網(wǎng)絡(luò)性能.1.2復(fù)雜網(wǎng)絡(luò)研究簡史七橋問題隨機(jī)圖理論小世界實(shí)驗(yàn)弱連接強(qiáng)度復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元1.2.1七橋問題1.2.1七橋問題七橋→圖論→復(fù)雜網(wǎng)絡(luò)歐拉對七橋問題的抽象和論證思想，開創(chuàng)了數(shù)學(xué)中的一個(gè)分支——圖論(graphtheory)的研究。因此歐拉被公認(rèn)為圖論之父，此圖也被稱為歐拉圖。復(fù)雜網(wǎng)絡(luò)的研究與歐拉當(dāng)年關(guān)于七橋問題的研究在某種程度上是一脈相承的，即網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)性質(zhì)密切相關(guān)。1.2.2隨機(jī)圖理論20世紀(jì)60年代匈牙利數(shù)學(xué)家Erd?s和Rényi建立了隨機(jī)圖理論，被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。Erd?s和Rényi研究的隨機(jī)模型〔ER隨機(jī)圖〕中，任意兩個(gè)節(jié)點(diǎn)之間有一條邊的概率是p。保羅·埃爾德什(1913-1996)匈牙利籍猶太人。數(shù)學(xué)天才：3歲已能解算3位數(shù)的乘法；4歲時(shí)單獨(dú)發(fā)現(xiàn)了負(fù)數(shù)數(shù)學(xué)苦行僧：無妻兒，“私有財(cái)產(chǎn)就是累贅〞；工作狂，“墳?zāi)估镉械氖切菹r(shí)間〞最多產(chǎn)的數(shù)學(xué)家：1475篇高水平學(xué)術(shù)論文；“我的大腦敞開了〞；“另一個(gè)屋檐，另一個(gè)證明〞。1.2.2隨機(jī)圖理論如癡如醉，素?cái)?shù)理論、不定方程、組合論、概率論、數(shù)學(xué)分析和集合論等多個(gè)數(shù)學(xué)分支都做了大量創(chuàng)新性的工作。《我的大腦敞開著》和《數(shù)字情種》ER隨機(jī)圖一個(gè)含有N個(gè)節(jié)點(diǎn)的ER隨機(jī)圖邊的總數(shù)期望值為p(N*(N-1)/2)。進(jìn)一步推斷要產(chǎn)生一個(gè)含有N個(gè)節(jié)點(diǎn)M條邊的ER隨機(jī)圖概率為pM(1-p)N(N-1)/2-M。ER隨機(jī)圖(N→∞)Erd?s和Rényi系統(tǒng)研究了當(dāng)N→∞時(shí)ER隨機(jī)圖的性質(zhì)〔如連通性等〕與概率p之間的關(guān)系。幾乎每一個(gè)ER隨機(jī)圖都具有某種性質(zhì)Q，如果當(dāng)N→∞時(shí)產(chǎn)生具有這種性質(zhì)Q的ER隨機(jī)圖的概率為1。ER隨機(jī)圖(概率p)Erd?s和Rényi的最重要的發(fā)現(xiàn)是：ER隨機(jī)圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。對于任一給定的概率p，要么幾乎每一個(gè)圖都具有某個(gè)性質(zhì)Q(如：連通性)，要么幾乎每一個(gè)圖都不具有該性質(zhì)。

隨機(jī)圖→復(fù)雜網(wǎng)絡(luò)在20世紀(jì)的后40年中，隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)絡(luò)的根本理論。在此期間，人們也做了試圖解釋社會網(wǎng)絡(luò)的一些實(shí)驗(yàn)。下面介紹的小世界實(shí)驗(yàn)。小世界實(shí)驗(yàn)一個(gè)社會網(wǎng)絡(luò)就是一群人或團(tuán)體按某種關(guān)系連接在一起而構(gòu)成的一個(gè)系統(tǒng)。這里的關(guān)系可以多種多樣，

朋友關(guān)系

合作關(guān)系

聯(lián)姻關(guān)系

商業(yè)關(guān)系等等。

對于世界上任意兩個(gè)人來說，借助第三者、第四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系，平均需要通過多少人呢？

小世界實(shí)驗(yàn)小世界實(shí)驗(yàn)Milgram(1933-1984)的小世界實(shí)驗(yàn)上世紀(jì)60年代哈佛大學(xué)社會心理學(xué)家StanleyMilgram：世界上任意兩個(gè)人平均距離是6。六度別離(Sixdegreesofseparation)小世界實(shí)驗(yàn)選定兩個(gè)目標(biāo)：美國馬薩諸塞州沙朗的一位神學(xué)院研究生的妻子；波士頓的一個(gè)證券經(jīng)紀(jì)人。在堪薩斯州和內(nèi)布拉斯加州招募志愿者。通過自己認(rèn)識的人，用自己盡可能少的傳遞次數(shù)設(shè)法將信轉(zhuǎn)交到一個(gè)給定的目標(biāo)對象手中。利用3步：堪薩斯州的一位農(nóng)場主→圣公會的教父→沙朗的同事→研究生妻子。實(shí)驗(yàn)的結(jié)果從某種程度上反響了人際關(guān)系的“小世界〞特征。小世界實(shí)驗(yàn)六度別離理論告訴我們，有時(shí)候小數(shù)字，卻蘊(yùn)含著巨大的威力。例：如果你想象一下把一張足夠大的紙對折50次，會有多高？就算你的一張紙厚只有0.1毫米.那對折50次的高度就是：0.1*250，也就是2,2518萬千米，比太陽與地球相距的最遠(yuǎn)距離1,5210萬千米還要多近1億千米。小世界實(shí)驗(yàn)六度別離理論能給我們帶來什么？首先，社交網(wǎng)絡(luò)的開展是與其密不可分的。其次，它告訴我們每一個(gè)人要充分相信和利用自己的人脈。因?yàn)?，只需要小小的六步，它可以讓你認(rèn)識這個(gè)地球的每一個(gè)人。希望大家將來在實(shí)際生活和工作中充分利用這種理論。

小世界實(shí)驗(yàn)-Bacon游戲KevinBacon(凱文·貝肯:美國著名演員〕凱文·貝肯，美國電影演員。作品較多，1958年生于賓夕法尼亞州的費(fèi)城。1978年出演第一部電影《動(dòng)物屋》，1980年出演了電影《13號星期五》。與西恩·佩恩、方·基墨合作的百老匯舞臺劇《SlabBoys》最讓人難忘。代表作有《渾身是勁》、《刺殺肯尼迪》、《義海雄風(fēng)》、《阿波羅13號》、《沉睡者》、《神秘河》等。

小世界實(shí)驗(yàn)-Bacon游戲

KevinBacon游戲：如果一個(gè)人跟KevinBacon演過電影，他的Bacon數(shù)就是1，如果一個(gè)人跟KevinBacon演過電影的人演過電影，他的Bacon數(shù)就是2，以此類推。成龍的Bacon數(shù)為2比方成龍演了AroundtheWorldin80Days(2004年)，其中有LukeWilson，而LukeWilson演了MyDogSkip(2000年)，其中就有KevinBacon。所以成龍的Bacon數(shù)是2。

小世界實(shí)驗(yàn)-Bacon游戲Bacon數(shù)演員數(shù)0111682213239933572304862065673468527103813表1-1是對近60萬個(gè)演員所做的統(tǒng)計(jì)，左邊是Bacon數(shù)，右邊是具有這個(gè)Bacon數(shù)的演員個(gè)數(shù)。可以看到最大的Bacon數(shù)是僅僅是8，而平均Bacon數(shù)僅為2.994.小世界實(shí)驗(yàn)科研學(xué)術(shù)合作網(wǎng)絡(luò)之間也存在小世界特性Internet上的小世界實(shí)驗(yàn)小世界實(shí)驗(yàn)美國哥倫比亞大學(xué)社會學(xué)系任教的Watts組建小世界工程網(wǎng)絡(luò)，開始在世界范圍內(nèi)進(jìn)行一個(gè)檢驗(yàn)六度別離假說的網(wǎng)上在線實(shí)驗(yàn)。選定一些目標(biāo)對象。志愿者的任務(wù)就是把一條消息用電子郵件的方式傳到目標(biāo)對象那里。在一年多的時(shí)間，共有13個(gè)國家的18名目標(biāo)對象，166個(gè)國家和地區(qū)的6萬多名志愿者參加實(shí)驗(yàn)。最后有384個(gè)志愿者的電子郵件抵達(dá)了目的地。其中每封郵件平均轉(zhuǎn)了5~7次，即可到達(dá)目標(biāo)對象。但這項(xiàng)研究也存在一些不可控的因素。志愿者的朋友對于該實(shí)驗(yàn)可能沒有興趣。對陌生電子郵件往往抱有戒心。致使實(shí)驗(yàn)進(jìn)行得比較困難。弱連接的強(qiáng)度弱連接的強(qiáng)度弱連接:弱連接那么較能夠在不同的團(tuán)體間傳遞非重復(fù)性的訊息，使得網(wǎng)絡(luò)中的成員能夠增加修正原先觀點(diǎn)的時(shí)機(jī)。強(qiáng)連接:強(qiáng)連接關(guān)系通常代表著行動(dòng)者彼此之間具有高度的互動(dòng)，在某些存在的互動(dòng)關(guān)系型態(tài)上較親密。1.2.4弱連接的強(qiáng)度MarkGranovetter發(fā)表了一篇《弱連接的強(qiáng)度》(StrengthofWeakTies)的論文。人們在找工作的時(shí)候是靠親戚朋友還是通過各種招聘廣告？MarkGranovetter在波士頓采訪了近100人，并向200多人發(fā)出了問卷。結(jié)論：那些關(guān)系緊密的朋友〔強(qiáng)連接〕反倒沒有那些關(guān)系一般的甚至偶爾見面的朋友〔弱連接〕更能夠發(fā)揮作用。弱連接的強(qiáng)度例如：Edward高中認(rèn)識的一個(gè)女孩邀請他參加一個(gè)聚會，在聚會上認(rèn)識了一位女孩→姐姐→男朋友三年后，Edward辭去工作，在住所當(dāng)?shù)赜龅搅诉@位只有一面之交的朋友，他說所在公司需要一個(gè)制圖員，結(jié)果Edward順利被聘用了這篇論文被認(rèn)為是有史以來最有影響的社會學(xué)論文之一。

1.2.5復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元雖然隨機(jī)圖理論是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的根本理論；然而大多數(shù)實(shí)際的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)并不是完全隨機(jī)的。如兩個(gè)人是不是朋友等等。人們對復(fù)雜網(wǎng)絡(luò)的科學(xué)探索發(fā)生了重大的轉(zhuǎn)變：從物理學(xué)到生物學(xué)等復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元標(biāo)志性論文：1、《“小世界〞網(wǎng)絡(luò)的集體動(dòng)力學(xué)》---美國康奈爾大學(xué)Watts和Strogatz---Nature，1998.62、《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》---美國圣母大學(xué)Barabasi和Albert---Science，1999.10復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元當(dāng)前復(fù)雜網(wǎng)絡(luò)理論的主要研究內(nèi)容：發(fā)現(xiàn)：揭示刻畫網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)的統(tǒng)計(jì)性質(zhì)，以及度量這些性質(zhì)的適宜方法建模：建立適宜的網(wǎng)絡(luò)模型以幫助人們理解這些統(tǒng)計(jì)性質(zhì)的意義與產(chǎn)生機(jī)理復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元分析：基于單個(gè)節(jié)點(diǎn)的特性和整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)分析與預(yù)測網(wǎng)絡(luò)的行為控制：提出改善已有網(wǎng)絡(luò)性能和設(shè)計(jì)新的網(wǎng)絡(luò)的有效方法，特別是穩(wěn)定性、同步性和數(shù)據(jù)流通等方面小結(jié)1.1復(fù)雜網(wǎng)絡(luò)的根本概念復(fù)雜網(wǎng)絡(luò)定義※復(fù)雜性的主要表現(xiàn)：結(jié)構(gòu)復(fù)雜性、節(jié)點(diǎn)復(fù)雜性、網(wǎng)絡(luò)進(jìn)化性、連接多樣性、動(dòng)力學(xué)復(fù)雜性、多重復(fù)雜性融合1.2復(fù)雜網(wǎng)絡(luò)研究簡史※七橋問題、※隨機(jī)圖理論、小世界實(shí)驗(yàn)、弱連接強(qiáng)度、復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元思考題1、請舉例生活中的復(fù)雜網(wǎng)絡(luò)？2、如何來判斷復(fù)雜網(wǎng)絡(luò)？1.3網(wǎng)絡(luò)的根本概念網(wǎng)絡(luò)定義有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)加權(quán)網(wǎng)絡(luò)與等權(quán)網(wǎng)絡(luò)1.3.4.二分網(wǎng)絡(luò)網(wǎng)絡(luò)中的路徑與距離網(wǎng)絡(luò)定義1.網(wǎng)絡(luò)定義：通?？梢杂脠DG=〔V,E〕表示網(wǎng)絡(luò)。其中，V是網(wǎng)絡(luò)的節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)代表一個(gè)生物分子，或者一個(gè)環(huán)境刺激；E是邊的集合，每條邊代表節(jié)點(diǎn)之間的相互關(guān)系。當(dāng)V中的兩個(gè)節(jié)點(diǎn)v1與v2之間存在一條屬于E的邊e1時(shí)，稱邊e1連接v1與v2，或者稱v1連接于v2，也稱作v2是v1的鄰居。有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)根據(jù)網(wǎng)絡(luò)中的邊是否具有方向性或者說連接一條邊的兩個(gè)節(jié)點(diǎn)是否存在順序，網(wǎng)絡(luò)可以分為有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)，邊存在方向性，為有向網(wǎng)絡(luò)，否那么為無向網(wǎng)絡(luò).生物分子網(wǎng)絡(luò)的方向性取決于其所代表的關(guān)系。有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)如調(diào)控關(guān)系中轉(zhuǎn)錄因子與被調(diào)控基因之間是存在順序關(guān)系的，因此轉(zhuǎn)錄調(diào)控網(wǎng)絡(luò)是有向網(wǎng)絡(luò)，而基因表達(dá)相關(guān)網(wǎng)絡(luò)中的邊代表的是兩個(gè)基因在多個(gè)實(shí)驗(yàn)條件下的表達(dá)高相關(guān)性，因此是無向的。有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)圖1-1A有向網(wǎng)絡(luò)B無向網(wǎng)絡(luò)加權(quán)網(wǎng)絡(luò)與等權(quán)網(wǎng)絡(luò)網(wǎng)絡(luò)中的邊在網(wǎng)絡(luò)中具有不同意義或在某個(gè)屬性上有不同的價(jià)值是網(wǎng)絡(luò)中普遍存在的一種現(xiàn)象。比方交通網(wǎng)中，連接兩個(gè)城市〔節(jié)點(diǎn)〕的道路〔邊〕一般具有不同的長度，而在互聯(lián)網(wǎng)中兩臺直接相連的計(jì)算設(shè)備間通訊的速度也不盡相同。加權(quán)網(wǎng)絡(luò)與等權(quán)網(wǎng)絡(luò)如果網(wǎng)絡(luò)中的每條邊都賦予相應(yīng)的數(shù)字，這個(gè)網(wǎng)絡(luò)就稱為加權(quán)網(wǎng)絡(luò)，賦予的數(shù)字稱為邊的權(quán)重。權(quán)重可以用來描述節(jié)點(diǎn)間的距離、相關(guān)程度、穩(wěn)定程度、容量等等各種信息，具體所代表的意義依賴于網(wǎng)絡(luò)和邊本身所代表的意義。如果網(wǎng)絡(luò)中各邊之間沒有區(qū)別，可以認(rèn)為各邊的權(quán)重相等，稱為等權(quán)網(wǎng)絡(luò)或無權(quán)網(wǎng)絡(luò)。1.3.4.二分網(wǎng)絡(luò)如果網(wǎng)絡(luò)中的節(jié)點(diǎn)可分為兩個(gè)互不相交的集合，而所有的邊都建立在來自不同集合的節(jié)點(diǎn)之間，那么稱這樣的網(wǎng)絡(luò)為二分網(wǎng)絡(luò)〔bipartitenetwork〕。例如，藥物分子與其靶蛋白的結(jié)合關(guān)系即可以用二分網(wǎng)絡(luò)的形式表示出來。網(wǎng)絡(luò)中的路徑與距離網(wǎng)絡(luò)中的路徑是指一系列節(jié)點(diǎn)，其中每個(gè)節(jié)點(diǎn)都有一條邊連接到緊隨其后的節(jié)點(diǎn)。對包含節(jié)點(diǎn)數(shù)目有限的路徑來說，第一個(gè)結(jié)點(diǎn)稱為起點(diǎn)，最后一個(gè)節(jié)點(diǎn)稱為終點(diǎn)，二者均可稱為路徑的端點(diǎn)，其余的節(jié)點(diǎn)那么稱為路徑的內(nèi)點(diǎn)或中繼點(diǎn)。這樣的路徑也稱為連接起點(diǎn)與終點(diǎn)的路徑。網(wǎng)絡(luò)中的路徑與距離例如在圖1-1A中節(jié)點(diǎn)G到節(jié)點(diǎn)C的路徑有L1={G，A，B，C}，L2={G，A，D，C}，L3={G，F(xiàn)，A，B，C}和L4={G，F(xiàn)，A，D，C}。對無向網(wǎng)絡(luò)來說，只要將路徑的順序顛倒就可以得到從原來的終點(diǎn)指向起點(diǎn)的路徑.圖1-1A無向網(wǎng)絡(luò)網(wǎng)絡(luò)中的路徑與距離在有向網(wǎng)絡(luò)中，起點(diǎn)與終點(diǎn)是不可逆的。例如圖1-1B所示網(wǎng)絡(luò)中節(jié)點(diǎn)由A出發(fā)到節(jié)點(diǎn)C間存在路徑L3={A，D，C}，但C不能找到路徑回到A。圖1-1B有向網(wǎng)絡(luò)網(wǎng)絡(luò)中的路徑與距離網(wǎng)絡(luò)中如果兩個(gè)節(jié)點(diǎn)間由一條路徑連接，那么稱這兩個(gè)節(jié)點(diǎn)是連通的。所有能夠連通的節(jié)點(diǎn)和它們之間的邊構(gòu)成了一個(gè)連通分量。路徑中所經(jīng)過邊的權(quán)重之和稱為路徑的權(quán)重，也稱為路徑的長度。對于等權(quán)網(wǎng)絡(luò)而言，路徑的長度即為路徑中所經(jīng)過邊的數(shù)目。網(wǎng)絡(luò)中的路徑與距離圖1-1A中從節(jié)點(diǎn)G到節(jié)點(diǎn)C的路徑中，L1和L2的長度為3，L3和L4的長度為4。在連接兩個(gè)節(jié)點(diǎn)的所有路徑中，長度最短的路徑稱為最短路徑，最短路徑的長度稱為從起點(diǎn)到終點(diǎn)的距離。圖1-1A中從節(jié)點(diǎn)G到節(jié)點(diǎn)C的距離為3。圖1-1A無向網(wǎng)絡(luò)練習(xí)：計(jì)算圖1-1A中，所有點(diǎn)之間的距離。圖1-1A無向網(wǎng)絡(luò)思考題對于一個(gè)復(fù)雜網(wǎng)絡(luò)，我們?nèi)绾蝸矸治鼍W(wǎng)絡(luò)？1.4網(wǎng)絡(luò)的拓?fù)鋵傩赃B通度聚類系數(shù)介數(shù)緊密度拓?fù)湎禂?shù)直徑平均距離分布函數(shù)和連通度函數(shù)1.4網(wǎng)絡(luò)的拓?fù)鋵傩跃W(wǎng)絡(luò)的拓?fù)鋵傩裕菏敲枋鼍W(wǎng)絡(luò)本身及其內(nèi)部節(jié)點(diǎn)或邊結(jié)構(gòu)特征的測度。這些測度對進(jìn)一步分析網(wǎng)絡(luò)結(jié)構(gòu)和探索關(guān)鍵節(jié)點(diǎn)有重要的意義。1.4.1.連通度連通度〔degree〕是描述單一節(jié)點(diǎn)的最根本的拓?fù)湫再|(zhì)。節(jié)點(diǎn)v的連通度是指網(wǎng)絡(luò)中直接與v相連的邊的數(shù)目。例如在圖1-2A中節(jié)點(diǎn)A的連通度為3。對于有向網(wǎng)絡(luò)往往還要區(qū)分邊的方向，由節(jié)點(diǎn)v發(fā)出的邊的數(shù)目稱為節(jié)點(diǎn)v的出度，指向節(jié)點(diǎn)v的邊數(shù)那么稱為節(jié)點(diǎn)v的入度。圖1-2

有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)1.4.1.連通度我們用符號k來表示連通度，kout表示出度，kin表示入度。在圖1-2B中節(jié)點(diǎn)A的入度為1，出度為2。圖1-2

有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)1.4.1.連通度連通度描述了網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)的連接數(shù)量，整個(gè)網(wǎng)絡(luò)的連通性可以使用其平均值來表示。對于由N個(gè)節(jié)點(diǎn)和L條邊組成的無向網(wǎng)絡(luò)其平均連通度為Knet=2L/N。連通度是一種簡單而十分重要的拓?fù)鋵傩浴Ｔ谘芯恐?，連通度較大的節(jié)點(diǎn)稱為中心節(jié)點(diǎn)〔hub〕，它們很自然地成為目前研究的重點(diǎn)。1.4.1.連通度研究顯示，在蛋白質(zhì)互作網(wǎng)絡(luò)等生物網(wǎng)絡(luò)中，支持生命根本活動(dòng)的必需基因或其翻譯產(chǎn)物的比例在中心節(jié)點(diǎn)中出現(xiàn)的頻率顯著高于一般節(jié)點(diǎn)。同時(shí)，人類蛋白質(zhì)互作網(wǎng)絡(luò)的研究說明，中心節(jié)點(diǎn)顯著富集著與癌癥等遺傳性疾病相關(guān)的基因。練習(xí)：計(jì)算圖1-1A和1-1B中A點(diǎn)的連通度，以及圖1-1A的網(wǎng)絡(luò)的連通度。K=5Kout=3Kin=2Knet=16/7=2.291.4.2.聚類系數(shù)在很多網(wǎng)絡(luò)中，如果節(jié)點(diǎn)v1連接于節(jié)點(diǎn)v2，節(jié)點(diǎn)v2連接于節(jié)點(diǎn)v3，那么節(jié)點(diǎn)v3很可能與v1相連接。這種現(xiàn)象表達(dá)了局部節(jié)點(diǎn)間存在的密集連接性質(zhì)，可以用聚類系數(shù)〔clusteringcoefficient〕CC來表示，在無向網(wǎng)絡(luò)中，聚類系數(shù)定義為：v1v2vnv4v31.4.2.聚類系數(shù)公式中，K表示節(jié)點(diǎn)V的鄰居數(shù)目，n表示節(jié)點(diǎn)V的K個(gè)鄰居兩兩之間連接的邊數(shù)，Ck2表示K個(gè)鄰居兩兩相連的最多邊數(shù)。

請同學(xué)們給出CCv的取值范圍，并說明原因。1.4.2.聚類系數(shù)因?yàn)閚表示在節(jié)點(diǎn)v的所有的k個(gè)鄰居間邊的數(shù)目，那么在無向網(wǎng)絡(luò)中，n的最大數(shù)目可以由鄰居節(jié)點(diǎn)的兩兩組合數(shù)k〔k-1〕/2來確定，所以CC值位于［0，1］區(qū)間。當(dāng)節(jié)點(diǎn)v的所有鄰居都彼此連接時(shí)，v的聚類系數(shù)CC=1；相反，當(dāng)v的鄰居間不存在任何連接時(shí)，CC＝0。1.4.2.聚類系數(shù)例：圖1-2A中，節(jié)點(diǎn)A有三個(gè)鄰居{B，C，D}，其間只有B和C有一條邊連接，所以節(jié)點(diǎn)A的聚類系數(shù)：圖1-2

A無向網(wǎng)絡(luò)練習(xí)請同學(xué)們計(jì)算B、C的聚類系數(shù)。圖1-2

A無向網(wǎng)絡(luò)1.4.2.聚類系數(shù)在有向網(wǎng)絡(luò)中，由于兩個(gè)節(jié)點(diǎn)間可以存在兩條方向相反的邊，那么標(biāo)準(zhǔn)化的聚類系數(shù)被定義為：其中，kout指v的出度，K指節(jié)點(diǎn)A指向的連接的鄰居個(gè)數(shù)，n指所有v所指向的連接的節(jié)點(diǎn)彼此之間存在的邊數(shù)。1.4.2.聚類系數(shù)例：在圖1-2B中，節(jié)點(diǎn)A連接2個(gè)節(jié)點(diǎn){B，C}，其間只有1條邊，那么節(jié)點(diǎn)A的聚類系數(shù)為圖1-2

B有向網(wǎng)絡(luò)介數(shù)一個(gè)節(jié)點(diǎn)的介數(shù)〔Betweenness〕是衡量這個(gè)節(jié)點(diǎn)出現(xiàn)在其它節(jié)點(diǎn)間最短路徑中的比例。節(jié)點(diǎn)v的介數(shù)Bv定義如下：其中，表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑的條數(shù)，表示其中通過節(jié)點(diǎn)v的路徑條數(shù)。介數(shù)介數(shù)也可以用標(biāo)準(zhǔn)化至[0，1]區(qū)間的形式表示：介數(shù)說明了一個(gè)節(jié)點(diǎn)在其它節(jié)點(diǎn)彼此連接中所起的作用。介數(shù)越高，意味著在保持網(wǎng)絡(luò)緊密連接性中節(jié)點(diǎn)越重要。介數(shù)例：在圖1-2A中，A以外的節(jié)點(diǎn)間有4個(gè)節(jié)點(diǎn)，彼此間存在共有6對節(jié)點(diǎn)關(guān)系，即{BC,BD,DE,CD,CE,DE},每對關(guān)系都只能找到1條最短路徑，那么所有的.圖1-2

有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)BC最短路徑〔BC〕1條，經(jīng)過A的路徑為0條BD最短路徑(BAD)1條，經(jīng)過A的路徑為1條〔BAD〕BE最短路徑〔BCE〕1條，經(jīng)過A的路徑為0條CD最短路徑〔CAD〕1條，經(jīng)過A的路徑為1條〔CAD〕CE最短路徑〔CE〕1條，經(jīng)過A的路徑為0條DE最短路徑〔DACE〕1條，經(jīng)過A的路徑為1條〔DACE〕圖1-2

有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)圖1-2B

有向網(wǎng)絡(luò)介數(shù)在圖1-2B中，由于存在方向性，節(jié)點(diǎn)A以外4個(gè)節(jié)點(diǎn)間彼此間可能存在的連通關(guān)系有條.BC×,BD×,BE×,CB∨,CD×,CE×,DB∨,DC∨,DE×,EB∨,EC∨,ED.真正連通的關(guān)系只有{C，B},{D，A，B},{D，A，C，B},{D，A，C},{E，C，B},{E，C}是連通的。其中通過節(jié)點(diǎn)A的最短路徑有2條，那么節(jié)點(diǎn)A的介數(shù)為2。緊密度緊密度〔closeness〕是描述一個(gè)節(jié)點(diǎn)到網(wǎng)絡(luò)中其它所有節(jié)點(diǎn)平均距離的指標(biāo)。節(jié)點(diǎn)v的緊密度Cv定義如下：其中dvj表示節(jié)點(diǎn)v到節(jié)點(diǎn)j的距離。緊密度測度衡量節(jié)點(diǎn)接近網(wǎng)絡(luò)“中心〞的程度，緊密型測度越小，節(jié)點(diǎn)越接近中心。緊密度在圖1-2A中，節(jié)點(diǎn)A到B、C、D、E的距離分別為1，1，1，2那么節(jié)點(diǎn)A的緊密度為1.25。圖1-2A

無向網(wǎng)絡(luò)請計(jì)算B和C的緊密度。拓?fù)湎禂?shù)類似于聚類系數(shù)，拓?fù)湎禂?shù)〔topologycoefficient〕是反映互作節(jié)點(diǎn)間共享連接比例的測度，節(jié)點(diǎn)v的拓?fù)湎禂?shù)Tv可以定義為：其中，表示與節(jié)點(diǎn)v和節(jié)點(diǎn)t都連接的節(jié)點(diǎn)數(shù)。為所有與節(jié)點(diǎn)v分享鄰居的節(jié)點(diǎn)集合。拓?fù)湎禂?shù)反映了節(jié)點(diǎn)的鄰居間被其它節(jié)點(diǎn)連接在一起的比例.拓?fù)湎禂?shù)例如圖1-2A中，與A節(jié)點(diǎn)共享鄰居的節(jié)點(diǎn)共有3個(gè)那么MA={B，C，E}其連通度分別為2，3，1那么節(jié)點(diǎn)A的拓?fù)湎禂?shù)圖1-2A

無向網(wǎng)絡(luò)請計(jì)算B和C的拓?fù)湎禂?shù)。TB=3/4，TC=11/18直徑直徑〔diameter〕是描述網(wǎng)絡(luò)總體性質(zhì)的一個(gè)屬性。網(wǎng)絡(luò)的直徑是指網(wǎng)絡(luò)中任意兩個(gè)連通節(jié)點(diǎn)間距離的最大值。網(wǎng)絡(luò)的直徑代表了網(wǎng)絡(luò)中節(jié)點(diǎn)連接可能出現(xiàn)的最遠(yuǎn)距離，標(biāo)志著網(wǎng)絡(luò)緊密的程度。平均距離網(wǎng)絡(luò)的平均距離〔averagedistance〕也是描述網(wǎng)絡(luò)總體性質(zhì)的一個(gè)屬性。網(wǎng)絡(luò)的平均距離是指網(wǎng)絡(luò)中任意兩個(gè)連通節(jié)點(diǎn)距離的平均值，也是衡量網(wǎng)絡(luò)緊密程度的重要指標(biāo)。連通度的分布函數(shù)和聚類系數(shù)的連通度函數(shù)除了平均連通度以外，連通度的分布P〔k〕,k=1,2,...是另一種重要描述網(wǎng)絡(luò)連通性的屬性。而類似的針對網(wǎng)絡(luò)還可以建立起隨連通度變化的聚類系數(shù)的連通度函數(shù)C〔k〕，這個(gè)函數(shù)被定義為當(dāng)函數(shù)自變量等于k時(shí)，C〔k〕等于所有連通度為k的節(jié)點(diǎn)的聚類系數(shù)的平均值。連通度的分布函數(shù)和聚類系數(shù)的連通度函數(shù)與連通度分布函數(shù)P〔k〕類似，C〔k〕也廣泛應(yīng)用與描述網(wǎng)絡(luò)結(jié)構(gòu)的根本性質(zhì)。相比于拓?fù)湫再|(zhì)指標(biāo)的平均數(shù)由于連通度的分布函數(shù)以及依賴于連通度的聚類系數(shù)函數(shù)包含更多的信息，對分布函數(shù)的分析往往可以揭示更為深刻的網(wǎng)絡(luò)性質(zhì)。分布函數(shù)P〔k〕A，B，C，D，E的度分別為：3，2，3，1，1，那么連通度的分布P〔K〕為圖1-2A

無向網(wǎng)絡(luò)K123P2/51/53/5聚類系數(shù)的連通度函數(shù)C〔k〕，A，B，C，D，E的度分別為：3，2，3，1，1，A，B，C，D，E的聚類系數(shù)分別為：1/3，1，1/3，0，0。C〔K=1〕=0，C〔K=2〕=1，C〔K=3〕1/3圖1-2A

無向網(wǎng)絡(luò)小結(jié)1.4網(wǎng)絡(luò)的拓?fù)鋵傩?連通度2※聚類系數(shù)3△

※介數(shù)4緊密度5△※拓?fù)湎禂?shù)6直徑7平均距離8△分布函數(shù)和連通度函數(shù)練習(xí)題計(jì)算以下圖A點(diǎn)的連通度、聚類系數(shù)、介數(shù)，緊密度，拓?fù)湎禂?shù)；計(jì)算網(wǎng)絡(luò)的直徑，平均距離，度分布以及聚類系數(shù)的連通度.圖1-1A無向網(wǎng)絡(luò)前節(jié)回憶：練習(xí)：計(jì)算圖中所有節(jié)點(diǎn)的聚類系數(shù)、介數(shù)，緊密度，拓?fù)湎禂?shù)。并比較哪個(gè)節(jié)點(diǎn)在圖中有更重要的作用。1.5拓?fù)浣Y(jié)構(gòu)屬性的補(bǔ)充定義平均路徑長度聚類系數(shù)度與度分布介數(shù)網(wǎng)絡(luò)分類有向網(wǎng)絡(luò)、無向網(wǎng)絡(luò)加權(quán)網(wǎng)絡(luò)、無權(quán)網(wǎng)絡(luò)1.平均路徑長度平均路徑長度：反響了網(wǎng)絡(luò)的規(guī)模大局部復(fù)雜網(wǎng)絡(luò)具有小的平均距離→小世界特征1.平均路徑長度計(jì)算以下圖的平均路徑長度。2.聚類系數(shù)在朋友網(wǎng)絡(luò)中，某個(gè)人的兩個(gè)朋友可能彼此也是朋友，這種屬性稱為網(wǎng)絡(luò)的聚類特性。2.聚類系數(shù)ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei和總的可能的邊數(shù)ki(ki-1)/2之比就定義為節(jié)點(diǎn)i的聚類系數(shù)。2.聚類系數(shù)從幾何上看，聚類系數(shù)的等價(jià)定義：與節(jié)點(diǎn)i相連的三元組是指包括節(jié)點(diǎn)

i的三個(gè)節(jié)點(diǎn)，并且至少存在從節(jié)點(diǎn)

i

到其他兩個(gè)節(jié)點(diǎn)的兩條邊。三角形以節(jié)點(diǎn)i為頂點(diǎn)之一的三元組的兩種可能形式ii三元組與點(diǎn)i相連的三元組的數(shù)量與點(diǎn)i相連的三角形的數(shù)量Ci=2.聚類系數(shù)網(wǎng)絡(luò)的聚類系數(shù):網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的聚類系數(shù)的平均值，反映網(wǎng)絡(luò)的聚集程度。聚類系數(shù)滿足：0<C<1假設(shè)C=1：任意兩個(gè)節(jié)點(diǎn)有連接假設(shè)C=0：無三角形連接大局部復(fù)雜網(wǎng)絡(luò)有較大的聚類系數(shù)→小世界特征2.聚類系數(shù)計(jì)算網(wǎng)絡(luò)聚類系數(shù)3.度與度分布節(jié)點(diǎn)的度〔Degree〕:單獨(dú)節(jié)點(diǎn)的屬性中簡單而又重要的概念。無向網(wǎng)絡(luò)中:節(jié)點(diǎn)i的度ki定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目；有向網(wǎng)絡(luò)中:節(jié)點(diǎn)的度分為出度和入度網(wǎng)絡(luò)的平均度為網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值，記為<k>。3.度與度分布無向網(wǎng)絡(luò)有向網(wǎng)絡(luò)3.度與度分布網(wǎng)絡(luò)中節(jié)點(diǎn)的度的分布情況可用分布函數(shù)P(k)描述P(k)表示的是一個(gè)隨機(jī)選定的節(jié)點(diǎn)的度恰好為k的概率常見的網(wǎng)絡(luò)度分布：Delta分布泊松(Poisson)分布〔完全隨機(jī)網(wǎng)絡(luò)〕冪律分布〔無標(biāo)度網(wǎng)絡(luò)〕Delta分布規(guī)那么網(wǎng)絡(luò)有著簡單的度序列：因?yàn)樗械墓?jié)點(diǎn)具有相同的度，所以其度分布為Delta分布，它是單個(gè)尖峰。規(guī)則網(wǎng)絡(luò)Delta分布其度分布為Delta分布，單個(gè)尖峰Delta分布Delta分布網(wǎng)絡(luò)中任何隨機(jī)化傾向，都將使這個(gè)尖峰的形狀變寬.Poisson分布完全隨機(jī)網(wǎng)絡(luò)的度分布近似為Poisson分布其形狀在遠(yuǎn)離峰值<k>處呈指數(shù)下降。Poisson分布冪律分布近幾年的大量研究說明，許多實(shí)際網(wǎng)絡(luò)的度分布明顯地不同于Possion分布。許多網(wǎng)絡(luò)的度分布可以用冪律形式p(k)∝k-γ來更好的描述。冪律分布曲線比Possion指數(shù)分布曲線下降要緩慢得多。冪律分布冪律分布冪律分布(對數(shù)坐標(biāo)系)4.介數(shù)介數(shù)反映了相應(yīng)的節(jié)點(diǎn)或者邊在整個(gè)網(wǎng)絡(luò)中的作用和影響力，是一個(gè)重要的全局幾何量，具有很強(qiáng)的現(xiàn)實(shí)意義。例如，在社會關(guān)系網(wǎng)或技術(shù)網(wǎng)絡(luò)中，介數(shù)的分布特征反映了不同人員、資源和技術(shù)在相應(yīng)生產(chǎn)關(guān)系中的地位，這對于發(fā)現(xiàn)和保護(hù)關(guān)鍵資源、技術(shù)和人才具有重要意義。介數(shù)分為邊的介數(shù)和節(jié)點(diǎn)介數(shù)。4.介數(shù)邊介數(shù)邊介數(shù)：網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該邊的路徑的數(shù)目占最短路徑總數(shù)的比例。邊的介數(shù)衡量的是邊作為“橋梁〞的作用。最短路徑：從起點(diǎn)到終點(diǎn)所含邊的數(shù)目最少的路徑。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題。

邊介數(shù)例：計(jì)算以下圖中邊CD的介數(shù)、JK邊的介數(shù)。圖中共有55條最短路徑，其中24條包括CD邊，CD邊的介數(shù)為0.69(24/55)，JK邊的介數(shù)為0.02(1/55)。CD邊的介數(shù)比JK邊的高。ACBHFGDKEJI邊介數(shù)練習(xí)：計(jì)算以下圖中邊ST的介數(shù)。XVUWTPRQS邊介數(shù)的缺乏如圖CD的介數(shù)為0.44(24/55)，ST的介數(shù)為0.56(20/36)。然而ST似乎