MMD_1b_PageRank

• Graph data
• web graph
  • history
  • challenges and thumb
• flow formulation
  • idea
  • model
  • simple formulation
  • matrix formulation
    • intro
• power iteration
  • intro
  • randomWalk interpretation
  • existane and uniqueness
• teleports
  • three questions
    • spider trap
    • dead end
  • solution
  • why its useful
    • markov chains
    • provement
    • google matrix
    • examples
• PageRank in reality
  • problems
  • sparse matrix
  • algorithm

Graph data

• social networks
• media networks
• information nets
• communication nets(the Internet)
• seven bridges

web graph

这里写图片描述

history

ways to organize web

1. web directories
2. web search(find relevant doc in small and trusted set, but it becomes impossible when web is huge and full of untrusted things.)

challenges and thumb

all pages are not equally important.

这里写图片描述

flow formulation

idea

这里写图片描述

model

这里写图片描述

simple formulation

这里写图片描述

matrix formulation

intro

这里写图片描述

power iteration

intro

这里写图片描述

randomWalk interpretation

这里写图片描述

existane and uniqueness

if the graph satisfy certain conditions

这里写图片描述

but what’s the certain condition?

teleports

we wanna know if the power iteration is exist and unique and when it meets requirement?

three questions

这里写图片描述

spider trap

这里写图片描述

dead end

这里写图片描述

solution

• for spider strp: random teleports
• for dead end: always teleports

这里写图片描述

why it’s useful

markov chains

这里写图片描述

provement

这里写图片描述

google matrix

这里写图片描述

examples

这里写图片描述

PageRank in reality

problems

如果N比较大的时候，算出来的A会很大，给存储和计算带来困难。

这里写图片描述

sparse matrix

这里写图片描述

algorithm

这里写图片描述