[Day 22] Graph - 페이지랭크 & 전파

📍 PageRank

  🔥 배경

    - 웹 = Web page + Hyper Link인 방향성 있는 그래프

웹 페이지는 정점에 해당하고 하이퍼링크는 간선에 해당

    - 구글 이전의 검색 엔진으로는 디렉토리로 웹을 정리하는 경우가 있었음

      -> 웹페이지 수 증가에 따라 카테고리의 수와 깊이도 무한정 커지는 문제 발생

    - 다음으로는 키워드에 의존한 검색 엔진이 있었음

      -> 사용자가 입력한 키워드에 대해, 해당 키워드를 여러 번 포함한 웹페이지를 반환

      -> 악의적으로 사용할 가능성이 높음(성인 사이트에 '운동'이라는 키워드를 보이지 않게 여러 번 포함하면, '운동'을 검색했을 경우 해당 성인 사이트가 결과로 나올 수 있음)

 

    - 구글에서는 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾기위해 노력했음

 

  🔥 정의(투표, 임의 보행)

    - 투표 관점에서 본 페이지랭크가 있다.

      -> 투표(웹페이지가 하이퍼링크를 통해 투표)를 통해 사용자가 원하는 웹페이지를 찾음

      -> 들어오는 간선이 많을수록 신뢰도가 높아짐

        => 하지만 이는 악용의 소지가 있음

        => 어떻게 막을 수 있을까? 가중치

 

    - 임의 보행(Random Walk) 관점에서 정의

      -> 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정: 웹서퍼는 현재 page에서 하이퍼링크를 균일한 확률로 클릭

      -> 웹서퍼가 t번째 방문한 웹페이지가 원하는 i페이지일 확률을 p_i(t)라고 한다면 p(t)는 웹페이지 수와 같은 확률분포 벡터

     -> 그렇게 된다면 아래 식이 성립

      -> 웹서퍼가 이 과정을 무한히 반복하고 나면(t가 무한대로가면) 확률 분포는 p(t)에 수렴(즉, p(t) = p(t+1) = p)

        => 수렴한 p를 정상 분포(Stationary Distribution)이라고 함.

        => 아래와 같이 식을 변경할 수 있음

    - 투표의 관점에서나 임의 보행관점에서나 결국 같은 식이 도출된 다는 것을 알 수 있음.

 

  🔥 계산

    - 반복곱(Power Iteration)을 사용

 

    - 하지만 반복곱이 항상 수렴하는 것은 아니다!

      -> 들어오는 간섭은 있지만 나가는 간선이 없는 스파이더 트랩(Spider trap)에서 문제가 발생

 

    - 또한 반복곱이 '합리적인' 점수로 수렴하는 것을 보장하지 않는다!

      -> 들어오는 간선은 있지만 나가는 간선이 없는 막다른 정점(Dead End)에서 문제가 발생

 

      => 이러한 문제를 해결하기 위해 순간이동(Teleport)을 도입

 

    - 임의 보행 관점에서 보게되면 아래와 같다.

α를 감폭 비율(Damping Factor)이라고 부르며 보통 0.8정도를 사용

      -> 아래와 같은 식이 수행됨.

 

📍 전파

  🔥 전파의 예시

    - 정보, 행동, 고장, 질병 등이 존재

      -> 전파의 과정을 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요

        => 의사 결정 기반, 확률적 전파 모형 등이 존재

 

  🔥 의사결정 기반의 전파 모형

    - 주변 사람들의 의사결정을 고려해 각자 의사결정을 내리는 경우에 사용(선형 임계치 모형이 존재)

    - 선형 임계치 모형(Linear Threshold Model)

      -> 친구 관계의 두 사람 u, v가 있을 경우, A기술과 B기술 중 하나를 선택해야한다.

      -> A를 둘다 고를 경우 a만큼 만족도가 있고, B의 경우 b만큼 만족도가 있다. 하지만 다를 경우 0이다.

    - 위의 경우에는 엄청나게 작은 네트워크를 보았다면 어마어마하게 큰 소셜 네트워크를 보자.

 - 만약 2a > 3b라면 A를 선택하고 나머지의 경우는 B를 선택한다고 하자.

- 그 경우 p의 비율의 이웃이 A를 선택하고 (1-p)의 비율이 B를 선택했다고 할 수 있다. 따라서 A를 선택하게 될 경우는 pa > (1-p)b가 되고 이를 정리하면 아래와 같다.

 p > b/(a+b)   ==> 여기서 b/(a+b)를 임계치 q라고 한다.

 

 

  🔥 확률적 전파 모형

    - COVID-19와 같은 의사 바탕이 아닌 확률적으로 감염이 되는 것에 사용되는 모델

      -> 독립 전파 모형(Independent Cascade Model)

    - 독립 전파 모형

      -> 방향성이 있고 가중치가 있는 그래프

      -> 간선(u, v)의 가중치 P_u,v는 v가 감염되지 않고 u가 감염되어 있을 때, u에게서 v가 감염될 확률을 예시로 들 수 있음(단, 감염자는 회복이 안된다는 전제)

      => 회복을 가정하는 SIS, SIR등의 모형이 존재

 

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

    - 바이럴 마케팅: 소비자들로 하여금 상품에 긍정적인 입소문을 내게하는 기법(ex. 소셜 인플루언서의 광고)

      -> 대표적으로 '미들턴 효과(Kate Middleton Effect)'가 있음

 

    - 전파 최대화 문제(Influence Maximization Problem)

      -> 시드 집합(Seed set)을 선택할 수 있을 때, 그래프, 전파모형, 시드 집합의 크기를 고려해 전파를 최대화 하는 시드집합을 찾는 문제. 즉, 영향력 있는 시드 집합을 찾아내는 문제

      -> 그래프에 |v|개의 정점이 있을 경우, 시드 집합의 크기를 K로 제한하더라도 경우의 수는 |v| combination k이다.

        => 정점: 10,000개, k: 10이라고 했을때에도 경우의 수는 2.7x10^34개나 됨 => NP-hard임(거의 불가능)

 

    - 따라서 근사적(휴리스틱)으로 접근

      -> 정점의 중심성(Node Centrality)을 사용(페이지 랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있음)

      -> 합리적이지만, 최고의 시드 집합을 찾는다는 보장은 없음

 

  🔥 탐욕 알고리즘(Greedy Algorithm)

    - 시드 집합의 원소를 한번에 하나씩 선택하여 목표하는 크기의 시드 집합에 도달할 때까지 반복하는 알고리즘

    - 해당 알고리즘의 경우 정확도는 수학적으로 다음과 같다.