[SMM11] - Infomation Diffusion
Information Diffusion
• Information diffusion: process by which a piece of information (knowledge) is spread and reaches individuals through interactions.
• Studied in a plethora of sciences.
• We discuss methods from
– Sociology, epidemiology, and ethnography
– All are useful for social media mining.
• We focus on techniques that can model information diffusion.
• Sender(s). 확산을 시작하는 사람들(Oreo company)
• Receiver(s). 정보를 받고 다른 사람에게 전달하는 사람들(트위터 사용자)
• Medium. 메세지를 전달하는 매체(트위터, 매체가 꼭 존재하지 않을 수 있음, the medium can be the personal)
Information Diffusion Types
local - 친구를 통해서 전달 (cf. Global)
전염병이 확산될 때는 network 구조가 확실하지 않음
expediting, delaying, or even stopping diffusion as Intervention(간섭하는 활동)
Herd Behavior : 무리 행동
관찰이 가능하고 public imfomation 에 의해서만 확산이 가능함
Ex)
1)온라인 옥션 참여자들은 타인의 옥션 경매를 모니터링 할 수 있음 (profile 정보를 파악할 수 있음)
무리에 의한 행동 : 타인을 따라함
경매에 참여하는 사람들이 인기가 없는 상품에 대해 경매에 참여하는 현상을 볼 수 있음
왜 일어날까?
명명있는 사람이 높은 경매가를 부르면 -> 일반적인 사람들도 경매에 참여해서 경매가가 올라가게 됨
코인, 주식
2) 음식점
Trip advisor 평점에 따라 갔지만 해당 음식점에는 사람이 없지만 옆 가게에 사람이 많으면 A대신 B로 가게 됨
3) Milgram’s Experiment
1사람이 하늘을 보면 지나가는 사람 중 4%만 행동에 동참 했으나, 5명으로 늘어나면 20 % -> 18 명일 때 50%가 하늘을 봄
Main Components of Herd Behavior : 각 개인들간의 connection, 정보를 전달하는 행위, 행위를 task하는 method, 관찰하는 method 등 ex)새들이 날아감, 동물 무리, 스포츠이벤트 사람들 등등
Network Observability in Herb Behavior
complete graph와 유사, 전체적인 정보가 공유될 때 herb behavior 발생
1. There needs to be a decision made.
– In our example, it is going to a restaurant , 하늘을 봄
2. Decisions need to be in sequential order
3. Decisions are not mindless and people have private information that helps them decide 결정할 때 의식적으로 행동
4. No message passing is possible. Individuals don’t know the private information of others, but can infer what others know from what is observed from their behavior.
개
통계학적으로 발생하는 시점 실험 (확률적으로 나타나는 현상)(
바구니에서 공을 꺼내서 색을 확인하고, blue, red인지에 대해 학생들에게 개별로 수행하면 해당 현상이 나타남
• First Student:
– Board: -
• Observed: B -> Guess: B
-or-
• Observed: R -> Guess: R
• Second Student: 두 번째 학생이기 때문에 Herb Behavior x
– Board: B
• Observed: B -> Guess: B
-or-
• Observed: R -> Guess: R/B (flip a coin)
• If board: B, R
– Observed: B -> Guess: B, or
– Observed: R- > Guess: R
내가 꺼낸 공에 상관 없이 선례를 따름
• If board: B, B
– Observed: B -> Guess: B, or
– Observed: R -> Guess: B (Herding Behavior)
The forth student and onward
– Board: B,B,B
– Observed: B/R à Guess: B
Herding Intervention(중단 간섭)
Herding: we only have access to public information
- not accessible before private 정보가 유출되면 herding intervation, When a new piece of private information releases,
Information Cascade
network가 주어지고, network 이웃을 통해 정보가 전달될 때
ex) 어떤 트윗 메세지를 리트윗하는 경우, 친구들을 통해 정보가 확산되는 과정들
Cascade 에서의 정보 확산 과정
ㅇ network directed 구조
ㅇ 연결된 노드들 끼리만 정보 전달 가능
ㅇ Decisions are binary. nodes can
– Active: the node has adopted the behavior/innovation/decision;
행위나 결정을 채택하는 노드
– Inactive
ㅇ An activated node can activate its neighboring nodes; 다른 이웃 노드를 활성화 시킬 수 있음 -> inactive 노드 활성화 시킬 수 있음 (활성화 node(정보를 받은 node))
ㅇ Activation is a progressive process(진행해나가는 과정), where nodes change from inactive to active, but not vice vers(역은 불가능)
Independent Cascade Model (ICM)
보내는 사람 위주의 정보 확산 모델
time t에서 활성화된 노드는, time t+1의 이웃 노드를 활성화시킬 수 있는 기회는 한 번 (active한 노드 sender, 활성화되는 노드 receiver)
ex) 트위터, 페이스북
• Assume v is activated at time t
– For any neighbor w of v, there’s a probability p_vw that node w gets activated at time t + 1.
edge 사이의 값을 가지고 정보를 전달할지 말지를 결정
Maximizing the Spread of Cascades Social Media
정보를 확산시킬 때, 모든 node에 정보를 알려주면 비용이 많이듦.
이를 해결하기 위해 small setup node를 파악하서 그 node에 전달하면 결과적으로 network상의 정보전달이 최대가 되도록 함
Problem Setting
• Given
광고를 하기 위해 주어진 예산 B, 개인 사이 spread 평가
• Goal
정보의 확산을 최대로 투입할 수 있는 방법
• Question
어떤 노드에 정보를 타겟팅해서 전달 할때 전체 네트워크의 유저를 얼마나 많이 보게 할 수 있을 까?
ex)
We need to pick k nodes such that maximum number of nodes are activated
Spread of node set S f(S) : 초기 set에 있는 S로 정보를 전달할 때, 기대할 수 있는 정보 확산 노드 개수
Problem:
– Given a parameter k (budget), find a k-node set S to maximize f(S)
– A constrained optimization problem with f(S) as the objective function
f(S): Properties
1. Non-negative (obviously 양수)
2. Monotone
초기 노드의 initial set이 큰 쪽이 더 크게 나옴(단조 증가)
3. Submodular
– N은 유한한 집합
- A set function is submodular if an
d only if, 필요충분 f : 2^N -> R
2^N은 부분 집합의 개수(N개의 노드로 구성된 network에서의 부분집합)
작은 node에 새로운 노드를 추가했을 때, 훨씬 확산이 잘됨
ㅇ Bad News
practical 시간안에 최적의 해결을 구할 수 없음
ㅇ Good News
– We can use a greedy algorithm (효율성 63% 가짐, 1 − 1/e )
i = 1, j= 5 인 경우, 5 mod 3 = 1 -> 정보전달 x
i = 1, j= 6 인 경우, 5 mod 3 = 2 -> 정보전달 o
S 초기 node를 끄집어 내고 싶은데, k=2로 정해져 있음
| S | S = {1} | S = {2} | S = {3} | S = {4} | S = {5} | S = {6} |
| 이동 가능 경로 | 1 -> 6 6 -> 4 4 -> 2 |
2 x-> 3 | 3 x-> 2 3 x-> 4 3 x-> 6 |
4 -> 2 | 5 x-> 2 5 x-> 4 5 x-> 1 |
6 -> 1 1 x-> 5 6 -> 4 4 -> 2 |
| f(S) | f(S) = 4 | f(S) = 1 | f(S)=1 | f(S) = 2 | f(S)=1 | f(S)= 4 |
S = {6} 이 들어와 있을 때,
1,2,3,4,5 중 또 선택,
| S | S = {6,1} | S = {6,2} | S = {6,3} | S = {6,4} | S = {6,5} |
| 이동 가능 경루 | 6일 경우 6, 4, 1, 2 활성화 추가로 활성화 될 수 있는 node 없음 |
6일 경우 6, 4, 1, 2 활성화 추가로 활성화 될 수 있는 node 없음 |
|||
| f(S) | f(S) = 4 | f(S) = 4 | f(S) = 5 | f(S) = 4 | f(S) = 5 |
3 또는 5를 선택했을 때 최대가 됨
S가 될 수 있는 것은 {6,3} or {6,5}
=>조건에 대해 활성화시키고 cascade 시킴
Intervention
- out-links 개수 제한
- in-links 개수 제안
- activation probability 감소를 통해 활성화되는 노드의 정도를 조절
Diffusion of Innovations
혁신의 확산 이론 왜 확산되고 어떻게 확산되는지
Diffusion of Innovations Models
I. The Iowa Study of Hybrid Corn Seed
The hybrid corn was highly resistant to diseases and other catastrophes such as droughts
Farmers did not adopt it due to its high price and its inability to reproduce
확산 경향
1) Innovators (top 2.5%)
2) Early Adopters (next 13.5%)
3) Early Majority (next 34%)
4) Late Majority (next 34%)
5) Laggards (last 16%)
II. Katz Two-Step Flow Model
