復雜網絡分析

前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇復雜網絡分析范文，相信會為您的寫作帶來幫助，發現更多的寫作思路和靈感。

復雜網絡分析范文第1篇

關鍵字：物流網絡，復雜網絡，復雜性

1.引言

物流網絡是物流活動的重要體現，也是衡量物流活動有效性的重要指標。隨著人工，倉租以及燃油費用的上升，企業要想有效地控制物流成本和提升服務客戶的能力，就必須清楚地認識物流網絡的結構和功能，以及合理地對物流網絡進行管理，在達到滿足客戶需求的基礎上最大程度地降低物流成本的目的，從而大大增加企業的價值。

物流網絡系統是動態的復雜網絡系統，是復雜網絡系統的一個子集，因而它具有復雜網絡系統的大部分特征。復雜網絡理論的研究方法可以用來深入分析和準確研究物流網絡系統運行的客觀規律、物流網絡系統的結構和功能以及物流網絡系統的動態發展趨勢和規律。

2.物流網絡的研究現狀

Mortiz Fleischmann等對不同行業的產品回收物流網絡設計研究并概括產品回收網絡的一般特征，并比較它們與傳統的物流結構，此外，為不同類型的回收網絡得出一個分類方案【1】。姚衛新等探討了在電子商務環境下，為滿足客戶需要所形成閉環供應鏈物流網絡的特點【2】。王建華等針對具有批量折扣和轉運的供應鏈優化問題特征，提出供應物流網絡的概念及其優化參數：節點、線路和流量【3】。楊光華等分析了區域物流網絡的結構并闡述了物流宏觀層面的特征，建立了基于加權網絡的區域物流網絡模型；從節點度和強度的分布、邊的權重差異度等對區域物流網絡的結構進行了定量分析【4】。吉迎東基于物流網絡的整體性和動態性，分析了中國煤炭物流網絡的特征【5】。韓舒怡等認為網絡化是物流發展的方向，物流網絡協同服務是物流網絡化的主要表現形式之【6】。

從研究方法看，目前從復雜網絡、復雜性來分析物流網絡的研究較少，對物流網絡系統的結構演化以及網絡演化的內部規律探討較少。從研究理論的視角來看，當前的研究往往基于靜態、局部的視角，通常把物流網絡系統的結構看成是相對穩定的、靜止的，并試圖優化網絡系統中的物流、資金流和信息流，而沒有充分注意到物流網絡系統的動態適應性問題，沒有從系統的整體運行規律上來考慮問題。在實際操作中，物流網絡系統的結構是可根據企業的整體需要來改變的，目前的研究不能說明物流網絡的形成演化機制，不同行業的物流網絡為何有顯著差別等問題。因此，有必要深入挖掘復雜網絡理論、復雜性理論在物流網絡分析中的應用價值。

3.物流網絡的復雜網絡特征

物流網絡的小世界網絡特征。研究表明：小世界網絡具有高集聚系數和較小的平均路徑長度。物流網絡的聚集系數和平均路徑長度反映了小世界的復雜性網絡特征：

（1）平均路徑長度是指網絡中所有節點對之間的平均最短距離。網絡中任意兩個節點i和j之間的距離 定義為連接兩個節點的最短路徑。網絡的直徑為網絡中任意兩個節點之間距離的最大值，記為D= 。在無向網絡中，網絡中節點對之間最短距離的算術平均值為平均路徑長度L，其公式為：L= 。其中，N表示網絡中的節點總數。平均路徑長度公式中包含了每個點到自身的距離（為0）。對于物流網絡來言，平均路徑可以表示產品交付給客戶的時間也可以表示配送產品或者中間產品到客戶的費用。隨著商品生命周期不斷縮短的同時客戶對配送時間要求的提高，如何以最小費用、最短時間內將產品交付客戶成為節點企業生存與發展的戰略問題。物流網絡中的任何一個節點企業為了在激烈的競爭中保持優勢，必須做到以下幾點：注重信息網絡的建設，加快信息流通的速度，減少產品運輸距離，提高自身協調和反應能力，建立配送物流中心，使物流網絡具有較小的平均路徑長度。

（2）聚集系數是衡量網絡集聚特性的統計量，其定義有很多種不同的表述方式，本文介紹一個Watts等人提出的定義【7】： 假設網絡中的某個節點i有 個節點與它相連，這 個節點就稱為節點i的鄰節點，這 個節點之中最多可能有 條邊， 因此這 個節點之間實際存在的邊數 和總的可能邊數為 之比為節點i的集聚系數 ： = 。對于度為0或1的節點，上式中的分子和分母均為0，故認為集聚系數 =0。所有節點i的集聚系數 的平均值是網絡的集聚系數C，記為：C= 。對物流網絡而言，平均聚類系數是物流網絡節點企業之間相互連接和交流的程度。隨著計算機技術和互聯網技術的高速發展，越來越多的企業應用信息技術和互聯網建立連接，如ERP、EDI系統的使用等。通過信息共享，使得物流網絡中各節點企業之間的聯系更加緊密，交流更加頻繁。因此，物流網絡具有較高的聚集系數。

度分布是網絡的一個重要統計特征，節點的度指是與節點連接的邊數【8】。Barabdsi和Albert在1999年提出了著名的BA模型，準確地描述了無標度網絡形成的機制。無標度網絡最大的特點在于網絡的度分布自相似性結構和存在節點度很大的節點。一個節點的度越大，表示它在網絡中的重要性就越大。節點的度可以根據其鄰接矩陣來定義，將其定義為： 。網絡中節點的度分布可用函數P（k）來表示，它表示網絡中任意的一個點，度值為k的概率。從統計學上來講，即為網絡中度數為k的節點個數與網絡節點總數的比值：P（k）= 。其中， 表示網絡中度數為k的節點個數，而N表示網絡中總節點個數，即網絡的規模。網絡的節點平均度為網絡中所有節點i的度 的平均值。從目前的研究來看，兩種度分布較為常見：一種是指數度分布，P（k）隨著k的增大以指數形式衰減；另一種分布是冪律分布，即P（k）- 。物流網絡中，通常都有一個或者多個核心企業，眾多的節點企業圍繞核心企業建立的生產、營銷、庫存、配送網絡體系，極大地體現了復雜網絡的無標度性。近年來，基于低成本、高服務質量而建立的第三方、第四方物流的物流網絡更是集中體現了復雜網絡的無標度性。

4.物流網絡的復雜性分析

首先，現實中的物流網絡一般都有大量的節點數，其拓撲結構以及數量巨大的節點相互作用下“涌現”網絡演化的規律和網絡動力學的特性。物流網絡中的節點數量不僅眾多，而且各自的種類多樣。從網絡的拓撲結構來看，物流網絡通常具有多層次性，由眾多的子網絡構成。子網絡一層一層往下拓展，從而形成了復雜的空間拓撲排列，如圖1.4所示【9】。

第二，節點之間的線路是不確定的。由于節點之間相互作用的關系是不確定的，那么節點之間的線路也是時刻在變化的。節點之間的線路意義很多，可以表示路徑，也可以表示流量，還可以表示相互之間的策略選擇等。物流網絡內節點之間的連接是有機的，連接的方式是按節點企業之間的協議來進行的。從圖上來看，物流網絡內節點之間的連接是按非線性方式進行轉化；連接各個節點的邊所代表的內容多種多樣，可表示配送線路的連接、有無庫存供貨的合作、合作的緊密度等，其連接方式呈現立體動態結構。物流網絡內節點是相互影響，相互關聯的，并逐步擴大為不同物流網絡之間的相互連接、相互影響、相互作用，以復雜的耦合方式推動不同網絡之間的演進，從而形成一個紛繁復雜的大世界。

第三，物流網絡的動態性。物流網絡是動態網絡，而且網絡具有實時動態演進的特征，這又導致了網絡結構和功能的實時變化，并通過涌現和自組織的機理產生網絡的復雜效應。物流網絡隨著時間的變化而變化，經過網絡內部和外界環境的相互作用，不斷適應、調節網絡的結構和功能，同時通過自組織作用，整個網絡向更高級的有序化發展，不斷涌現出復雜網絡獨特的行為與特征。

第四，物流網絡的運行環境是不確定的。物流網絡的運行環境是瞬息萬變的。從宏觀環境來講，經濟、科技、信息的全球化使得信息的傳播迅速且廣泛，信息數量之多使得網絡的反饋系統任務繁重。“牽一發而動全身”，由于宏觀環境的任何一個細微的變化都有可能造成物流網絡巨大的震蕩。從微觀環境而言，物流網絡中的任何一個節點所處的外界環境都是不同的，而且每個節點對待環境的變化所持的策略和態度各異，因此對整個物流網絡的作用而言是非常復雜且是不確定的。物流網絡是開放的動態系統，它與外部世界相互聯系、相互作用，系統與外界環境是緊密相關的。物流網絡時刻與外界進行物質、能量、資源和信息的交換。只有通過交換，物流網絡才能得以生存和發展。任何一個復雜網絡，只有在開放的條件下才能形成，才能維持，才能發展。

第五，物流網絡的自組織。物流網絡都具有自組織能力，能通過反饋系統進行自控和自我調節，以達到適應外界變化的目的。物流網絡一旦建立，在運行中無不表現出系統的自組織屬性。物流網絡的各個節點企業通過契約、合作、戰略聯盟等方式進行物流、資金流、現金流的交換，在市場的作用下進行物質和能量的交換，優勝劣汰。在物流網絡系統遠離平衡態的情況下，有些節點企業發展較好，獲得的資源較多，技術力量也日漸雄厚；反之，有些節點企業在市場競爭的角逐下，日漸衰弱，從而推出原有的物流網絡系統。

第六，物流網絡的混沌性。物流網絡也受自身結構和功能的種種參數約束。如物流網絡中的牛鞭效應，充分說明了物流網絡有時受初值的影響是巨大的，物流網絡在動態演化的過程中，只要起始狀態（初始值）稍微有一點點微笑的變化，這種變化會迅速積累和成倍地放大，最終導致物流網絡行為發生巨大的變化。簡單假設一個物流網絡系統，這個網絡只有1個零售商、1個批發商、1個分銷商和1個制造商。零售商預測客戶需求，然后向批發商訂貨，批發商向分銷商訂貨，而分銷商則向制造商訂貨，制造商根據分銷商的訂貨量進行生產的同時保持一定的安全庫存。如果客戶需求是n，假設每個節點企業上的安全庫存率是10%，那么零售商、批發商、分銷商的訂貨量分別為1.1n， n， n，那么制造商的生產量應為 n（即為1.62n）。因為可以看出第1個時間段，制造商最后的產量是客戶需求量的160%，那么第t個時間段，制造商的產量是客戶需求的 倍，其中t大于等于1。因此，只要這個初始值n發生一個小小的變動，即可產生巨大變化。針對物流網絡中產生的混沌效應，節點企業必須重視需求預測，信息共享，每個節點企業縮短供貨的時間，盡量減少不確定性，建立戰略伙伴關系，設置合理的安全庫存。

第七，物流網絡的穩定性。物流網絡具有一定的穩定性，在一定的外界條件下能保證網絡結構的穩定和基本功能的正常發揮，換句話說物流網絡具有一定的抗干擾性，如網絡的魯棒性。網絡的魯棒性是指網絡系統在一定的外界環境作用下，網絡的某些結構發生變化、節點數量的增減或則是出現運行故障的情況下，網絡系統仍能保持其正常的相關性能進行運轉，網絡系統的這種穩定的、自我調整、自我適應的能力稱為“魯棒性”。劉楚燕在她的碩士論文中提出集聚型供應鏈網絡的內部存在多個核心節點企業，這些企業在戰略、戰術、資源和信息方面相互依賴、相互交互，以信息流、資金流、物流的交換方式構成一個復雜的供應鏈網絡，而這種網絡具有較強的魯棒性【10】。浙江大學李剛的博士論文研究了供應鏈的網絡魯棒性，將魯棒性具體分為靜態魯棒性和動態魯棒性；關于靜態魯棒性，文中提出隨機刪除節點， 刪除目標節點，隨機刪除連接邊和刪除目標連接邊四種規則對其模擬研究，結果顯示，供應鏈物流網絡針對不同類型的破壞呈現出不同的魯棒性能【11】。在物流網絡中，由于受到突發事件的影響，如果有些節點不能正常運轉，或者需要臨時增加網絡節點來滿足需求，很多情況下，物流網絡的整體運作是不受影響的，換句話說還是能正常完成其系統特有的功能的。這就說明，物流網絡具有一定的穩定性。

隨著經濟、信息全球化的程度加深，競爭的加劇，內外部環境的不確定性增加，物流網絡涉及到的節點企業越來越多，結構越來越復雜，功能的變化也趨于復雜。利用復雜網絡的理論和復雜性理論來揭示物流網絡的性質，研究物流網絡的動態生成演化過程機制，探索物流網絡節點企業之間的協調機制，分析各個節點的脆弱性、不確定性，以及整個網絡的魯棒性和適應性，以此來實現物流網絡的優化。

參考文獻

【1】Mortiz Fleischmann， Hans Ronald Krikke， Rommert Dekker， Simme Douwe P. Flapper. A characterisation of logistics networks for product recovery. Omega， Volume 28， Issue 6， December 2000， Pages 653-666；

【2】姚衛新.電子商務條件下閉環供應鏈物流網絡的設計.管理科學.2005年06期；

【3】王建華，李南，徐斌.具有批量折扣的供應物流網絡優化遺傳算法研究.中國管理科學，2007年03期；

【4】楊光華，李夏苗，謝小良.加權區域物流網絡結構分析.計算機工程與應用.2009年26期；

【5】吉迎東.煤炭物流網絡風險分析與應對研究.物流工程與管理，2012年12期；

【6】韓舒怡，徐杰.物流網絡協同服務影響因素的實證研究.物流工程與管理，2012年03期；

【7】Watts D J， Strogatz S H. Collective dynamics of 'small-world' networks[J]. Nature， 1998， 393：440-442；

【8】R.Albert and A.L Barabasi，tatistical mechanics of complex networks，Rev，Mod，Phys.74，2002；

【9】李靖， 張永安.復雜網絡理論在物流網絡研究中的應用.中國流通經濟2011年第5期；

【10】劉楚燕.集聚型供應鏈網絡的魯棒性研究.浙江工商大學，管理科學與工程，2011，碩士；

復雜網絡分析范文第2篇

關鍵詞：戰略網絡 復雜網絡理論 網絡效率 節點重要性

引言

戰略網絡是由不同利益成員構成的系統，由于各成員目標可能不同，每個成員都以自身利益最大化為目的參與合作，所以戰略網絡中存在不可避免的矛盾。目前國內外對于戰略網絡節點管理的研究角度多偏向于生態學理論、博弈論及系統論，對企業戰略網絡節點選擇、節點數量及節點的進退機制進行研究。復雜網絡研究的不同之處在于：從統計的角度出發，考察網絡中的大規模節點以及節點之間的連接性質，這些性質的不同意味著網絡內部結構的不同，而內部的結構不同將導致網絡系統的功能不同。利用復雜網絡理論，可以分析網絡中各節點的重要程度，反映各個環節的瓶頸問題。還可以用來發現網絡中的關鍵節點，從而對網絡進行有針對性的優化，進而達到整體網絡的優化。

復雜網絡理論在企業網絡中的應用

科學家們發現大量的真實網絡既不是規則網絡， 也不是隨機網絡，而是具有與前兩者都不同的統計特征的網絡，這樣的一些網絡被科學家們叫做復雜網絡（Albert R，Albert-Laszlo B，2002；Newman M E J，2003）。復雜網絡被發現具有很多與規則網絡和隨機網絡不同的統計特征，其中最突出的是小世界效應和無尺度特性（Drik Helbing，2006；Christian Kuhnert，Dirk Helbing，2006；Marco Laumanns，Erjen Lefeber，2006）。由于現代企業網絡越來越具有復雜性和不穩定性特點，復雜網絡理論在企業網絡方向上的應用也逐漸成為研究熱點。

李守偉、錢省三（2006）在對產業網絡供應鏈的復雜性研究中發現，我國的半導體產業的供應鏈條符合無標度網絡的特征。此外，阮平南、李金玉（2010）將復雜網絡理論用于戰略網絡，闡述了戰略網絡的無標度特征，建立了BA演化模型，解釋了無標度網絡演化的過程，進而解釋了戰略網絡中核心節點的形成。龐俊亭等（2012）探索了集群創新網絡所具有的小世界和無標度結構特性及集群網絡在受到攻擊時所具有的穩健性和脆弱性。

目前多數研究側重定性研究網絡的復雜網絡特性及演化研究，有充分考慮企業網絡的動態適應性問題，沒有考慮到系統整體運行規律。另外，以網絡效率為標準，研究網絡中的節點重要性方面的文獻還是很缺乏的。本文試圖以復雜網絡理論為基礎，從這一全新視角來研究戰略網絡中重要節點識別問題。

戰略網絡的復雜網絡特性分析

（一）戰略網絡拓撲結構

戰略網絡就是由那些具有戰略意義的組織或個人組成的社會網絡。它是由消費者、市場中介、供應商、競爭對手、其他產業的企業、利益相關者、其他組織和企業本身等節點構成的（見圖1）。

用復雜網絡理論研究戰略網絡，首先應將戰略網絡抽象成拓撲模型。將戰略網絡中的企業、科研機構、政府等作為網絡中的節點。節點確定以后，根據各節點的實際聯系確定是否存在邊的關系。作為核心的網絡節點企業存在眾多的合作關系，這就導致戰略網絡的節點的邊越來越多。為了能比較好地模擬出一個戰略網絡，根據戰略網絡的基本結構，描繪出一個簡單戰略網絡拓撲圖，如圖2所示。

（二）戰略網絡的復雜特性

1.戰略網絡的小世界網絡的特征。平均路徑長度是指在網絡中將兩點間的距離被定義為連接兩點的最短路所包含的邊的數目，把所有節點對的距離求平均，就得到了網絡的平均距離。網絡的平均路徑長度L（N）定義為任意兩個節點之間的距離的平均值，平均路徑長度表示產品的交付時間。為在保持激烈競爭環境中的優勢，企業必須采取以下對策：重組整合，減少補給提前期，加快信息的流通速度，減少產品運輸距離，提高自身的反應能力和適應變化的能力，建立配送物流中心，以便能夠更好地實現準時供貨。基于時間的競爭戰略對于各節點成員來說是至關重要的，如何以最短的時間將產品交付給客戶成為節點企業參與戰略網絡競爭必須應對的關鍵戰略問題。在戰略網絡環境中，企業之間的平均最短路徑，可以體現為產品或服務從一個環節到另一個環節所需要的平均最少中轉數目。整個網絡的平均最短路徑L的計算公式為：

上述公式中，dij表示產品或服務從環節i到達環節j所需的最少中轉次數，N表示戰略網絡中的企業總數。

聚集系數指與節點相鄰的節點之間實際存在的邊數與這些節點都互連的最大邊數之比，網絡中所有節點聚集系數的平均就是網絡的聚集系數。對于戰略復雜網絡而言，平均聚集系數相應于網絡節點企業之間相互交流的程度，隨著信息高速發展時代的到來，越來越多的企業應用信息技術和互聯網的媒介建立彼此之間的連接。通過信息共享的各種途徑促使各節點企業之間聯系更加緊密，交流更加頻繁，這就體現戰略網絡具有較高的聚集系數。

2.戰略網絡復雜網絡的無標度特征。無標度網絡的特點是網絡中的大部分節點的度值都很低，但存在著度數非常高的核心節點。各節點企業在企業網絡中所處的網絡地位不同，戰略網絡中的核心企業形成占有的知識不均勻，節點間的連接就具有擇優性（Boschmma R A，Wal A L J，2007）。戰略網絡核心節點的形成主要來源于擇優連接機制，在戰略網絡中，組織會傾向于選擇連接數目較多的網絡節點。通常一些節點企業通過先進的技術、富有競爭力的產品和良好的管理，在非常短的時間內獲得大量的關系連接；網絡中存在歷史較長的企業，有較長的時間來積累與其它組織的關系連接。核心節點的連接數目遠遠超出了一般的節點，并且網絡主要由這些核心節點所支配。

戰略網絡節點重要性模型構建

在復雜網絡中，節點度是單個節點極其重要的屬性節，點的度直接反映該節點在網絡中與其他節點相聯系的廣度，定義為鄰接矩陣中與該節點連接的其他節點邊的數目。傳統復雜理論中判斷核心節點方法是依據網絡中節點度或點強度參數，這個方法是具有很大片面性和局限性的。節點度高的企業只能說明企業與周圍企業的聯系程度密切，而不能真實地反映出該企業在網絡中的作用和地位（朱大智、吳俊，2007）。因此本文將以網絡效率為依據，從新的視角出發對戰略網絡中的節點進行重要性識別。

（一）戰略網絡的網絡效率建模

網絡效率指標被用來衡量網絡中點與點之間的信息溝通程度。在戰略網絡中最短路徑長度反映了戰略網絡內各節點企業產品交付時間的效率。路徑越長，企業獲取資源的時間越長，效率就越低；反之，路徑越短，資源獲取的時間成本越低，效率越高。為了計算網絡效率E，首先要建立這樣一個網絡模型。假設忽略所有企業內部信息，只考慮企業間的聯盟關系；任意兩節點間的連接度是等值的。設網絡G是一個無重邊的無向網絡，即網絡中的邊沒有固定的方向，用G=（N，K）來代表，N是網絡中節點集合，K是網絡中邊集合，G的鄰接矩陣A=（aij）定義如下：

則A是一個n階的對稱矩陣，如果兩個節點之間有聯系，aij=1；否則aij=0。

假設節點i與節點j間的連通的效率eij與最短路徑成反比，即eij=1/dij。那么，給出如下的戰略網絡效率計算公式：

（1）

上述公式中，eij表示完全連通情況下兩個節點企業之間的效率。在突況下，加入變量wij，即網絡效率因子。0≤wij≤1，作為企業連通效率參數。Wij=1表示相關節點企業正常運營。在遭遇突況下，Wij將降低，取0≤wij≤1。這樣可以比較真實地模擬出企業在面對不同風險時，網絡出現效率變化的情況。隨著wij的變化，與該企業有貿易往來的相關企業均會受到一定程度的影響，將導致整個網絡的效率會出現非線性的變化。通過評價網絡的效率，可以嘗試改善網絡的構造從而優化網絡的效率，網絡的效率得以提高，使網絡更具穩定性。

（二）戰略網絡中重要節點的識別建模

網絡效率E無疑成為衡量戰略網絡效率有效的指標，然而它只能表現網絡的平均水平，因此需要更深入的研究，識別網絡中的關鍵節點。此方法主要考察的是當從網絡中剔除節點i以后，網絡的效率變化，根據節點對于網絡效率影響能力的大小，可以識別網絡中的關鍵節點。

E=E=E（G）-E（G`） i=1，2，……N （2）

E（G`）表示wij變化時的網絡平均效率。根據網絡效率變化的大小對網絡中節點的重要性指數進行排序，在wij一定的情況下，網絡效率變化值較大的節點無疑是網絡中重要性相對較高的節點。也就是去除該節點后，網絡效率下降越大，說明該企業的重要性越高。針對企業對于網絡整體的作用不同，需加強預防工作，做到真正的防患于未然。對于這些重要節點，必須予以重點關注，例如，更加頻繁地關注它的運作狀況、與其他企業的連通狀況，建立完備的預警機制等。

結論

基于網絡整體的考慮，本文運用復雜網絡理論，側重從宏觀整體的角度去分析單獨的點和整體網絡之間的關系，通過建立網絡拓撲結構、衡量網絡效率、識別重要網絡節點三個方面，闡述了復雜網絡在戰略網絡管理中的應用前景。建立數學模型比較真實地模擬了網絡在正常情況和突況下的網絡效率。本文只是從復雜網絡理論的角度討論通過戰略網絡效率的辦法計算節點重要性，而由此識別出來的重要企業也是具有現實意義的。

參考文獻：

1.Albert R，Albert-Laszlo B.Statistical mechanics of complex networks[J].Reviews of Modern Physics，2002（74）

2.Newman M E J.The structure and function of complex networks[J].Siam Review，2003（45）

3.Drik Helbing.Information and material flows in complex networks[J].Physica A，2006，363（1）

4.Christian Kuhnert，Dirk Helbing.Scaling laws in urban supply networks[J].Physica A，2006，363（1）

5.Marco Laumanns，Erjen Lefeber.Robust optimal control of material flows in demand-driven supply networks[J].Physica A，2006，363（1）

6.李守偉，錢省三.產業網絡的復雜性研究與實證.科學學研究，2006（4）

7.阮平南，李金玉.戰略網絡中基于無標度網絡的核心企業形成研究.科技管理研究，2010（16）

8.龐俊亭，游達明.基于復雜網絡視角的集群創新網絡特性研究.統計與決策，2012（2）

復雜網絡分析范文第3篇

針對復雜網絡交疊團的聚類與模糊剖析辦法設計Issue(問題),給出一種新的模糊度量及對應的模糊聚類辦法,并以新度量為根底,設計出兩種發掘網絡模糊拓撲特征的新目標:團間銜接嚴密水平和模糊點對交疊團的銜接奉獻度,并將其用于網絡交疊模塊拓撲構造微觀剖析和團間關鍵點提取。實驗后果標明,運用該聚類與剖析辦法不只能夠取得模糊勾結構,并且可以提醒出新的網絡特征。該辦法為復雜網絡聚類后剖析提供了新的視角。

關鍵詞:網絡模糊聚類;團—點相似度;團間連接緊密度;團間連接貢獻度;對稱非負矩陣分解;網絡宏觀拓撲

團結構是復雜網絡普遍而又重要的拓撲屬性之一,具有團內連接緊密、團間連接稀疏的特點。網絡團結構提取是復雜網絡分析中的一個基本步驟。揭示網絡團結構的復雜網絡聚類方法[1~5]對分析復雜網絡拓撲結構、理解其功能、發現其隱含模式以及預測網絡行為都具有十分重要的理論意義和廣泛的應用前景。目前,大多數提取方法不考慮重疊網絡團結構,但在多數網絡應用中,重疊團結構更為普遍,也更具有實際意義。

現有的網絡重疊團結構提取方法[6~10]多數只對團間模糊點進行初步分析,如Nepusz等人[9,10]的模糊點提取。針對網絡交疊團結構的深入拓撲分析,本文介紹一種新的團—點相似度模糊度量。由于含有確定的物理含意和更為豐富的拓撲信息,用這種模糊度量可進一步導出團與團的連接緊密程度,以及模糊節點對兩團聯系的貢獻程度,并設計出新指標和定量關系來深度分析網絡宏觀拓撲連接模式和提取關鍵連接節點。本文在三個實際網絡上作了實驗分析,其結果表明,本方法所挖掘出的網絡拓撲特征信息為網絡的模糊聚類后分析提供了新的視角。

1新模糊度量和最優化逼近方法

設A=[Aij]n×n(Aij≥0)為n點權重無向網絡G(V,E)的鄰接矩陣,Y是由A產生的特征矩陣,表征點—點距離,Yij>0。假設圖G的n個節點劃分到r個交疊團中,用非負r×n維矩陣W=[Wki]r×n來表示團—點關系,Wki為節點i與第k個團的關系緊密程度或相似度。W稱為團—點相似度矩陣。令Mij=rk=1WkiWkj(1)

若Wki能精確反映點i與團k的緊密度,則Mij可視為對點i、j間相似度Yij的一個近似。所以可用矩陣W來重構Y,視為用團—點相似度W對點—點相似度Y的估計:

WTWY(2)

用歐式距離構造如下目標函數:minW≥0FG(Y,W)=Y-WTWF=12ij[(Y-WTW)。(Y-WTW)]ij(3)

其中:•F為歐氏距離;A。B表示矩陣A、B的Hadamard矩陣乘法。由此,模糊度量W的實現問題轉換為一個最優化問題,即尋找合適的W使式(3)定義的目標函數達到最小值。

式(3)本質上是一種矩陣分解,被稱為對稱非負矩陣分解,或s-NMF(symmetricalnon-negativematrixfactorization)。s-NMF的求解與非負矩陣分解NMF[11,12]的求解方法非常類似。非負矩陣分解將數據分解為兩個非負矩陣的乘積,得到對原數據的簡化描述,被廣泛應用于各種數據分析領域。類似NMF的求解,s-NMF可視為加入限制條件(H=W)下的NMF。給出s-NMF的迭代式如下:

Wk+1=Wk。[WkY]/[WkWTkWk](4)

其中:[A]/[B]為矩陣A和B的Hadamard矩陣除法。

由于在NMF中引入了限制條件,s-NMF的解集是NMF的子集,即式(4)的迭代結果必落入NMF的穩定點集合中符合附加條件(H=W)的部分,由此決定s-NMF的收斂性。

在求解W之前還需要確定特征矩陣。本文選擴散核[13]為被逼近的特征矩陣。擴散核有明確的物理含義,它通過計算節點間的路徑數給出任意兩節點間的相似度,能描述網絡節點間的大尺度范圍關系,當兩點間路徑數增加時,其相似度也增大。擴散核矩陣被定義為K=exp(-βL)(5)

其中:參數β用于控制相似度的擴散程度,本文取β=0.1;L是網絡G的拉普拉斯矩陣:

Lij=-Aiji≠j

kAiki=j(6)

作為相似度的特征矩陣應該是擴散核矩陣K的歸一化形式:

Yij=Kij/(KiiKjj)1/2(7)

基于擴散核的物理含義,團—點相似度W也具有了物理含義:團到點的路徑數。實際上,W就是聚類結果,對其列歸一化即可得模糊隸屬度,需要硬聚類結果時,則選取某點所對應列中相似度值最大的團為最終所屬團。

2團—團關系度量

團—點相似度W使得定量刻畫網絡中的其他拓撲關系成為可能。正如WTW可被用來作為點與點的相似度的一個估計,同樣可用W來估計團—團關系:

Z=WWT(8)

其物理含義是團與團間的路徑條數。很明顯,Z的非對角元ZJK刻畫團J與團K之間的緊密程度,或團間重疊度,對角元ZJJ則刻畫團J的團內密度。

以圖1中的對稱網絡為例,二分團時算得

Z=WWT=1.33760.0353

0.03531.3376

由于圖1中的網絡是對稱網絡,兩團具有同樣的拓撲連接模式,它們有相同的團內密度1.3376,而團間重疊度為0.0353。

3團間連接貢獻度

ZJK度量了團J與團K間的重疊程度:

ZJK=na=1WJaWKa(9)

其中:WJaWKa是這個總量來自于點a的分量。下面定義一個新指標來量化給定點對團間連接的貢獻。假設點i是同時連接J、K兩團的團間某點,定義點i對團J和團K的團間連接貢獻度為

Bi=[(WJiWKi)/(na=1WJaWKa)]×100%(10)

顯然,那些團間連接貢獻大的點應處于網絡中連接各團的關鍵位置,它們對團間連接的穩定性負主要責任。將這種在團與團間起關鍵連接作用的點稱為關鍵連接點。為了設定合適的閾值來提取團間關鍵連接點,本文一律取B>10%的點為關鍵連接點。

4實驗與結果分析

下面將在三個實際網絡上展開實驗,首先根據指定分團個數計算出團—點相似度W,然后用W計算團—團關系和B值,并提取關鍵連接點。

4.1海豚社會網

由Lusseau等人[14]給出的瓶鼻海豚社會網來自對一個62個成員的瓶鼻海豚社會網絡長達七年的觀測,節點表示海豚,連線為對某兩只海豚非偶然同時出現的記錄。圖2(a)中名為SN100(點36)的海豚在一段時間內消失,導致這個海豚網絡分裂為兩部分。

使用s-NMF算法聚類,海豚網絡分為兩團時,除30和39兩點外,其他點的分團結果與實際觀測相同,如圖2(a)所示。計算B值并根據閾值提取出的五個關鍵連接點:1、7、28、36、40(虛線圈內),它們對兩團連接起到至關重要的作用。圖2(b)為這五點的B值柱狀圖。該圖顯示,節點36(SN100)是五個關鍵連接點中B值最大者,對連接兩團貢獻最大。某種程度上,這個結果可以解釋為什么海豚SN100的消失導致了整個網絡最終分裂的影響。本例說明,s-NMF算法及團間連接貢獻程度指標在分析、預測社會網絡演化方面有著獨具特色的作用。

4.2SantaFe科學合作網

用本算法對Newman等人提供的SantaFe科學合作網絡[15]加以測試。271個節點表示涵蓋四個學術領域的學者,學者合作發表文章產生網絡連接,構成了一個加權合作網絡。將本算法用于網絡中一個包含118個節點的最大孤立團,如圖3(a)所示。

圖3(a)中,四個學科所對應的主要組成部分都被正確地分離出來,mathematicalecology(灰菱形)和agent-basedmodels(白方塊)與文獻[15]的結果一致,中間的大模塊statisticalphysics又被細分為四個小塊,以不同灰度區分。計算了24個點的團間連接度貢獻值B,從中分離出11個B值大于10%的點作為關鍵連接點:1、2、4、6、11、12、20、47、50、56、57,其標號在橫軸下方標出,見圖3(b),并在圖3(a)中用黑色圓圈標記,這些連接點對應那些具有多種學科興趣、積極參與交叉研究的學者。除去這11個點時,整個網絡的連接布局被完全破壞,見圖3(a)下方灰色背景縮小圖,可見關鍵連接點的確起到重要的溝通各模塊的作用。

4.3雜志索引網絡

在Rosvall等人[16]建立的2004年雜志索引網絡上進行測試。網絡節點代表雜志,分為物理學(方形)、化學(方形)、生物學(菱形)、生態學(三角形)四個學科領域,每個學科中各選10份影響因子最高的刊物,共40個節點,若某刊物文章引用了另一刊物文章,則兩刊間有一條連線,形成189條連接。使用s-NMF對該網4分團時,聚類結果與實際分團情況完全一致,如圖4(a)所示。

由本算法得出的團—點相似度W在網絡宏觀拓撲結構的挖掘方面有非常有趣的應用,如第2章所述,用W計算團—團相似度矩陣Z=WWT,其對角元是團內連接密度,非對角元表征團與團的連接緊密程度,故Z可被視為對原網絡的一種“壓縮表示”。如果將團換成“點”,將團與團之間的連接換成“邊”,利用Z的非對角元,就能構造出原網絡的一個壓縮投影網絡,如圖4(b)所示。這是原網絡的一個降維示意圖,也是團與團之間關系定量刻畫的形象表述,定量地反映了原網絡在特定分團數下的“宏觀(全局)拓撲輪廓”,圖上團間連線色深和粗細表示連接緊密程度。由圖4(b)可以看到,physics和chemistry連接最緊密,而chemistry與biology和biology與ecology次之。由此推測,如果減少分團數,將相鄰兩團合并,連接最緊密的兩團必首先合并為一個團。實際情況正是如此:分團數為3時,biology和ecology各自獨立成團,physics和chemistry合并為一個大團,這與文獻[11]結果一致。

5討論

網絡模糊聚類能幫助研究者進一步對團間的一些特殊點進行定量分析,如Nepusz等人[9]用一種橋值公式來刻畫節點在多個團間的共享程度,即節點從屬度的模糊程度。而本文的團間連接貢獻度B反映出節點在團間連接中所起的作用大小。本質上它們是完全不同的兩種概念,同時它們也都是網絡模糊分析中所特有的。團間連接貢獻度指標的提出,將研究引向對節點在網絡宏觀拓撲模式中的影響力的關注,是本方法的一個獨特貢獻。無疑,關鍵連接點對團間連接的穩定性起到很大作用,如果要迅速切斷團間聯系,改變網絡的宏觀拓撲格局,首先攻擊關鍵連接點(如海豚網中的SD100)是最有效的方法。團間連接貢獻度這一定義的基礎來自于對團與團連接關系(Z)的定量刻畫,這個定量關系用以往的模糊隸屬度概念無法得到。由于W有明確的物理含義,使得由W導出的團—團關系Z也具有了物理含義,這對網絡的宏觀拓撲分析非常有利。

6結束語

針對復雜網絡交疊團現象,本文給出了一個新的聚類后模糊分析框架。它不僅能對網絡進行模糊聚類,而且支持對交疊結構的模糊分析,如關鍵點的識別和網絡宏觀拓撲圖的提取。使用這些新方法、新指標能夠深入挖掘潛藏于網絡的拓撲信息。從本文的聚類后分析不難看出,網絡模糊聚類的作用不僅在于聚類本身,還在于模糊聚類結果能夠為網絡拓撲深入分析和信息挖掘提供支持,而硬聚類則不能。今后將致力于對團間連接貢獻度指標進行更為深入的統計研究。

參考文獻:

[1]趙鳳霞,謝福鼎.基于K-means聚類算法的復雜網絡社團發現新方法[J].計算機應用研究,2009,26(6):2041-2043,2049.

[2]汪小帆,劉亞冰.復雜網絡中的社團結構算法綜述[J].電子科技大學學報,2009,38(5):537-543.

[3]NEWMANMEJ.Modularityandcommunitystructureinnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2006,103(23):8577-8582.

[4]WHITES,SMYTHP.Aspectralclusteringapproachtofindingcommunitiesingraphs[C]//ProcofSIAMInternationalConferenceonDataMining.2005.

[5]ENRIGHTAJ,DONGENSV,OUZOUNISCA.Anefficientalgorithmforlarge-scaledetectionofproteinfamilies[J].NucleicAcidsResearch,2002,30(7):1575-1584.

[6]BEZDEKJC.Patternrecognitionwithfuzzyobjectivefunctionalgorithms[M].NewYork:PlenumPress,1981.

[7]PALLAG,DERENYII,FARKASI,etal.Uncoveringtheoverlappingcommunitystructuresofcomplexnetworksinnatureandsociety[J].Nature,2005,435(7043):814-818.

[8]REICHARDTJ,BORNHOLDTS.Detectingfuzzycommunitystructuresincomplexnetworkswithapottsmodel[J].PhysicalReviewLetters,2004,93(21):218701.

[9]NEPUSZT,PETROCZIA,NGYESSYL,etal.Fuzzycommunitiesandtheconceptofbridgenessincomplexnetworks[J].PhysicalReviewE,2008,77(1):016107.

[10]ZHANGShi-hua,WANGRui-sheng,ZHANGXiang-sun.IdentificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyC-meansclustering[J].PhysicalReviewA:StatisticalMechanicsandItsApplications,2007,374(1):483-490.

[11]PAATEROP,TAPPERU.Positivematrixfactorization:anon-negativefactormodelwithoptimalutilizationoferrorestimatesofdatavalues[J].Environmetrics,1994,5(2):111-126.

[12]ANTTILAP,PAATEROP,TAPPERU,etal.SourceidentificationofbulkwetdepositioninFinlandbypositivematrixfactorization[J].AtmosphericEnvironment,1995,29(14):1705-1718.

[13]KONDORRI,LAFFERTYJ.Diffusionkernelsongraphsandotherdiscretestructures[C]//Procofthe19thInternationalConferenceonMachineLearning.SanFrancisco:MorganKaufmann,2002.

[14]LUSSEAUD,SCHNEIDERK,BOISSEAUOJ,etal.Thebottlenosedolphincommunityofdoubtfulsoundfeaturesalargeproportionoflong-lastingassociations:cangeographicisolationexplainthisuniquetrait?[J].BehavioralEcologyandSociobiology,2003,54(4):396-405.

復雜網絡分析范文第4篇

關鍵詞 武昌城區 交通網絡 數字特征

中圖分類號：U491.13 ；TU984.191 文獻標識碼：A

1武昌城區基本網絡結構特點

我們所得到的網絡是一個連通的整體，它是由194個相互獨立的節點組成的。也就是說，如果用連線來表示兩位節點之間有合作，則任意兩個不同的節點之間有直接的連線或間接的連線。

在該交通網絡中整個網絡的度分布情況如下表1所示：

從表1中可以看出，整個網絡平均度=3.299大部分的節點數度值都集中于2、3、4。其中，含4個節點的小組最多，有55個。

雖然度值最高的點和聚類系數大的點不一定是實際公交線路中的繁忙點，但是它們卻是網絡中取的交通規劃中流通性最好的站點。在這些站點上如果發生交通堵塞時，公交網絡受到的影響并不是很大，公交線路可以很容易的改變繼續運行，即該公交網絡也具有某種“魯棒性”。由此可見，當這幾個節點發生交通堵塞的時候，整個公交網絡的流通性有了明顯的下降；即某種意義上，該公交網絡也具有“脆弱性”。

在該網絡中我們分析了它的全局數字特性，那么下面我們來看看聚類系數與度之間有沒有什么關系。（如表2）

我們由前面所給出的度分布可以看出，大多數節點的度值集中于2、3、4；其中，含4個節點的小組最多；而我們通過上表可以看到，盡管度值在4的節點的聚類系數都很低，但整個網絡具有比隨機網絡更高的平均聚類系數，顯示了比較明顯的聚類效應。

下面我們從該網絡中選取幾個有代表性的子網進行一下研究：（選取的五個網絡的數字特征分別如表3所示。

在這幾個子網中，我們可以看到它們的全局效率比整個網絡要高的多，聚類系數均高于整個網絡的的平均聚類系數。這說明了這幾個子網的流通性要比該整體公交網絡要好。但我們也可以發現在E子網中，當節點137與節點138的線路堵塞時，該網絡被分為兩個網絡，即該子網具有非常高的脆弱性。因此在以后的公交網絡的規劃中，我們應該注意在保持局部公交網絡的效率不降低的情況下對整個網絡進行改造，提升公交網絡的整體效率。

2一個公交網絡查詢系統的開發

基于我們的研究結果，我們嘗試開發了一個用于研究該交通網絡結構與功能的工具查詢系統，該查詢系統界面如下圖所示：

復雜網絡分析范文第5篇

關鍵詞：WS小世界網絡；甲型HIN1流感；Agent；GIS

中圖分類號：R181.3 文獻識別碼：A 文章編號：1001-828X（2017）010-0-01

引言

流行病研究主流方法建立疾病傳播的動力學方程，但方程建立在均勻混合人群的理想狀態下，無法描述真實的社會網絡中傳播的情況[1]。由于小世界網絡具有聚類系數大、平均距離小的特點，即使感染強度很小也會引起網絡上的廣泛傳播，許多社會網絡具有小世界的特點，而流感傳播具有社會網絡的特點，研究選取小世界網絡對流感時空傳播行為特征構建多智能體模型。利用GIS對流行病數據進行空間分析，得出時空傳播特征及規律，為應急預警和追蹤監測服務。 Agent能夠模擬人的智能行為，通過微觀的智能體的交互作用來模擬流行病在整個社會網絡上傳播的宏觀情況。

一、實現步驟

流感傳播的多智能體模型是在研宄建立復雜網絡與智能體模型的基礎上，考慮人的地理時空特性，將“個體”人放置在一定的地理環境中，賦予其空間屬性。因此，將小世界網絡、智能體模型與GIS集成在模型中，使用Repast J平臺，利用Java語言，將智能體進行動態模擬，從而動態展示甲流患者在流感傳播中的時空特性[2]。

二、概念模型設計

1.模型中智能體的分類

根據流感的傳播特征，對經典的SIR模型進行改進，把Agent分成五類.提出了SEITR模型，易感人群Susceptible（S），暴露人群Exposed （E），感染人群Infectious（I），治療人群Treated（T），恢復人群Recovered（R）。治療人群有兩種狀態，一種是患病后就醫治療的人群，另一種是確診后需要被隔離的人群，因為其在隔離期間也接受治療，所以這類統稱為治療人群。治愈后的康復人群重新成為普通的Agent，由于治療后的患者具有一定的免疫能力，所以假定治愈后的康復人群不再被病毒感染。

2.智能體屬性特征

資料顯示，個體年齡、職業等對流感傳播有巨大影響。在設定智能體屬性時，一般考慮年齡、職業、教育水平等因素。在判斷Agent之間是否存在交互感染時，如果Agent年齡在25-45歲之間或小于5歲和大于65歲，將會有更高的感染幾率，而如職業、教育水平等屬性，在不同程度上影響著被感染的幾率。

3.智能體行為特征

流感主要傳播路徑是呼吸道飛沫和接觸傳播，健康 Agent 與具有傳染性的 Agent 在一定的空間范圍內接觸則就可被傳播。如果健康 Agent和具有傳染性的 Agent 在界定的空間距離范圍內直接接觸，并滿足傳播條件，就確定已經被感染。

4.模型環境因素

Agent 的環境因素包括社會和自然因素，社會因素對 Agent 的行為產生影響，自然因素是對自然空間的一種模擬，它為 Agent 提供了一定的活動空間。用 Shapefile格式表達地理空間環境，包括不同圖層。

5.節點選擇

以往人們針對免疫策略常根據節點在網絡中的地位選擇。該模型選用三種控制節點方式進行研究：選取度較大節點、選取隨機節點、選取“熟人免疫”節點[3]。模擬結果較大節點控制率更高。

三、模型結果分析

研究選取感染概率、就醫時間、免疫方式為模型的可調影響因素，并結合實際情況進行調整。為了保證單次模擬結果的準確性，模型在保持其他參數不變的情況下，分別進行 10 次模擬，每次運行時間為三個月，即 90 個 TICK 取平均值為最后結果，結果顯示，在無人為干預的情況下疫情爆發兩周后達到高峰期，一個月后疫情得到控制并逐漸消亡。但在無人為干預的情況下，感染人數呈指數級增長。在疫情早期實施快速有效的干預手段是降低流感危害的關鍵。就醫時間能較大地影響流感的傳播，控制疫情發展的最佳就醫時間為 2 天，在這期間能夠使新增感染數保持在一個較低的水平；當就醫時間大于 2 天時，新增量較高，累計感染人數增加較快，結果表明，流感傳播的高危熱點區域經歷一個少數零星到多數集中變化過程，且被感染的智能體多分布于人口密度較大的區域。人口密度大的區域，潛在接觸的人群也就越大，度較大的節點存在的概率也越高。

四、結語

本文在馱油絡理論指導下，以甲型H1N1流感為例，結合GIS空間分析技術，構建甲型H1N1流感傳播的時空模型。利用歷史數據對流感傳播情況進行反演。結果表明：模型模擬得出的結果與現實官方公布的數據比較吻合，但由于時間和能力的限制，模型沒有很好地充分得到測試和調試，還存在著一定的不確定性，這也是當前研究的下一步工作重點之一。度較大節點在他們患病后傳染給他人的概率較大，采取隔離控制措施，如學校停課，減少集會和出行等。但光控制度較大的節點還不夠，度較小的節點如果在關鍵位置也會引發疾病大規模的傳播。由此提出一種重要的免疫方法：對比較重點的對象諸如學校師生、醫療相關人員等進行免疫接種，擴大接種范圍的隨機免疫等，減小甲流傳播范圍。

參考文獻：

[1]張海峰，傅新楚.含有免疫作用的SIR傳染病模型在復雜網絡上的動力學行為[J].上海大學學報：自然科學版，2007，13（2）：189-192.

[2]郝成民，劉湘偉，郭世杰，等.Repast：基于Agent建模仿真的可擴展平臺[J].計算機仿真，2007， 24（11）：285-288.