Chapter12. Network Effects and Cascading Behavior
PreviousChapter11. Link Analysis: PageRankNextChapter13. Probabilistic Contagion and Models of influnce
Last updated
Was this helpful?
Last updated
Was this helpful?
많은 것들은 네트워크를 통해 영향력이 퍼져나갑니다. SNS를 생각해보면, 친구의 친구의 친구 소식을 한번에 알지는 않을 것이다. 이처럼 Network는 연속성을 가지고 작용하는 곳들이 있습니다. 지금 당장 유행하는 코로나만 보더라도, 결국 2차 3차 4차 감염 등 시간걸쳐 Spreading됩니다. 이번, 주차는 전반적으로 예시가 많고 사실 내용이 별로 없는 것 같습니다.
*용어정리
Contagion : 전염이 퍼지는 것 ( 유행도 될 수 있고 전염병이 전염되는 것도 Contagion)
Infection event : 전염이 돼서 활성화 된 것
Main Player : 전염이 될 수 있는(Activate 될 수 있는) Node들
*모델 종류 : Probabilistic model vs Decision based Model-> Probabilistic(어휴 이름만들어도 공포스럽네)는 다음시간에!!
Model이 전염되는 것이 확률이 아닌, Deterministic하게 정해지는 것! (투빅스 여러분들은 무슨 의미인지 직관적으로 아시죠?)
payoff matrix : 어떤 두 개가 있을 때, 서로 같은 것을 선택하면 둘다 0보다 큰 이득을 얻지만, 둘 이 다른 것을 선택하면 0의 이득을 얻는 것을 예로 들었습니다. 다만 실제적으로 payoff matrix는 경제학점 개념으로 V/W일 때 한쪽은 이득을 얻고 한쪽은 손해를 보는 구조를 가지고 있습니다.. 여기서는 그냥 둘다 0으로 정의하고 문제를 풉니다!
자 일단 위와 같은 경우(둘다 A를 선택하면 a의 이득 B를 선택하면 b의 이득 다른걸 선택하면 0)일 때 A를 선택했을 때 Payoff는 당연히 a*p*d(d는 Neighbor의 수고, p는 A를 선택한 비율이라고 생각하면 될 것 같습니다)
그러면 B를 선택했을 때 Payoff는 b*(1-p)*d가 되겠죠?
그렇다면 A를 선택하려면 a*p*d > b*(1-p)*d가 되고 이것을 전개하면 위와 같은 식이 됩니다. 너무도 자명합니다! 사실 이것도 그냥 하나의 예시이고 실제로는 이렇게 deterministic하지 않으니 수식이 중요한 건 아니고, payoff 관계, 노드가 변화는 아이디어 등만 얻어가시면 될 것 같습니다.
또다른 Example
만약 내 주변 50프로가 이러한 행동을 한다면, 나도 그런 행동을 한다고 하는 어떤 행동이 있다고 합시다. 어떻게 진행될까요?
스페인의 Anti-austerity protest : ~ 2011년 스페인은 아주 높은 실업률을 기록했고, 이에 반대해서 저항운동이 일어났습니다.
이 때, 트위터는 사람들로 하여금 저항에 참여하게 만들기 위한 수단으로 작용하였습니다. protest에서는 70개의 해시태그가 사용되었죠. 우리는 이 사례를 참조하여 응용사례를 하나 보고합니다.
70개의 해시태그가 포함된 트윗은 약 58만개였고, 약 9만 명의 유저가 그러한 것을 사용하였죠. 트위터에서 서로를 follow한 경우를 하나의 edge(즉 directed를 undirected로 바꾼거죠)로 잡아서 분석을 해보려고합니다.
kin은 내가 저항에 참여하기로 했을 때, 내 이웃의 수이고, ka는 user가 저항에 참여했을 때 저항에 참여하고 있던 유저 수입니다. 즉, 내 주변에 친구들이 몇프로나 이 저항에 참여하는 지를 보고, 내가 참여를 하는 지를 나타낸 그래프라고 생각하시면 됩니다.
ka/kin(이하 임계값)이 0에 가깝다면 이 유저는 Social pressure가 없다고 생각을 하면 됩니다. 만약 임계값이 1에 가까운 우져는 주변의 social pressure를 굉장히 많이 의식한다고 생각할 수 있습니다. (그런데 저는 이게 꼭 correlation이 있다고 생각 하지는 않는데, 일단 그렇다고 생각하도록 하겠습니다.)
이 그래프는 임계값의 분포를 나타낸 그래프입니다. 이 그래프는 두 개의 peak이 존재합니다.
처음부분 : 주변 사람 눈치따위 보지 않고 운동을 시작하는 사람들
0.5 부근 : 절반이 넘어가니 나도 해야겠다는 생각이 드는 부분
이라는 것을 알 수 있습니다.
결과를 좀 더 자세히 보도록 하겠습니다. 이 그래프는 누적확률분포를 나타냅니다. 정확히 말하면 burst ness를 나타낸 것인데, 분모를 ka로 나누고 있습니다. 즉, 특정 시점에서 사람들이 더 많이 참여할 수록 분모가 커짐으로써, 이 누적분포표의 기울기는 작아져야합니다.
실제로 두 번의 급증하는 구간이 존재하는 것을 알 수 있습니다. 사실 생각해보면 말이 안되는 것처럼 보일 수 있지만 로그스케일에 주의하세요!
결국 우리는 그래프를 분석함으로써, 사람들이 영향을 받는 어떤 임계점을 예측할 수 있다는 거죠!
만약 한 유저가 메세지를 tweet하면, follower들이 그 메세지를 다음 time에 트윗합니다. 사실 이 부분은 잘 이해가 가지 않습니다. cascades가 주어지지 않았다고 하는데 time step별로 tweet을 한다면 이건 cascades가 주어진 것 아닌가요.? 다만 여기서 추가로 말한 점은 이러한 경우에 2에서 1의 메세지를 tweet하지 않는다면 이것은 전파가 많이 되지 않고, 아예 끊겨버릴 수 있다는 것입니다.
대부분의 cascade는 성공하지 못한다고 합니다. Size가 커질수록 cascade가 될 확률은 적어지고, 아주 소수의 cascade만이 남게 되죠.
K-core decomposition은, 말 그대로 sub graph내에서 모든 node들이 k개의 degree를 ㄱ자ㅣ고 있는 것을 말합니다. Central Node와 peripheral nodes로 나눠져있으며, 비유를 해보자면면 우리가 유명한 tech 유튜버로부터, 새로나온 삼성폰이 최고의 명 기계라는 소식을 듣습니다. 그래서 나도 아이폰을 구매하고, 내 주변 사람들(기계에 별로 관심이 없는 사람들)이 나에게 영향을 받아 아이폰을 구매한다. 이러한 방식으로 K-core의 rank를 이해해도 좋을 것 같다는 생각이 드네요.
즉 K-core가 높은 것들(Central node)로 부터 시작된 것이 cascade가 높게 나옵니다.
트위터 데이터 요약 : Activation은 처음 시작하는 사람들 / 절반정도 주변사람들이 Activation했을 때 하는 사람들이 많다.
대부분의 cascades는 빨리 죽는다
Cascade가 성공적이려면, Central user에 의해 시작되어야한다(K-core가 높은 유저들)
다음과 같은 상황이 있다고 해봅시다. A-A (a) B-B(b) AB-A (A) AB-B(B) AB-AB MAX(A,B) cost c , 뭐가 많아보이지만 딱 A는 카톡 B는 라인을 예로 잡고 생각해봅시다.
예시를 들어보면 나는 카톡을 씁니다. 제 친구는 라인을 쓰는 친구도 있고 카톡을 쓰는 친구도 있습니다. 난 카톡을 쓰는 친구와 a만큼의 이득을 얻을 수 있겠죠? 근데 내가 라인을 쓴다면 b만큼의 이득을 얻을 수 있을거에요. 다만 카톡을 쓰는 친구와는 메신저를 쓸 수 없겠죠? 그런데 내가 라인과 카톡을 모두 쓰면 어느 친구와도 소통할 수 있지만, 용량도 잡아먹고 두 가지 메신저를 관리해야하기 때문에 상당히 귀찮아 집니다 그러므로 cost가 드는 거죠. 정말 단순하게 이렇게 생각을 하면 됩니다.
다음과 같은 상황을 생각해 봅시다. A와 B 라는 선택지만 있다면 한 명이 A를 쓰기 시작하면 다 A로 갈아 타겠죠? (위와 같은 그림에서) 그런데 AB라는 선택지가 생기게 되면, B를 쓰는 친구들과 A를 쓰는 친구를 연결해주는 친구는 A B를 선택하는것이 최상의 옵션이 됩니다. A나 B중 한 명과 소통을 끊을 필요가 없어지니까요. 그러면 오른쪽은 B를 바꿀 이유가 없습니다. 자기 친구들은 B만 쓰게 되거든요. 그러면 cascade는 끝나게 됩니다.
그런데 이렇게 A의 보상이 커지게 되면, AB인 친구와 소통할 때 B를 쓰는 것보다 A를 쓰는게 더 낫다는 생각이 들게 되고 cascade는 모든 것이 A로 바뀔때까지 지속됩니다. (근데 왜 never stops라고 돼있을까요 ㅠㅠ)
그런데, 이 때 좀 더 general한 케이스를 생각해봅시다. a와 c가 고정이 돼있지 않다고 말이죠. 실제 마케터들은 a와 c값을 조절해서 B를 쓰는 유저들을 A로 넘어오게 만들어버립니다.
다음과 같이 생각할 수 있습니다. a의 보상이 커지면 당연히 a로 갈아타겠지만, c의 cost가 작다면 굳이 B를 버릴 필요가 없기 때문이죠.
AB : a + 1 - c > max(a,1)
B : 1 > max(a,a+1-c)
A : a > max(1, a+1-c)
경우가 많아 보이지만, 사실 저 식 세개를 풀어서 전개하면 위와 같은 그림을 얻을 수 있을 것입니다.(검증은 안해봤지만 맞을거에요 ㅎㅎ)
이 그림을 보면 A가 B랑 호환성을 높게 만들면(즉, c가 낮아지면) B -> AB -> A 로 넘어가지만, 호환성을 낮게 만들면 direct하게 A로 바뀝니다. 애플의 이어폰단자(물론 이건 방수방진 / 구조적문제가 있겠지만)를 생각해보면 쉽게 이해할 수 있을거라고 생각합니다. a를 쓰는 이점이 매우 크기 때문에, 호환성을 낮춰서 B를 버리고 A로 오게 하는거죠.. ㅠㅠ
