SNS Network measures를 하는 이유
1. Who are the central figures (influential individuals) in the network?
– 중심도 파악을 위해(Centrality)
2. What interaction patterns are common in friends? (interaction pattern을 찾기위해- level of interaction)
– Reciprocity(상호성) and Transitivity
– Balance and Status
3. Who are the like-minded users and how can we find these similar individuals?
– Similarity(유사도 측정을 위해)
Centrality
다른노드의 관점에서 centrality가 측정됨
(즉, 내 SNS는 나의 주변 노드들을 통해 centrality가 측정 됨)
Degree centrality: ranks nodes with more connections higher in terms of centrality
아래그림에서 v1의 Degree centrality(length-1)는 8
V2의 Degree centrality(length-1)는 1임
(length-2)는 바로 연결된 것이 아닌,
이웃의 이웃까지 보고 정의하는 것
방향성이 있을 때, degree centrality
여기서 vi의 in-degree=3, out-degree=2,
total은 5임
in-degree가 높다 = prestige함
out-degree가 높다 = gregariousness함
Normalized degree centrality
1. Normalized by the maximum possible degree
어떤 그래프에 노드가 존재할 때,
하나의 노드가 가질 수 있는 최대 degree는 n-1개임
2. Normalized by the maximum degree
가장 큰 degree를 가진 노드를 기준으로 상대화 하여
비교할 수 있게 하는 방법
3. Normalized by the degree sum
모든 edge의 합의 2배로 나눠서 normalize하는 방법
참고로 degree의 총합= 모든 edge의 2배 임
Eigenvector Centrality
단순히 follower가 많다고(연결된 노드가 많다고)중요한 것이 아니라,
important friends가 있어야지 중요하다고 하는 측정방법
즉, neighbor의 중요도를 incorporating(반영)하는 것임
power iteration방법으로 Eigenvector centrality구하는 방법
예를 들어, 2라는 값의 1번째 스탭에서의 값은
2와 연결 되어있는 1,4,3의 합(즉, 0번째 스탭의 1+1+1)이 1번째 스탭에 채워야될 값임
최종적으로 max값인 52로 값을 나눠주게되면 Eigenvector와 유사한 값을 가지게 됨
위의 반복되는 것을 수식으로 표현하면 아래와 같음
참고로 방향성있을 때는 A!=Transpose(A)
(15~19 page생략)
아래 네트워크 그래프에서 Eigenvalue의 값이 가장 큰 것의 Eigenvalues vector를 봐보면
2번째인 0.5825값이 가장 크고
그 말인즉슨, v2의 노드가 centrality의 값이 크다는 것을 보여준다고 할 수 있다.
Eigenvector Centrality문제점
방향성이 있을때, strongly connected(모든 노드간의 path가 존재)되어있으면
Eigenvector centrality가 잘 작동하나,
weakly connected graph에서는 잘 작동하지 않음
왜냐하면, 현재노드의 centrality는 이웃 노드의 centrality의 합을 통해서 구하기 때문
(Centrality only passes over outgoing edges.)
특히, acyclic(비순환적인) graph에서는 최종적으로 모든 값이 0이되버림
Katz Centrality
알파와 베타값을 줌으로써 0이되는 것을 방지
베타는 0~1사이값으로 보통 줌.
Katz centrality로 centrality를 구하면
노드 v3, v2값이 가장 크다.
Katz centrality의 문제점
만약 한 노드에서 연결된 edge가 많다면(5개라면)
자기자신의 값을 모두 그대로 전달해주게 됨
(즉, neighbor node의 degree를 반영하지 않음)
--> 해결책: PageRank
PageRank는 1/5씩 비율로 나눠서 값을 전달하고 그 값으로 centrality를 구하게됨
(Katz와 PageRank의 차이점: neighbor노드의 outgoing degree의 fraction만큼만 가져옴)
(centrality를 구하는 더 효과적인 방법)
(Eigenvector문제점 & Katz문제점 & PageRank가 나온 이유들 기억하기)
PageRank
B/2에서 "2"는 B의 degree값인 2임
Step을 멈출 때는 이전 step과 현 step의 차이가 크지 않을때(threshold 사용)
** google에서 알파는 0.85, 베타는 (1-알파)/n으로 사용함
(power iteration기법으로 수기로 구하는 방법은 ppt참고)
** Katz와 page rank의 차이점: page rank는 outgoing edge의 fraction만큼만 가져옴
Betweenness Centrality
(Centrality in terms of how you connect others)
노드가 다른 노드와 연결될때 얼마나 중요한 역할을 하는지
(Bridge랑 같은 개념 추가?!)
vi가 중요한 노드일 수록 Cb값은 1과 가까워짐
각 노드의 Cb값을 아래값으로 normalization해줌
--> Betweenness centrality구할 때 사용하는 알고리즘
1. Dijkstra's Algorithm
2. Brandes Algorithm
Closeness Centrality
Centrality in terms of how fast you can reach others
(얼마나 가까운지, 빠르게 다른노드에 도달할수 있는지)
값이 클수록 centrality가 큰 것임
centrality 비교
| Low degree | Low closeness | Low betweenness | |
| High Degree | 다른 네트워크 그룹과 연결성이 낮은(멀리있는) 노드 | 그 노드의 connection이 중복이라, 그 노드를 거치지 않고도 갈수있는 방법이 많음 | |
| High closeness | 다른노드와 빠르게 연결되는 key node임 | 굳이 이 노드를 통하지 않고도 다른노드와 연결할수 있으면서도, 이 노드는 다른노드와 많이 연결된 것임 | |
| High betweenness | 매우 중요한 노드임 | 매우 드문 경우로, small 그룹과 big 그룹을 연결해주는 유일한 창구 |
Group Centrality
node의 Centrality를 통해 Group Centrality를 파악할 수 있음
Group of nodes를 super node로 대치해서 계산하면 됨
Group 내의 structure는 무시함
S: the set of nodes in the group
V-S: the set of outsiders
수식으로 표현하면 아래의 값이 4가되고
normalization을 해주기 위해서 4/(|8-4|)=1 이므로
위의 S는 cetrality가 높다.
Group betweenness centrality
Group closeness Centrality
'IT > SNS분석' 카테고리의 다른 글
| Network models1 - real world network 특징 (0) | 2022.05.02 |
|---|---|
| [SNS analysis]Network measures2 (0) | 2022.04.12 |
| Graph algorithms (0) | 2022.03.22 |
| [SNS analysis] 용어정리 및 그래프 종류 (0) | 2022.03.15 |
| [SNS analysis] 그래프 관련 기본 개념 (0) | 2022.03.08 |