matrixpagerank

1/20RandomWalks,PageRank,andComputerScienceSiuOnChanDepartmentofComputerScienceandEngineeringTheChineseUniversityofHongKongJuly30,20152/20Yahooin1996:Human-editeddirectory3/20Only5directoryentriesfor"LinearAlgebra"4/20Googletoday~10,000,000LinearAlgebrapages,rankedmostlybyimportance5/20PartI:PageRankandRandomwalk6/20PageRankAlgorithmNamedafterLarryPage,GooglecofounderandcurrentCEODetermineswebpages'importanceonlybylinkstructureofthedirectedgraphofwebpages6/20PageRankAlgorithmNamedafterLarryPage,GooglecofounderandcurrentCEODetermineswebpages'importanceonlybylinkstructureofthedirectedgraphofwebpagesBasedonstationarydistributionofarandomwalk6/20PageRankAlgorithmNamedafterLarryPage,GooglecofounderandcurrentCEODetermineswebpages'importanceonlybylinkstructureofthedirectedgraphofwebpagesBasedonstationarydistributionofarandomwalkSpectralgraphtheory!
Forsimplicity,focusonundirected,regulargraphsinthistalk7/20RandomWalkStochasticprogressonagraph(undirectedfornow)7/20RandomWalkStochasticprogressonagraph(undirectedfornow)Startsfromavertex,ateachtimesteptmovestoauniformlyrandomneighbourofthecurrentvertex8/20DistributionptProbabilitytransitionmatrixKRowvectorpt:distributionattimetpt+1=ptKpt=p0KtDoesptconvergeastincreases9/20StationarydistributionIfptconverges,thelimitingdistributionp∞mustbestationaryp∞K=p∞uniformdistributionalwaysastationarydistribution(foranundirected,regulargraph)10/20Limitingdistribution:unique10/20Limitingdistribution:uniqueNotuniqueondisconnectedgraphs(Somevertexnotreachablefromsomeothervertexviaintermediatevertices)10/20Limitingdistribution:uniqueNotuniqueondisconnectedgraphs(Somevertexnotreachablefromsomeothervertexviaintermediatevertices)Notuniqueonbipartitegraphs(CanpartitionallverticesintotwosubsetsV1,V2sothatalledgesonlygobetweenV1andV2)11/20UniquelimitingdistributionTheorem(Uniqueness)Anundirected,regular,connected,non-bipartitegraphhasauniquestationarydistributionp.
Further,givenanyinitialdistributionp0,limt→∞pt=p.
12/20Eigenvaluesandeigenvectorsλ∈Risaneigenvalueandq∈RnisaneigenvectorofKifqK=λqFact:TransitionmatrixKofanundirectedgraphisrealsymmetricLemma(SpectralTheorem)Anyn*nrealsymmetricmatrixKhasneigenvalue-eigenvectorpairsq(1)K=λ1q(1).
.
.
q(n)K=λnq(n)suchthat{q(1)q(n)}isanorthogonalbasis13/20ProofTheorem(Uniqueness)Anundirected,regular,connected,non-bipartitegraphhasauniquestationarydistributionp.
Further,givenanyinitialdistributionp0,limt→∞pt=p.
Proof.
Byspectraltheorem,{q(1)q(n)}formsabasis.
Expandp0=ni=1αiq(i).
pt=p0Kt=ni=1αiq(i)Kt.
14/20Proof(continued)pt=p0Kt=ni=1αiq(i)KtSinceq(i)Kt=λiq(i)Kt1=λi2q(i)Kt2λitq(i),thetopequationbecomespt=ni=1αiλitq(i).
15/20GraphspectrumAssumeeigenvaluesaresortedλ1λ2.
.
.
λn15/20GraphspectrumAssumeeigenvaluesaresortedλ1λ2.
.
.
λnOnecanshow1λ1andλn1Recall:λ1=1,uniformdistributionasaneigenvector15/20GraphspectrumAssumeeigenvaluesaresortedλ1λ2.
.
.
λnOnecanshow1λ1andλn1Recall:λ1=1,uniformdistributionasaneigenvectorPropositionλ2=1ifandonlyifdisconnectedgraph15/20GraphspectrumAssumeeigenvaluesaresortedλ1λ2.
.
.
λnOnecanshow1λ1andλn1Recall:λ1=1,uniformdistributionasaneigenvectorPropositionλ2=1ifandonlyifdisconnectedgraphPropositionλn=1ifandonlyifbipartitegraph16/20Proof(finalbits)pt=ni=1αiλitq(i).
Forregular,connected,bipartitegraph,|λ2|PageRankTheorem(Uniqueness)Anundirected,regular,connected,non-bipartitegraphhasauniquestationarydistributionp.
Further,givenanyinitialdistributionp0,limt→∞pt=p.
Asimilartheorem(suitablymodified)holdsfordirected,non-regulargraphs:Perron–FrobeniustheoremLimitingdistributionpnotnecessarilyuniformPageRankiterativelycomputesthedistributionpt=p0Ktfromanarbitraryinitialdistributionp018/20PartII:ConnectionstoTheoreticalComputerScience19/20SpectralgraphtheoryandexpandersSpectralgraphtheory:studyofgrapheigenvaluesλ1,…,λnandgraphproperties19/20SpectralgraphtheoryandexpandersSpectralgraphtheory:studyofgrapheigenvaluesλ1,…,λnandgraphpropertiesGraphswithλ2muchsmallerthanλ1=1arecalledexpandersValuabletocomputerscience19/20SpectralgraphtheoryandexpandersSpectralgraphtheory:studyofgrapheigenvaluesλ1,…,λnandgraphpropertiesGraphswithλ2muchsmallerthanλ1=1arecalledexpandersValuabletocomputerscienceFord-regulargraphs,howsmallcanλ2beRecentbreakthrough:Yaletheoreticalcomputerscientists(Marcus,Spielman,andSrivastava)constructedbipartitegraphsforanydegreedwithmax{|λ2|,|λn1|}2√d1/d.
Smallestpossible(Alon–Boppana)19/20SpectralgraphtheoryandexpandersSpectralgraphtheory:studyofgrapheigenvaluesλ1,…,λnandgraphpropertiesGraphswithλ2muchsmallerthanλ1=1arecalledexpandersValuabletocomputerscienceFord-regulargraphs,howsmallcanλ2beRecentbreakthrough:Yaletheoreticalcomputerscientists(Marcus,Spielman,andSrivastava)constructedbipartitegraphsforanydegreedwithmax{|λ2|,|λn1|}2√d1/d.
Smallestpossible(Alon–Boppana)Theirnoveltechniquesalsoresolve54-year-oldKadison–SingerprobleminMathematicsandengineering20/20MatrixmultiplicationandcomputationalcomplexityGiventwomatricesAandBofsizen,computeABRecall(AB)ij=kAikBkjStraightforwardalgorithmrequiresroughlyn3elementaryoperations20/20MatrixmultiplicationandcomputationalcomplexityGiventwomatricesAandBofsizen,computeABRecall(AB)ij=kAikBkjStraightforwardalgorithmrequiresroughlyn3elementaryoperationsStrassenalgorithm:roughlynlog27≈n2.
807elementaryoperationsLeGallalgorithm(currentbest):roughlyn2.
373elementaryoperations20/20MatrixmultiplicationandcomputationalcomplexityGiventwomatricesAandBofsizen,computeABRecall(AB)ij=kAikBkjStraightforwardalgorithmrequiresroughlyn3elementaryoperationsStrassenalgorithm:roughlynlog27≈n2.
807elementaryoperationsLeGallalgorithm(currentbest):roughlyn2.
373elementaryoperationsIsn2possibleIfso,potentiallyveryusefulIfnot,whynot