네트워크 특징 (1) : 동류성 및 경로와 거리

 

1. 노드 간의 유사성

- 소셜 네트워크와 동류성

 소셜 네트워크에서 노드는 다양한 속성(예: 나이, 성별, 위치, 관심사)을 가지며, 연결된 노드들은 종종 유사한 속성을 공유한다. 이러한 경향은 동류성(assortativity)으로 알려져 있으며, 네트워크에서 중요한 연구 주제 중 하나이다. 예를 들어, 페이스북 사용자들의 성적 지향이나 트위터 사용자들의 정치적 성향은 프로필에 명시되지 않아도 친구 집단의 속성을 분석하여 정확히 예측할 수 있다.

 

- 동류성의 주요 원인

동종선호 (Homophily)	사람들이 비슷한 특성을 가진 상대와 연결되려는 경향임. - 예를 들어, 지리적으로 가까운 사람들, 같은 취미를 공유하는 사람들이 연결될 가능성이 높임. - 데이트 앱에서는 공통된 특징을 기반으로 매칭 시스템에 동종선호를 활용합니다.
사회적 영향 (Social Influence)	연결된 사람들이 상호작용을 통해 시간이 지나면서 더 비슷해지는 현상임. 인간은 본질적으로 사회적 동물이기 때문에 타인의 의견, 선호, 행동에 큰 영향을 받음. - 예: 친구 간의 유사한 행동 및 취향 형성

 

- 동류성의 문제점

• 같은 의견을 가진 사람들과의 연결이 쉬워지고, 반대 의견을 가진 사람들과의 관계를 쉽게 끊을 수 있다.
• 선택적 정보 소비로 인해 메아리 방(Echo Chamber)이 형성되어 자신의 신념을 강화하는 정보만 접하게 된다.
• 이는 온라인 커뮤니티의 분열과 의견 극단화를 유발할 수 있다.

 

- NetworkX를 이용한 동류성 계산

# 범주형 속성을 기반으로 동류성 계산 assort_a = nx.attribute_assortativity_coefficient(G, category) # 수치형 속성을 기반으로 동류성 계산 assort_n = nx.numeric_assortativity_coefficient(G, quantity)

 

- 연결선 수 동류셩(Degree Assortativity)

 네트워크에서 노드의 연결선 수(degree)와 이웃 노드들의 연결선 수 간의 상관관계는 네트워크의 구조를 이해하는 데 중요한 지표이다.

동류적 네트워크 (Assortative Network)	연결선 수가 많은 노드가 다른 연결선 수가 많은 노드와 자주 연결됨. - 예: 소셜 네트워크 - 코어-주변부 구조(Core-Periphery Structure)를 형성.
이류적 네트워크 (Disassortative Network)	연결선 수가 많은 노드가 연결선 수가 적은 노드와 주로 연결됨. - 예: 월드와이드웹, 생태계 먹이 그물.

 

- 연결선 수 동류성 측정

• 피어슨 상관계소(Pearson Correlation Coefficient) : 연결된 노드들의 연결선 수 사이의 상관관계를 측정하며, -1에서 1 사이의 값을 가진다.
  • r > 0 : 네트워크는 동류적
  • r < 0 : 네트워크는 이류적
  • r = 0 : 상관관계가 없음

# 연결선 수 동류성 계산 r = nx.degree_assortativity_coefficient(G)

 

• 이웃의 평균 연결선 수 : 노드 iii의 이웃 노드들의 평균 연결선 수 k_nn(i)를 기반으로 동류성을 측정한다.
  • ⟨k_nn​(k)⟩가 k에 대해 증가하면 동류적, 감소하면 이류적 네트워크를 의미한다

 

• NetworkX를 이용한 연결선 수 및 상관관계 계산

import networkx as nx import scipy.stats # 이웃의 연결선 수를 계산 knn_dict = nx.k_nearest_neighbors(G) k = list(knn_dict.keys()) # 연결선 수 knn = list(knn_dict.values()) # 이웃의 평균 연결선 수 # 피어슨 상관계수 계산 r, p_value = scipy.stats.pearsonr(k, knn) print(f"피어슨 상관계수: {r}, p-value: {p_value}")

 

2. 경로와 거리

 네트워크에서 원천 노드(Source node)에서 출발하여 목표 노드(Target node)에 도달할 수 있다면, 두 노드 사이에 경로(Path)가 존재한다. 경로는 연결된 링크들의 배열로 구성되며, 경로를 이루는 링크의 수를 경로 길이(Path length)라고 한다.

 

- 경로의 특성과 유형

• 두 노드 사이에는 여러 개의 경로가 존재할 수 있다.
  • 서로 다른 길이를 가질 수 있음.
  • 같은 링크를 공유하거나 그렇지 않을 수 있음.
• 방향성 경로에서는 링크의 방향을 반드시 따라야 한다.

사이클(Cycle)	시작 노드와 목표 노드가 동일한 경로임
단순 경로(Simple Path)	동일한 링크를 두 번 지나지 않는 경로임

 

- 네트워크에서 거리(Distance)

 거리는 두 노드를 연결하는 링크의 개수로 정의된다. 두 노드를 연결하는 링크 수가 가장 적은 경로를 최단 경로(Shortest Path)라고 하며, 이 경로의 길이를 최단 경로 길이(Shortest-Path Length)라고 한다. 네트워크에서 두 노드 사이에는 여러 개의 최단 경로가 존재할 수 있으며, 이들 모든 최단 경로의 길이는 동일하다.

 

- 가중치와 거리

 네트워크가 가중치(Weight)를 가진다면 링크의 거리를 합산하여 경로 길이를 재정의할 수 있다. 예를 들어,  "베를린 → 파리 → 로마" 경로의 길이는 "베를린 → 파리 거리" + "파리 → 로마 거리"이다. 가중치가 없는 네트워크는 모든 링크의 거리를 1로 간주하는 특수한 경우이다.

무방향 네트워크	링크 수가 최단 경로의 기준이 됨
방향성 네트워크	링크의 방향을 고려하여 경로를 탐색함
가중치 네트워크	링크의 가중치를 고려하여 최단 경로를 계산함

 

- 특별한 거리 측정

 링크 가중치가 노드 간 유사성이나 상호작용의 강도를 표현하는 경우, 가중치 역수(1/가중치)를 사용하여 큰 가중치를 짧은 거리로 변환할 수 있다.

 

- 네트워크의 평균 거리와 지름

 평균 최단 경로 길이(Average Shortest-Path Length)는 네트워크 내 모든 노드 쌍 사이의 최단 경로 길이의 평균을 의미하며, 지름(Diameter)은 네트워크에서 모든 노드 쌍 간 최단 경로 길이 중 가장 긴 값을 말한다. 예를 들어, 기하학에서 원의 지름은 원 위의 두 점 사이 최대 거리를 나타낸다.

 단, 두 노드 사이에 경로가 존재하지 않는 경우, 평균 최단 경로 길이와 지름은 정의될 수 없다. 이러한 상황에서는 거리를 무한대(∞)로 간주된다.

• 평균 경로 길이
  • 여기서, ℓ_ij는 노드 i와 j 사이의 최단 경로의 길이이며, N은 노드 수이다.
  • 가중치 네트워크에서는 링크 거리에 기반해 계산된다.

• 평균 경로 길이 : 무방향 네트워크에서 경로가 없는 경우

 

- NetworkX를 이용한 경로와 거리 계산

• 경로 존재 여부 확인

nx.has_path(G, 'a', 'b')    # 'a'에서 'b'로 가는 경로가 있는지 확인

 

• 최단 경로와 경로 길이

nx.shortest_path(G, 'a', 'b')      # 'a'에서 'b'까지의 최단 경로 반환 nx.shortest_path_length(G, 'a', 'b')      # 'a'에서 'b'까지 최단 경로 길이

 

• 모든 최단 경로 계산

nx.shortest_path(G, 'a')      # 'a'에서 시작하는 모든 최단 경로 반환 nx.shortest_path_length(G, 'a')      # 'a'에서 시작하는 모든 최단 경로 길이 nx.shortest_path(G)      # 네트워크의 모든 노드 쌍에 대한 최단 경로 반환 nx.shortest_path_length(G)      # 모든 노드 쌍의 최단 경로 길이 반환

 

• 네트워크 평균 거리 계산

n x.average_shortest_path_length(G) # 평균 최단 경로 길이

 

• 방향성 네트워크에서 링크의 방향에 따른 경로 탐색

nx.has_path(D, 'a', 'b')      # 'a'에서 'b'로 가는 방향성이 있는 경로가 있는지 확인 nx.shortest_path(D, 'a', 'b')      # 방향성을 고려한 최단 경로 계산

 

• 가중치 네트워크에서 가중치를 이용한 최단 경로 탐색

nx.shortest_path_length(W, 'a', 'b', weight='weight')     # 가중치를 고려한 최단 경로 길이

 

 이와 같은 기능을 통해 네트워크의 구조를 분석하고 최단 경로 및 거리 관련 문제를 해결할 수 있다.

 

3. 연결상태와 덩어리

 네트워크의 구조와 기능을 이해하기 위해 연결 상태(connectedness)를 고려하는 것이 중요하다. 연결 상태는 네트워크의 물리적 구조와 관련된 여러 특성을 설명하는 데 유용하다.

 

- 네트워크의 링크 수와 연결 가능성

 네트워크의 링크 수는 노드 수에 따라 상한값이 정해지며, 링크가 전혀 없는 경우 하한값은 0이다. 링크가 많아지고 조밀도가 높아질수록, 네트워크의 모든 노드가 연결될 가능성이 높아진다. 반대로, 링크가 적고 조밀도가 낮으면 네트워크가 단절될 가능성이 커져, 많은 노드 또는 노드 그룹이 서로 연결되지 않을 수 있다.

 

- 네트워크의 연결 여부

 네트워크가 모든 노드 쌍 간에 경로를 통해 연결되어 있다면, 이를 연결된 네트워크(connected network)라고 한다. 반면, 연결되지 않은 네트워크는 단절된 네트워크(disconnected network)라고 하며, 이는 두 개 이상의 연결된 덩어리(connected components)로 구성된다. 연결된 덩어리는 하나 이상의 노드로 이루어진 서브네트워크로, 덩어리 내 모든 노드는 경로를 통해 서로 연결된다. 하지만, 다른 덩어리에 속하는 노드 간에는 연결 경로가 없다. 많은 실제 네트워크에서는 가장 큰 연결된 덩어리가 전체 네트워크의 상당 부분을 차지하며, 이를 거대 덩어리(giant component)라고 부른다.

 

- NetworkX의 네트워크 연결 여부 확인

 NetworkX는 네트워크가 연결 상태인지 확인할 수 있는 유용한 알고리즘을 제공한다.

import networkx as nx # 완전 그래프: 모든 노드가 서로 연결된 그래프 K4 = nx.complete_graph(4) print(f"Complete Graph (K4) 연결 여부: {nx.is_connected(K4)}") # 순환 그래프: 노드들이 순환 형태로 연결된 그래프 C = nx.cycle_graph(4) print(f"Cycle Graph (C) 연결 여부: {nx.is_connected(C)}") # 경로 그래프: 노드들이 일렬로 연결된 그래프 P = nx.path_graph(5) print(f"Path Graph (P) 연결 여부: {nx.is_connected(P)}") # 스타 그래프: 하나의 중심 노드가 모든 주변 노드와 연결된 그래프 S = nx.star_graph(6) print(f"Star Graph (S) 연결 여부: {nx.is_connected(S)}")

 

- 방향성 네트워크와 덩어리

 방향성 네트워크에서는 링크의 방향성을 고려하여 덩어리를 정의한다.

약하게 연결된 덩어리 (weakly connected components)	링크 방향을 무시하고 네트워크를 무방향 네트워크로 간주했을 때 연결된 덩어리임
강하게 연결된 덩어리 (strongly connected components)	덩어리 내 모든 노드 쌍이 양방향 경로로 연결된 경우를 말함. 강하게 연결된 네트워크는 모든 노드에서 출발하여 다시 출발점으로 돌아올 수 있는 방향성 사이클을 포함함.

 

- 속 덩어리와 바깥 덩어리

강하게 연결된 덩어리(S)를 기준으로, 특정 노드 집합을 정의할 수 있다.

속 덩어리(in-component)	S에 도달할 수 있지만, S로부터 도달할 수는 없는 노드 집합임
바깥 덩어리(out-component)	S로부터 도달할 수 있지만, S에는 도달할 수 없는 노드 집합임

 

- 단절된 네트워크와 거리 계산

 단절된 네트워크의 거리를 계산하는 방법에는 두 가지가 있다.

• 거대 덩어리에 속한 노드만 고려하여 계산한다.
• 모든 덩어리를 포함하되, 같은 덩어리 내의 노드 쌍만 평균 거리를 계산한다.

단절된 네트워크의 지름은 각 덩어리의 지름을 계산한 후 최댓값을 취해 정의할 수 있다.

 

- NetworkX를 이용한 연결된 덩어리 식별 및 분석

 NetworkX는 네트워크의 연결된 덩어리(connected components)를 식별하고 분석할 수 있는 다양한 기능을 제공한다. 이를 통해 연결 상태를 확인하거나 네트워크 구조를 분석할 수 있다.

import networkx as nx # 네트워크가 연결되어 있는지 확인 print(f"네트워크 연결 여부: {nx.is_connected(G)}") # 연결된 덩어리(connected components) 식별 및 정렬 comps = sorted(nx.connected_components(G), key=len, reverse=True) # 가장 큰 연결된 덩어리(Giant Component) 추출 nodes_in_giant_comp = comps[0] GC = nx.subgraph(G, nodes_in_giant_comp) # 거대 덩어리가 연결 상태인지 확인 print(f"거대 덩어리 연결 여부: {nx.is_connected(GC)}") # 방향성 네트워크에서 강하게 연결된 덩어리 확인 print(f"강하게 연결된 네트워크 여부: {nx.is_strongly_connected(D)}") # 방향성 네트워크에서 약하게 연결된 덩어리 확인 print(f"약하게 연결된 네트워크 여부: {nx.is_weakly_connected(D)}") # 약하게 연결된 덩어리 나열 weakly_connected_comps = list(nx.weakly_connected_components(D)) print(f"약하게 연결된 덩어리: {weakly_connected_comps}")

 

 출력되는 덩어리 정렬 방법은 다음과 같다.

# 연결된 덩어리 나열 및 정렬 comps = sorted(nx.connected_components(G), key=len, reverse=True) print(f"연결된 덩어리들: {comps}") print(f"거대 덩어리: {comps[0]}")