사회연결망 분석

Social Network Analysis; SNA, 소셜 네트워크 분석
개인이나 집단(노드) 사이의 관계(링크)를 그래프로 나타내고, 그 구조와 각 노드의 위치를 계량적으로 분석하는 기법

사회연결망 분석은 사람, 조직, 웹 페이지, 계정 같은 개체를 노드(node, vertex)로, 개체 사이의 친구 관계·통화·거래·인용·멘션 같은 관계를 링크(link, edge, tie)로 표현한 뒤, 연결망 전체의 구조(밀도, 군집)와 개별 노드의 영향력(중심성)을 수치로 계산한다. 이론적 바탕은 그래프 이론이며, ADP에서는 텍스트 마이닝과 함께 비정형 데이터 마이닝의 한 축으로 다룬다. 고객 사이의 영향 관계를 찾아 마케팅 대상을 고르거나, 통신·금융 거래에서 사기 조직을 찾거나, 조직 안의 핵심 인물을 찾는 데 쓰인다.

참고로 IT 분야에서 SNA라는 약어는 IBM의 네트워크 구조(Systems Network Architecture)를 가리키기도 하므로, 이 문서의 SNA와 구분해야 한다.

기본 용어

용어	설명
노드(node)	분석 대상 개체. 사람, 조직, 문서, 계정 등
링크(link)	노드 사이의 관계. 방향이 있으면 방향 그래프(유향), 없으면 무방향 그래프이다. 관계의 강도를 값으로 주면 가중 그래프가 된다
연결 정도(degree)	한 노드에 직접 연결된 링크 수. 방향 그래프에서는 들어오는 연결(in-degree)과 나가는 연결(out-degree)로 나눈다
경로·거리	두 노드를 잇는 링크의 연속이 경로이고, 가장 짧은 경로의 링크 수가 거리(geodesic distance)이다
1-모드 / 2-모드 네트워크	한 종류의 노드끼리 연결된 것이 1-모드, 사람-행사처럼 두 종류의 노드 사이 연결이 2-모드이다. 2-모드는 행렬 곱으로 1-모드로 바꿔 분석한다
에고 네트워크(ego network)	특정 노드 하나와 그 노드에 직접 연결된 이웃만으로 이루어진 부분 연결망

연결망 표현 방법

방법	표현	특징
집합론적 방법	노드 집합과 노드 쌍(관계)의 집합으로 표현한다. 예: {(A, B), (A, C), (B, C)}	관계를 쌍으로 나열하는 가장 기본적인 형태. 간선 목록(edge list)과 같다
그래프 이론적 방법	노드를 점, 관계를 선으로 그린 소시오그램(sociogram)	구조를 눈으로 보기 쉽지만 노드가 많으면 알아보기 어렵다
행렬 방법	n개 노드에 대해 n×n 인접 행렬을 만들고, i와 j가 연결되면 1, 아니면 0을 넣는다	컴퓨터 계산에 적합하다. 무방향 그래프의 인접 행렬은 대칭 행렬이다. 2-모드 자료는 준연결망(affiliation) 행렬로 표현한다

연결망 수준 지표

밀도(density): 실제 링크 수를 가능한 최대 링크 수로 나눈 값이다. 무방향 그래프에서 노드가 n개, 링크가 L개이면 다음과 같다. 0에서 1 사이 값이며, 1에 가까울수록 구성원이 서로 촘촘히 연결되어 있다.

$D = \frac{L}{n (n - 1) / 2} = \frac{2 L}{n (n - 1)}$

방향 그래프에서는 분모가 n(n − 1)이다.
포괄성(inclusiveness): 전체 노드 가운데 다른 노드와 연결된 노드의 비율이다.
중앙 집중도(centralization): 연결망 전체가 소수의 노드에 얼마나 집중되어 있는지를 나타낸다. 별 모양 연결망이 가장 높다.

중심성

중심성(centrality)은 한 노드가 연결망 안에서 얼마나 중심에 있는지를 나타내는 지표이다. 연결·근접·매개 중심성은 Freeman(1978)이 개념을 정리했고, 위세 중심성은 Bonacich의 고유벡터 기반 측도에서 나왔다. n은 노드 수이다.

중심성	의미	계산 (정규화 형태)
연결 중심성(degree centrality)	직접 연결된 노드가 많을수록 중심에 있다	$C_{D} (i) = \frac{\deg (i)}{n - 1}$
근접 중심성(closeness centrality)	다른 모든 노드까지의 거리가 짧을수록 중심에 있다. 간접 연결까지 반영한다	$C_{C} (i) = \frac{n - 1}{\sum_{j \neq i} d (i, j)}$
매개 중심성(betweenness centrality)	다른 노드 쌍 사이의 최단 경로 위에 자주 놓일수록 중개자 역할이 크다	$C_{B} (i) = \sum_{s \neq i \neq t} \frac{σ_{s t} (i)}{σ_{s t}}$ 를 무방향 그래프에서 $(n - 1) (n - 2) / 2$ 로 나눈다
위세 중심성(eigenvector centrality)	영향력이 큰 노드와 연결될수록 자신의 영향력도 커진다	인접 행렬 A의 가장 큰 고윳값 λ에 대한 고유벡터 x: $λ x = A x$

σ_st는 s에서 t로 가는 최단 경로의 수, σ_st(i)는 그 가운데 i를 지나는 경로의 수이다.
위세 중심성을 변형한 것으로 보나시치 권력 지수(Bonacich power), 웹 페이지 순위에 쓰인 PageRank가 있다.
연결 중심성이 낮아도 두 집단을 잇는 다리 위치에 있으면 매개 중심성이 높을 수 있다.

커뮤니티 탐지

연결망 안에서 내부 연결은 촘촘하고 외부 연결은 느슨한 노드 집단을 찾는 작업이다. 분할이 얼마나 좋은지는 보통 모듈성(modularity)으로 평가한다.

방법	설명
컴포넌트·클리크	서로 연결된 덩어리(component), 모든 노드가 서로 연결된 부분 그래프(clique)를 찾는다
Girvan-Newman(에지 매개)	매개 중심성이 가장 큰 링크를 하나씩 끊어 가며 연결망을 나눈다(2002)
Walktrap	짧은 무작위 행보(random walk)가 같은 집단 안에 머무는 경향을 이용한다
Louvain	모듈성을 탐욕적으로 최대화하며 노드를 묶어 나가는 빠른 방법(Blondel 외, 2008)

연결 구조가 비슷한 노드끼리 묶는 구조적 등위성(structural equivalence) 분석도 집단 분석의 한 방법이다.

분석 도구

R igraph

함수	기능
graph_from_data_frame(), graph_from_edgelist(), graph_from_literal()	데이터 프레임·간선 목록·식으로 그래프 생성
degree(), closeness(), betweenness(), eigen_centrality()	연결·근접·매개·위세 중심성
page_rank()	PageRank
edge_density()	밀도
centr_degree()	연결 중심성 기준 중앙 집중도
cluster_edge_betweenness(), cluster_walktrap(), cluster_louvain()	커뮤니티 탐지

library(igraph)
g <- graph_from_literal(A-B, A-C, B-C, C-D, D-E, E-F, E-G, F-G)
edge_density(g)
degree(g, normalized = TRUE)
closeness(g, normalized = TRUE)
betweenness(g, normalized = TRUE)
eigen_centrality(g)$vector
cl <- cluster_louvain(g)
membership(cl)
plot(g, vertex.color = membership(cl))

igraph의 eigen_centrality()는 기본값으로 가장 큰 값이 1이 되도록 척도를 맞추므로, 아래 networkx 결과와 숫자 크기는 다르고 순위는 같다.

Python networkx

두 삼각형(A-B-C, E-F-G)이 D를 거쳐 이어진 7개 노드 연결망이다.

import networkx as nx
from networkx.algorithms.community import louvain_communities, modularity

G = nx.Graph()
G.add_edges_from([("A","B"),("A","C"),("B","C"),("C","D"),
                  ("D","E"),("E","F"),("E","G"),("F","G")])
print("밀도:", round(nx.density(G), 4))
dc = nx.degree_centrality(G)
cc = nx.closeness_centrality(G)
bc = nx.betweenness_centrality(G)
ec = nx.eigenvector_centrality(G, max_iter=1000)
for n in sorted(G):
    print(n, f"{dc[n]:.3f} {cc[n]:.3f} {bc[n]:.3f} {ec[n]:.3f}")
com = louvain_communities(G, seed=1)
print([sorted(c) for c in com], round(modularity(G, com), 4))

networkx 3.4.2로 실행한 결과는 다음과 같다. 밀도는 8 / 21 = 0.381이다.

노드	연결 중심성	근접 중심성	매개 중심성	위세 중심성
A, B, F, G	0.333	0.400	0.000	0.335
C, E	0.500	0.545	0.533	0.450
D	0.333	0.600	0.600	0.384

D는 연결 수(2)가 C·E보다 적지만 두 삼각형을 잇는 다리이므로 근접 중심성과 매개 중심성이 가장 높다. D를 지나야 하는 노드 쌍은 {A, B, C}×{E, F, G}의 9쌍이므로 매개 중심성은 9 / 15 = 0.6이다.
위세 중심성은 연결 수가 많은 C와 E가 가장 높다.
Louvain 결과(seed=1)는 [A, B, C, D]와 [E, F, G] 두 커뮤니티, 모듈성 0.3672였다. 이 연결망은 좌우 대칭이어서 D가 어느 쪽에 붙을지는 난수 시드에 따라 달라질 수 있다.

분석 절차와 활용

관계 데이터 수집: 통화 기록, 거래, 댓글·멘션, 공동 저자 등에서 노드와 링크를 뽑는다.
연결망 구성: 간선 목록이나 인접 행렬로 만든다. 대규모 자료는 하둡 같은 분산 처리 환경에서 계산하기도 한다.
지표 계산: 밀도, 중심성, 커뮤니티를 계산한다.
활용: 중심성·커뮤니티 결과를 고객 이탈 예측, 추천, 사기 탐지 모델의 파생 변수로 넣거나, 영향력 있는 고객(인플루언서)을 골라 마케팅에 쓴다.

시험 포인트

중심성 4종의 정의를 구분한다. 직접 연결 수는 연결 중심성, 거리의 합은 근접 중심성, 최단 경로상의 중개 역할은 매개 중심성, 연결된 상대의 영향력까지 반영하면 위세(고유벡터) 중심성이다.
밀도 = 실제 링크 수 / 가능한 최대 링크 수. 무방향 n개 노드의 최대 링크 수는 n(n − 1)/2이다. 작은 그래프에서 밀도와 연결 중심성을 손으로 계산하는 문제에 대비한다.
연결망 표현의 세 방법(집합론적·그래프 이론적·행렬)과 인접 행렬의 대칭성을 묻는다.
실기에서는 networkx나 igraph로 중심성과 커뮤니티를 계산하고 결과를 해석하는 형태로 응용할 수 있다.

같이 보기

참고 문헌

Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239. doi:10.1016/0378-8733(78)90021-7
Bonacich, P. (1987). Power and Centrality: A Family of Measures. American Journal of Sociology, 92(5), 1170–1182. doi:10.1086/228631
Girvan, M., Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821–7826. doi:10.1073/pnas.122653799
Blondel, V. D. 외 (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics, P10008. doi:10.1088/1742-5468/2008/10/P10008
NetworkX Documentation - Centrality
NetworkX Documentation - Communities
R igraph Reference
한국데이터산업진흥원 데이터자격검정 - ADP 시험과목 및 출제기준