網(wǎng)絡(luò)科學(xué)第二講網(wǎng)絡(luò)與圖

網(wǎng)絡(luò)科學(xué)基礎(chǔ)

ElementsofNetworkScience齊魯工業(yè)大學(xué)信息學(xué)院

主講人：張維玉

電話箱：zwy@第二講網(wǎng)絡(luò)與圖2023/2/1主講教師：張維玉2Canonewalkacrossthesevenbridgesandnevercrossthesamebridgetwice?

Canonewalkacrossthesevenbridgesandnevercrossthesamebridgetwice?

1735:LeonhardEuler’stheorem:Ifagraphhasnodesofodddegree,thereisnopath.Ifagraphisconnectedandhasnoodddegreenodes,ithasat

leastonepath.

components:nodes,vertices（節(jié)點(diǎn)）

N

interactions:links,edges （連邊）

L

system: network,graph （網(wǎng)絡(luò)，圖）

(N,L)NetworkScience:GraphTheory2012網(wǎng)絡(luò)組件networkoftenreferstorealsystemswww,socialnetworkmetabolicnetwork.Language:(Network,node,link)graph:mathematicalrepresentationofanetworkwebgraph,socialgraph(aFacebookterm)

Language:(Graph,vertex,edge)Wewilltrytomakethisdistinctionwheneveritisappropriate,butinmostcaseswewillusethetwotermsinterchangeably.（大部分場(chǎng)合，我們互用網(wǎng)絡(luò)和圖這兩個(gè)概念）網(wǎng)絡(luò)與圖的關(guān)系PeterMaryAlbertAlbertco-workerfriendbrothersfriendProtein1Protein2Protein5Protein9Movie1Movie3Movie2Actor3Actor1Actor2Actor4N=4L=4網(wǎng)絡(luò)是一種通用工具Thechoiceofthepropernetworkrepresentationdeterminesourabilitytousenetworktheorysuccessfully.

Insomecasesthereisaunique（獨(dú)一無(wú)二）,unambiguousrepresentation.Inothercases,therepresentationisbynomeansunique.

Forexample,thewayweassignthelinksbetweenagroupofindividualswilldeterminethenatureofthequestionwecanstudy.選擇一個(gè)適當(dāng)?shù)木W(wǎng)絡(luò)表達(dá)Ifyouconnectindividualsthatworkwitheachother,youwillexploretheprofessionalnetwork.NetworkScience:GraphTheory2012Ifyouconnectthosethathavearomanticandsexualrelationship,youwillbeexploringthesexualnetworks.Ifyouconnectindividualsbasedontheirfirstname(allPetersconnectedtoeachother),youwillbeexploringwhat?Itisanetwork,nevertheless.根據(jù)我們要研究的目標(biāo)來(lái)構(gòu)建網(wǎng)絡(luò)是開展研究的第一步！網(wǎng)絡(luò)不是毫無(wú)目的隨意構(gòu)建的！Links:undirected(symmetrical，對(duì)稱關(guān)系) Graph:

Directedlinks:URLsonthewwwphonecallsmetabolicreactions（代謝反應(yīng)）Undirected（無(wú)向網(wǎng)絡(luò)）Directed有向網(wǎng)絡(luò)ABDCLMFGHILinks:directed(arcs).Digraph=directedgraph:Undirectedlinks:coauthorshiplinksActornetworkproteininteractionsAnundirectedlinkisthesuperpositionoftwooppositedirectedlinks.AGFBCDENodedegree:thenumberoflinksconnectedtothenode.UndirectedIndirectednetworkswecandefineanin-degreeandout-degree.The(total)degreeisthesumofin-andout-degree.Source:anodewithkin=0;Sink:anodewithkout=0.DirectedAGFBCDEAB節(jié)點(diǎn)的度(degree)Wehaveasampleofvaluesx1,...,xNAverage

(a.k.a.mean):typicalvalue

<x>=(x1+x1+...+xN)/N=Σixi/N度的平均值能表達(dá)什么信息？度的平均值--一個(gè)統(tǒng)計(jì)意義上的值N–thenumberofnodesinthegraphUndirectedDirectedAFBCDEjiThemaximumnumberoflinksanetworkofNnodescanhaveis:AgraphwithLinkL=Lmax

iscalledacompletegraph,anditsaveragedegreeis<k>=N-1完全網(wǎng)絡(luò)Mostnetworksobservedinrealsystemsaresparse（稀疏）:L<<Lmax

or

<k><<N-1. WWW(NDSample): N=325,729; L=1.4106 Lmax=1012 <k>=4.51 Protein(S.Cerevisiae): N=1,870; L=4,470 Lmax=107 <k>=2.39 Coauthorship(Math): N=70,975; L=2105 Lmax=31010 <k>=3.9 MovieActors: N=212,250; L=6106 Lmax=1.81013 <k>=28.78

真實(shí)的網(wǎng)絡(luò)大多都是稀疏的(sparse)ThemaximumnumberoflinksanetworkofNnodescanhaveis:METCALFE’SLAW（梅特卡夫定律）Aij=1ifthereisalinkbetweennodeiandjAij=0ifnodesiandjarenotconnectedtoeachother.網(wǎng)絡(luò)表示形式—連接矩陣Notethatforadirectedgraph(right)thematrixisnotsymmetric.

42312314abcdefgha01001010b10100001c01010110d00101000e10010000f

00100010g

10100000h

01000000begacfhdUndirected2314Directed42313UndirectedDirected1423214Actornetwork,protein-proteininteractionsWWW,citationnetworksUnweighted（無(wú)權(quán)重）(undirected)Weighted（有權(quán)重）(undirected)31423214protein-proteininteractions,wwwCallGraph,metabolicnetworksSelf-interactionsMultigraph(undirected)31423214Proteininteractionnetwork,wwwSocialnetworks,collaborationnetworksCompleteGraph(undirected)3142Actornetwork,protein-proteininteractions真實(shí)的網(wǎng)絡(luò)往往具備多種特征WWW>directedmultigraphwithself-interactionsProteinInteractions>undirectedunweightedwithself-interactionsCollaborationnetwork>undirectedmultigraphorweighted.Mobilephonecalls>directed,weighted.FacebookFriendshiplinks>undirected,unweighted.你的微博網(wǎng)絡(luò)符合哪些特征？bipartitegraph

(orbigraph)isagraphwhosenodescanbedividedintotwodisjointsets

UandVsuchthateverylinkconnectsanodeinUtooneinV;thatis,UandVareindependentsets.Examples:

HollywoodactornetworkCollaborationnetworksDiseasenetwork(diseasome)二部圖GenenetworkGENOMEPHENOMEDISEASOMEDiseasenetworkGoh,Cusick,Valle,Childs,Vidal&Barabási,PNAS(2007)GENENETWORK–DISEASENETWORKHUMANDISEASENETWORKNetworkScience:GraphTheory2012ApathisasequenceofnodesinwhicheachnodeisadjacenttothenextonePi0,inoflengthnbetweennodesi0andinisanorderedcollectionofn+1nodesandnlinks

Apathcanintersectitselfandpassthroughthesamelinkrepeatedly.Eachtimealinkiscrossed,itiscountedseparatelyAlegitimate（合法的）pathonthegraphontheright:ABCBCADEEBA

Inadirectednetwork,thepathcanfollowonlythedirectionofanarrow.PATHS（路徑）ABCDEThedistance(shortestpath,geodesicpath)betweentwonodesisdefinedasthenumberofedgesalongtheshortestpathconnectingthem.*Ifthetwonodesaredisconnected,thedistanceisinfinity.Indirectedgraphseachpathneedstofollowthedirectionofthearrows.ThusinadigraphthedistancefromnodeAtoB(onanABpath)isgenerallydifferentfromthedistancefromnodeBtoA(onaBCApath).DISTANCEINAGRAPHShortestPath,GeodesicPathDCABDCABNij,numberofpathsbetweenanytwonodesiandj:

Lengthn=1:

Ifthereisalinkbetweeniandj,thenAij=1andAij=0otherwise.Lengthn=2:

Ifthereisapathoflengthtwobetweeniandj,thenAikAkj=1,andAikAkj=0otherwise.Thenumberofpathsoflength2:Lengthn:Ingeneral,ifthereisapathoflengthnbetweeniandj,thenAik…Alj=1andAik…Alj=0otherwise.Thenumberofpathsoflengthnbetweeniandjis*

*holdsforbothdirectedandundirectednetworks.使用連接矩陣可以方便求出n步路徑的數(shù)量。NUMBEROFPATHSBETWEENTWONODESAdjacencyMatrixDistancebetweennode

1

andnode4:Startat

1.FINDINGDISTANCES:BREADTHFIRSTSEATCH1111222223333333344444444111111111222223333333344444444Distancebetweennode

1

andnode4:Startat

1.Findthenodesadjacentto

1.Markthemasatdistance1.Puttheminaqueue.11111111222223333333344444444Distancebetweennode

1

andnode4:Startat

1.Findthenodesadjacentto

1.Markthemasatdistance1.Puttheminaqueue.Takethefirstnodeoutofthequeue.Findtheunmarkednodesadjacenttoitinthegraph.Markthemwiththelabelof2.Puttheminthequeue.111122222111Distancebetweennode

1

andnode4:Repeatuntilyoufindnode4ortherearenomorenodesinthequeue.Thedistancebetween

1

and

4

isthelabelof

4

or,if

4

doesnothavealabel,infinity.1111222223333333344444444Diameter:

dmax

themaximumdistancebetweenanypairofnodesinthegraph.

Averagepathlength/distance,<d>,foraconnectedgraph:wheredij

isthedistancefromnodeitonodej

Inanundirectedgraph

dij=dji,so

weonlyneedtocountthemonce:NETWORKDIAMETERANDAVERAGEDISTANCECanonewalkacrossthesevenbridgesandnevercrossthesamebridgetwice?

/answer/graphs.htmEulerPATHorCIRCUIT:returntothestartingpointbytravelingeachlinkofthegraphonceandonlyonce.Everyvertexofthisgraphhasanevendegree,thereforethisisanEuleriangraph.FollowingtheedgesinalphabeticalordergivesanEuleriancircuit/cycle./wiki/Euler_circuitEULERIANGRAPH:ithasanEulerianpathIfadigraphisstronglyconnectedandthein-degreeofeachnodeisequaltoitsout-degree,thenthereisanEulercircuitOtherwisethereisnoEulercircuit.inacircuitweneedtoentereachnodeasmanytimesasweleaveit.ABCDEFGEULERCIRCUITSINDIRECTEDGRAPHSPATHOLOGY:summary25431Path25431ShortestPathAsequenceofnodessuchthateachnodeisconnectedtothenextnodealongthepathbyalink.Thepathwiththeshortestlengthbetweentwonodes(distance).PATHOLOGY:summary25431Diameter25431AveragePathLengthThelongestshortestpathinagraphTheaverageoftheshortestpathsforallpairsofnodes.25431Cycle25431Self-avoidingPathApathwiththesamestartandendnode.Apaththatdoesnotintersectitself.2543125431EulerianPathHamiltonianPathApaththatvisitseachnodeexactlyonce.Apaththattraverseseachlinkexactlyonce.Connected(undirected)graph:anytwoverticescanbejoinedbyapath.Adisconnectedgraphismadeupbytwoormoreconnectedcomponents.Bridge:ifweerase（去除）

it,thegraphbecomesdisconnected.LargestComponent:GiantComponent最大連通子圖Therest:IsolatesCONNECTIVITYOFUNDIRECTEDGRAPHSDCABFFGDCABFFGTheadjacencymatrixofanetworkwithseveralcomponentscanbewritteninablock-diagonalform,sothatnonzeroelementsareconfinedtosquares,withallotherelementsbeingzero:FigureafterNewman,2010CONNECTIVITYOFUNDIRECTEDGRAPHSAdjacencyMatrixNetworkScience:GraphTheory2012Stronglyconnecteddirectedgraph:hasapathfromeachnodetoeveryothernodeandviceversa(e.g.ABpathandBApath).Weaklyconnecteddirectedgraph:itisconnectedifwedisregardtheedgedirections.Stronglyconnectedcomponentscanbeidentified,butnoteverynodeispartofanontrivialstronglyconnectedcomponent.In-component:nodesthatcanreachthescc,Out-component:nodesthatcanbereachedfromthescc.DCABFGEECABGFDDegreedistribution pkTHREECENTRALQUANTITIESINNETWORKSCIENCEAveragepathlength <d>Clusteringcoefficient CWehaveasampleofvaluesx1,...,xNDistributionofx(a.k.a.PDF):probabilitythatarandomlychosenvalueisx

P(x)=(#valuesx)/N

ΣiP(xi)=1always!STATISTICSREMINDERHistograms>>>（直方圖）NetworkScience:GraphTheory2012Degreedistribution

P(k):probabilitythat

arandomlychosenvertexhasdegreekNk=#nodeswithdegreekP(k)=Nk/N?plotkP(k)123DEGREEDISTRIBUTIONdiscreterepresentation:pkist