A measure of betweenness centrality based on rando

AmeasureofbetweennesscentralitybasedonrandomwalksAuthor:M.E.J.NewmanPresentedby:AmrutaHinganeDepartmentofComputerScienceKentStateUniversityOverview•Introduction•CentralityMeasures•TypesOfBetweenness•Random-walkBetweenness–Acurrentflowanalogy–Randomwalks•ComparisonOfDifferentBetweennessMeasures•CorrelationWithOtherMeasures•ExamplesApplicationsCentralityMeasuresDegree:•Simplestcentralitymeasure•Numberofedgesincidentonavertexinanetwork•Thenumberoftiesanactorhasinsocialnetworkparlance•Ameasureinsomesenseofthepopularityofanactor.abcDegreeofb=?CentralityMeasuresContinued…Closeness:•Centralitymeasurewhichisthemeangeodesic(shortest-path)distancebetweenavertexandallotherverticesreachablefromit.•MeasureofhowlongitwilltakeinformationtospreadfromagivenvertextoothersinthenetworkBetweenness:•MeasureoftheextenttowhichavertexliesonthepathsbetweenothersBetweenness•Thebetweennessofavertexiisdefinedtobethefractionofshortestpathsbetweenpairsofverticesinanetworkthatpassthroughi.Σstgi(st)/nstbi=----------------½n(n−1)n=Totalnoofverticesinnetworkgi(st)=noofgeodesicpathsfromvertexstovertextthatpassthroughi.nst=totalnoofgeodesicpathsfromstot.Shortest-pathBetweenness•Ameasureoftheextenttowhichanactorhascontroloverinformationflowingbetweenothers.•Inanetworkinwhichflowisentirelyoratleastmostlyalonggeodesicpaths,thebetweennessofavertexmeasureshowmuchflowwillpassthroughthatparticularvertex.•BetweennesscanbecalculatedforallverticesintimeO(mn)m:edgesn:verticesExampleofShortest-pathBetweennessShortestpathbetweennessVerticesAandBwillhavehigh(shortest-path)betweennessinthisconfiguration,whilevertexCwillnotDrawbacksofShortest-pathBetweenness•Doesinformationflowonlyalonggeodesicpaths?•News,rumor,fad,message–doesitknowtheidealroute•Togetfromoneplacetoanothermorelikelyamessagewandersaroundmorerandomly,encounteringwhoitwill.•Certainlyitispossibleforinformationtoflowbetweentwoindividualsviaathirdmutualacquaintance,evenwhenthetwoindividualsinquestionarethemselveswellacquainted•Arealisticbetweennessmeasureshouldincludenon-geodesicpathsinadditiontogeodesiconesFlowbetweenness•Flowbetweennessofavertexiisdefinedastheamountofflowthroughvertexiwhenthemaximumflowistransmittedfromstot,averagedoverallsandt.•Flowbetweennesscanbethoughtofasmeasuringthebetweennessofverticesinanetworkinwhichamaximalamountofinformationiscontinuouslypumpedbetweenallsourcesandtargets.•Maximumflowfromagivenstoallreachabletargetstcanbecalculatedinworst-casetimeO(m2)andhencetheflowbetweennessforallverticescanbecalculatedintimeO(m2n)ExampleofFlowBetweennessWhilecalculatingflowbetweenness,verticesAandBwillgethighscoreswhilevertexCwillnotDrawbacksofFlowBetweenness•Doesinformation“know”theidealroute(oroneoftheidealroutes)fromeachsourcetoeachtarget,inordertorealizethemaximumflow?•Althoughtheflowbetweennessdoestakeaccountofpathsotherthantheshortestpaththisstillseemsunrealisticformanypracticalsituations•Flowbetweennesssuffersfromsomeofthesamedrawbacksasshortest-pathbetweenness,asinflowdoesnottakeanysortofidealpathfromsourcetotarget,beittheshortestpath,themaximumflowpath,oranotherkindofidealpathRandomWalkBetweenness•Random-walkbetweennessofavertexiisequaltothenumberoftimesthatarandomwalkstartingatsandendingattpassesthroughialongtheway,averagedoverallsandt•Random-walkbetweennesscanbecalculatedforallverticesinanetworkinworst-casetimeO((m+n)n2)usingmatrixmethods•ThismeasureisappropriatetoanetworkinwhichinformationwandersaboutessentiallyatrandomuntilitfindsitstargetBasicMatrixNotations43210111100010011010A0110000000011000A4321njnjnjjnjjnaaakkkK,1,12,1121...00............0...00...0...00............0...00...0AdjacencyMatricesBasicMatrixNotationsContinued…•RankofamatrixA=maximalnumberoflinearlyindependentrows/columns•AsquarematrixAnxnisinvertibleonlyifrankA=n•Productofeigenvaluesofamatrix=determinantofthematrix•Ax=λxx=non-zeroeigenvectorA=matrixλ=eigenvalue•Singularmatrix=determinantiszero=matrixisnon-invertibleCurrentFlowAnalogyCurrentflowbetweennessofavertexiistheamountofcurrentthatflowsthroughiaveragedoverallsourceandtargetpointsKirchoff’slawofcurrent:Totalcurrentflowintooroutofanyvertexiszeroi=i1+i2ixy=[V(x)–V(y)]/RxyInjectedcurrent=1unitExtractedcurrent=1unitResistance=1unitCurrentflowbetweennessByKirchoff’slawofcurrentconservation,thevoltagessatisfy:ΣjAij(Vi-Vj)=δis–δitAijisanelementofadjacencymatrixAij=δijistheKnockerδ=1ifthereisanedgebetweeniandj0otherwise1ifi=j0otherwiseCurrentflowbetweennessContinued…SinceΣjAij=kidegreeofvertexiTherefore,(D-A).V=sD=diagonalmatrixwithelementsDii=kisissourcevectorwithelementssi=+1fori=s-1fori=t0otherwiseCurrentflowbetweennessContinued…ToobtainV,matrix(D–A)cannotbeinvertedasitissingularRemovingvthrowofD–A.Vv=0asvoltageismeasuredwithrespecttocorrespondingvertexRemovingvthcolumn,Dv-Avasquarematrix(n-1)*(n-1)V=(Dv-Av)-1.SAddingbackthemissingvertexwithvaluesallequaltozeroVoltageati:Vi(st)=Tis–TitTistheresultingmatrixCurrentflowbetweennessContinued…Currentthroughi=halfofthesumoftheabsoluteval