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

玄雪冬

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

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

玄雪冬

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

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

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

一、引言

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

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

二、相關知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3、重復第1步的操作，當n>30時。將所得到的孤立點利用FN算法進行社群的劃分

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

四、總結

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

[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]復雜網(wǎng)絡中的社團結構算法綜述[J].汪小帆,劉亞冰.電子科技大學學報.2009(05)

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