Web as as Graph

Structure of the web

• 인터넷 웹을 그래프로 생각해보자
  • nodes = web pages
  • edges = hyperlinks
  • 웹 페이지 내부에서 외부 웹 페이지로 링크를 달면 edge가 생긴다고 볼 수 있다
    

• Web is a Directed Graph
  • web grpah를 보면 directed graph인 것을 알 수 있다
  • 이렇게 연결된 링크를 BFS로 크롤링을 하면 Google의 웹페이지를 몽땅 훑어볼 수 있다
    

What does the web look like?

• 인터넷 웹을 그래프로 만들었으면 어떻게 생겼을까?
• Web as a directed graph [Broder et al, 2000]
  • In(v): node v가 directed edge를 따라서 도달할 수 있는 다른 node의 set
  • Out(v): directed edge를 따라서 node v에 도달할 수 있는 다른 node의 set
    

• Two types of directed graphs

  • Strongly connected: 어느 node에서든 다른 node에 도달할 수 있음
    In(A) = Out(A) = {A, B, C, D, E}
    

  • Directed Acyclic Graph(DAG): cycle이 없음. 노드 v에서 u에 도달할 수 있다고해도 u에서 v로 갈 수 없을 수도 있음
    

  • 모든 directeed graph(e.g. web)은 이 2가지 타입에 속한다!

Strongly Connected Component(SCC)

• SCC 내에서 어느 noed에서 출발하든 다른 node에 도달할 수 있음(strongly connected)

• 현재 SCC를 포함한 또 다른 SCC는 존재할 수 없음 → 모든 node는 한 SCC에만 속한다
  

• FACT: 모든 directed graph는 SCC의 DAG으로 표현할 수 있다

  • SCC는 전체 그래프의 partition이다. partition이라 함은 중복이 없다는 뜻
  • 전체 그래프 G를 참고하여 G의 SCC를 G'로 만들 수 있다. 이 때 edge는 G와 G' 모두 동일하게 매핑할 수 있고 G'는 DAG라고 볼 수 있다.

Graph structure of the web

• Computational issue: 현재 node가 어느 SCC에 포함되어있는지 어떻게 알 수 있을까?
• Observation: node v를 포함하는 SCC = Out(v)∩In(v) = Out(v, G)∩Out(v, G')
  

• Directed version of the web graph
  • 웹을 graph로 정의하고 일부 노드에서 시작해서 BFS어디까지 탐색할 수 있을까?
  • 결과를 살펴보면 출발 node 노드 비중이 어느 시점을 기준으로 대부분 탐색할 수 있거나 조금 밖에 탐색할 수 없는 경우로 나타났다
    
• random node v에 대하여
  • Out(v): 1억(전체 node의 50%)
  • In(v): 1억(전체 node의 50%)
  • 가장 큰 SCC: 5천 6백만(전체 node의 28%)
  • 이러한 인사이트를 바탕으로 Bowtie structure를 그릴 수 있다
    

PageRank

• How to organize the web
• made by Google research

Ranking nodes on the graph

• 모든 웹 페이지 각각의 중요성은 저마다 다를 것이다
  • 신윤종의 깃헙 vs HuggingFace 깃헙
• 그래서, web graph를 활용하여 rank를 매겨보자
• Link analysis approaches
  * PageRank
  • Personalized PageRank
  • Random Walk with Restarts

Link as Votes

• IDEA: link(edge)는 민주주의적으로 투표로 따집시다
• link가 많은 page는 중요도가 높을 것이다!
• In-link를 중요도의 지표로 따져보자
  • 신윤종의 깃헙(팔로워 11명) vs HuggingFace 깃헙(Transformers만 해도 star 42만개)
• 모든 in-link가 중요할까?
  • 중요한 페이지에서 보낸 link가 다른 link보다 더 중요할 것이다
• Recursive question!

PageRank: The "Flow" Model

• 중요한 페이지에서 보낸 "투표"가 더 가치 있을 것이다
  • 각 link는 source page의 중요성 비율이다
  • 만약 page i의 중요도 $r_i$가 $d_i$ out link를 가지고 있을 때, 각 link는 $\frac{r_i}{d_i}$만큼의 vote 가중치를 가진다
  • page j의 중요도 $r_j$는 j의 in-link vote의 합이다
    $r_j = \displaystyle\sum_{i→j}\frac{r_i}{d_i}$
    

Matrix Formulation

• Stochastic adjacency matrix M
  • page j는 out link {d_j}를 가진다고 하자
  • 만약 j에서 i로 링크가 연결된다면 ${M_{ij}} = \frac{1}{d_j}$
    • $M$의 column 하나의 sum은 1이다
      
• Rank vector r
  • $r_i$는 page i의 중요도를 의미한다
  • $\sum_{i}{r_i} = 1$
• flow equation
  ${r} = {M}\cdot{r}$
  

Random walk interpretation

• random web surfer
  • 특정 time t에 page i를 서핑하고 있다고 해보자
  • 다음 t+1에 uniformly random하게 결정된 out-link를 따라 page j로 이동한다
  • 이 과정을 무한히 반복한다
    
• $p(t)$: 전체 페이지 개수만큼의 벡터로, i째 원소는 time t에서 i에 도달할 확률을 의미한다
• time t+1에 어디에 있을까?
  • 균등확률로 랜덤하게 움직여보자
    $p(t+1) = {M}\cdot{p(t)} = p(t)$
    p(t)는 aP = a를 만족하는 stationary distribution 상태이다
    
• 앞서 배운 rank vector는 ${r} = {M}\cdot{r}$인데?
  • 따라서 r은 random walk에서 stationary distribution 상태이다

Eigenvector formulation

• ${r} = {M}\cdot{r}$ 에 따라 rank vector r은 stochastic web matrix M의 eigenvector임을 확인하였다

  • 임의의 node u에서 출발해서 random walk를 진행한다고 해보자 수식은
    $r = \lim\limits_{i \to \infty}M(M(...M(M u)))$가 된다.

  • 좀더 풀어서 써보면 $r = Mu = M(M u) = M(M(M U) = M(M(...M(M u)))$

  • 그럼 우리의 pagerank를 쉽게 뽑을 수 있을 거 같다

Power iteration

• Power iteration; simple iterative scheme
  • 초기화: $r^{(0)} = [1/N, ..., 1/N]^T$ where N= # of nodes
  • 반복: $r^{(t+1)} = {M}\cdot{r^{(t)}}$
  • 기저: $|r^{(t+1)} - r^{(t)}|_1 < ε|$ (L1 norm)

PageRank: how to solve?

• 모든 노드마다 page rank를 초기화한다
• power iteartion으로 수렴할 때까지 반복한다
  

3 Questions

• 그래서 실제 그래프에서는 수렴하긴 하나?
• 수렴하면 우리가 원하는 모양으로 수렴하나?
• 결과는 합리적인가?

→그러니까 일반적인 상황에서 써먹을 수 있냐구

Problems

• Problem 1) 어떤 페이지는 막다른길이다
  • out-link가 없다
  • importance의 leakage를 유발한다
  • pagerank의 수렴에는 문제가 되지 않지만 pagerank score가 맘에 들지 않을 것이다
    
• Problem 2) Spider traps
  • 모든 out-link가 group에 속해있을 때 모든 importance는 해당 group이 모두 흡수해버린다
  • pagerank 수렴에 문제가 생긴다
    

Solutions

• Spider traps의 해결책: 각 time마다 random sufer는 2가지 선택지가 생긴다
  • 확률 β는 link를 그대로 따라갈 확률이다
  • 확률 1-β는 연결되어있지 않는 랜덤한 page로 점프할 확률이다
  • 일반적으로 β는 0.8~0.9로 설정한다
• Dead ends 해결책:
  • Teleports: 막다른 길에 다다른 node에게 다른 node로 연결될 확률은 배분한다
    * dead ends node m이 다른 node로 갈 확률의 전체 합은 1이다
    

Google matrix

• Spider traps를 고려한 Pagerak 수식
  ${r_{j}} = \displaystyle\sum_{i→j}β\frac{r_i}{d_i} + (1-β)\frac{1}{N}$
  • 이 수식은 $M$에 균등확률을 배정하는 전처리를 진행하여 dead ends 문제를 피할 수 있다.
• Google Matrix A
  ${A} = β M + (1-β)[\frac{1}{N}]_{N×N}$
  • 여전히 $r = {A}\cdot{r}$의 재귀적인 문제가 있지만 power iteration을 사용해준다
    

How do we actually compute PageRank?

Computing PageRank

• N = 10억 page
  • 각 entry마다 4byte를 쓴다고하자
  • pagerank r이 old, new 2종류가 합해서 8GB가 필요하다
• Google matrix A는 N*N크기이다
  • 개수만 해도 ${10}^{18}이다

Sparse Matrix formulation

• 수식을 재정의해보면 ${A} = β M + (1-β)[\frac{1}{N}]_{N}$
• M은 sparse matrix로 dead ends가 없다는 가정하에 10개의 링크가 각 노드마다 달려있다고하면 10N entries가 있다고 볼 수 있다
• 매 반복마다 pagerank 공식에 (1-β)/N의 상수를 각 $r^{new}$에 더하면 된다
• 다만 dead-ends가 우려되는 상황이라면 normalize해주자

Complete algorithm

• Input: Graph G and parameter β
• Output: Pagerank vector $r^{new}$
  • Set $r^{old}_j = \frac{1}{N}$
  • 수렴할 때까지 반복: $\displaystyle\sum_{j}|r^{new}_j - r^{old}_k| < ε$
    • $r'^{new}_j = \displaystyle\sum_{i→j}βr'^{new}_i / d_i$
    • in-link가 없는 경우에는 0
  • leaked pagerank 정보를 더해준다
    • $r^{new}_j = r'^{new}_j + (1-S / N)$

Node Proximity Measurement

• Bipartite graph에서의 pagerank는?
• 같은 종류끼리는 독립인데?
  

Proximity on graphs

• personalized pagerank: random walk로 계산해보자
• query nodes가 주어지면 random walk 수행
• restart proba가 주어지면 random walk를 처음부터 수행하게 됨
• 주어진 query nodes들이 가장 많이 방분한 node가 highest proximity를 보인다