그래프와 추천시스템 4-5

그래프를 이용한 바이럴 마케팅

Futher Reading https://arxiv.org/abs/1808.05502

그래프를 통해 정보, 행동, 고장, 질병 등은 전파된다.
- SNS를 통해 정보, 행동이 전파된다.
- 컴퓨터 네트워크에서 일부 장비의 고장이 전파되어 네트워크의 마비로 이어진다.
- 질병의 전파

의사결정 기반의 전파모형
- 카카오톡과 라인 중 어떤 메신저를 사용하며 그 이유는?
  → 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다
- 선형 임계치 모형(Linear Threshold Model)
  가장 간단한 형태의 의사결정 기반 전파모형
  - 추상화
    - 2인일 때
      u, v 정점(사용자)가 모두 A를 사용할 때 효용: a
      u, v 정점(사용자)가 모두 B를 사용할 때 효용: b
      u, v 정점(사용자)가 각각 A,B를 사용할 때 효용: 0
    - 일반화
      아래와 같은 그래프에서의 u의 효용: 2a / 3b
      두 가지 선택지 중 효용이 큰 것을 u가 선택한다고 가정. p비율의 이웃이 A를 선택
      u는 $a p > b(1-p)$ 일 때, A를 선택하며 이는 $p > {{b}\over{a+b}}$ 일 때 이고 우항을 임계치 q라 한다.
  - 시드집합(Seed Set)
    선형임계치 모형에서 사용자(정점)은 모두 B를 사용하는 상황을 가정
    처음 A를 사용하는 사용자(정점)을 얼리어답터로 가정하며, 이들을 시드 집합이라고 함
    시드집합은 항상 A를 고수한다고 가정
  - 임계치는 55%로 가정하는 경우
    시드집합 u, v가 등장할 때 그래프의 변화

확률적 전파 모형
코로나 같은 질병은 의사결정을 내리지 않음
질병과 같은 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야 함
- 독립적 전파모형(Independent Cascade Model)
  가장 간단한 형태의 확률적 전파모형으로, 방향성이 있고 가중치가 있는 그래프를 가정.
  정점 u가 감염되었을 때, v가 감염될 확률을 $p_{uv}$ 로 표현. 각 이웃이 점염되는 확률은 독립적.
  - 과정
    시드집합: 최초감염자
    각 최초 감염자는 이웃에게 해당 확률로 전파
    새로운 감염자가 없으면 종료
    감염자는 계속 감염상태로 남아있는 것을 가정 (SIS, SIR 등의 전파모형은 감염자의 회복을 가정)

바이럴 마케팅과 전파 최대화 문제
바이럴 마케팅: 소비자들에게 상품에 대한 긍정적인 입소문을 내게 하는 기법
소문의 시작점이 중요. 시작점에 따라 입소문이 전파되는 범위가 영향을 받음. → 소셜 인플루언서들이 높은 광고비 받는 이유
ex. 미들턴 효과 (영국 왕자 부인)
선형임계치 모형이나 독립적 전파 모형 모두 시드집합이 전파 크기에 많은 영향을 미침
선형임계치 모형에서 시드집합을 아래와 같이 설정하는 경우, 전파가 발생하지 않는다.
- 전파 최대화 문제 (Influence Maximization Problem)
  그래프, 전파모형, 시드집합의 크기가 주어질 때 전파를 최대화 하는 시드 집합을 찾는 문제.
  시드 집합을 선택할 수 있다면, 누구를 시드로 선택할 것인가.
  → 대신에 근사하는 방법인 휴리스틱이나 탐욕알고리즘을 사용
- 전파 최대화 문제 해결방안
  - 휴리스틱
    정점 중심성(Node Centrality)이 높은 순으로 K개의 정점을 선택
    합리적인 방법이지만 최고 시드집합을 찾는 보장은 없음
    - 정점 중심성으로 사용할 수 있는 것
      페이지 랭크 점수
      연결중심성: 정점들과 연결성이 높은 정점을 선택
      근접중심성: 정점들과의 평균거리가 작은 정점을 선택
      매개중심성: 정점간 최단 경로에 많이 놓이는 정점을 선택
  - 탐욕알고리즘
    전파를 최대화하는 최초 전파자를 목표하는 크기의 시드 집합에 도달할 때까지 한 명씩 선택한다.
    - 탐욕알고리즘의 최저성능은 수학적으로 최고 시드집합 성능의 0.632 ( $1-{{1}\over{e}}$ )로 보장되어 있음
- 추가자료: https://arxiv.org/abs/1808.05502

군집 탐색

군집(Community)
1. 집합에 속하는 정점 사이에는 많은 간선이 존재
1. 집합에 속하는 정범과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재
군집은 사회적무리(Social Circle)을 의미
예시: 부정 행위에 연류된 계정은 군집을 형성함. 회사 내 보고 체계 이메일 그래프를 분석해 보고 체계의 효율성 확인 가능.

군집 탐색 문제(Community Detection Problem)
클러스터링과 유사하다. 클러스터링이 벡터를 군집으로 묶는 것이라면, 군집탐색문제는 정점을 군집으로 묶는 것이 다름.

군집탐색문제의 평가
배치모형과 비교하여 군집의 성능 평가
- 배치모형(configuration model)
  각 정점의 연결성(Degree)을 보존한 상태에서 간선을 무작위로 재배치해 얻은 그래프.
  임의의 두 정점 i와 j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례.
- Metric: 군집성(Modularity)
  군집성은 무작위로 연결된 배치모형과 비교를 통해 계산.
  [-1, 1]의 값을 가지며 군집성이 0.3 ~ 0.7 일 때, 그래프에서 통계적으로 유의미한 군집을 찾았다고 함.
  (배치모형은 무작위성을 포함하기 때문에 배치모형의 기댓값 활용)

Girvan-Newman 알고리즘
하향식(top-down) 군집 탐색 알고리즘. 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아 제거하자.
다리역할 → 매개 중심성(Betweenness Centrality): 간선이 정점간의 최단 경로에 놓이는 횟수
- 과정
  매개중심성이 높은 간선을 순차적으로 제거
  Girvan-Newman 알고리즘은 간선의 제거 정도에 따라 다른 입도(Granularity)의 군집 구조가 나타남.
  군집성이 최대가 될 때까지 간선을 제거한다
  이 후의, 연결 요소들을 하나의 군집으로 간주

Louvain 알고리즘
상향식(Bottom-up) 군집 탐색 알고리즘. 개별 정점에 시작해 군집 형성.
- 과정
  1. 개별 정점으로 크기 1의 군집으로 부터 시작
  1. 각 정점을 기존 혹은 새로운 군집으로 이동. 이 때 군집성이 최대화 되도록 군집을 결정
  1. 더 이상 군집성이 증가하지 않을 때까지 b 반복
  1. 각 군집을 하나의 정점으로 하는 군집레벨의 그래프를 얻은뒤 c를 수행
    군집레벨 그래프
  1. 한개의 정점이 남을 때 까지 d 반복

중첩이 있는 군집 구조
위에서 배운 군집 알고리즘은 군집간의 중첩이 없다고 가정

중첩군집모형 & 완화된 중첩군집모형
- 가정
중첩군집모형은 각 정점이 군집에 속하거나 속하지 않음을 중간상태로 표현하지 않아, 계산하기 어려움
이를 위해, 완화된 중첩군집모형을 사용해 각 정점이 군집에 속해있는 정도를 실수값으로 표현해, 최적화 기법을 활용해 모형을 탐색할 수 있음