12. Network Effects and Cascading Behavior

tobigsGNN·2021년 3월 22일
3

CS224W Review

목록 보기
12/18
post-thumbnail

작성자 : 이예진

Contents

  1. Intro: Spreading Through Networks
  2. Decision Based Model of Diffusion
  3. Application: Modeling protest recruitment on social networks
  4. Extending the Model: Allow People to Adopt A and B
  5. 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 modelProbabilistic 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

  • vw가 모두 행동A를 선택하면 payoff a>0 획득
  • vw가 모두 행동B를 선택하면 payoff b>0 획득
  • vw가 서로 반대 선택을 하면 각각 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 (첫 순간, 언제 시작했는지)
  • kink_{in} = The total number of neighbors when a user became active
    - 유저가 active 시작할 당시 모든 이웃 수
  • kak_{a} = Number of active neighbors when a user
    - 유저가 active 시작할 때 active 이웃 수
  • Activation threshold = ka/kink_{a}/k_{in}
    - 0<ka/kin<10 < k_{a}/k_{in} < 1
    - 마법의 tradeoff는 없고 상황이나 데이터에 따라 알아내야함

(4) Recruitment & Activation Threshold

  • ka/kin0k_{a}/k_{in}\approx 0
    - 주변에 active 이웃 없는데 active하는 상황
    - no social pressure
  • ka/kin1k_{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가 선택 AB모두 하는 것을 허용합니다.
    - 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 SA를 선택합니다. (앱등이)
  • 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.

profile
2021 투빅스 GNN 스터디

2개의 댓글

comment-user-thumbnail
2021년 3월 27일

behaviornetwork 안에서 전파됩니다. ( cascading )

생활 속의 cascading 예시로는, 전염병, 기술의 전파, Viral Marketing 등이 있습니다.
하나의 node 에서 시작되어, 이웃 node로 전달되고, 전달 받은 node 가 또 전달하는 형식으로 behavior 가 전파되게 됩니다. (propagation tree)

확산을 모델링 하는 Diffusion Model 방법론은 두 가지가 있습니다.

  1. Decision Based Model
    • 전파 여부를 결정할 수 있는, Decision Making 선택권이 있는 모델
    • ex. 기술 채택, 물건 구매 결정
  2. Probablistic Model
    • 결정권이 없는, 확률에 의해 전파 여부가 결정되는 모델
    • ex. corona .....

이번 강의에서 공부하는 model 은 Decision Based Model 입니다.


1. Decision Based Model of Diffusion

Decision Based Model 은 Game Theory 개념을 바탕으로 진행됩니다.

대부분의 사람들이 선택하는 방향으로 선택하는 것이 더 많은 이익 (payoff) 을 얻게 되므로, 보상을 고려한 다수결의 선택을 하게 됩니다.

이웃 node 의 50% 이상이 빨간색을 선택하고 있다면, 빨간색으로 선택을 하게 됩니다. 위의 그림처럼 이웃 node 의 선택에 따라 선택을 바꾸게 되고, 점점 빨간색 선택이 전파되게 됩니다.


전파의 양상을 살펴보기 위해서는, Threshold 를 설정해 판단합니다.

스페인 긴축방지 시위 예시에서는, Activation Threshold = kak_{a} / kink_{in} 를 통해 사회 현상을 판단했습니다.

  • kink_{in} : user 가 active 를 시작할 때 모든 이웃의 수
    kak_{a} : user 가 active 를 시작할 때 active 한 이웃의 수
  • kak_{a} / kin0k_{in} \approx 0 : no social pressure
  • kak_{a} / kin1k_{in} \approx 1 : high social pressure

k-core decomposition

k-core 는 모든 node 가 적어도 k개의 degree 를 가진 subgraph 를 말하며, high k-core number 를 가질수록 전파에 성공할 가능성이 높은 node 라고 합니다.


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

A 혹은 B 라는 두 가지 선택만을 고려하지 않고, A와 B 모두 선택할 수 있는 AB 선택지를 추가합니다.
AB 선택 시 max(a,b) payoff 를 얻을 수 있지만, cost c 를 지불하게 됩니다.

A 선택이 전파되는 양상을 보고 싶을 때, Path Graph 를 통해 순서대로 node 값을 바꾸고, 얻는 보상을 바꾸어 가며 전파 양상을 볼 수 있습니다.
원하는 대로 전파되지 않을 시 A에 대한 payoff 값을 크게 하는 방향으로 조정합니다.

(c,a) (c : cost & a : A payoff) 선택 여부에 따라 달라지는 일반적인 양상은 위와 같습니다.


머쨍이 지니님 ~ 띵강 넘넘 감사함니당 ~ (하트) * 100

답글 달기
comment-user-thumbnail
2024년 9월 15일

It was a chilly Wednesday evening, and I was in the mood to unwind. I logged into my favorite blackjack site, feeling somewhat skeptical after a string of losses earlier that week. My luck seemed to change when I joined a table with a friendly group of players. The dealer was engaging and kept the atmosphere https://madnixcasinofrance.com/ light, which helped me focus. Despite a rocky start where I was down to my last $20, I decided to stick with it. The next few hands turned out to be pivotal. I started to catch breaks, winning crucial hands that pulled me out of the red. In a dramatic turnaround, I managed to recoup all my losses and then some, ending up with a respectable profit. It was a reminder that in blackjack, fortunes can change in an instant, and persistence can truly pay off.

답글 달기