comparison and validation of community structures in complex networks28446

《comparison and validation of community structures in complex networks28446》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ARTICLEINPRESSPhysicaA367(2006)559–576www.elsevier.com/locate/physaComparisonandvalidationofcommunitystructuresincomplexnetworksMikaGustafsson,MichaelHo¨rnquist,AnnaLombardiDivisionofPhysicsandElectronics,DepartmentofScienceandTechnology,Linko¨pingUniversity,SE-60174Norrko¨ping,Swed

2、enReceived4November2005;receivedinrevisedform6December2005Availableonline6January2006AbstractTheissueofpartitioninganetworkintocommunitieshasattractedagreatdealofattentionrecently.Mostauthorsseemtoequatethisissuewiththeoneoffindingthemaximumvalueofthemodularity,asdefinedbyNewman.Sincet

3、heproblemformulatedthiswayisbelievedtobeNP-hard,mostefforthasgoneintotheconstructionofsearchalgorithms,andlesstothequestionofothermeasuresofcommunitystructures,similaritiesbetweenvariouspartitioningsandthevalidationwithrespecttoexternalinformation.Hereweconcentrateonaclassofcomputerg

4、eneratednetworksandonthreewell-studiedrealnetworkswhichconstituteabench-markfornetworkstudies;thekarateclub,theUScollegefootballteamsandagenenetworkofyeast.Weutilizesomestandardwaysofclusteringdata(originallynotdesignedforfindingcommunitystructuresinnetworks)andshowthattheseclassicalm

5、ethodssometimesoutperformthenewerones.Wediscussvariousmeasuresofthestrengthofthemodularstructure,andshowbyexamplesfeaturesanddrawbacks.Further,wecomparedifferentpartitionsbyapplyingsomegraph-theoreticconceptsofdistance,whichindicatethatoneofthequalitymeasuresofthedegreeofmodularityco

6、rrespondsquitewellwiththedistancefromthetruepartition.Finally,weintroduceawaytovalidatethepartitioningswithrespecttoexternaldatawhenthenodesareclassifiedbutthenetworkstructureisunknown.Thisisherepossiblesinceweknoweverythingofthecomputergeneratednetworks,aswellasthehistoricalanswertoh

7、owthekarateclubandthefootballteamsarepartitionedinreality.ThepartitioningofthegenenetworkisvalidatedbyuseoftheGeneOntologydatabase,whereweshowthatacommunityingeneralcorrespondstoabiologicalprocess.r2006ElsevierB.V.Allrightsreserved.Keywords:Network;Community;Validation;Distancemeasur

8、e;Hierarchic