面向大规模应用层拓扑的社团发现技术(2)

　　采用三个快速社团发现算法来进行一系列对比实验。这三个算法分别是：CNM算法[2]、Wakita算法[3]和Louvain算法[4]。三个算法的原理都是通过最大化模块性Q的值来得到尽可能好的社团划分结果。表1是进行对比实验的软硬件环境配置。

　　表1实验环境

　　Tab.1Experimentalenvironment操作系统RedHatEnterpriseLinuxServerrelease5.2

　　（Tikanga）CPUIntel（R）Xeon（R）CPUE5405@2.00GHz（共8个）CPU缓存6MB内存容量4GB硬盘容量540GB磁盘缓存大小3GB

　　在这一系列对比实验中，使用了7个现实世界网络的数据。这些数据分别是：Karate[9]、C.Elegans[9]、Protein[10]、AS[11]、Facebook[10]、WWW[10]和Youtube[10]。而其详细统计信息如表2所示。

　　表2实验数据统计信息

　　Tab.2Statisticsoftheexperimentaldata统计信息实验数据KarateC.ElegansProteinASFacebookWWWYoutube节点数34297184632930637303257291138499边数782148220312413381709010901082990443平均节点度4.614.52.47.525.76.75.3平均聚类系数0.570.290.0710.380.220.230.09

　　3实验结果分析

　　下面将依次给出可扩展性、准确度和敏感度这三个指标所对应的实验结果，并根据这些实验结果详细说明这三个指标的实际应用意义。

　　3.1可扩展性结果

　　可扩展性实验中，分别使用三个快速算法处理Karate等7个数据，并在处理每个数据时，记录各算法的运行时间。实验结果如表3所示。

　　结合表2中的实验数据统计信息，可以从表3中观察分析，并得到以下结论：

　　（1）对于节点数小于5000的网络，三个算法基本不消耗任何运行时间；

　　表3可扩展性实验结果

　　Tab.3Resultsofscalability时间（s）

　　算法实验数据KarateC.ElegansProteinASFacebookWWWYoutubeCNM00082117425277345626Wakita00012625213370Louvain000121742

　　（2）当网络节点数超过5000时，CNM算法效率开始下降；

　　（3）当网络节点数超过100万时，CNM算法效率下降严重；

　　（4）当网络节点数超过100万，边数超过1000万时，Wakita算法消耗的时间明显增加，Wakita算法的效率也开始明显下降。

　　综上所述，从算法运行时间的增长趋势中，可以知道，Louvain算法可扩展性最高，其次是Wakita算法，最后是CNM算法。

　　3.2准确度结果

　　准确度对比实验的过程分为以下3步：

　　（1）准备测试数据。对7个实验数据中的每一个，重新对数据中的节点进行随机编号，以达到打乱节点输入顺序的目的。每个数据都进行100次同样的操作。因此，每个数据都能够得到数据相同但节点输入顺序不同的100组数据。本文将这100组数据称为一个数据集合。

　　（2）运行算法程序。在每一个数据集合上，分别运行三个算法，记录每个算法在各个数据集合上得出的模块性Q的值。

　　（3）处理测试结果。计算每个算法在各个数据集合上得到的模块性Q的平均值和方差。

　　准确度实验结果如表4所示。表4中，未能在合理时间内得出社团划分结果的用“——”表示。

　　表4准确度实验结果

　　Tab.4ResultsofaccurancyQ平均值

　　算法实验数据KarateC.ElegansProteinASFacebookWWWYoutubeCNM0.38070.37110.84430.5489——————Wakita0.41230.30820.83080.51750.37370.8952——Louvain0.41520.39140.84320.58680.63310.93570.7197

　　从表4中，可以知道：Louvain算法得到的模块性Q的平均值大于CNM算法和Wakita算法。这表明Louvain算法所得社团划分结果的准确度要高于其它两个算法；另外CNM算法的准确度则要高于Wakita算法。

　　3.3敏感度结果

　　根据准确度实验所得的社团划分结果来计算节点成对概率pij。节点成对概率的计算结果使用累积分布函数（CDF）图展示。图1为Karate数据和C.Elegans数据上计算得到的节点成对概率的累积分布函数图。

　　从图1中可以知道：在Karate数据上，CNM算法所得划分结果的pij只有0和1这两个值；这是最理想的结果，即划分结果完全一致，不受节点输入顺序的影响；在C.Elegans数据上，CNM算法所得划分结果的pij也大部分为0或1；Wakita算法的表现虽然比Louvain算法好，但相对CNM算法来说则要差上很多；因此，从节点成对概率角度进行判断，对Karate数据和C.Elegans数据来说，敏感度由高到低依次是Louvain算法、Wakita算法、CNM算法。

　　图2为三个算法在Protein数据和AS数据上得出的节点成对概率的CDF图。

　　论文榜（www.zglwb.com），是一个专门从事期刊推广、投稿辅导的网站。
本站提供如何投稿辅导，寻求投稿辅导代理，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。


期刊鉴别	论文检测	免费论文	特惠期刊	学术答疑	发表流程

搜索

面向大规模应用层拓扑的社团发现技术(2)