復雜網(wǎng)絡初探

《復雜網(wǎng)絡初探》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、第24卷第2期五邑大學學報(自然科學版)、b1．24No．22010年5月JOURNALOFWUYIUNIVERSITY(NaturalMav2OlO文章編號：1006．7302(2010)02．O012-0l復雜網(wǎng)絡初探吳今培(五邑大學智能技術與系統(tǒng)研究所．廣東江門529020)摘要：討論了復雜網(wǎng)絡的基本概念。重點介紹了小世界網(wǎng)絡和無標度網(wǎng)絡，提出了一些值得進一步研究的復雜網(wǎng)絡問題．關鍵詞：復雜網(wǎng)絡；小世界網(wǎng)絡；無標度網(wǎng)絡中圖分類號：TP393文獻標志碼：AAnIntroductiontoComplexNetworksIVUJin-pei(InstituteofIntelligen

2、ceTechnologyandSystem，WuyiUniversity，Jiangmen529020，China)Abstract：Inrecentyears，researchoncomplexnetworkshasarousedgreatinterestsamongresearchersfromdifferentdisclines．Thispaperbrieflyintroducestheconceptsoncomplexnetworks，especiallythefeaturesofsmall-worldandscale-freenetworks，andproposessome

3、keyproblemsmeritingfurtherresearch．Keywords：complexnetworks；small-worldnetworks；scale-freenetworks人類從遠古走來，很早就構造出林中路，并且把路構造成網(wǎng)絡；在農(nóng)業(yè)社會，人又構造出各種水利網(wǎng)絡，通過航海網(wǎng)絡，資本主義才遍布全世界；在工業(yè)社會，普通的小路被公路、鐵路所替代，休閑散步的路被高速公路所淹沒，公路和鐵路之網(wǎng)覆蓋大地；在今天的信息時代，各個國家致力于建設自己的信息高速公路，即新型的信息網(wǎng)路，如今，lnternet／www網(wǎng)絡已經(jīng)基本覆蓋整個世界．與人們生活息息相關的還有通信網(wǎng)絡、電力網(wǎng)

4、絡、航空網(wǎng)絡、銀行網(wǎng)絡、商業(yè)網(wǎng)絡等等．人類把自己生存的世界變成了網(wǎng)絡世界，網(wǎng)絡越發(fā)達、越有效，世界就越小，人的社會性就越得到強化．網(wǎng)絡如此廣泛、如此重要，人類處在網(wǎng)絡的叢林中．如何開辟出一條林中路，揭示網(wǎng)絡拓撲結構的形成機制，探索網(wǎng)絡的演化規(guī)律和整體行為，認識網(wǎng)絡內(nèi)部深奧的動力學特性，挖掘網(wǎng)絡展現(xiàn)出的廣泛、潛在的應用價值等問題，正引起國內(nèi)外學術界的高度重視，掀起了復雜網(wǎng)絡的研究熱潮．1復雜網(wǎng)絡的表述方式和主要特征度量復雜網(wǎng)絡是指由一個節(jié)點集V和一個邊集E組成的元組(V，E)，中元素稱為節(jié)點或頂點(node或vertex)，E中元素稱為邊或連線(edge或link)，且￡中的每條邊，有

5、V的一對節(jié)點(1f，'，)與之對收稿日期：2009—05-l4特約稿作者簡介：吳今培(1937一)，男，江西吉安人，教授，中南大學、北京航空航天大學博士生導師，研究方向：智能信息處理，E-mail：wjpwyu@163．com．2五邑大學學報(自然科學版)2010正應，如果E中任意的節(jié)點對(u，v)和(v，材)對應同一條邊，則該網(wǎng)絡稱為無向網(wǎng)絡，否則為有向網(wǎng)絡；如果￡中所有邊的長度均為1，即I，『I=l，則稱網(wǎng)絡為無權網(wǎng)絡，否則為加權網(wǎng)絡．V中元素個數(shù)和E中元素個數(shù)分別稱網(wǎng)絡的階(order)和邊數(shù)(size)．階和邊數(shù)都有限的網(wǎng)絡稱為有限網(wǎng)絡或有限圖(finitegraph)．邊所

6、連接的節(jié)點稱為端點(end-vertices)，兩端點相同的邊稱為環(huán)(1oop)．有公共起點并且有公共終點的兩條邊稱為平行邊(paralleledges)或重邊(multi-edge)．復雜網(wǎng)絡結構的宏觀特性通常由給定網(wǎng)絡G=(，E)微觀量的統(tǒng)計分布或統(tǒng)計平均值來刻畫，其主要特征量為度分布、集聚系數(shù)和平均路徑長度【I】．1)度分布(DegreeDistribution)網(wǎng)絡節(jié)點f的度k為與該節(jié)點連接的邊的總數(shù)目．在不同的網(wǎng)絡中度代表不同的含義．如在朋友關系網(wǎng)中，每一個人都是一個節(jié)點，兩個人若是朋友則他們之間就連一條邊，一個節(jié)點的度也就是一個人的朋友數(shù)．網(wǎng)絡中節(jié)點的度分布用概率分布函數(shù)

7、p(k)表示，其含義為一個任意選擇的節(jié)點恰好有k條邊連接的概率．在目前的網(wǎng)絡研究中，2種度分布較為常見：一種是指數(shù)度分布p(k)一P～，即p(k)隨著k的增大以指數(shù)形式衰減；另一種是冪律分布，即P(k)～七～，其中稱為度指數(shù)，不同7／的網(wǎng)絡其動力學性質(zhì)也不同．2)集聚系數(shù)(ClusteringCoemcient)集聚系數(shù)C用來描述網(wǎng)絡中節(jié)點的集聚情況，即網(wǎng)絡有多緊密．比如在社會網(wǎng)絡中，你的朋友可能也是我的朋友，或者你的兩個朋友可能彼此也是朋友．節(jié)點f的集聚