강의 복습 내용

페이지랭크를 이용한 검색
- 페이지랭크
- 막다른정점, 스파이더트랩 문제
- 해결하기위한 순간이동
그래프로보는 전파
- 의사결정기반 모형
- 확률적전파 모형
- 바이럴 마케팅을 위한 시드집합 찾기
  - 전파최대화 문제

얻은 지식

검색엔진(페이지랭크)

배경

웹은 거대한 하이퍼링크로 이루어진 그래프
- 각 페이지는 정점
- 하이퍼링크는 방향성 있는 간선이 된다.
디렉토리를 통한 검색 엔진
- 웹을 거대한 디렉토리로
- 웨페이지가 증가함에 따라 카테고리의 수와 깊이도 무한이 커지는 문제가 있다.
키워드에 의존한 검색 엔진
- 키워드가 여러번 포함된 웹페이지를 반환
- 악의적으로 특정키워드를 안보이게 여러번 포함하면, 특정키워드와 관련없는 페이지도 검색 결과로 나온다.
the pagerank citation ranking: bringing order to the web
- 투표 방식의 웹페이지

페이지 랭크 핵심

핵심은 투표
- 투표의 주체는 웹페이지
- 하이퍼링크를 통해 투표
- 들어오는 간선이 많을 수록 신뢰할 수 있다
투표의 악용
- 인위적으로 들어오는 간선을 늘리는게 가능
가중투표
- 페이지랭크에서는 가중 투표를 진행
- 관련성이 높고 신뢰성이 높은 윂 사이트의 투표에 가중
- 출력을 입력으로?
투표 관점의 페이지랭크 점수
- 각 웹페이지는 각각의 나가는 이웃에게 (자신의 페이지랭크점수(r)/나가는 이웃의 수(d_out)) 만큼 가중치로 투표
- 페이지 랭크 점수는 받은 투표의 가중치 합으로 정의
- $r_j = \Sigma_{i \in N_{in}(j)}{\frac{r_i}{d_{out}(i)}}$ 일반화 식
- 이런 각 웹사이트의 페이지랭크 식을 연립 방정식으로 계산이 가능하다.
임의 보행(random walk) 관점의 페이지랭크 점수
- 웹서퍼가 현재 웹페이지의 하이퍼링크중 하나를 균일한 확률로 클릭하는 방식일때
- p_i(t)
  - t번째 방문한 웹페이지가 i일 확률
- 전체 확률 분포 벡터 크기가 웹페이지 수가 되며, 각각 p_1(t)p_2(t),…,p_v(t)를 가진다.
- $p_j(t+1) = \Sigma_{i \in N_{in}(j)}{\frac{p_i(t)}{d_{out}(i)}}$식
  - t+1번째 방문할 페이지가 j일 확률
  - j로 들어노는 모든 페이지 i에 대해 계산
  - (페이지 i가 t번째일 확률 / 페이지 i가 나가는 간선수) 를 전부 더한값을 가진다.
- 이 과정을 무한히 반복하면 p(t)는 수렴
  - p(t) = p(t+1) = p 가 성립된다.
- \[p_j = \Sigma_{i \in N_{in}(j)}{\frac{p_i}{d_{out}(i)}}\]
투표관점의 랭크점수는 임의보행 관점의 정상 분포가 동일하다.

페이지 랭크 계산

반복곱(power iteration)을 사용
1) 각 웹페이지 i의 페이지랭크 점수$r_i^{(0)}$를 통동일하게 (1/웹 페이지수)로 초기화$
- $r_i^{(0)}$는 0번째 iteration일때 i의 페이지랭크점수
2) $r_j^{(t+1)} = \Sigma_{i \in N_{in}(j)}{\frac{r_i^{(t)}}{d_{out}(i)}}$
3) $r_j^{(t+1)}$과 $r_i^{(t)}$ 가 유사하질때 까지(수렴) 2 를 반복
- 0번째 초기화로 1/전체 웹페이지 갯수로 1/3이 페이지랭크 점수로 들어간다.
- 1번째
  - y로 들어오는것은 y와 a이고, a는 2개의 나가는 선이 있다 y는 1/3*1/2 + 1/3 * 1/2가 되어 1/3이된다.
  - a로 들어노느것은 y와 m, y는 2개의 나가는선이므로 1/6, m은 1개의 나가는 선이므로 1/3으로 1/6+1/3 1/2가 된다.
  - m로 들어오는것은 a이고, a는 2개의 나가는 선이 있으니 1/3*1/2로 1/6이된다.
- 이를 반복
반복곱의 문제점
- 수렴이 항상되나
- 합리적인 점수로 수렴되는지

페이지랭크 문제점

스파이더 트랩(spider trap)
- 페이지 랭크 점수결과
- 들어오는 간선은 있지만 나가는 간선은 없는 정점 집합인 스파이더 트랩에 의한 문제
막다른 정점(dead end)
- 페이지 랭크 점수결과
- 들어오는 간선은 있지만 나가는 간선은 없는 정점 막다른 정점에 의한 문제

페이지 랭크 순간이동(teleport)

순서
- 1) 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동
- 2) 현재 웨페이지에 하이퍼링크가 있다면, 일정확률alpha의 동전 사용
- 3) 앞면은 하이퍼이크중 균일한 확률로 선택해 클릭
- 4) 뒷면은 임의의 페이지로 순간이동
alpha를 감폭 비율(damping factor)라고 부른다.
페이지 랭크 계산식 변경
- 각 막다른 정점에서 모든 다른 정점으로 가는 간선 추가
- $r_j^{(t+1)} = \Sigma_{i \in N_{in}(j)}{\alpha \frac{r_i^{(t)}}{d_{out}(i)}} + (1-\alpha)\frac{1}{\mid V \mid}$식으로 반복곱 수행
  - 더하기관점에서 좌측은 하이퍼링크로 j로 도착할 확률, 우측은 순간이동으로 j에 도착할 확률이된다.

그래프와 바이럴 마케팅

그래프를 통한 전파

전파 과정은 다양하고 매우 복잡하다
이를 체계적으로 이해하기 위해서는 수학적 모형화가 필요
- 의사 결정 기반의 전파 모형
  - 선형 임계치 모형
- 확률적 전파 모형
  - 독립적 전파 모형

결정기반의 전파 모형

카카오톡과 라인중에 어떤것을 사용할지?
- 주변사람들의 의사결정이 본인의 의사결정에 영향을 미친다.
의사결정 기반의 전파 모형
- 주변 사람들의 의사결정정을 고려하여 각자 의사결정을 내릴때
- 선형 임계치 모형(linear threshold model)

선형 임계치 모형

기본 이론
- A라는 기술을 같이 사용하면 a만큼 행복도가 증가
- B라는 기술을 같이 사용하면 b만큼 행복도가 증가
- 서로다른 기술을 사용하면 행복도가 증가하지 않는다.
여러명이될때
- u가 본인일때, 이웃의 비율을 빨간색A의 비율p 행복도는 a, 파란색B의 비율을 (1-P) 행복도는 b라고 하자
- u가 A를 사용한다면, $a*p*N$
- u가 B를 사용한다면, $b*(1-p)*N$이 된다.
- A를 선택할 때는 $a*p*N >b*(1-p)*N$가 된다.
  - 이를 p로 정리하면 $p > \frac{b}{a+b}$로 된다.
- 이때 $\frag{b}{a+b}$를 임계치 q라고 한다.
시드집합
- A를 새로운 기술, B를 기존의 기술이라고 생각
- 모형 전부는 B를 사용하고 있고, 처음 A를 사용하는 얼리어답터들을 가정
- 시드집합들은 A를 고수한다
예시
- u,v는 얼리어답터로 A를 주변상황 상관없이 사용한다
- 임계치는 55%
- 다시 각 정점에서 이웃의 임계치를 넘은경우들은 A를 선택하도록 반복적으로 진행한다.

확률적 전파 모형

코로나(질병)는 의사결정 내려서 걸리는 경우가 아니다.
확률적 과정이므로 확률적 전파 모형을 고려
독립 전파 모형(independent cascade)

독립적 전파 모형

방향성이 있고 가중치가 있는 그래프
간선 (u,v)의 가중치 p_uv
- u가 감염되었을때 v를 감염시킬 확률
서로 다른 이웃이 전염되는 확률은 독립적
시드 집합
- 최초 감염자들
감염자는 계속 감염자 상태로 남아있다고 가정

바이럴 마케팅

바이럴 마케팅은
- 소비자들이 상품에대한 긍정적인 입소물은 내게하는 기법
시드 집합
- 소문의 시작점이 중요
- 입소문의 전파 되는 범위가 영향을 받는다.

전파 최대화 문제(Influence Maximization)

전파를 최대화 하는 시드 집합을 찾는 문제
선형임계치, 독립전파 모형에도 사용 가능
가능한 경우의 수가 너무 크다
- 모든 경우를 고려하면 가능한 경우의 수가 너무 커진다.
- NP-hard문제
- 최고의 시드집합을 찾기는 어렵다.

시드집합 찾기

1) 휴리스틱으로 정점의 중심성(node centrality)을 사용
- 휴리스틱 : 실험적으로 잘돌아가지만, 이론적으로는 보장이 안되는것
- 시드집합의 크기가 k개일때, 정점의 중심성이 높은 순으로 k개의 정점을 선택하는 방법
- 정점의 중심성으로 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성이 있다.
- 합리적이지만 최고의 시드 집합을 찾는다는 보장이 없다.
2) 탐욕(greedy)알고리즘 사용
- 최초 전파자를 한번에 한명씩 선택
- 1) 최대가 되는 전파자 집합을 찾는다.
- 2) 찾은 전파자를 집합에 추가
- 3) 목표하는 크기의 시드 집합에 도달할때 까지 1,2를 반복
- 어느정도 최저의 성능의 시드집합을 찾는것은 수학적으로 보장된다고 한다.

실습

페이지랭크

nx.pagerank(H,alpha=0.8)
- pagerank구하는 메소드
- H는 부분그래프

전파 모형 시물레이터

독립전파 모형 시뮬레이션
선형임계치 모형 시뮬레이터

좀더 찾아보기

페이지랭크

피어세션 정리

조교님 시간
- 금요일 4시
- 질문 생각하기
순간이동에서 왜 자기자신 포함해서 이동하나?
- v-1로 해야 되는게 아닌가?
시뮬레이터로 반복하여 평균낸다는 의미는?
과제 관련 (1-S)/V는 어떤 의미?

further question

회복된다는 가정을 위해서는?
- 가중치를 0으로 하면 되나?
- node빼기
- edge빼기