探究超級網絡的具體算法

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了探究超級網絡的具體算法范文，希望能給你帶來靈感和參考，敬請閱讀。

1。算法研究

GN算法可以稱得上是一種較為經典的社團區(qū)劃算法，其與模塊度搭配后更是常常能夠取得較為良好的區(qū)劃結果，而且GN算法的限制條件較少，適應性較高，其應用面也較為廣泛。但近期通過研究我們發(fā)現該算法在區(qū)劃準確性方面仍存在一些不足，GN算法對于與相連各社團連邊均等的點的劃分歸類存在不足，常常出現錯誤，劃分結果不夠理想，例如在對Zachary空手道俱樂部網絡進行劃分時，節(jié)點3的錯誤劃分。Zachary空手道俱樂部網絡是復雜網絡與社會網分析領域中常用的一個經典測試網絡，WayneZachary用幾年時間觀察一所大學空手道俱樂部成員間的社會關系,并構造出俱樂部成員的社會關系網，網絡包含34個節(jié)點，每個節(jié)點表示一個俱樂部成員,節(jié)點間的連邊表示兩個成員之間的朋友關系。調查過程中,該俱樂部因為主管與教練之間的爭執(zhí)而分裂成兩個以他們二人為核心的小社團。該網絡作為一個真實的社會關系網,常常被用于測試社團區(qū)劃方法的準確性與有效性。

2。GN算法對Zachary空手道俱樂部網絡進行劃分的結果

GN算法雖然非常經典，但其對均等節(jié)點的劃分常常存在問題，劃分效果不夠理想，本文提出的新算法在GN算法的基礎上引入標準化程度中心性理論方法，該方法可以用于衡量某一節(jié)點在某團體內的相對重要程度，可以有效地對均等節(jié)點等歧義節(jié)點進行度量與測算，從而能夠有效地彌補GN算法在均等節(jié)點劃分上的不足。另外，當前傳統(tǒng)GN算法對劃分對象的處理基本都是基于單網絡視角的，這樣就未能將社團區(qū)劃前后的節(jié)點拓撲屬性進行比對，也就未能從此角度對社團的區(qū)劃進行審視與改進。新算法引入超網絡理論方法作為算法的主要框架，將劃分前的整個網絡視為全網絡，而將劃分之后的各個社團網絡視為子網絡，進而建立起超網絡理論分析的模型架構，將超網絡的相關理論方法運用其中，可以有效地彌補GN算法在社團劃分前后節(jié)點拓撲屬性比對方面的不足。程度中心性算法是當前測度網絡節(jié)點重要程度的一種主要方法。擁有較高程度中心性的個體，在這個團體或網絡中也具有一個較為重要的地位。其公式如下，公式(1)為絕對數值，就是把某個體的關系數加總，公式(2)為標準化數值，是將其除以該個體在該網絡中最大可能的關系數，便于不同網絡間的比較。

3。具體操作

直到每個節(jié)點就是一個退化的社團為止。然后選擇具有模塊度Q局域峰值的社團區(qū)劃結果進行分析。分析選定結果中社團間連邊的頂點Qv是否符合其與各相連社團的連邊均等，我們將與相連各社團連邊均等的節(jié)點定義為均等節(jié)點jdv，即判斷此時QjdvV是否成立。則比較其全網標準化程度中心性1SQDQSdvSCvg和其在所屬社團內的子網標準化程度中心性1ZaZaGQaDQGdvZCvg（設此時QZavG），若其全網標準化程度中心性大于其在所屬社團內的子網標準化程度中心性，即DQaDQSCvZCv，否則結束。計算網絡中經過每條邊的最短路徑數目B(e)，ijijvvVBene，ijne表示節(jié)點,ijvvV間最短路徑中包括邊e的數量。找到經過最短路徑數目最多的邊并將它從網絡中移除，并將移除邊的頂點按照其對應模塊度Q值的不同分別記錄下來，即按照模塊度值的不同生成對應的社團間邊頂點的集合QV。該點復制至選定區(qū)劃結果的其他社團中，再計算其在新的社團內的子網標準化程度中心1ZxQZxQGvQxDQGvdvZCvg，（xa），將xDQZCv與其全網標準化程度中心性DQSCv進行比較，找到大于其全網標準化程度中心性且值最大的結果，則此時對應的區(qū)劃結果即為所求。

作者：武澎 王恒山 劉奇 單位：上海理工大學