生物分子網絡基礎

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

隨機圖→復雜網絡在20世紀的后40年中，隨機圖理論一直是研究復雜網絡的根本理論。在此期間，人們也做了試圖解釋社會網絡的一些實驗。下面介紹的小世界實驗。小世界實驗一個社會網絡就是一群人或團體按某種關系連接在一起而構成的一個系統(tǒng)。這里的關系可以多種多樣，

朋友關系

合作關系

聯(lián)姻關系

商業(yè)關系等等。

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

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

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

小世界實驗-Bacon游戲

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

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

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

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

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

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

A無向網絡練習請同學們計算B、C的聚類系數。圖1-2

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

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

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

有向網絡與無向網絡圖1-2B

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

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

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

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

無向網絡小結1.4網絡的拓撲屬性1連通度2※聚類系數3△

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

i的三個節(jié)點，并且至少存在從節(jié)點

i

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

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