AITech 학습정리-[Day 22] 페이지랭크 & 전파 모델

========================================

학습내용

[Graph 3강] 검색 엔진에서는 그래프를 어떻게 활용할까?

 

page rank

어떻게 신뢰할 수 있는 웹페이지를 검색결과로 띄울 수 있는가? 각 디렉토리를 만들어 분류하는 방법이나 키워드 갯수로 하려했으나 악용의 소지가 있다. 그래서 투표방법으로 결정하자고 했는데 투표를 웹 페이지 안에 있는 하이퍼링크를 통해 한다.

 

 

그럼 개념은 세웠으니까 적용할 수 있도록 수학적 식을 세워야 한다. 식을 세우는데 2가지 관점으로 세울 수 있는데, 투표 관점과 임의 보행 관점이다.

 

투표관점은 위에서 생각한 발상을 토대로 저런 식으로 page rank 식을 정의한다.

 

임의 보행 관점에서는 웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 확률을 pi(t) 로 하면 pj(t+1) 에 대한 식을 세울 수 있는데, 얘를 무한히 반복하다 보면 투표 관점에서 정의한 식과 같은 식이 나온다. 무한히 반복한다는 것은 주사위를 던졌을 때 처음에 몇번 던지면 각 숫자가 나올 확률이 뒤죽박죽이지만 무한히 던지다 보면 1/6의 확률이 되는 것과 비슷한 형식을 한 것으로 보인다.

어쨋든 투표 정의 관점에서 보든, 임의의 사이트에서 아무거나 눌러서 가는 확률 관점에서 보든, 식은 똑같다.

 

 

초기 정의 및 수 정의 계산 방법. 초기엔 사이트 갯수로 각 page rank값을 초기화 한 다음 식 대로 넣어서 계산한다. 그렇게 하다보면 page rank가 특정 값으로 수렴하는데, 이 값을 최종 page rank로 확정한다.

그러나 이런 방법엔 2가지 문제가 있는데, 스파이더 트랩이라고 지들끼리만 고인물 되면 특정값에 수렴이 안되고, 아얘 나가는 곳이 없는 막다른 정점이면 page rank들이 0에 수렴하게 된다.

그래서 이렇게 지들끼리만 가거나 아예 막다른 정점에 가서 막히는 것을 방지하기 위해, 웹 서퍼가 임의로 순간이동 하게 할 확률을 가지게 한다. 이러면 막히지도 않고 어디든지 잘 다닐 거다.

실습

https://colab.research.google.com/drive/1GMKQxVFMi9S7Kclx5_6Q6fZOk2Op3XHz?usp=sharing

 

 

[Graph 4강] 그래프를 바이럴 마케팅에 어떻게 활용할까?

 

전파에는 정보의 전파, 행동의 전파, 고장의 전파, 질병의 전파 4가지 종류 이상이 있다. 이를 이해하기 위해선 수학적 모형화가 필요하다.

전파 과정을 위한 수 많은 모형 중 두가지만 소개한다. 

 

의사결정 기반의 전파 모형중 한 종류인...

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

자기 이웃들 중 기준점 이상이 하면, 자기도 하는 것. 수학적 모형을 정의하기 위해 행복도 라는걸 정의해서 수치화해서 푼다.

A는 무조건 early adaptor라고 가정하고 B는 기존에 있던걸로 한다. 처음에 A를 시작하고 임계치에 따라 자기 이웃에 A가 얼마나 있는지 파악해서 퍼진다. 그래서 (b/(a+b)) 라는 식은 자기 총 이웃들 a+b 가 있을때 바뀌지 않은 b의 비율보다 p비율만큼 더 많으면 옮겨타는 거다. 이 임계치 (b/(a+b)) 를 편의상 q라고 한다.

자신이 선호해서 바꾸기 때문에 선형 '임계치' 모형이다.

확률적 전파 모형중 한 종류인...

독립 전파 모형(Independent Cascade Model)

 

자신의 의사와 상관없이 확률만으로 퍼질때가 있다. 이게 독립 전파 모형.

각자의 확률은 독립적이다. 감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파모형도 있지만 우린 그냥 한번 감염되면 영원한 감염자가 되는걸 반복한다.

 

 

 

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

 

그래서 위와 같은 현상이 일어나니까 어디서 시작하는 지도 중요하다. 그래프, 전파 모형, 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다.

그래프에 |V| 개의 정점이 있을 때, 시드 크기를 k로 제한해도 |V|Ck 의 조합수가 나와서 정점이 10,000개, 시드 집합의 크기가 10이어도 경우의 수가 2,743,355,077,591,282,538,231,819,720,749,000 개가 된다. 말이 안돼죠?

그래서 이상적인 방법은 포기하고, 대표적으로 휴리스티긍로 정점의 중심성(Node Centrality)를 사용한다. 즉, 시드 집합의 크기가 k개로 고정되어 있을 때, 정점의 중심성이 높은 순으로 k개 정점 선택을 하는 방법이다.

정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근점 중심성, 매개 중심성 등이 있다. 하지만 최고의 시드를 찾는다는 보장은 없다. 또 여기서 사용할 탐욕 알고리즘(Greedy Algorithm) 역시 많이 사용된다. 전파를 최대화 하는 시드를 1개부터 2개.. 3개... 늘려나가며 찾는 방식. 목표하는 크기의 시드 집합에 도달할 때까지 반복. 수학적으로 최저 성능이 보장되어 있다.

 

실습

https://colab.research.google.com/drive/1rIvQ3ZkGI6AWSMp_6uJMiS4PdtiMZX3s?usp=sharing

 

 

 

==========================================

과제 / 퀴즈

 

https://colab.research.google.com/drive/1_nSG9GrVFKypEj5J11hTrgtnI4_UC9n9?usp=sharing

변수 이름을 잘 보자 ...

 

 

=======================================

피어세션

 

면접준비는 

운영체제

웹이니까 웹 관련된거. 와즈랑 웹서버 차이

소프트웨어 공학 (클래스 설계)

 

======================================

후기

공부하기 싫어지고 나태해지는게 느껴진다.

어떻게 하지..