Day22 학습정리 - 페이지랭크 & 전파 모델

강의복습

1. 검색 엔진에서는 그래프를 어떻게 활용할까?

1) 페이지랭크의 배경

• 웹: 웹페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프
• 구글 이전의 검색 엔진의 한계
  • 디렉토리: 웹페이지 수가 증가하면 카테고리의 수와 깊이도 무한정 커짐, 카테고리 구분 모호
  • 키워드: 악의적인 웹페이지에 취약
•  구글의 창업자인 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)이 페이지랭크 개념 제안

2) 페이지랭크의 정의

• 투표 관점: 하이퍼링크를 통한 가중 투표(주체: 웹페이지)
  • 악용 막기 위해 가중 투표 함 씨가 (자신의 페이지랭크 점수 / 나가는 이웃의 수)
  • 재귀(Recursion): 연립방정식 풀이
  • 페이지랭크 점수: 측정하려는 웹페이지의 관련성 및 신뢰도

• 임의 보행 관점: 웹서퍼가 각 웹페이지를 방문할 확률
  • 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 식으로 서핑
  • p(t): t번째 방문한 웹페이지가 웹페이지 i일 확률
  • 정상 분포(Stationary Distribution): p(t) = p(t+1) = p 성립

3) 페이지랭크의 계산

• 반복곱
  1. 각 웹페이지의 페이지랭크를 동일하게 (1 / 웹페이지의 수)로 초기화
  2. 각 웹페이지의 페이지랭크 점수 갱신
  3. 페이지랭크 점수가 수렴하였으면 종료 
• 스파이더 트랩(Spider Trap) 및 막다른 정점(Dead End) 문제를 해결하기 위한 순간 이동
  • 하이퍼링크가 없을 때: 임의의 웹페이지로 순간이동
  • 하이퍼링크가 있을 때: 앞면 나올 확률이 𝛼인 동전 던짐
    • 앞면: 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭
    • 뒷면: 임의의 웹페이지로 순간이동
  • 𝛼: 감폭 비율(Damping Factor), 보통 0.8정도 사용

4) 실습: 위키피디아 검색 엔진

2. 그래프를 바이럴 마케팅에 어떻게 활용할까?

1) 그래프를 통한 전파의 예시

• 정보, 행동, 고장, 질병 등

2) 의사결정 기반의 전파 모형

• 각각의 정점이 개인의 행복을 최대화하도록 의사결정하는 상황을 모형화
• 대표 예시: 선형 임계치 모형(Linear Threshold Model)
  • 이웃 중 A를 선택한 비율이 임계치 q를 넘을 때에만 A 선택

3) 확률적 전파 모형

• 질병의 전파 등 확률적 과정을 모형화
• 대표 예시: 독립적 전파 모형(Independent Cascade Model)
  • 첫 감염자: 시드 집합(Seed Set)
  • 각 최초감염자 𝑢는 각 이웃 v에게 𝑝_𝑢𝑣 확률로 병 전파
  • 감염자의 회복 가정한 전파모형도 있음(SIS, SIR 등)

4) 바이럴 마케팅과 전파 최대화 문제

• 바이럴 마케팅: 소비자로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법
• 전파를 최대화하는 시드 집합을 찾는 문제
• 정점 중심성 휴리스틱, 탐욕 알고리즘 등

5) 실습: 전파 모형 시뮬레이터 

---

코멘트

오늘은 페이지랭크와 전파모형에 대해 배웠다. 공부하면서 실생활에서 전파모형으로 나타낼 수 있는 사례를 생각해보았다.