Peer Session Badge

My assignment: PageRank

페이지랭크

  • 배경

    • 웹
      • 웹페이지(정점), 하이퍼링크(간선)로 구성된 방향성 있는 그래프
      • 웹페이지는 키워드 정보를 포함
    • 구글 이전의 검색엔진: 디렉토리
      • 웹을 거대한 디렉토리로 정리 시도
      • 웹페이지의 수가 증가함에 따라 카테고리의 수과 깊이가 무한정 커짐
      • 현재는 수백억 개의 웹페이지 존재
    • 구글 이전의 검색엔진: 키워드
      • 사용자가 입력한 키워드에 대해 해당 키워드를 (여러 번) 포함한 웹페이지 반환
      • 악의적 (광고성) 웹페이지에 취약
    • 구글의 페이지랭크
      • 사용자 키워드와 관련성이 높으면서, 동시에 신뢰할 수 있는 웹페이지 찾는 방법

  • 정의

    • 투표
      • 투표의 주체: 웹페이지
      • 하이퍼링크를 통해 투표
      • 웹페이지 $u$가 $v$로의 하이퍼링크를 포함한다면 $\rightarrow$ $u$가 $v$에게 투표한 것
      • 들어오는 간선이 많을 수록 신뢰할 수 있음
      • 악용(인위적 조작)에 의한 효과 줄이기 위해 가중 투표
      • 가중치: $\frac{\text{자신의 페이지랭크 점수}}{\text{나가는 이웃의 수}}$

      • 페이지랭크 점수

        $r_j = \sum_{i \in N_{in}(j)} \frac{r_i}{d_{out}(i)}$

    • 임의 보행(random walk)
      • 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 서핑
      • $p_i(t)$: 웹서퍼가 $t$번째 방문한 웹페이지가 i일 확률
      • $p_i(t)$: 길이가 웹페이지 수와 같은 확률분포 벡터
      • $p_i(t+1) = \sum_{i \in N_{in}(j)} \frac{p_i(t)}{d_{out}(i)}$
      • $t$가 무한히 커지만 $p(t)$는 정상 분포(stationary dist.) $p$에 수렴하고 $p(t) = p(t+1) = p$ 성립

      • 정상 분포 $p$

        $p_i = \sum_{i \in N_{in}(j)} \frac{p_i}{d_{out}(i)}$

    • 투표 관점에서 정의한 페이지 랭크 점수 = 임의 보행 관점에서의 정상 분포

      관점
      값
      식
      투표 페이지랭크 점수 $r_j = \sum_{i \in N_{in}(j)} \frac{r_i}{d_{out}(i)}$
      임의 보행 정상 분포 $p_i = \sum_{i \in N_{in}(j)} \frac{p_i}{d_{out}(i)}$

  • 계산

    • 반복곱(power iteration)
      • 각 웹페이지 $i$의 페이지랭크 점수 $r_i^{(0)}$를 $\frac{1}{\text{웹페이지 수}}$로 초기화

      • 다음 식으로 각 웹페이지 페이지랭크 점수를 갱신

        $r_j^{(t+1)} = \sum_{i \in N_{in}(j)} \frac{r_i^{(t)}}{d_{out}(i)}$

      • 페이지랭크 점수가 수렴하면 종료, else 계속 갱신
    • 반복곱의 문제점
      • Spider trap(들어오는 간선만 있고 나가는 간선은 없는 정점 집합) 때문에 수렴 보장 x
      • Dead end(들어오는 간선만 있고 나가는 간선은 없는 정점) 때문에 합리적 점수로 수렴 보장 x
    • 순간이동(teleport) 도입
      • 임의 보행 관점에서 웹서퍼의 행동을 다음과 같이 수정
      • 현재 웹페이지에 하이퍼링크가 없다면 임의의 웹페이지로 순간이동, 하이퍼링크가 있다면 동전 던지기
      • 동전 앞면(확률: $\alpha$, damping factor, 보통 0.8)일 경우 하이퍼링크 중 하나를 균일한 확률로 선택, 뒷면일 경우 임의의 웹페이지로 순간이동

    • 수정된 반복곱

      $r_j = \sum_{i \in N_{in}(j)} \Big( \alpha \frac{r_i}{d_{out}(i)} \Big) + (1 - \alpha) \frac{1}{\vert V \vert}$

      • $\vert V \vert$: 전체 웹페이지의 수

그래프와 전파

  • 전파 예시

    • 정보
      • 정보
      • 행동 (아이스 버킷 챌린지, 펭귄 문제)
      • 고장 (네트워크 장비), 정전
      • 질병 (코로나-19)

  • 수학적 모형화

    • 의사결정 기반 전파 모형
      • 주변 사람들의 의사결정을 고려해 각자 의사결정을 내리는 경우
      • ex. Linear threshold model
      • $p$ 비율의 이웃이 $A$를 선택, $1-p$ 비율의 이웃이 $B$를 선택
      • $A$를 선택해야할 때: $apN > b(1-p)N$
      • 따라서 임계치 $q = \frac{b}{a+b}$ 를 넘을 때에 $A$ 선택
      • 시드 집합(seed set): 처음 $A$를 사용하는 얼리 어답터 집합. 항상 $A$ 고수
      • 이웃 중 $A$를 선택한 비율이 임계치를 넘을 경우, $A$ 선택으로 변경하는 식으로 전파됨
    • 확률적 전파 모형
      • 질병 전파와 같이, 의사결정을 내려 선택하는 게 아닌 것의 전파 모형
      • ex. 독립 전파 모형(independent cascade model): 감염자는 계속 감염자 상태로 남아있는 것을 가정
      • 간선 $(u,v)$의 가중치 $p_{uv}$: $u$가 감염되었을 때 감염되지 않은 $v$를 감염시킬 확률

  • 바이럴 마케팅

    • 소비자로 하여금 긍정적 입소문을 효과적으로 전파시키는 방법
    • 소문의 시작점(시드 집합)에 따라 입소문이 전파되는 범위가 영향을 받음
    • 전파 최대화(influence maximization) 문제
      • 그래프, 전파 모형, 시드 집합 크기 주어짐
      • 전파를 최대화하는 시드 집합을 찾는 문제
      • 많은 전파 모형에서 NP-hard 문제
        • $\vert V \vert$개의 정점이 있을 때 $k$개로 제한된 시드 집합의 경우의 수만 해도 $\binom{\vert V \vert}{k}$개로 굉장히 큰 수가 됨
      • 정점의 중심성(node centrality)
        • 휴리스틱 방법
        • 정점의 중심성이 높은 순으로 $k$개 정점을 선택
        • 페이지랭크 점수, 연결 중심성, 근점 중심성, 매개 중심성 등을 기준으로 삼음
        • 합리적이지만, 최적 시드 집합 보장 x
      • 탐욕(greedy) 알고리즘
        • 시드 집합의 원소를 한번에 한 명씩 선택
          1. 집합 $(1),(2), \dots, (\vert V \vert)$를 비교해 전파를 최대화하는 시드 집합을 찾는다 $\rightarrow (x)$
          2. 집합 $(x,1),(x,2), \dots, (x, \vert V \vert)$를 비교해 전파를 최대화하는 시드 집합을 찾는다 $\rightarrow (x,y)$
          3. $k$개를 찾을 때까지 반복
        • 최초 전파자 간의 조합의 효과 고려 x
        • 최적 전파 크기의 0.632배 이상임이 수학적으로 보장되어 있음 $(\geq \Big( 1 - \frac{1}{e} \Big))$