资源描述：
《offdiagonal complexity a computationally quick complexity measure for graphs and networks》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、OffdiagonalComplexity:Acomputationallyquickcomplexitymeasureforgraphsandnetworks(PhysicaA,inprint)JensChristianClaussenInstitutf¨urTheoretischePhysikundAstrophysik,Universit¨atKiel,Leibnizstraße15,24098Kiel,Germanyphone++49-431-880-4096claussen@theo-physik.uni-kiel.deAbstractAvastvarietyofbiolo
2、gical,social,andeconomicalnetworksshowstopologiesdras-ticallydifferingfromrandomgraphs;yetthequantitativecharacterizationremainsunsatisfactoryfromaconceptualpointofview.Motivatedfromthediscussionofsmallscale-freenetworks,abiasedlinkdistributionentropyisdefined,whichtakesanextremumforapowerlawdis
3、tribution.Thisapproachisextendedtothenode-nodelinkcross-distribution,whosenondiagonalelementscharacterizethegraphstructurebeyondlinkdistribution,clustercoefficientandaveragepathlength.Fromhereasimple(andcomputationallycheap)complexitymeasurecanbedefined.ThisOffdiagonalComplexity(OdC)isproposedasan
4、ovelmeasuretocharacterizethecomplexityofanundirectedgraph,ornetwork.WhilebothforregularlatticesandfullyconnectednetworksOdCiszero,ittakesamoderatelylowvalueforarandomgraphandshowshighvaluesforapparentlycomplexstructuresasscale-freenet-worksandhierarchicaltrees.TheOffdiagonalComplexityapporachis
5、appliedtotheHelicobacterpyloriproteininteractionnetworkandrandomlyrewiredsurrogates.arXiv:q-bio/0410024v2[q-bio.MN]23Aug20061IntroductionWhilerandomgraphtheoryandscale-freenetworkresearchknowasetofstandardmeasurestoquantifytheirproperties,thequestionofcomplexityofagraphstillisinitsinfancies.A‘
6、blind’applicationofothercomplexityPreprintsubmittedtoElsevierScienceOctober16,2004;revisedAugust11,2006measures(asforbinarysequencesorcomputerprograms)doesnotaccountforthespecialpropertiessharedbygraphsandespeciallyscale-freegraphs.Moreover,someknowncomplexitymeasuresthemselveshaveahighcompu-t
7、ationalcomplexity.Sinceaseriesofseminalpapers(Watts&Strogatz[1],Barabasi&Albert[2][2,3],Newman[4],Dorogovtsev&Mendes[5])since1999(seealso[6]foranoverview),small-worldandscale-freenetworksareahottopicofinvestigationinabroadrangeofsystems
