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

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

1。算法研究

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

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

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

3。具體操作

直到每個(gè)節(jié)點(diǎn)就是一個(gè)退化的社團(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，即判斷此時(shí)QjdvV是否成立。則比較其全網(wǎng)標(biāo)準(zhǔn)化程度中心性1SQDQSdvSCvg和其在所屬社團(tuán)內(nèi)的子網(wǎng)標(biāo)準(zhǔn)化程度中心性1ZaZaGQaDQGdvZCvg（設(shè)此時(shí)QZavG），若其全網(wǎng)標(biāo)準(zhǔn)化程度中心性大于其在所屬社團(tuán)內(nèi)的子網(wǎng)標(biāo)準(zhǔn)化程度中心性，即DQaDQSCvZCv，否則結(jié)束。計(jì)算網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑數(shù)目B(e)，ijijvvVBene，ijne表示節(jié)點(diǎn),ijvvV間最短路徑中包括邊e的數(shù)量。找到經(jīng)過最短路徑數(shù)目最多的邊并將它從網(wǎng)絡(luò)中移除，并將移除邊的頂點(diǎn)按照其對(duì)應(yīng)模塊度Q值的不同分別記錄下來，即按照模塊度值的不同生成對(duì)應(yīng)的社團(tuán)間邊頂點(diǎn)的集合QV。該點(diǎn)復(fù)制至選定區(qū)劃結(jié)果的其他社團(tuán)中，再計(jì)算其在新的社團(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é)果，則此時(shí)對(duì)應(yīng)的區(qū)劃結(jié)果即為所求。

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