[BOOSTCAMP AI TECH] 22일차_페이지랭크 & 전파 모델

• 강의 목록

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

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

---

• 요약

강의

 

피어세션

 

---

• 학습정리

웹과 그래프

• 웹은 웹 페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프이다.
• 웹 페이지는 정점에 해당하며, 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당한다.
• 단, 웹 페이지는 추가적으로 키워드 정보를 포함한다.

 

• 구글 이전의 검색 엔진은 웹을 거대한 디렉토리 구조로 정리하려 했다.
• 하지만 웹 페이지의 수가 증가함에 따라 카테고리의 수와 깊이가 무한정 커졌다.
• 또한 카테고리 구분이 모호한 경우가 많아 저장과 검색의 어려움이 있었다.

 

• 그래서 키워드에 의존한 검색 엔진을 구축했다.
• 하지만 이 방식은 악의적인 웹페이지에 취약하다는 단점이 있다.
• 예를 들어 불법 사이트가 여러 키워드를 포함하면 검색의 결과로 불법 사이트가 나올 수 있다.

 

• 그래서 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹 페이지를 찾기 위해, 구글의 창업자인 래리 페이지와 세르게이 브린이 페이지 랭크를 개발했다.

 

---

 

페이지 랭크

• 페이지 랭크의 핵심 아이디어는 투표이다.
• 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹 페이지를 찾는다.
• 투표의 주체는 웹 페이지이며, 하이퍼링크를 통해 투표를 한다.
• 사용자 키워드를 포함한 웹페이지가 특정 하이퍼링크를 포함하고 있다면, 해당 웹 페이지의 작성자가 해당 하이퍼 링크가 주제에 맞음을 의미하고, 투표했다고 생각한다.

 

• 들어오는 간선이 많을 수록 신뢰할 수 있다.
• 단, 간선의 수를 세기만 하는 것은 악용될 소지가 있다. 인위적으로 웹 페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있기 때문.
• 이런 악용을 막기 위해 페이지 랭크는 가중 투표를 한다.
• 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주한다.

 

• 이러한 방식은 재귀, 즉 연립방정식 풀이를 통해 가능하다.

• 각 웹페이지는 각각의 나가는 이웃에게 (자신의 페이지랭크 점수 / 나가는 이웃의 수) 만큼의 가중치로 투표를 한다.
• 또한 페이지 랭크는 임의 보행 (Random Walk)의 관점에서도 정의할 수 있다.

 

 

---

페이지 랭크의 계산

 

1) 반복곱

반복곱 예시

• 각 웹페이지 i의 페이지 랭크 점수를 동일하게 (1 / 웹페이지의 수)로 초기화한다.
• 이후 위의 식을 이용해 각 웹 페이지의 페이지 랭크 점수를 갱신한다.
• 페이지 랭크 수가 수렴했으면 종료하고, 아니면 2번 단계로 돌아간다.

 

 

• 그러나 반복곱은 반드시 수렴하는 것을 보장할 수 없다.
• 또한 합리적인 점수로 수렴하는 것을 보장할 수 없다.
• 이러한 문제 해결을 위해 순간이동(Teleport)를 도입했다.

 

 

2) 순간이동 (Teleport)

• 임의 보행 관점에서 웹을 서핑하는 웹서퍼의 행동을 다음과 같이 수정한다.

1.  현재 웹 페이지에 하이퍼링크가 없다면 임의의 웹페이지로 순간이동
2.  현재 웹 페이지에 하이퍼링크가 있다면 앞면이 나올 확률이 a인 동전을 던진다.
3.  앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭
4.  윗면이라면 임의의 웹 페이지로 순간이동

• 위의 과정 중 순간이동은 전체 웹 페이지들 중 하나를 균일 확률로 선택한다.
• 순간이동에 의해 스파이더 트랩과 막다른 정점에 갇히는 일이 없어졌다.
• 확률 a는 감폭 비율(Damping Factor)이라 부르며, 보통 0.8을 값으로 사용한다.

 

• 순간이동 도입은 페이지 랭크 점수 계산을 다음과 같이 바꾼다.

 

 

Python에서의 페이지 랭크

#방향성이 있는 networkx.DiGraph를 사용해 G를 정의한다.
#G에 그래프를 정의하고, 이 중 필요한 키워드들을 node_key : list 로 정의한다.

#node_key에 대한 부분 그래프를 만든다.
H = G.subgraph(node_key)

#alpha 값을 0.9로 하여 pagerank를 수행한다.
pr = networkx.pagerank(H, alpha=0.9)

 

---

 

바이럴 마케팅에서의 그래프

 

그래프를 통한 전파

1. 정보의 전파 : 유용한 과학적 정보가 전파되기도 한다.
2. 행동의 전파
3. 고장의 전파 : 컴퓨터 네트워크에서는 일부 장비의 고장이 전체 네트워크를 마비할 수 있다. (정전 전파 사례도 유사)
4. 질병의 전파 : 사회라는 거대한 네트워크를 통해 질병의 전파도 가능하다.

• 이렇듯 전파 과정을 다양할 뿐 아니라 매우 복잡하다.
• 이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요하다.

 

• 오늘 수업에서는 전파 과정을 위한 모형들 중 두 가지를 학습했다.

 

---

의사결정 기반의 전파 모형

• 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미치는 경우.
• 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우, 의사결정 기반의 전파 모형을 사용한다.
• 선형 임계치 모형은 가장 간단한 형태의 의사결정 기반의 전파 모형이다.

 

 

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

좌=>우, 상=>하

• 위의 마지막 모형을 선형 임계치 모형이라고 한다.
• 각 정점은 이웃 중 A를 선택한 비율이 임계치 q를 넘을 때만 A를 선택한다.

 

• 그런데 위 모형은 전부 B를 사용하는 상황을 가정한다.
• 그리고 처음 A를 사용하는 얼리 어답터들을 가정하는데, 이들을 '시드 집합'이라고 부른다.
• 시드 집합은 주변의 선택과 관계없이 항상 무언가를 고수한다고 가정하는 집합이다.
• B는 이미 사용되고 있는 기술, A는 새롭게 등장한 기술이라고 보면 된다.

 

임계치가 55%일 때 시드 집합의 전파

• 시드 집합은 새로운 기준으로써 주위 노드들에 전파된다.

 

 

---

 

확률적 전파 모형

• 질병의 전파 과정의 경우, 의사결정 기반 모형은 적합하지 않다.
• 그 누구도 질병에 걸리겠다고 의사결정을 내리지 않기 때문.
• 이런 경우 확률적 전파 모형이 사용되는데, 질병의 전파와 같이 확률적 과정의 전파에 사용한다.
• 독립 전파 모형은 가장 간단한 형태의 확률적 전파 모형이다.

 

 

독립적 전파 모형 (Independent Cascade Model)

• 각 간선 (u,v)의 가중치 p(uv)는 u가 감염되었을 때 u가 v를 감염시킬 확률이다.
• 즉, 각 정점 u가 감염될 때마다 각 이웃 v는 p(uv)< 확률로 전염된다.
• 서로 다른 이웃이 전염되는 확률은 독립적이다.
• 그렇기에 모든 노드들이 감염될 확률은 독립적이다.
• 모형의 모델은 최초 감염자들로부터 시작한다. 독립적 전파 모형에서는 이러한 최초 감염자들을 시드 집합이라 한다.
• 계속해서 전파하며 더 이상 새로운 감염자가 없으면 종료한다.

 

 

---

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

 

바이럴 마케팅

• 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 방법
• 효과적인 바이럴 마케팅을 위해서는 소문의 시작점이 중요하다.
• 시작점에 따라 입소문이 전파되는 범위가 영향을 받기 때문.
• 소셜 인플루언서들이 높은 광고비를 받는 이유이다.
• 이들을 시드 집합이라 한다.
• 앞서 소개한 전파 모형들에서도 시드 집합이 전파 크기에 많은 영향을 미친다.
• 그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화 문제라고 한다.

*전파 모형은 선형 임계치 모형, 독립 전파 모형 등 다양한 모형으로 구축할 수 있다.

 

 

 

전파 최대화 문제

• 전파 최대화 문제는 방대한 그래프에서 영향력 있는 시드 집합을 찾아내는 문제이다.
• 전파 최대화 문제는 너무 많은 경우의 수를 고려해야 하기에 매우 어려운 문제이다.
• 이론적으로 많은 전파 모형에 대해 전파 최대화 문제는 NP-hard 임이 증명되었다.

*NP-hard : 다항시간내에 풀 수 없는 문제

• 이로 인해 거대한 그래프에 대해 최적의 시드 집합을 찾는 것은 포기해야 하는 경우가 많다.
• 대신 휴리스틱이라 불리는 근사 알고리즘을 사용해야 한다.

 

 

정점 중심성 휴리스틱

• 휴리스틱이란 실험적으로는 잘 동작할 수 있지만 이론적으로는 정확도를 보장할 수 없는 알고리즘을 의미한다.
• 전파 최대화 문제에서 대표적인 휴리스틱으로는 정점 중심성 휴리스틱이 있다.

 

• 정점 중심성 휴리스틱은 시드 집합의 크기가 k개로 고정되었을 때, 정점의 중심성이 높은 순으로 k개의 정점을 선택하는 방법이다.
• 정점의 중심성은 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등으로 측정할 수 있다.

 

• 정점 중심성 휴리스틱은 분명 합리적인 방법이지만 최고의 시드 집합을 찾는다는 보장이 없다.

 

 

 

탐욕 알고리즘

• 정점 중심성 휴리스틱 외에도 탐욕 알고리즘도 많이 사용된다.
• 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한 번에 한 명씩 선택한다.
• 정점의 집합이 {1,2, ..., v}일 경우 구체적인 단계는 다음과 같다.

 

• 위의 과정에서 볼 수 있듯 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않는다.
• 그저 근시안적으로 최초 전파자를 선택하는 과정을 반복할 뿐이다.
• 탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있다.
• 즉, 최적의 성능은 보장할 수 없지만 어느정도의 성능은 보장한다.

 

 

---

• 피어세션 회의 내용

 

---

• 해야할 일

 

---