网络科学第二讲网络与图

网络科学基础

ElementsofNetworkScience齐鲁工业大学信息学院

主讲人：张维玉

电话箱：zwy@第二讲网络与图2023/2/1主讲教师：张维玉2Canonewalkacrossthesevenbridgesandnevercrossthesamebridgetwice?

Canonewalkacrossthesevenbridgesandnevercrossthesamebridgetwice?

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

leastonepath.

components:nodes,vertices（节点）

N

interactions:links,edges （连边）

L

system: network,graph （网络，图）

(N,L)NetworkScience:GraphTheory2012网络组件networkoftenreferstorealsystemswww,socialnetworkmetabolicnetwork.Language:(Network,node,link)graph:mathematicalrepresentationofanetworkwebgraph,socialgraph(aFacebookterm)

Language:(Graph,vertex,edge)Wewilltrytomakethisdistinctionwheneveritisappropriate,butinmostcaseswewillusethetwotermsinterchangeably.（大部分场合，我们互用网络和图这两个概念）网络与图的关系PeterMaryAlbertAlbertco-workerfriendbrothersfriendProtein1Protein2Protein5Protein9Movie1Movie3Movie2Actor3Actor1Actor2Actor4N=4L=4网络是一种通用工具Thechoiceofthepropernetworkrepresentationdeterminesourabilitytousenetworktheorysuccessfully.

Insomecasesthereisaunique（独一无二）,unambiguousrepresentation.Inothercases,therepresentationisbynomeansunique.

Forexample,thewayweassignthelinksbetweenagroupofindividualswilldeterminethenatureofthequestionwecanstudy.选择一个适当的网络表达Ifyouconnectindividualsthatworkwitheachother,youwillexploretheprofessionalnetwork.NetworkScience:GraphTheory2012Ifyouconnectthosethathavearomanticandsexualrelationship,youwillbeexploringthesexualnetworks.Ifyouconnectindividualsbasedontheirfirstname(allPetersconnectedtoeachother),youwillbeexploringwhat?Itisanetwork,nevertheless.根据我们要研究的目标来构建网络是开展研究的第一步！网络不是毫无目的随意构建的！Links:undirected(symmetrical，对称关系) Graph:

Directedlinks:URLsonthewwwphonecallsmetabolicreactions（代谢反应）Undirected（无向网络）Directed有向网络ABDCLMFGHILinks:directed(arcs).Digraph=directedgraph:Undirectedlinks:coauthorshiplinksActornetworkproteininteractionsAnundirectedlinkisthesuperpositionoftwooppositedirectedlinks.AGFBCDENodedegree:thenumberoflinksconnectedtothenode.UndirectedIndirectednetworkswecandefineanin-degreeandout-degree.The(total)degreeisthesumofin-andout-degree.Source:anodewithkin=0;Sink:anodewithkout=0.DirectedAGFBCDEAB节点的度(degree)Wehaveasampleofvaluesx1,...,xNAverage

(a.k.a.mean):typicalvalue

<x>=(x1+x1+...+xN)/N=Σixi/N度的平均值能表达什么信息？度的平均值--一个统计意义上的值N–thenumberofnodesinthegraphUndirectedDirectedAFBCDEjiThemaximumnumberoflinksanetworkofNnodescanhaveis:AgraphwithLinkL=Lmax

iscalledacompletegraph,anditsaveragedegreeis<k>=N-1完全网络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

真实的网络大多都是稀疏的(sparse)ThemaximumnumberoflinksanetworkofNnodescanhaveis:METCALFE’SLAW（梅特卡夫定律）Aij=1ifthereisalinkbetweennodeiandjAij=0ifnodesiandjarenotconnectedtoeachother.网络表示形式—连接矩阵Notethatforadirectedgraph(right)thematrixisnotsymmetric.

42312314abcdefgha01001010b10100001c01010110d00101000e10010000f

00100010g

10100000h

01000000begacfhdUndirected2314Directed42313UndirectedDirected1423214Actornetwork,protein-proteininteractionsWWW,citationnetworksUnweighted（无权重）(undirected)Weighted（有权重）(undirected)31423214protein-proteininteractions,wwwCallGraph,metabolicnetworksSelf-interactionsMultigraph(undirected)31423214Proteininteractionnetwork,wwwSocialnetworks,collaborationnetworksCompleteGraph(undirected)3142Actornetwork,protein-proteininteractions真实的网络往往具备多种特征WWW>directedmultigraphwithself-interactionsProteinInteractions>undirectedunweightedwithself-interactionsCollaborationnetwork>undirectedmultigraphorweighted.Mobilephonecalls>directed,weighted.FacebookFriendshiplinks>undirected,unweighted.你的微博网络符合哪些特征？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步路径的数量。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