基于熵的复杂有向网络异质性度量方法

:1001-4098(2011)08-0123-04周　漩,张凤鸣,惠晓滨,李克武,姜苈峰(,710038):复杂网络异质性度量方法研究中,现有方法虽然考虑了网络中节点度分布,但没有考虑相邻节点之间的差异性和节点相互作用的方向性,对此,提出了一种基于熵的复杂有向网络异质性度量方法,综合考虑有向网络节点度分布和相邻节点之间的差异性,突出网络对称性在消除网络异质性中所起的作用,使得有向网络异质性的度量更加准确,为复杂有向网络复杂性的度量提供一种新的思路。算例表明该方法具有合理性和有效性。:异质性;度分布;熵;有向网络:N945:A1　引言,,,,,,,,0;Scale-free,,,,,,,[1]4,:,[2],,[3],,,,,,2基于熵的复杂有向网络异质性度量,Mowshowitz[5],:()(),,,,,,,,298(212)　　　　　　系　统　工　程Vol.29,No.820118SystemsEngineeringAug.,2011:2011-03-12:(1986-),,,,:,;(1963-),,,,,:2.1G=G(V,E),,,,,,,GNm,iki,(1):Efo=-mi=1kiNlog2kiN(1)N,N,Efo,Efo-max=log2N;,Efo,Efo-min=0,:Efos=Efo-Efo-minEfo-max-Efo-min=Efolog2N(2)2.2,,,,1,AB3,,AB;,,ABB;A:18,2367,45AB.,13,[2][6],,,[1],,,,,,GNl,iki,(3):Eso=-li=1kiNlog2kiN(3),,N,N,Eso,Eso-max=log2N;,,,Eso,Eso-min=0,:Esos=Eso-Eso-minEso-max-Eso-min=Esolog2N(4)2.3,:E=E2fos+E2sos(5)(5),EEfosEEsos.Esos=0,;Efos=0,2.4,:1:,,(1)(2)2:,(3)(4)3:(5),3　算例与分析3.11,1,AB,Efos-A=Efos-B=0,,,AB:PA={(1,8),(2,3,6,7),(4,5)};PB={(1,2,3,4,5,6,7,8)},,Esos-A=0.5,Esos-B=0(5)EA=0.5,EB=0,A1242011B.,,1(A)18,,18,1818,,,,3.2,G1G2G1G22,V={a,b,c,d,e,f,g}21:G1G2,11G1G202{a}02{a}11{b,c,e,f}11{b,d,e}22{d}12{c}20{g}21{f}20{g}1,G1G2G14,4,G25(2)G1G2:Efos(G1)=-4i=1ki7log2ki7log27=-37log217-47log247log27=0.593Efos(G2)=-5i=1ki7log2ki7log27=-47log217-37log237log72=0.7582:,22G1G2{b,c}{a}{b,c}{a}{a,d}{b,c}{a,g}{b}{b,ce,f}{d}{a,d,e}{c}{d,g}{e,f}{c,f}{d,e}{e,f}{g}{d,e,g}{f}{b,f}{g}2,G1G2G22,6(4)G1G2:Esos(G1)=-5i=1ki7log2ki7log27=-47log227-37log217log27=0.797Esos(G2)=-6i=1ki7log2ki7log27=-57log217-27log227log27=0.8983:(5),,G1G2:E(G1)=0.993,E(G2)=1.175,G1G2,,G1G2,G11258,:,,;,,,,E(G1)E(G2),G2G14　结论,,,:,,,,,,:[1],.Scale-freeScale-free[M].:,2009.[2]XiaoYH,etal.Symmetry-basedstructureentropyofcomplexnetworks[J].PhysicaA,2008,387(11):26112619.[3]HeF,etal.Developmentofthecomplexitymeasureforassemblylinesystemsusingentropyconcept[C]//WorldCongressonIntelligentControlandAutomation,2008:90379042.[4]ParkJ,JungW,HaJ.Developmentofthestepcomplexitymeasureforemergencyoperatingproceduresusingentropyconcepts[J].ReliabilityEngineeringandSystemSafety,2001,71(2):115130.[5]MowshowitzA.Entropyandthecomplexityofgraphs:I.anindexoftherelativecomplexityofagraph[J].BulletinofMathematicalBiophysics,1968,30(1):175204.[6]LauriJ,ScapellatoR.Topicsingraphautomorphismandreconstruction[M].Cambridge:CambridgeUniversityPress,2003.[7],.[J].,2004,24(6):13.[8],,.PPI[J].,2009,26(1):9798.MethodforMeasuringtheHeterogeneityofcomplexDirectedNetworkBasedonEntropyZHOUXuan,ZHANGFeng-ming,HUIXiao-bin,LIKe-wu,JIANGLi-feng(EngineeringCollege,AirForceEngineeringUniversity,Xian710038,China)Abstract:Accordingtotheresearchonthemeasurementofcomplexnetworkheterogeneity,theexistingmethodstookthedegreedistributionofnetworkintoaccount,buttheydidntconsiderthedifferencebetweenadjacentnodesandthedirectionofinteraction.Inviewofthis,thispaperprovidesanewmethodformeasuringtheheterogeneityofcomplexdirectednetworkbasedonentropy,considersthedegreedistributionandthedifferencebetweenadjacentnodes,gaveprominencetotheroleofnetworkssymmetryintheeliminationofheterogeneitytoquantifythestructuralheterogeneityofnetworksmorepreciselyandproposesnewideaformeasuringthecomplexityofcomplexdirectednetwork.Anillustrativeexampleprovesthatthemethodisreasonableandvalid.Keywords:Heterogeneity;DegreeDistribution;Entropy;DirectedNetwork1262011