搜索
53Vol.5No.320089COMPLEXSYSTEMSANDCOMPLEXITYSCIENCESep.2008:1672-3813(2008)03-0019-24,,,(,100875):,,,:;;:N94:ACommunityStructureinComplexNetworksLIXiao2jia,ZHANGPeng,DIZeng2ru,FANYing(DepartmentofSystemsScience,SchoolofManagement,BeijingNormalUniversity,Beijing100875,China)Abstract:Communitystructureexistswidelyinmostofactualsystemsandnetworks.Investigationoncommunitystructureisanimportantwaytounderstandboththestructureandfunctionofnetworks.Inthispaper,wereviewmainresultsinthestudyofcommunitystructureincomplexnetworks.Firstly,wefocusontheunweightedandundirectednetworks.Definitionsofcommunitystructureandalgorithmsthatdetectcommunitiesareintroduced.Meanwhilesomemeasurementsondetectingalgorithmsandclassicalnet2worksarelisted.Theemphasisofourworkisevaluatingalgorithmsusingmeasurementsandtheresultsforclassicalnetworks.Secondlyweextendstudytoweightedandundirectednetworks.Finally,thecom2parisonofsomealgorithmsandabriefintroductiontotherelationshipbetweencommunitystructureandnetworkfunctionaregiven,andprospectofstudyoncommunitystructureinthefutureisoutlined.Keywords:complexnetworks;communitystructure;clustering:2008-01-23:(70771011):(1984-),,,,1,,,[1-6],,,,,20089(),:Internet[7-8][9][10-11],,,,,,,,,[12],1:,;[13],;,[14-16];,;,,:,[17];,,1[22]4:1);2);3);4):2,3,,,4,5,22.1,:,[12,22],,[18-19]:VVV[18-19]:VVVV,LS[24],LS,,[21]33,,,n-:2-,3-,n,n-[21],,0253,:,,,[24],2.2Q,GirvanNewman[25],,:,,Q,cii,6ijAij(ci,cj)6ijAij=12m6ijAij(ci,cj),Aij,i,jAij=1,0;(ci,cj),ci=cj1,0;m=126ijAij,,i,jkikj2m,kiiQ[26]Q=12m6ijAij-kikj2m(ci,cj)Q[25]n,nneeijijTre=6ieii()ai=6ieij,ieijaieij=aiaj,Q2[25]Q=6i(eii-a2i)=Tre-e2,e2e2,e2,Q[23]Q=6nv=1lvL-dv2L2,lvV,dvV,L,Q,Q1,,Q013017,[25],Q,,(),(2)1220089Q,,Q,Q[23],,lvdvVlvL-dv2L20,Q,2L,,Q,33.1,4:,:1);2),,;3),,;4);5),,343[22],,:1);2);3),,;4),4GN,,,Potts342253,:3.2,,,,,,,,,,3.3:,,,,,,128[12],1284,4,32,,pin,,poutpinpout,16Zin,Zout,Zin+Zout=16Zout,,;Zout,,,Zout,,,Zout,,100%,Zout,Zout,Zout,,,,;,;,,44[25][12]:2070,WayneZachary,34,;78,,,4,(1),(33):,3:1)[26],arxiv.org,,;2)[12],19992000271,3220089,,;3)[27],()PhysicaAISI(),2000[12],,115,,616;LindaWolfe3,[28],1616,,69,,,,,3.4,;,33.4.1[12],,,,,128,3,,3,50%,,,3.4.2DanonL[30-31][29],3.4.1:N,,NNijijA,BI(A,B)=-26cAi=16cBj=1NijlogNijNNi.N.j6cAi=1Ni.logNi.N+6cBj=1N.jlogN.jN,cA,cB,Ni.Niji,N.jNijj,I(A,B)1;I(A,B)0,I(A,B)3.3,01858,3.4.3D[32],D,,A,B,AB,(AB)(AB)(ABAB),A,B(s)(d)4253,:s=ABABd=(AB)(AB)AB,,:1):,,,2),3),:D=6dXYk,XY,kD[0,1],1,0,,01625,4,,:3,,4,,,Q,4.1,,4.1.12070[33-34],90,[35],[36]N,AK-1,N=K-1AKkii=6Sj=1aij,S,1,(1,1,1)5,m,Nm-11,m-1,:,,6,,,,,,,5220089:,1,;,,,,,,,[36]i,jrij=xixj-xixj[(x2i-xi2)(x2j-xj2)],xii,,0,0,,rij,,,4.1.2[37-38],:,,,,1971LorrainWhite,,,Burt,i,jDij=6Sk=1,ki,j(aik-ajk)2,aik,iki,j,,Dij0,,,,6253,:3:1),;2),;3),,Q4.1.3GNGirvanNewman,GN[12,22,25],,,,,GirvanNewman,,;:1);2),(,);3);4)2)3),7GN[25],,,:,,,,,,GN,Qnm,,O(m),n,O(m),,O(nm2);,O(n3)GNGN,9Zout6,90%;Zout,,Zout8,30%GN,GN,3Q7GN8a,7220089:13,Q=017201028b,,;,,,a,;,b8[25]4.1.4GN,Radicchi[18],i,jC(3)i,j=z(3)i,jmin[(ki-1),(kj-1)],z(3)i,j,min[(ki-1),(kj-1)],;,z(3)i,j=0,ki,kj,C(3)i,j0,,:C(3)i,j=z(3)i,j+1min[(ki-1),(kj-1)],,C(g)i,j=z(g)i,j+1s(g)i,j,gg,z(g)i,jg,s(g)i,jg:1)();2),;3),O(m2),GN,8253,::,4.1.5Latora,Marchion[39-40],[41]i,jijdijE[G]:E[G]=6ijGijn(n-1)=1n(n-1)6ijG1dij,G,ni,j,dij=+,0kk:Ck=EE=E[G]-E[Gk]E[G],k=1,,m,m,GkGkm-1Fortunato[42],,:;;;;Q,9,GN,,,:,,10k,,,11,O(n4),4.24.2.1PottsJorgReichardtStefanBornholdtPotts[43-44],,,,,,4:1);2);3)9220089;4)4H({})=-6ijaijAij(i,j)internallinks+6ijbij(1-Aij)(i,j)internalnonlinks+6ijcijAij[1-(i,j)]externallinks-6ijdij(1-Aij)[1-(i,j)]externalnonlinks11[42],i,j;Aij,i,jAij=1,0;i,j,i,j;,i=ji,j,(i,j)=1,0;aij,bij,cij,dij,,,:i,j(i,j)=1,Aij=1,aij,,,aij=cij,bij=dij,42,aij,bijpij,i,jaij,bijaij=1-pij,bij=pij,aij,bijpij,:i,jpij,aij,i,j,,:H({})=-6ij(Aij-pij)(i,j),p,i,jpijp,,,,i,jpij=kikj2M,ki,kji,j,M,q,:1),q2)3)H=Hnew-Hold0,;H=Hnew-Hold0,(0,1),exp(-H),,=1T,4)2),5),0,0353,:,[44],JorgReichardtStefanBornholdt,2p=1,Q:Q=-1MH({})Q4.2.2,[45-47],,,,ijPij=Aijd(i),Aij,d(i)iPtPt,Ptijitjj,i,,ij,kPtikµPtjkrij,rij=6Sk=1(Ptik-Ptjk)2d(k)t,rtijt,tPtijj,i,Q4.2.3F.WuB.A.Huberman,[48]:,i,j,i1,j0,,,,,,0in,,i6nk=1Ik=6nk=1Vk-ViR=0,Ikki,Vkk,RiVi=1n6nk=1Vk,F.WuB.A.HubermanN,i,j,Vi=1,Vj=0,0;i,j,;,,,,i,j1,0,10,i,j,,,,,,,,,,1320089,F.WuB.A.Huberman,1134,21617,31226,4323312,1,2,3,;4,,12[48]4.3Q4.3.1Newman[49]Q,Newman:1)11,1n,n2),Q:Q=eij+eji-2aiaj=2(eij-aiaj)Q(),,QQ,m,O(m)e(eQ2),,eijO(n)O(m=n)3)2),,n-1,O((m+n)n),O(n2),Q,eij01,Newman,2.3128Zout,,1313Zout,Zout,Zout=6,90%Zout=8,,Newman,Q01381,14,17,10,,5,GNQ01713,6004,77%,2353,:4,,,,13GN[49]14[49]4.3.2ClausetNewman[72],Q,O(nlog2n),ClausetQ,QQ,,3:1)Q,;2)H,Q,;3)a:1),i,jeij=1/2m(m),0;ai=ki/2mQ:Qij=1/2m-kikj/(2m)20i,jQ,H2)HQij,i,j,jQHa,:(1)Q,ij,ji:ki,j,Qjk=Qik+Qjk;kij,Qjk=Qik-2ajak;kji,Qjk=Qjk-2aiak(2)Q,H(3)a:aj=aj+aiai=03)2),Q,Q,Q,Q,Qij,Q,Newman,,40200Amazon.com3320089,4.3.3[50],NPC[51-52],,,DuchArenas[53],Q,,iQ,qi=r(i)-kiar(i),r(i)rir,kii,ar(i)irm,QqiQ=(1/2m)6iqiQ[-1,1],qi,Q,,iQ:i=qiki=r(i)ki-ar(i)iiQ,iiQQ,iir,ir,:1),,15a,15b,,2)i,(),Q