FN算法在開放式社會網路中的應用

玄雪冬

(山東科技大學數學與系統科學學院 山東 青島 266590)

FN算法在開放式社會網路中的應用

玄雪冬

(山東科技大學數學與系統科學學院 山東 青島 266590)

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

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

一、引言

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

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

二、相關知識

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

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

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

Step2統計出各自社團的中心點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)平均距離。需要采用哪種決策，則根據實際情況和需求來確定。

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

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

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

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

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

三、模型構建以及算法實現

假設社會網絡中已經分好的社群為A1、A2、A3、……AI。n為孤立點的個數。對于新進入的點：

1、利用基于密度的離群點檢測方法判斷該點是否是離群的，即是否與原始網絡孤立。如果為孤立點。則令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算法對社會網絡不斷接入新節點進行了社群的劃分。不僅可以將新接入的點劃分到原來社會網絡中原有的社群中。也可以通過離群點檢測方法增加新的社群，從而增加了新的社群。達到了更新式社會網絡劃分社群的目的。彌補了FN算法在開放式網絡中不斷重復運算的繁瑣過程。對于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]復雜網絡中的社團結構算法綜述[J].汪小帆,劉亞冰.電子科技大學學報.2009(05)

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