Graph2
검색엔진에서의 그래프
페이지랭크의 배경
1.1 웹과 그래프
웹(방향성이 있는 그래프) = 웹페이지(node) + 하이퍼링크(edge)
웹페이지는 추가적으로 키워드 정보를 포함하고있다.
2.2 구글이전의 검색엔진
웹을 거대한 디렉토리로 정리
웹페이지의 수가 증가함에 따라 카테고리 수도 무한정 커지는 문제가 있다
카테고리 분류가 모호할수가 있다.
키워드에 의존한 검색엔진
악의적인 웹피이지에 취약하다
따라서 page rank라는 하나의 알고리즘을 구글이 만들었다
페이지랭크의 핵심은 투표이다.
웹페이지는 하이퍼 링크를 통해 투표를하게 된다.
사용자가 입력한 키워드를 포함한 웹페이지에서 u가 v에 연결되어있다면 v는 신뢰가능
많이 인용된 논문을 신뢰하는것과 비슷한 알고리즘
웹페이지를 여러개 만들어서 간서의 수를 부풀릴수 있다.
이런식의 악용은 온라인 sns에서도 흔히 발견이 된다.
이러한 악용을 막기위해 가중투표를 사용한다.
측정하려는 웹페이지의 관련성과 신뢰도
자시의 점수 / 나가는 이웃의 수
또한 페이지 랭크는 임의보행의 관점에서도 정의 할 수있다.
웹서퍼는 현재 하이퍼링크중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑한다.
이 과정을 무한히 수행하면 p(t) = p(t+1)이된다. 수렴한 p는 정상분포라고 부른다. 결국 이를 정리해보면 투표관점에서의 pagerank정의 수식과 비슷함을 확인할 수 있었더.
페이지랭크의 계산
반복곱
Power iteration은 각웹페이지에 페이지 랭크를 구할때 사용된다
각웹페이지 i의 페이지 렝크 점수를 동일하게 (1/웹페이지수) 로 초기화 한다
아래의 식을 사용하여 웹페이지의 점수를 갱신한다
페이지 랭크 점수가 수렴할때까지 계산을 반복한다.
과연 반복곱이 할상 수렴을 할까요?
수렴하지 않을수가 있다. -> 들어오는 정점은 있지만 나가는 간선이 없는 spider trap에 의해 일어남
과연 수렴을 한다고 해도 이 결과가 합리적인 값일까요?
이 문제점들에 대한 해결책 : 순간이동
임의 보행관점에서
(1) 현재 웹페이지에 하이퍼링크가 없다면 임의의 웹페이지로 순간이동을 한다
(2) 현재 웹페이지에 하이퍼링크가 있다면
$\alpha$의 확률로 파이퍼 링크중 하나를 균일한 확률로 선택하고 클릭한다
(1-$\alpha$)의 확률로 임의의 웹페이지로 순간이동 한다
이로 인해 spider trap이나 dead end에 갇히는 일이 사라졌다.
순간이동의 도입은 수식이 바뀐다
각 막다른 정점에서 다른모든 정점으로 가는 간선을 추가한 후
이제는 이 수식을 사용한다.
그래프를 이용한 바이럴 마케팅
의사결정 기반의 전파
주변의 의사결정을 고려하여 의사결정을 할때 의사결정 기반의 전파모형을 사용한다
—> 선형임계치모형 (linear threshold model)
확률적 전파
코로나의 전파를 수학적으로 나타낼때는 확률적 모형을 사용해야 한다.
Independent Cascade model
바리럴 마케팅이란?
소비자로 하여금 상품에대한 긍정적인 입소문을 내게 하는 기법
바이럴 마케팅을 위해서는 소문의 시작점이 중요하다.
시드 집합이 전파에 많은 영향을 미친다
그래프. 전파모형, 시드집합의 크기가 주어졋을때 전파의 최대화를 위한 시드집합은 전파최대화 문제이다.
어려운 문제이다. 그래프에 V개의 정점이 있는경우 시드집합이 k개일때 경우의 수는 vCk 이다
이론적으로 전파최대화 문제는 풀기가 힘든 문제임이 증명이되어있다.
대표적 휴리스틱으로 정점의 중심성 을 사용합니다.
즉시드 크기가 k개로 고정이되어있을때 정점의 중심성이 높은수으로 k개 정점을 선택하는 방법이다.
정점의 중심성으로는 페이지 랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성등이있다.
탐욕 알고리즘
시드 집합의 원소를 한번에 한명씩 선택을 한다.
정점의 집합 : {1,2,….,V}
각 집합에 대해 시뮬레이션을 반복하여 평균값을 사용한다. x라는정점이 최초의전파자로 선정이 되어있다. 이런 비교를 통해 뽑힌 집합은 x라고 하자. 이제 x를 포함한 크기가 2이 시드 집합을 찾는다.이를 목표의 크기까지 반복한다.
최초전파자간의 조합을 고려하지 않는다.
탐욕 알고리즘은 항상 최고의 시드 집합을 찾는다는 보장이 없는 근사의 알고리즘이다
항상 최적의 값이 아니라는 말이다.
하지만 적어도 어느정도의 시드집합은 찾을 수 있다.