Network models1 - real world network 특징

network model이 필요한 이유

실제 social network data를 구하기 어려움 - 개인정보/보안이슈

(플랫폼 회사내부에서는 분석이 쉬움)

→ 인공적으로 SNS와 유사한 그래프를 만들어서 사용

→ 그러므로 이번 챕터에서는 SNS의 특징을 갖는 그래프를 학습할 예정

 

실제 network와 유사한 데이터를 생성함으로써 얻을 수 있는 3가지

1. cost-efficient: 실제 데이터와 유사한 데이터를 생성하여 분석할 수 있다.

2. 그래프에 대한 수학적 설명을 제시함으로써 real-world data를 더 잘 이해할 수 있다.

3. 다양한 실험을 수행할 수 있다. (controlled experiments)

 

Real-world network의 3가지 특징

1. Power-law Distribution (=Scale-Free network = 파레토 법칙과 유사)

   :node of degree는 Power-law 분포를 따른다.

2. High Clustering Coefficient

3. Small Average Path Length (6steps)

 

 

Degree distribution

power law distribution의 7가지 예

1. Wealth Distribution

2. City population(인구밀집지역)

3. Social Media(소수의 노드만 인기있음)

4. Site Popularity

5. User activity(소수의 유저의 광범위적 활동)

6. Product Price

7. Friendships

 

Power law distribution 수식

d: node degree

a: power-law 상수값

b: power-law 지수값 [2,3] 범위의 내의 값

Pd: degree "d"를 갖는 user의 비율

 

a=1로 가정했을 때,

Pd는 degree가 커질 수록 낮은 확률 값임

→ degree가 높은 user의 확률은 낮음

 

eg) call networks의 Pd는

즉, b=2인 것

하루에 k번의 전화를 받을 전화번호의 비율 

 

Power-law distribution 그래프

b는 고정값

→ degree가 증가할수록 비율은 줄어듬

→  Large instances: extremely rare

 

참고: 기존 power-law distribution에 로그씌운것

y=-ax+b의 형태임

log-log Plot이라 함

 

 

Power-law distribution test

1. 전체 네트워크의 popularity measure를 구해서

2. Pd를 구한 뒤,

3.  log-log plot을 그렸을 때 위와 같은 모양이 나오면

power-law distribution형태를 띈다고 할 수 있음

 

** power-law distribution의 tail은 길다.

 

 

clustering coefficient(대충 넘어가도됨)

: 삼각형 개수 찾기

In real-world networks, friendships are highly transitive.

– Friends of a user are often friends with one another

– These friendships form triads

– High average [local] clustering coefficient

** 다른 인터넷 웹사이트보다 SNS에서 clustering coefficient가 높다.

 

Average Path Length

SNS에서 average path length는 6이다.

소문이 퍼지는 경로.. 6-hops

 

Milgram's experiment

Milgram의 실험에서도 6-hops이 밝혀짐

→ 편지 전달

 

유사한 실험들:

Erdos Number:

논문 평균 4.5번만 통과하면 공저자의 관계임

 

또 다른 real-world networks 특성들

1. Friendship paradox

: 당신의 친구가 당신보다 더 많은 친구들을 가지고 있다. 

2. Core-Periphery Structure(=Jelyfish/Octopus structures)

가운데는 dense core, 주변부는 sparse한 node들로 구성됨