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

　　在Protein数据上，三个算法得出的结果曲线非常接近。其中，CNM算法的结果曲线与X轴基本平行，Louvain算法的结果曲线则略优于Wakita算法的结果曲线。三个算法所得结果的节点成对概率绝大部分都为1，表明对于Protein数据而言，三个算法的敏感度都比较低。在AS数据上，CNM算法依然是表现最好的，敏感度最低。Louvain算法的结果曲线比较接近CNM算法的结果曲线。Wakita算法的结果曲线的倾斜度明显高于CNM算法和Louvain算法。因此，在AS数据上，CNM算法的敏感度最低，Wakita算法的敏感度最高。

　　图3为三个算法在Facebook数据、WWW数据的划分结果上取得的节点成对概率的CDF图。因为CNM算法的可扩展性较差，导致其在合理的时间内无法处理完成Facebook数据和WWW数据而得到社团划分结果，所以图3中只有Wakita算法和Louvain算法的结果曲线。

　　从图3中可以看到，在Facebook数据上，Wakita算法的结果曲线的倾斜度明显高于Louvain算法的结果曲线，表明Louvain算法对于Facebook数据的敏感度要低于Wakita算法。但是，这两个算法的结果曲线与X轴有的倾斜度都比较大，表明这两个算法在Facebook数据上的敏感度都不是很理想。在WWW数据上，两个算法的结果曲线很接近，且两条结果曲线都接近于与X轴平行。总体来说，Louvain算法的结果曲线稍微优于Wakita算法。因此，在WWW数据上，Louvain算法的敏感度低于Wakita算法。

　　由于只有Louvain算法能够在合理的时间内处理完成Youtube数据，因此，无法在这个数据上比较三个算法的敏感度。

　　综上所述，在这6个数据上，CNM算法在敏感度方面的表现最好，其得到的社团划分结果比较一致，不容易受节点输入顺序的影响。同时，Wakita算法和Louvain算法的敏感度大小则取决于所处理的图。对于某些图而言，Wakita算法的敏感度相对较低，而对于另外一些图，Louvain算法的敏感度较低。

　　4结束语

　　针对大多数社团发现算法并不具备实际应用价值的情况，文中提出了三个用于筛选社团发现算法的指标：可扩展性、准确度和敏感度。可扩展性旨在衡量社团发现算法能够处理的网络规模；准确度体现社团发现算法所得社团划分结果的好坏；敏感度则用来判断社团发现算法所得划分结果的一致程度。通过这三个指标的结合利用，就可以从众多已提出的社团发现算法中选出能适合于实际应用的社团发现算法。

　　为了查看这三个指标的实际表现情况，使用三种快速社团发现算法——CNM算法、Wakita算法和Louvain算法——进行了一系列的对比实验。实验结果表明，Louvain算法的可扩展性和准确度相对来说最高，CNM算法的敏感度最低。该结论可用于指导在实际应用中如何选择三种社团发现算法。比如，若要处理规模巨大的图，则可使用可扩展性高的Louvain算法；若对结果的稳定性要求较高，则可使用CNM算法。

　　从敏感度实验结果中，可以看到对于大部分数据而言，社团发现算法的敏感度都不太理想。这就使得重复使用某一社团发现算法处理同一个图所得到的社团划分结果没有太大的参考意义。因此，如何降低社团发现算法的敏感度，使得社团发现算法得到的结果能够尽量一致将是下一步研究工作的重点。

　　参考文献：

　　[1]GIRVANM，NEWMANMEJ.Communitystructureinsocialandbiologicalnetworks[C]//ProceedingsoftheNationalAcademyofScienceoftheUSA，2002，99（12）：7821–7826.

　　[2]CLAUSETA，NEWMANMEJ，MOOREC.Findingcommunitystructureinverylargenetworks[J].Phys.Rev.E.，2004，70：066-111.

　　[3]WAKITAK，TSURUMIT.Findingcommunitystructureinmega-scalesocialnetworks[C]//CoRR，abs/cs/0702048，2007.

　　[4]BLONDELVD，etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanics：TheoryandExperiment，2008，10（10008）：12.

　　[5]GUIMERA`R，SALES-PARDOM，LANA.Modularityfromfluctuationsinrandomgraphsandcomplexnetworks[R].PhysicalReviewE.2004，70：25-101.

　　[6]DL，MUNOZMA.Detectingnetworkcommunities：anewsystematicandefficientalgorithm[J].JournalofStatisticalMechanics：TheoryandExperiment，2004，10（1）：1-12.

　　[7]PALLG，etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety[J].Nature，2005，435（7043）：814–818.

　　[8]KWAKH，CHOIY，EOMY，etal.Miningcommunitiesinnetworks：asolutionforconsistencyanditsevaluation[C]//Proceedingsofthe9thACMSIGCOMMconferenceonInternetmeasurementconference，November04-06，2009.

　　[9]http：//www-personal.umich.edu/～mejn/.

　　[10]http：//socialnetworks.mpi-sws.org.

　　[11]OLIVEIRAR，etal.ObservingtheevolutionofInternetAStopology[J].SIGCOMM’07，2007，21（2）：313-324.

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


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

搜索

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