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

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

1。算法研究

GN算法可以稱得上是一種較為經(jīng)典的社團(tuán)區(qū)劃算法，其與模塊度搭配后更是常常能夠取得較為良好的區(qū)劃結(jié)果，而且GN算法的限制條件較少，適應(yīng)性較高，其應(yīng)用面也較為廣泛。但近期通過研究我們發(fā)現(xiàn)該算法在區(qū)劃準(zhǔn)確性方面仍存在一些不足，GN算法對于與相連各社團(tuán)連邊均等的點(diǎn)的劃分歸類存在不足，常常出現(xiàn)錯誤，劃分結(jié)果不夠理想，例如在對Zachary空手道俱樂部網(wǎng)絡(luò)進(jìn)行劃分時，節(jié)點(diǎn)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é)點(diǎn)，每個節(jié)點(diǎn)表示一個俱樂部成員,節(jié)點(diǎn)間的連邊表示兩個成員之間的朋友關(guān)系。調(diào)查過程中,該俱樂部因?yàn)橹鞴芘c教練之間的爭執(zhí)而分裂成兩個以他們二人為核心的小社團(tuán)。該網(wǎng)絡(luò)作為一個真實(shí)的社會關(guān)系網(wǎng),常常被用于測試社團(tuán)區(qū)劃方法的準(zhǔn)確性與有效性。

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

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

3。具體操作

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

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