그래프를 바이럴 마케팅에 어떻게 활용할까?

그래프를 바이럴 마케팅에 어떻게 활용할까?¶

---

✅ 의사결정 기반의 전파 모형¶

1️⃣ 언제 의사결정 기반의 전파 모형을 사용할까?¶

1970년대에는 VHS와 Betamax라는 호환되지 않는 두 종류의 비디오 유형이 있다.

• 어떤 유형의 비디오 플레이어를 구매하시겠습니까?
• 의사 결정을 위해 어떤 정보를 참고해야 할까요?

카카오톡 vs 라인

• 카카오톡과 라인 중에 어떤 것을 사용하시고 있나요? 왜 그런 결정을 하셨나요?

📌 두 경우 모두 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다.¶

• 친구들이 대부분 라인을 쓴다면, 카카오톡을 사용하는 것이 불편하다.
• 친구들이 대부분 VHS유형을 쓴다면, 같은 유형을 써야 서로 비디오를 빌려줄 수 있다.

주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용한다.
🔎 가장 간단한 형태의 의사결정 기반의 전파 모형인 선형 임계치 모형(Linear Threshold Model)을 살펴보자.

2️⃣ 선형 임계치 모형¶

📌 친구 관계의 두사람 𝑢와𝑣를 가정하자. 둘은 두 개의 호환되지 않는 기술 𝐴와 𝐵중에서 하나를 선택해야한다.¶

• 둘 모두 𝐴기술을 사용할 경우, 행복이 𝑎만큼 증가한다.
• 둘 모두 𝐵기술을 사용할 경우, 행복이 𝑏만큼 증가한다.
• 하지만, 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않는다.

📌 소셜 네트워크를 고려해 보자¶

우리는 동시에 여러 사람과 친구 관계를 맺는다. 각각의 친구, 즉 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 고려해야한다.

• 위 예시에서 𝑢가 𝐴를 선택할 경우, 행복이 2𝑎만큼 증가한다.
• 위 예시에서 𝑢가 𝐵를 선택할 경우, 행복이 3𝑏만큼 증가한다.

📌 각자가 행복이 최대화되는 선택을 한다고 가정해 보자¶

• 만약, 2𝑎>3𝑏 라면 𝑢는 𝐴를 택할 것이다.
• 반면, 2𝑎<3𝑏 라면 𝑢는 𝐵를 택할 것이다.
• 편의상2𝑎=3𝑏 라면 𝑢는 𝐵를 택한다고 하자.

📌 좀 더 일반화 해 보자¶

📍 $p$비율의 이웃이 A를 선택했다고 해보자. 즉, $1-p$ 비율의 이웃이 B를 선택하게 된다

언제 A를 선택하게 될까??

• $ap > b(1-p)$일 때 이다.

정리하면 $p > {b \over a+b}$ 일때 이다. 편의상 ${b \over a+b}$를 임계치 $q$라고 하자.
이 모형을 선형 임계치 모형(Linear Threshold Model)이라고 하고 각 정점은 이웃 중 A를 선택한 비율이 임계치 $q$를 넘을 때만 A를 선택한다.

이 모형은 전부 B를 사용하는 상황을 가정하고 처음 A를 사용하는 얼리 어답터들을 가정한다. 시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 A를 고수한다고 가정한다. 파란색은 B, 빨간색은 A를 선택한 상황이다.

📌 임계치 q는 55%를 가정하고 u와 v가 시드 집합인 상황이다. 이때 u,v의 선택을 고려하여 다른 이웃들의 선택이 어떻게 바뀌는지 확인해 보자.¶

각각 주변 A의 비율를 계산하여 임계치 55%이상이 정점은 A를 선택하게 되고 위와 같이 바뀌게 된다.

위 단계를 계속 진행하게 되면 최종적으로 위와 같은 선택이 최종으로 나타난다.

✅ 확률적 전파 모형¶

1️⃣ 언제 확률적 전파 모형을 사용할까?¶

📌 코로나의 전파 과정을 수학적으로 추상화해 보자¶

• 의사결정 기반 모형은 적합하지 않다. 누구도 코로나에 걸리기로 "의사결정"을 내리는 사람은 없기 때문이다.
• 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야한다.

2️⃣ 독립적 전파 모형¶

📌 방향성이 있고 가중치가 있는 그래프를 가정해 보자¶

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

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

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

📌 모형은 모델은 최초 감염자들로부터 시작합니다.¶

• 이전 모형과 마찬가지로 첫 감염자들을 시드 집합(Seed Set)이라고 부른다.
  

• 각 최초 감염자 𝑢는,각 이웃 𝑣에게 $p_{uv}$확률로 병을 전파한다.

• 위 과정을 새로운 감염자 각각에게 반복한다.
• 위 과정을 새로운 감염자 각각에게 반복한다.
  …
• 더 이상 새로운 감염자가 없으면 종료한다.

감염자는 계속 감염자 상태로 남아있는 것으로 가정
감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파 모형도 있다.

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

1️⃣ 시드 집합의 중요성¶

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

2️⃣ 전파 최대화 문제¶

📌 시드 집합을 우리가 선택할 수 있다면, 누구를 선택할까?¶

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

📌 전파 최대화 문제는 굉장히 어려운 문제이다.¶

• 그래프에 $|V|$개의 정점이 있을 경우, 시드 집합의 크기를 $k$개로 제한하더라도 경우의 수는 ${|V| \choose k}$개 이다.
• 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명 되었다.

3️⃣ 정점 중심성 휴리스틱¶

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

• 즉, 시드 집합의 크기가 $k$개로 고정되어 있을때, 정저믜 중심성이 높은 순으로 $k$개 정점 선택하는 방법
• 정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있다.
• 합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없다.

4️⃣ 탐욕 알고리즘¶

📌 탐욕 알고리즘(Greedy Algorithm) 역시 많이 사용한다.¶

탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택한다. 정점의 집합을 $\{1, 2, ..., |V|\}$라고 할 경우 구체적인 단계는 다음과 같다.

• 집합 $\{1\}, \{2\}, ..., \{|V|\}$를 비교하여, 전파를 최대화하는 시드 집합을 찾는다. 이 때, 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균 값을 사용하고 뽑힌 집합을 $\{x\}$라고 하자.

• 집합 $\{x,1\}, \{x,2\}, ..., \{x,|V|\}$를 비교하여, 전파를 최대화하는 시드 집합을 찾고 뽑힌 집합을 $\{x,y\}$라고 한다.

• 집합 $\{x,y,1\}, \{x,y,2\}, ..., \{x,y,|V|\}$를 비교하여, 전파를 최대화하는 시드 집합을 찾고 뽑힌 집합을 $\{x,y,z\}$라고 한다.

위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복한다.
즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고 근시안적으로 최초 전파자를 선택하는 과정을 반복한다.

📌 탐욕 알고리즘은 얼마나 정확한가?¶

독립 전파 모형에 경우, 이론적으로 정확도가 일부 보장된다. 항상 입력 그래프와 무관하게 다음 부등식이 성립한다.

✅ 전파 모형 시뮬레이터¶

1️⃣ 독립적 전파 모형 시뮬레이터¶

라이브러리 로드¶

In [1]:

# 실습에 필요한 library를 import하고 그래프 및 변수를를 초기화합니다.
import networkx as nx
import matplotlib.pyplot as plt
import random

import os
import os.path as osp

방향성이 있고 가중치가 있는 그래프를 파일에서 읽어온다¶

In [2]:

G = nx.DiGraph()
data='../실습코드/data/lab/lab4/simple_weighted_directed_graph.txt'
f = open(data)
# line_split = (간선이 나가는 정점, 간선이 들어가는 정점, 가중치)
for line in f:
    line_split = line.split()
    src = int(line_split[0])
    dst = int(line_split[1])
    w = float(line_split[2])
    G.add_edge(src, dst, weight=w)

시드 집합, 즉 최초 전염자를 지정한다. 0번 정점을 최초 전염자로 지정¶

In [3]:

# 독립적 전파 모델이 전파되는 과정을 draw하는 함수입니다.
def draw(G: nx.Graph, affected: set(), used: set()) -> None:
    pos = {
            0:[0.5, 0.8], 1: [0.1, 0.5], 2:[0.2, 0.2],
            3:[0.8, 0.7], 4: [0.7, 0.4], 5:[0.45, 0.45],
            6:[0.6, 0.1], 7:[0.9, 0.35], 8:[0.7, 0.1]
    }
    
    nodeColorList = []
    nodeList = []
    for i in range(len(G.nodes)):
        nodeList.append(i)
        if i in affected:
            nodeColorList = nodeColorList + ['red']
        else :
            nodeColorList = nodeColorList + ['blue']
    im = nx.draw_networkx_nodes(G, pos, nodelist = nodeList, node_color=nodeColorList, node_size=100)
    edgeList = []
    edgeColorList = []
    for edge in G.edges:
        edgeList.append(edge)
        if edge in used:
            edgeColorList = edgeColorList + ['red']
        else :
            edgeColorList = edgeColorList + ['blue']
    nx.draw_networkx_edges(G, pos, edgelist = edgeList, edge_color = edgeColorList)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color="black")
    plt.show()

In [4]:

# 시드 집합, 즉 최초 전염자를 지정합니다
affected = set()                         # 그래프의 정점 중 시드 집합을 초기화 합니다.
affected_new = set({0})
used_edge = set()                       # 전염을 시도한 간선들을 set으로 관리합니다. (그림을 그릴 때 사용)
draw(G, affected | affected_new, used_edge) # 그래프의 초기 상태를 그립니다. 빨간색 : 감염된 정점 및 간선, 파란색 : 감염되지 않은 정점 및 간선

독립적 전파 모형을 시뮬레이션¶

In [5]:

# 독립적 전파 모형을 시뮬레이션 합니다.
while len(affected_new) != 0:
    temp = set()
    for src in affected_new:
        neighbors = G.neighbors(src)
        for dst in neighbors:
            if (dst not in affected) and (dst not in affected_new):
                p = random.uniform(0, 1)
                if p < G.edges[src, dst]["weight"]:
                    temp.add(dst)
                used_edge.add((src, dst))
    affected = affected | affected_new
    affected_new = temp
    draw(G, affected, used_edge)

2️⃣ 선형 임계치 모형 시뮬레이터¶

방향성이 없고 가중치도 없는 그래프 읽어오기¶

In [6]:

#선형 임계치 모형 시뮬레이터 

# 사용할 방향성이 없고 가중치도 없는 그래프를 읽어 불러옵니다.
G = nx.Graph()                                                                                              
data = '../실습코드/data/lab/lab4/simple_undirected_graph.txt'  
f = open(data)
# linew_split = (간선이 나가는 정점, 간선이 들어가는 정점)
for line in f:
    line_split = line.split()
    src = int(line_split[0])
    dst = int(line_split[1])
    G.add_edge(src, dst)

시드 집합, 즉 얼리 어답터를 지정한다. 4,5번 정점을 얼리 어답터로 지정하였다.¶

In [7]:

# 선형 임계치 모형이 전파되는 과정을 그리는 함수입니다.
# networkx graph와 감염된 정점 리스트(affected)를 받아서 그림을 그립니다.
# 생략하고 넘어가셔도 좋습니다.

def draw(G: nx.Graph, affected: set()) -> None:
    pos = {
            0:[0.5, 0.8], 1: [1, 0.85], 2:[1.2, 0.9],
            3:[0.3, 0.6], 4: [0.7, 0.6], 5:[1.3, 0.6],
            6:[1.5, 0.7], 7:[0.6, 0.2], 8:[1.2, 0.3],
            9:[1, 0.1], 10:[0.4, 0.1]
    }
    
    nodeColorList = []
    nodeList = []
    for i in range(len(G.nodes)):
        nodeList.append(i)
        if i in affected:
            nodeColorList = nodeColorList + ['red']
        else :
            nodeColorList = nodeColorList + ['blue']
    im = nx.draw_networkx_nodes(G, pos, nodelist = nodeList, node_color=nodeColorList, node_size=100)
    nx.draw_networkx_edges(G, pos)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color="black")
    plt.show()

In [8]:

# 시드 집합, 즉 얼리 어답터를 지정합니다.
team_A = set({4, 5})                                                                                                              
team_B = set([v for v in G.nodes if v not in team_A])
draw(G, team_A)  

선형 임계치 모형 시뮬레이션¶

In [9]:

# 선형 임계치 모형을 시뮬레이션 합니다.
threshold = 0.5
while True:
    new_A = set()
    for v in team_B:
        neighbors = list(G.neighbors(v))
        neighbors_A = [v2 for v2 in neighbors if v2 in team_A]
        if len(neighbors_A) / len(neighbors) > threshold:
            new_A.add(v)
    if len(new_A) == 0:
        break
    team_A = team_A | new_A
    team_B = team_B - new_A
    draw(G, team_A)