资源描述：
《comparison and validation of community structures in complex networks》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ComparisonandvalidationofcommunitystructuresincomplexnetworksMikaGustafsson,MichaelHornquist¨∗,AnnaLombardiDivisionofPhysicsandElectronics,DepartmentofScienceandTechnology,Linkoping¨University,SE-60174Norrkoping,Sweden¨AbstractTheissueofpartitioninganetwo
2、rkintocommunitieshasattractedagreatdealofatten-tionrecently.Mostauthorsseemtoequatethisissuewiththeoneoffindingthemaximumvalueofthemodularity,asdefinedbyNewman.SincetheproblemformulatedthiswayisNP-hard,mostefforthasgoneintotheconstructionofsearchalgorithms,
3、andlesstothequestionofothermeasuresofcommunitystructures,similaritiesbetweenvariouspartition-ingsandthevalidationwithrespecttoexternalinformation.Hereweconcentrateonaclassofcomputergeneratednetworksandonthreewell-studiedrealnetworkswhichconstituteabench-m
4、arkfornetworkstudies;thekarateclub,theUScollegefootballteamsandagenenetworkofyeast.Weutilizesomestandardwaysofclusteringdata(originallynotdesignedforfindingcommunitystructuresinnetworks)andshowthattheseclassicalmethodssometimesoutperformthenewerones.Wedisc
5、ussvar-iousmeasuresofthestrengthofthemodularstructure,andshowbyexamplesfeaturesanddrawbacks.Further,wecomparedifferentpartitionsbyapplyingsomegraph-theoreticconceptsofdistance,whichindicatethatoneofthequalitymeasuresofthedegreeofmodu-laritycorrespondsquit
6、ewellwiththedistancefromthetruepartition.Finally,weintroduceawaytovalidatethepartitioningswithrespecttoexternaldatawhenthenodesareclassi-fiedbutthenetworkstructureisunknown.Thisisherepossiblesinceweknoweverythingofthecomputergeneratednetworks,aswellasthehi
7、storicalanswertohowthekarateclubandthefootballteamsarepartitionedinreality.Thepartitioningofthegenenetworkisval-idatedbyuseoftheGeneOntologydatabase,whereweshowthatacommunityingeneralcorrespondstoabiologicalprocess.arXiv:physics/0601057v1[physics.soc-ph]1
8、0Jan2006Keywords:network,community,validation,distancemeasure,hierarchicalclustering,K-means,GOPACS:89.75.Fb,89.75.Hc,87.16.Yc02.10.Ox∗CorrespondingauthorEmailaddress:[mikgu,micho,annlo]@itn.liu.se(MikaGustafsson,Mi
