Web Graph Theory

웹 그래프를 다음 구조로 알아보자!

 

1) real system인 Web이 있다.

2) 우리는 이 Web을 directed graph로 나타낼 것이다.

3) Graph theory 중 Strongly Connected Components를 주로 볼 것이다.

4) SCC가 실제로 Web Graph를 잘 나타내는지 실험적으로 확인할 것이다.

5) Structure of Web이 Bowtie라는 것을 알 수 있다!

 

1. The Web as a Graph

• 정의
  • bridge edge: 없으면 그래프가 끊긴다.
  • local bridge: edge of span>2, bridge는 아니다.
  • edge of span:
• node는 웹사이트, edge는 하이퍼링크라고 이해하면 된다.
• 옛날의 web link는 navigational 한 특징이 있었지만, 요즘은 좋아요, 댓글 등 transactional 하다.
• 한 node에 대해 In(A)와 Out(A)를 정의할 수 있다.
• 모든 웹상의 directed graph는 아래 두 가지 종류 중 하나로 표현할 수 있다.
  • Stringly Connected: 모든 노드에서 모든 노드로 도달할 수 있다,  In(A) = Out(A) = {all}
  • Directed Acyclic Graph: 사이클이 존재하지 않는다, u는 v로 갈 수 있지만 반대는 그렇지 못하다.
• Connected Graph
  • Strongly connected
  • Directly acyclic

2. SCC: Strongly Connected Component

• 정의
  • 모든 노드 쌍은 서로에게 도달할 수 있다.
  • 위 성질을 가진 더 큰 set은 없다.
• Every direct graph is a DAG on its SCCs
  • SCCs partitions the nodes of G
    • 각 노드는 정확히 하나의 SCC에만 포함된다.
  • Every directed graph is a DAG on its SCCs
    • 모든 방향성 그래프는 비순환 그래프이다.

3. Structure of the Web

• Goal
  • Take a large snapshot of the Web and try to understand how its SCCs fit together as a DAG
• Computational issue
  
  • starting node가 무엇인지에 따라 SCC를 찾기 위해 굉장히 많은 node를 순회해야 할 수도 있다.
• Bowtie Structure of the Web
  • In: 100
  • Out: 100
  • SCC: 56
  • Bowtie: 44 - 56 - 44

4. Why is it that axquaitances are most helpful?

• friendship에 대한 두가지 관점
  
  • Structural: 친구 집합은 그래프의 다른 부분에 위치한다.
  • Interpersonal: 관계는 weak이거나 strong이다.
    • structurally embedded edges는 strong 하다.
    • long range edges는 weak 하다.
    • strong 한 관계의 information은 redundant 하다.
• Tradic Closure
  • A-B 친구이고 A-C 친구이면 B-C가 친구일 확률이 높다.
• 만약 strong tradic closure가 만족된다면 local bridges are weak tie
• Edge Overlap
  • 두 노드 이웃 교집합/두 노드 이웃 합집합
  • edge가 local bridge라면 Overlap=0
• Edge Overlap과 Strength의 관계
  • permutated data보다 strength가 클수록 overlap이 컸다.
  • 그래프로 보았을 때도 strength가 큰 edge가 모여있는 것을 볼 수 있다.
• Edge Removal by Strength
  • strength가 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.
• Edge Removal by Overlap
  • overlap이 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.