探究超級網(wǎng)絡(luò)的具體算法

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

1。算法研究

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

2。GN算法對Zachary空手道俱樂部網(wǎng)絡(luò)進行劃分的結(jié)果

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

3。具體操作

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

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