资源描述:
《Overlapping Community Detection in Networks- .pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、OverlappingCommunityDetectioninNetworks:theStateoftheArtandComparativeStudy1JIERUIXIE(jierui.xie@gmail.com)NetworkScienceandTechnology,RensselaerPolytechnicInstitute,NewYork,USASTEPHENKELLEY(kelleys@ornl.gov)OakRidgeNationalLaboratory,Tennessee,USAandBOLESLAWK.SZYMANSKI(szymans
2、k@cs.rpi.edu)NetworkScienceandTechnology,RensselaerPolytechnicInstitute,NewYork,USAThispaperreviewsthestateoftheartinoverlappingcommunitydetectionalgorithms,qualitymeasures,andbenchmarks.Athoroughcomparisonofdifferentalgorithms(atotaloffourteen)isprovided.Inadditiontocommunityle
3、velevaluation,weproposeaframeworkforevaluatingalgorithms’abilitytodetectoverlappingnodes,whichhelpstoassessover-detectionandunder-detection.AfterconsideringcommunityleveldetectionperformancemeasuredbyNormalizedMutualInformation,theOmegaindex,andnodeleveldetectionperformancemeas
4、uredbyF-score,wereachedthefollowingconclusions.Forlowoverlappingdensitynetworks,SLPA,OSLOM,GameandCOPRAofferbetterperformancethantheothertestedalgorithms.Fornetworkswithhighoverlappingdensityandhighoverlappingdiversity,bothSLPAandGameproviderelativelystableperformance.However,te
5、stresultsalsosuggestthatthedetectioninsuchnetworksisstillnotyetfullyresolved.Acommonfeatureobservedbyvariousalgorithmsinreal-worldnetworksistherelativelysmallfractionofoverlappingnodes(typicallylessthan30%),eachofwhichbelongstoonly2or3communities.CategoriesandSubjectDescriptors
6、:A.1[GeneralLiterature]:INTRODUCTORYANDSUR-VEY;I.5.3[Clustering]:Clustering—Algorithms;H.3.3[Clustering]:InformationSearchandRetrieval—Clustering;E.1[Data]:DATASTRUCTURES—GraphsandnetworksGeneralTerms:Algorithms,PerformanceAdditionalKeyWordsandPhrases:Algorithms,overlappingcomm
7、unitydetection,socialnet-works1.INTRODUCTIONarXiv:1110.5813v4[cs.SI]3Jul2012Communityormodularstructureisconsideredtobeasignificantpropertyofreal-worldsocialnetworksasitoftenaccountsforthefunctionalityofthesystem.De-spitetheambiguityinthedefinitionofcommunity,numeroustechniquesha
8、vebeendevelopedforbothefficientandeffectivecommunitydetec