資源描述：
《comparison and validation of community structures in complex networks》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、ComparisonandvalidationofcommunitystructuresincomplexnetworksMikaGustafsson,MichaelHornquist¨?,AnnaLombardiDivisionofPhysicsandElectronics,DepartmentofScienceandTechnology,Linkoping¨University,SE-60174Norrkoping,Sweden¨AbstractTheissueofpartitioninganetwo
2、rkintocommunitieshasattractedagreatdealofatten-tionrecently.Mostauthorsseemtoequatethisissuewiththeoneof?ndingthemaximumvalueofthemodularity,asde?nedbyNewman.SincetheproblemformulatedthiswayisNP-hard,mostefforthasgoneintotheconstructionofsearchalgorithms,
3、andlesstothequestionofothermeasuresofcommunitystructures,similaritiesbetweenvariouspartition-ingsandthevalidationwithrespecttoexternalinformation.Hereweconcentrateonaclassofcomputergeneratednetworksandonthreewell-studiedrealnetworkswhichconstituteabench-m
4、arkfornetworkstudies;thekarateclub,theUScollegefootballteamsandagenenetworkofyeast.Weutilizesomestandardwaysofclusteringdata(originallynotdesignedfor?ndingcommunitystructuresinnetworks)andshowthattheseclassicalmethodssometimesoutperformthenewerones.Wedisc
5、ussvar-iousmeasuresofthestrengthofthemodularstructure,andshowbyexamplesfeaturesanddrawbacks.Further,wecomparedifferentpartitionsbyapplyingsomegraph-theoreticconceptsofdistance,whichindicatethatoneofthequalitymeasuresofthedegreeofmodu-laritycorrespondsquit
6、ewellwiththedistancefromthetruepartition.Finally,weintroduceawaytovalidatethepartitioningswithrespecttoexternaldatawhenthenodesareclassi-?edbutthenetworkstructureisunknown.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
