Social Network

Social Network

Social Network

사회는 각 사람들을 node로, 사회적 관계를 link로 표현하여 그래프로 나타낼 수 있다.

 

용어

• Connected components : 서로 연결되어 도달 가능한 nodes와 그들 사이의 link들의 집합
• Giant component : connected component 중 가장 큰 component
• Network diameter : 하나의 connected component 내에서 두 node의 shortest path 중 가장 긴 것
• Cluster : 밀집 되어있는 link들의 집합
• Degree : node가 가지는 edge의 수 (친구 수)

 

Social Network의 Quantity에 대한 이슈

• Connected components : 얼마나 많고 얼마나 큰가?
• Network diameter
  
  • small-world phenomenon : giant component에서의 network diameter를 살펴보면 세상이 얼마나 작은지 볼 수 있다. (몇 다리 건너면 다 아는 사이)
  • diameter을 구하기 위한 cost는 얼마나 되는가
• Clustering
  • locality : 같은 community 내에는 link가 모여있다.
  • link가 cluster 내에는 얼마나 많고 다른 cluster 사이에는 별로 없는가
  • 정말 link가 local하게는 많이 연결되어있고 long-distance link는 별로 없는가
  • local과 long-distance connection이 어떻게 상호연관 되는가
• Degree distribution
  
  • 네트워크 내에서 평균 degree는 어느정도인가 
  • 전반적인 distribution은 어떤가 → 사람들은 보통 친구를 얼마나 사귀는가

 

Canonical Natural Network (전형적인 Network)의 특징

• connected components : 적은 수
  • 주로 1개이거나 적은 수의 connected components로 구성된다.
  • 즉, 모두가 서로서로 연결되어있다.
• diameter : 작음
  • network size와 독립적으로 주로 6이다. → 6다리만 건너면 서로서로 아는사이 
  • 네트워크의 사이즈 분포는 log에 비례한다. → 매우 천천히 증가한다.
• degree : 높음
  • random network가 아닌 local하게 서로 연결되어있다.
  • 어느 조직에 들어가면 급격히 아닌 사람이 늘어난다.
  • degree가 높기 때문에 몇 다리만 건너면 아는 사람 이라 diameter가 작다.
• degree distribution : heavy-tailed
  • 적지만 high-degree vertices가 존재한다. (친구가 매우 많은 사람이 존재한다.)
  • power law의 형태를 따른다.

power law distribution (출처 : 위키피디아)