[22-1] 그래프 전파 모형

1️⃣ 선형 임계치 모형 

 

주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용합니다.

그중 가장 간단한 형태의 의사결정 기반의 전파 모형인 선형 임계치 모형(Linear Threshold Model)에 대해 알아봅니다.

 

예를 들어, 친구 관계의 두 사람 𝑢와 𝑣를 가정합시다.

둘은 두 개의 호환되지 않는 기술 𝐴와 𝐵 중에서 하나를 선택합니다.

 

둘 모두 𝐴 기술을 사용할 경우, 행복이 𝑎만큼 증가합니다.

둘 모두 𝐵 기술을 사용할 경우, 행복이 𝑏만큼 증가합니다.

하지만, 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않습니다.

 

https://www.edwith.org/bcaitech1

 

만약, 아래 그림에서 𝑢가 𝐴를 선택할 경우 행복이 2𝑎 만큼 증가합니다.

대신 𝑢가 𝐵를 선택할 경우 행복이 3𝑏 만큼 증가합니다.

 

https://www.edwith.org/bcaitech1

 

각자가 행복이 최대화되는 선택을 한다고 가정해봅시다.

 

만약, 2𝑎 > 3𝑏 라면 𝑢는 𝐴를 택할 것입니다.

반면, 2𝑎 < 3𝑏 라면 𝑢는 𝐵를 택할 것입니다.

편의상 2𝑎 = 3𝑏 라면 𝑢는 𝐵를 택한다고 합시다.

 

그렇다면 좀 더 일반화해봅시다.

 

𝑝 비율의 이웃이 𝐴를 선택했다고 해봅시다.

즉, 1 − 𝑝 비율의 이웃이 𝐵를 선택했습니다.

 

https://www.edwith.org/bcaitech1

 

그렇다면 𝑢가 A를 선택할 때는 다음과 같습니다.

 

$a \cdot p \cdot N$ > $b \cdot (1-p) \cdot N$ (여기서 N은 이웃의 수)

 

하지만 N은 같으므로 생략해서 다음과 같이 표시할 수 있습니다.

 

$a \cdot p$ > $b \cdot (1-p)$

 

즉, p를 중심으로 정리하면 다음과 같습니다.

 

$$p > \frac {b} {a+b}$$

 

여기서 $\frac {b} {a+b}$는 임계치 $q$입니다.

 

이 모형을 선형 임계치 모형(Linear Threshold Model)이라고 합니다.

 

각 정점은 이웃 중 𝐴를 선택한 비율이 임계치 𝑞를 넘을 때만 𝐴를 선택합니다.

 

이 모형은 전부 𝐵를 사용하는 상황을 가정합니다.

그리고 처음 𝐴를 사용하는 얼리 어답터들을 가정합니다.

시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 𝐴를 고수한다고 가정합시다.

 

 

예를 들어, 임계치 𝑞는 55%를 가정했을 때 아래 그림과 같이 𝑢와 𝑣가 시드 집합입니다.

 

https://www.edwith.org/bcaitech1

 

여기서 𝑢와 𝑣 근처에 있는 4개의 node가 추가로 A를 선택했습니다.

이웃 중 𝐴를 선택한 비율이 임계치 55%를 넘었기 때문입니다.

 

https://www.edwith.org/bcaitech1

 

다음에는 추가로 1명이 𝐴를 선택했습니다.

 

https://www.edwith.org/bcaitech1

 

계속 전파가 퍼지다가 어느 순간 전파가 멈추게 됩니다.

바로 두 Node의 임계치 55%가 넘지 않고, 더 이상의 Node를 전파하지 못하기 때문입니다.

 

https://www.edwith.org/bcaitech1

 

 

2️⃣ 독립 전파 모형

 

'의사 결정'을 내리는 사람이 없는, 확률적 과정을 확률적 전파 모형이라고 합니다.

그중 가장 간단한 형태의 의사결정 기반의 전파 모형인 독립 전파 모형(Independent Cascade Model)에 대해 알아봅니다.

 

방향성이 있고 가중치가 있는 그래프를 가정합시다.

각 간선 (𝑢, 𝑣)의 가중치 $p_{uv}$는 𝑢가 감염되었을 때 (그리고 𝑣가 감염되지 않았을 때) 𝑢가 𝑣를 감염시킬 확률에 해당합니다. 즉, 각 정점 𝑢가 감염될 때마다, 각 이웃 𝑣는 $p_{uv}$ 확률로 전염됩니다.

 

https://www.edwith.org/bcaitech1

 

서로 다른 이웃이 전염되는 확률은 독립적입니다.

𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑢가 감염되었을 때 𝑢가 𝑤를 감염시킬 확률과 독립적입니다.

𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑤가 감염되었을 때 𝑤가 𝑣를 감염시킬 확률과 독립적입니다.

 

모형은 모델은 최초 감염자들로부터 시작합니다. 첫 감염자들을 시드 집합(Seed Set)이라고 부릅니다.

 

 

 

3️⃣ 전파 최대화 문제

 

앞서 소개한 전파 모형들에서도 시드 집합이 전파 크기에 많은 영향을 미칩니다.

 

선형 임계치 모형의 예시에서 시드 집합으로 𝑢와 𝑣를 선택했을 때, 총 9명이 𝐴를 선택했습니다.

 

https://www.edwith.org/bcaitech1

 

만약, 시드 집합으로 𝑥와 𝑦를 선택했다면, 추가 전파는 발생하지 않습니다. 2명만이 𝐴를 선택했습니다.

 

https://www.edwith.org/bcaitech1

그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다

 

전파 최대화 문제는 굉장히 어려운 문제입니다. 전파 최대화 문제는 NP-hard이기 때문이죠.

그래프에 |𝑉|개의 정점이 있을 경우, 시드 집합의 크기를 𝑘개로 제한하더라도 경우의 수는 ${|𝑉| \choose 𝑘}$ 개입니다.

( ${|𝑉| \choose 𝑘} = _{|V|}\mathrm{C}_{k} = \frac {|V|!} {k! (|V|-k)!}$ )

 

따라서 heuristic이라는 개념을 사용합니다.

heuristic (휴리스틱)은 실험적으로는 잘 동작할 수 있지만, 이론적으로는 어떠한 보장도 할 수 없는 알고리즘을 의미합니다.

 

대표적 휴리스틱으로 정점의 중심성(Node Centrality)을 사용합니다.

 

즉, 시드 집합의 크기가 𝑘개로 고정되어 있을 때, 정점의 중심성이 높은 순으로 𝑘개 정점 선택하는 방법입니다.

 

정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있습니다.

 

• 연결 중심성 : 연결성이 높은 정점들이 높은 중심성을 가짐
• 근접 중심성 : 다른 정점들로의 평균 거리를 측정한 뒤 그 평균 거리가 작은 정점들이 높은 근접 중심점을 갖는 것
• 매개 중심성 : 정점 간 최단 경로를 고려, 그리고 그 최단 경로에 많이 놓이는 정점일수록 많은 정점 쌍을 연결하는 역할을 하기 때문에 매개 중심성이 높음

이러한 방법이 합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없습니다.

 

 

4️⃣ 탐욕 알고리즘

 

탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한 번에 한 명씩 선택합니다.

 

즉, 정점의 집합을 {1, 2, … , |𝑉|}라고 할 경우 구체적인 단계는 다음과 같습니다.

집합 {1},{2}, … ,{|𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다.

이때, 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균값을 사용합니다.

뽑힌 집합을 {𝑥} 라고 합시다.

 

집합 {𝑥, 1},{𝑥, 2}, … ,{𝑥, |𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다 ( 총 |𝑉|-1 개의 집합)

뽑힌 집합을 {𝑥, 𝑦} 라고 합니다. 즉, $y$를 두 번째 전파자로 선택했습니다.

 

집합 {𝑥, 𝑦, 1}, {𝑥, 𝑦, 2}, … ,{𝑥, 𝑦, |𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다.

뽑힌 집합을 {𝑥, 𝑦, 𝑧}라고 합시다. 즉, $z$를 세 번째 전파자로 선택했습니다.

 

위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복합니다.

 

즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고 근시안적으로 최초 전파자를 선택하는 과정을 반복합니다. 이러한 한계 때문에 탐욕 알고리즘은 전파를 최대화하는 시드 집합을 반환한다는 보장이 없습니다.

 

다만, 독립 전파 모형에 경우, 이론적으로 정확도가 일부 보장됩니다.

입력 그래프와 무관하게 다음 부등식이 성립합니다.