작성자 : 이예진

Contents

0. Intro: Spreading Through Networks
1. Decision Based Model of Diffusion
2. Application: Modeling protest recruitment on social networks
3. Extending the Model: Allow People to Adopt A and B
4. Summary & PREVIEW

---

Network Effects and Cascading Behavior

0. Intro: Spreading Through Networks

Keyword
cascade,diffusion,game theoretic model, k-core decomposition

12강은 제목 그대로 Network Effect와 Cascading Behavior에 대해 배웁니다. Spreading Through Networks에는 다음과 같은 분야들이 있습니다. '행동' 들은 network안에서 node에서 node로 흐릅니다(cascade).

Spreading Through Networks

• Cascading behavior
• Diffusion of innovations
• Netsork effects
• Epidemics

Example

• Biological: 전염병
• Technological
  - Cascading failures
  - Spread of information
• Social
  - Rumors, news, new technology
  - Viral marketing

-> Twitter & Facebook posh sharing(repost) 와 상품 추천 등이 해당

Network Cascades(and Terminology)

• contagion
• cascade
• infection event : Adoption, infection, activation
• main players : infected/active nodes, adopters

---

확산(Diffusion)을 어떻게 model로 만들까?

의사결정(decision making)여부에 따라 Decision based model 과 Probabilistic model 이 있습니다. 오늘은 Decision based model에 대해서만 알아보도록 하겠습니다.

---

1. Decision Based Model of Diffusion

Decision Based Model은 기본적으로 게임이론을 이용합니다.

Game Theoretic Model of Cascades

• 2명의 player가 각각 선택A나 선택B를 하는 의사결정 상황
• 만약 친구들이 내가 한 선택과 같은 선택을 한다면 더 많은 이득을 얻음
• ex. BetaMax vs VHS , BlueRay vs HD DVD
  
  

The Model for Two Nodes

payoff matrix

• v와 w가 모두 행동A를 선택하면 payoff a>0 획득
• v와 w가 모두 행동B를 선택하면 payoff b>0 획득
• v와 w가 서로 반대 선택을 하면 각각 0 획득

-> payoff는 여러 게임에서 보상의 합계로 계산
-> 큰 네트워크에서 각 node v는 근처 이웃의 행동을 따라하게 된다.

Calculation of Node v

쉽게 말해서 보상 받는 pay를 고려한 다수결의 선택을 합니다. (보수는 같을 수도, 다를 수도)

Example Scenario

Scenario

• Graph 안에 모두는 B에서 시작한다.

• 작은 집단 S들만 A를 일찍 적용한다. (Small set S of early adopters of A)
  - Hard-wire S : 보상에 상관없이 꾸준히 A만 선택 (꾸준하게 애플만 선택하는 앱등이)

• 내 친구 중 50% 이상이 A를 선택하면, 나도 A를 선택한다.(보상 a와 b가 거의 같은 상황인 것)

이게 Cascade입니다. 나(node)는 보상에 충실한 선택(친구따라) 선택했을 뿐인데, 결과적으로 다른 노드에 영향을 주었습니다*

2. Application: Modeling protest recruitment on social networks

The Dynamics of Protest Recruitment through an Online Network
Bailon et al. Nature Scientific Reports, 2011

cascade 사례를 보기위해서 스페인에서 일어난 긴축방지 시위(The Spanish 'Indignados' Movement)를 예시로 보겠습니다.

Twitter를 사용해서 모이고 모바일 유저들이 참여했습니다. #indignados_movement

(1) Data collected using hashtags

sns를 사용한 운동이었기 때문에 관련 해시태그를 모두 크롤링하고 그 중에 70개의 주요해시태그를 선택했습니다.

(2) Dataset

• 1달 동안 주요 해시태그가 포함된 트윗(tweets)을 수집했습니다. 결과적으로 581,750개의 트윗을 사용했습니다.
• 관련 사용자 데이터도 수집했습니다. tweet을 언급한 사람 + 그 사람의 followers 결과적으로 87,569의 유저 데이터를 사용했습니다.
• 2개의 network를 만들었습니다.
  1. Full network : with all Twitter follow links (directed)
  2. Symmetric network : with only the reciprocal follow links (strong connections only, i<->j)(undirected)

(3) Definitions

• User activation time : Moment when user starts tweeting protest messages (첫 순간, 언제 시작했는지)
• $k_{in}$ = The total number of neighbors when a user became active
  - 유저가 active 시작할 당시 모든 이웃 수
• $k_{a}$ = Number of active neighbors when a user
  - 유저가 active 시작할 때 active 이웃 수
• Activation threshold = $k_{a}/k_{in}$
  - $0 < k_{a}/k_{in} < 1$
  - 마법의 tradeoff는 없고 상황이나 데이터에 따라 알아내야함

(4) Recruitment & Activation Threshold

• $k_{a}/k_{in}\approx 0$
  - 주변에 active 이웃 없는데 active하는 상황
  - no social pressure
• $k_{a}/k_{in}\approx 1$
  - 주변 이웃이 모두 active
  - high social pressure
  

(5) Result & significant

---

성공하는 cascade는 누가 시작하나?

성공하는 cascade는 소수입니다. 네트워크에서 더 중앙에 있는 starter일수록 성공할까요? 성공하는 특정 player들에 대해서 알아보겠습니다. 방법은 k-core decomposition을 사용합니다.

---

k-core decomposition

• k-core : 모든 노드가 적어도 차수 k개를 가진 연결성이 큰 subgraph.
• Method : k보다 작은 차수를 가진 node를 반복적으로 제거해나간다.
• Higher k-core number of a node means it is more central
  
  

Summary : Cascades on Twitter

• Uniform activation threshold for users, with two local peaks
• Most cascades are short
• Successful cascades are started by central (more core) users

3. Extending the Model: Allow People to Adopt A and B

Decision based model을 multiple contagions가 가능하도록 확장한 모델에 대해서 알아보겠습니다.

Extending the model

• extra strategy "AB"를 추가합니다.
• 한 player가 선택 A와 B를 모두 하는 것을 허용합니다.
  - AB-A : gets a
  - AB-B : gets b
  - AB-AB : gets max(a,b)
  - cost c : AB라는 선택을 하면 cost c만큼의 비용을 지불해야합니다. 모든 보상과 비용을 합산합니다.

Cascades & Compatibility: Model

• 모든 node들은 infinite network에 있고 B로 시작합니다.
• finite set S만 A를 선택합니다. (앱등이)
• Run the model for t=1,2,3,...
  - Each node selects behavior that will optimize payoff(t-1시점에서 이웃이 선택한 상황이 주어지고 t에서 내가 선택)
  

언제 선택 B에서 A나 AB로 바꿀까?

(1) B -> AB : 3+2-1=4, 전에는 2를 받았다면 이제 4를 받기 때문에 AB선택할 것이다. 하지만 A가 흐르는 모습은 볼 수 없다.

(2) 보상이 바뀜 : 보상이 바뀌면서 A가 흐르게 된다. A를 선택함으로써 얻는 보상을 크게 해서 점점 A나 AB로 선택을 바꿨다.

General case

보상과 비용에 따라 선택이 달라지기 때문에 일반화 해봅시다.
어떻게 (c,a)를 설정해야 B로 시작하는 곳에서 A가 퍼질 수 있을까요?

• infinite path, start with all B
• payoffs for w : A:a, B:1, AB:a+1-c

(c,a) 에 대해서 x축 = a, y축 = b로 두고 그래프를 그리면 다음과 같습니다.

(1) 기본

(2) change payoff : b보상을 늘림

(3) 두 결과를 합침

lesson

좋은 A나 나올 때까지 디폴트가 B인 상황

• Infilteration : too compatibel
  - B가 호환가능성이 높으면 사람들은 두개 다 해보고 더 나쁜 것 (B)를 버릴것

• Direct conquest : not compatible
  - A가 호환되지 않는 경우, 경계에 있는 사용자가 선택. 더 좋은 것을 고름. 더 좋은 (A)를 선택 할 것

• Buffer zone
  - 최적인 상태를 고르는 경우, A와 B사이가 정적인 buffer 가 유지됨

이 그림을 보면 A가 B랑 호환성을 높게 만들면(즉, c가 낮아지면) B -> AB -> A 로 넘어가지만, 호환성을 낮게 만들면 direct하게 A로 바뀝니다. 애플의 이어폰단자를 생각해보면 쉽게 이해할 수 있을거라고 생각합니다. a를 쓰는 이점이 매우 크기 때문에, 호환성을 낮춰서 B를 버리고 A로 오게 하는거죠.. ㅠㅠ
(갓진혁의 정리중...발췌)

4. Summary & PREVIEW

Cascade의 기본 개념과 용어에 대해 알아보고, Diffusion(cascade)를 모델링 하는 방법 두 가지 중에 decision based model에 대해서 배웠습니다. decision based model은 게임이론이 베이스가 되고 기본형과 확장형이 있었습니다.

Reference

Stanford CS224W 2019
https://tobigs.gitbook.io/tobigs-graph-study/chapter12.