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-)，男，汉族，山东莱芜人，硕士，山东科技大学数学与系统科学学院，研究方向：精算学与风险管理。