FN算法在開放式社會網(wǎng)路中的應(yīng)用

玄雪冬

(山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 山東 青島 266590)

FN算法在開放式社會網(wǎng)路中的應(yīng)用

玄雪冬

(山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 山東 青島 266590)

基于模塊度的Fast—Newman算法越來越引起人們的重視，該算法雖然準(zhǔn)確度比較高，但是它的算法復(fù)雜度還是比較大，因此僅僅局限于研究中等規(guī)模的復(fù)雜網(wǎng)絡(luò)。本文通過利用FN算法及其后處理、離群點挖掘的相關(guān)知識，在已經(jīng)劃分好的社群中，將不斷接入社群的新的節(jié)點進(jìn)行劃分，從而達(dá)到社群的不斷更新，便于種群挖掘。

種群挖掘；FN算法；后處理；離群點檢測

一、引言

社團(tuán)結(jié)構(gòu)探測和聚類發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中的一個重要課題。一般而言社團(tuán)可以包含模塊、類、群、組等各種含義[1]。如萬維網(wǎng)可以看成是由大量網(wǎng)站社團(tuán)組成的，同一個社團(tuán)內(nèi)部的各個網(wǎng)站討論的是一些有共同興趣的話題[2]。類似地，在生物網(wǎng)絡(luò)或者電路網(wǎng)絡(luò)中，同樣可以將各個節(jié)點根據(jù)其不同的性質(zhì)劃分為不同的社團(tuán)[3]。揭示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對于了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性都很重要。社團(tuán)結(jié)構(gòu)分析在生物學(xué)、物理學(xué)、計算機(jī)圖形學(xué)和社會學(xué)中都有廣泛的應(yīng)用[4]。網(wǎng)絡(luò)社團(tuán)的研究已經(jīng)有了很長的歷史，它與計算機(jī)科學(xué)中的圖形分割和社會學(xué)中的分級聚類有著密切的關(guān)系[5]。根據(jù)這些算法可得到很多社團(tuán)結(jié)構(gòu)，具有巨大的應(yīng)用價值。為了辨別所挖掘的社團(tuán)結(jié)構(gòu)的優(yōu)劣，需要一個量化的標(biāo)準(zhǔn)來評估各種社團(tuán)結(jié)構(gòu)。迄今為止，模塊度函數(shù)Q是最廣泛使用的評價函數(shù)。同時，基于模塊度的理念，Newman提出的FN算法[21]是一種十分有效的用于發(fā)掘社團(tuán)結(jié)構(gòu)的聚類算法。通常對FN算法的研究發(fā)現(xiàn)，用FN算法被劃分好的多個社團(tuán)后，如果再有新的點加入該社會網(wǎng)絡(luò)，F(xiàn)N算法無法更新社團(tuán)群體。

本文利用FN算法結(jié)果的后處理方法，對新接入社會網(wǎng)絡(luò)的節(jié)點進(jìn)行種群的劃分，利用FN算法和離群點檢測方法不斷更新種群，以此來彌補(bǔ)FN算法在更新式網(wǎng)絡(luò)模型中應(yīng)用的缺陷。

二、相關(guān)知識

(一)FN算法的后處理(基于中心關(guān)系)

該方案基于社團(tuán)中心的思路。假設(shè)社團(tuán)中存在一個或若干個核心點，這個核心點類似于交通樞紐，一般處于社團(tuán)的中心地位(繁忙地位)。應(yīng)用廣度優(yōu)先最短路徑算法，計算出一個社團(tuán)內(nèi)任意兩個成員之間的最短路徑，并記錄最短路徑所經(jīng)過的點。那么處于中心地位的點出現(xiàn)的頻率應(yīng)當(dāng)是最高的，記為Core V(c)。再應(yīng)用 Dijkstra最短路徑算法來計算點Vi到CoreV(c)之間的距離，來確定Vi的歸屬社團(tuán)。算法步驟如下：

Step1分別計算社團(tuán)ci′和cj′內(nèi)部成員之間兩兩的最短路徑，并記錄所經(jīng)過的點(社團(tuán)之間的路徑不參與計算)。

Step2統(tǒng)計出各自社團(tuán)的中心點Core V(cj)和 Core V(ck)(一個或若干個)。

Step3 計算D1=Dijkstra(VI，Core V(cj′))和D2=Dijkstra(VI，Core V(cj′))。

Step4 若D1D2，則Vi∈ck。特別地，當(dāng)Core V(c)有多個時，有兩種決策來計算D值：1)最近中心點；2)平均距離。需要采用哪種決策，則根據(jù)實際情況和需求來確定。

(二)基于密度的離群點檢測方法

為了解決基于距離的離群點檢測方法無法檢測局部離群點的問題,Breuning等闡明了局部離群點的概念和基于密度的離群點的定義,并且定義了專門的度量單位:局部離群系數(shù)LOF(Local Outlier Factor)。LOF算法解決了局部離群程度的度量以及挖掘問題。LOF越大,表示它越可能是異常的,否則就表示它可能是正常的。

p的局部離群點因子(localoutlierfactor)定義表示如下:

目前針對LOF算法,也有很多學(xué)者對它進(jìn)行了改進(jìn)。如Jin等提出了基于反向k鄰域的局部離群點度量方法,防止數(shù)據(jù)分布比較復(fù)雜時LOF算法可能產(chǎn)生的錯判。

基于密度的方法與基于距離的方式同樣給出了對象是離群點程度的定量度量。通過對密度的定義,能夠檢測出局部離群點。但是它的時間復(fù)雜度為O(n2),效率仍然比較低下,受參數(shù)影響仍然比較大。

三、模型構(gòu)建以及算法實現(xiàn)

假設(shè)社會網(wǎng)絡(luò)中已經(jīng)分好的社群為A1、A2、A3、……AI。n為孤立點的個數(shù)。對于新進(jìn)入的點：

1、利用基于密度的離群點檢測方法判斷該點是否是離群的，即是否與原始網(wǎng)絡(luò)孤立。如果為孤立點。則令n=n+1(n的初始值為0)如果不為孤立點則進(jìn)行第2步。

2、利用FN算法的后處理計算A1、A2、A3、……Ai社群的中心與該點的距離記為D1、D2、D3、…Di。Dj=max{D1、D2、D3、…Di}，則該點劃分到Aj這個社群中。1

3、重復(fù)第1步的操作，當(dāng)n>30時。將所得到的孤立點利用FN算法進(jìn)行社群的劃分

4、更新社群，并且更新每個社群的中心點。重復(fù)第1步操作。不斷更新社群。

四、總結(jié)

本文利用FN算法對社會網(wǎng)絡(luò)不斷接入新節(jié)點進(jìn)行了社群的劃分。不僅可以將新接入的點劃分到原來社會網(wǎng)絡(luò)中原有的社群中。也可以通過離群點檢測方法增加新的社群，從而增加了新的社群。達(dá)到了更新式社會網(wǎng)絡(luò)劃分社群的目的。彌補(bǔ)了FN算法在開放式網(wǎng)絡(luò)中不斷重復(fù)運算的繁瑣過程。對于FN的算法在這方面的應(yīng)用還處于探索階段。仍需要進(jìn)一步的研究。在離群挖掘方面，以及中心點更新問題上仍需要做相應(yīng)的改善。

[1]Detectoverlappingandhierarchicalcommunitystructureinnetworks[J].HuaweiShen,XueqiCheng,KaiCai,Mao-BinHu.PhysicaA:StatisticalMechanicsanditsApplications.2008 (8)

[2]Identificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyc-meansclustering[J].ShihuaZhang,Rui-ShengWang,Xiang-SunZhang.PhysicaA:StatisticalMechanicsanditsApplications.2006 (1)

[3]Fastalgorithmfordetectingcommunitystructureinnetworks.Newman,MEJ.PhysicalReviewEStatistical,NonlinearandSoftMatterPhysics.2004

[4]Anefficientheuristicprocedureforpartitioninggraphs.KernighanBW,LinS.BellSystemTechnicalJournal,The.1970

[5]復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].汪小帆,劉亞冰.電子科技大學(xué)學(xué)報.2009(05)

玄雪冬(1992-)，男，漢族，山東萊蕪人，碩士，山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，研究方向：精算學(xué)與風(fēng)險管理。