빅데이터 분석 - 소셜 네트워크 분석 1(그래프 관련 정리)

소셜 네트워크 분석 전에 알아야 할 내용

먼저 네트워크란 다수의 점과 점들을 연결하는 다수의 선으로 구성된 망이다. 여기서 점을 그래프에서의 노드 혹은 정점(vertex)라고 하고 선을 링크 또는 엣지(edge)라고 한다.

 

네트워크에는 방향성이 있는 방향 네트워크, 방향이 없는 무방향 네트워크가 있다.

 

소셜 네트워크란 액터 간 사회적으로 연결된 망을 말한다. 즉, 액터 간 상호의존적 관계에 의해 만들어지는 사회적 관계 구조를 말한다.

소셜 네트워크 분석이란?

소셜 네트워크 분석은 소셜 개체들 간의 사회적 관계를 구조적으로 분석하여 내재된 관계를 파악하는 것이다

(사회 연결망 분석이라고도 한다.)

 

구글에서 따온 이미지, 소셜 네트워크의 간략화된 형태라고 볼 수 있겠다.

그래프

1. 그래프의 정의

그래프 G란 개체를 나타내는 정점 V와 개체를 연결하는 엣지 E의 집합이다.

 

2. 그래프의 종류

방향 그래프 : 정점 V1에서 V2로 가는 방향이 표시된 그래프. 트위터에서는 어떤 사람이 팔로우한 모든 사람이 반드시 그 사람을 팔로우 하지는 않음.

 

무방향 그래프 : 정점 V1에서 V2로 가는 방향이 표시되지 않는 그래프.(간선의 방향이 없다.)

 

완전 그래프 : 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 연결선을 가진 그래프이다.(모든 정점이 다른 정점들으로 향하는 모든 간선을 가짐)

 

가중 그래프 : 정점을 연결하는 엣지에 가중치를 할당한 그래프이다. 예를 들어, 이 가중치를 이용해 단순한 친구관계 혹은 두터운 친분관계를 표현할 수 있을 것이다.

 

3. 그래프 특징을 나타내는 지표

차수(degree)와 허브(hub) : 그래프에서 노드의 차수는 그 노드에 연결된 엣지들의 수이다. 방향그래프에서 노드의 차수는 해당 노드로 들어오는 엣지를 의미하는 진입차수와 나가는 엣지를 의미하는 진출차수로 나눈다.

네트워크에서 허브는 노드 중에서 가장 높은 차수를 가지고 있는 노드를 말한다.

 

차수의 분포(degree distribution) : 차수의 분포 P(k)는 그래프에서 차수 k를 갖는 노드의 비율을 말한다. N(k)를 차수 k를 갖는 노드의 수라고 할 때, P(k) = N(k) / N 이다. 즉, P(k)는 N(k)를 전체 노드 수 N으로 나눈 값이다.

평균차수를 중심으로 지수적으로 감소하는 경우 포아송 분포(이산 확률 분포 형태)를 따르고, 작은 차수에 많은 노드가 집중되는 경우 왼쪽으로(작은쪽으로) 치우치게 분포된다.

 

밀도(density) : 그래프에서 밀도는 최대 가능한 엣지들의 개수에 대한 실제 엣지들의 개수의 비이디. 즉, 밀도는 실제 네트워크에 존재하는 엣지의 개수를 모든 노드끼리 전부 연결되어 있다고 가정한 후에 구한 총 엣지 수로 나눈 것이다.

그래프 밀도는 0~1 사이의 값을 가진다. 그래프에서 노드들간 완전히 연결되면 밀도는 1의 값을 가진다.

 

밀도는 조합을 이용해 다음 공식처럼 구한다. 

d = 네트워크에 존재하는 연결(L) / nC2 즉,  2L / n(n-1)

 

중심성(centrality) : 중심성 지표는 개체가 전체 네트워크에서 얼마만큼 중심에 가까이 자리 잡고 있는지 나타내는 지표.특정 노드가 많은 다른 노드들과 연결되어 있을 수록 네트워크의 가운데 쪽으로 위치하게 된다. 중심성 지표에서는 연결정도 중심(degree centrality), 매개 중심성(betweenness centrality), 근접 중심성(closeness centrality)가 있다.

 

연결정도 중심성(degree centrality) : 네트워크에서 한 노드가 다른 노드들과 직접적으로 연결되어 있는지 측정하는 지표. 연결된 노드가 많을 수록 연결정도 중심성이 높아진다.

 

연결정도 중심성 = 특정노드와 직접 연결된 노드의 수 / 특정 노드와 직,간접 연결된 노드의 수

 

근접 중심성(closeness centrality) : 1촌 연결로는 네트워크의 영향력을 파악하기 어려움. 따라서 간접적인 연결까지 포함해 중심성을 측정하는 지표. 즉. 직접적으로 연결된 노드 뿐 아니라 간접적으로 연결된 노드까지 최단 거리를 가지고 중심성을 측정한다.

 

i 노드의 근접 중심성 = 노드의 수 - 1 / 최단 거리(i, j)의 모든 노드에 대한 합. (여기서 노드의 수 - 1은 간선의 개수와 동일하다.)

 

매개 중심성(betweennes centrality) : 한 노드가 다른 노드들 간의 네트워크를 구축하는데 중계자 혹은 매개자로서의 역할 정도를 나타내는 지표이다. 상이한 집단 간을 연결하는 노드일 수록 매개 중심성이 높게 나타난다.

매개 중심성은 그 노드를 통과하는 최단경로들의 개수로 정의한다.