네트워크 데이터 분석

데이터 사이언스

네트워크 데이터 분석 - 서론

skypainter 2024. 6. 20. 17:23

1. 그래프의 구성 요소
2. 특별한 네트워크들
- 2 - 1. Bipartite network
- 2 - 2. Complete network
3. 네트워크의 기본 개념들
4. 앞으로의 가정들 (assumptions)
5. 네트워크의 표현 (representations)

이번 포스트에서는 네트워크 데이터 분석의 기초가 되는 개념들을 다뤄보겠습니다.

1. 그래프의 구성 요소

네트워크 데이터란 두 관측치 사이의 연결성을 나타내는 데이터로, 그래프의 형태로 표현됩니다.
그래프는 N개의 노드 (node) 와 노드들을 잇는 edge들로 정의할 수 있습니다. 앞으로 ( $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ , $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ )는 노드 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 와 노드 $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ 를 잇는 edge로 정의하겠습니다. 이 경우, 두 노드 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ , $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ 는 인접 (adjacent) 하다고 합니다.

네트워크의 edge는 방향성이 있는 경우 (directed)와 방향성이 없는 경우 (undirected)로 나뉩니다. Undirected graph의 edge ( $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ , $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ )는 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 를 시작점으로 해서 $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ 로 간다는 의미입니다.

또한, 네트워크는 unweighted network와 weighted network로 나뉠 수 있습니다. Weighted network의 edge ( $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ , $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ , $w <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>w</mi></math>$ )는 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 와 $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ 를 잇고, w만큼의 weight을 갖는다는 의미입니다.

2. 특별한 네트워크들

네트워크는 형태와 특징에 따라 여러 종류로 나뉘지만, 여기서는 간단하게 두 가지의 특별한 네트워크를 생각해보겠습니다.

2 - 1. Bipartite network

Bipartite network에는 서로 다른 두 그룹의 node들이 존해하고, edge는 서로 다른 그룹에 속한 두 node 사이에서만 정의됩니다. 이러한 네트워크의 예시로는 학생들과 학생들이 수강하는 강의들이 있습니다.

2 - 2. Complete network

Complete network는 각 node가 다른 모든 node에 연결되어있는 그래프입니다. 즉, node가 주어졌을 때, 달성 가능한 최대의 edge의 개수를 가지고 있는 network입니다. Complete network를 기준으로 네트워크의 다양한 measurement가 정의될 수 있기 때문에 중요합니다.

3. 네트워크의 기본 개념들

앞으로 $N <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>N</mi></math>$ = 네트워크의 노드의 개수, $L <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>L</mi></math>$ = edge의 수 라고 하겠습니다.
그러면 undirected graph에서 만들어질 수 있는 최대의 edge의 개수는 $Lmax=(N2)=N(N−2)2<math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>L</mi><mrow data-mjx-texclass="ORD"><mi>m</mi><mi>a</mi><mi>x</mi></mrow></msub><mo>=</mo><mrow data-mjx-texclass="ORD"><mrow data-mjx-texclass="OPEN"><mo minsize="1.2em" maxsize="1.2em">(</mo></mrow><mfrac linethickness="0"><mi>N</mi><mn>2</mn></mfrac><mrow data-mjx-texclass="CLOSE"><mo minsize="1.2em" maxsize="1.2em">)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mi>N</mi><mo stretchy="false">(</mo><mi>N</mi><mo>−</mo><mn>2</mn><mo stretchy="false">)</mo></mrow><mn>2</mn></mfrac></math>$ 입니다.

3 - 1. Density

네트워크의 밀도 (density)는 다음과 같이 정의합니다.

$d=LLmax=2LN(N−1)<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mi>d</mi><mo>=</mo><mfrac><mi>L</mi><msub><mi>L</mi><mrow data-mjx-texclass="ORD"><mi>m</mi><mi>a</mi><mi>x</mi></mrow></msub></mfrac><mo>=</mo><mfrac><mrow><mn>2</mn><mi>L</mi></mrow><mrow><mi>N</mi><mo stretchy="false">(</mo><mi>N</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mfrac></math>$

즉, 네트워크의 edge의 개수와 최대로 달성 가능한 edge의 개수의 비율입니다.
보통 $d << <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mo><<</mo><mn>1</mn></math>$ 이면 네트워크가 sparse 하다고 합니다.

Directed graph의 경우는 최대로 얻을 수 있는 edge의 개수가 $L_{m a x} = N (N - 1)$ 입니다.
따라서, directed graph의 density는 다음과 같습니다.

$d = \frac{L}{L_{m a x}} = \frac{L}{N (N - 1)}$

3 - 2. Subnetwork

Subnetwork는 주어진 network의 노드의 부분집합과 이 부분집합 사이의 edge들로 정의됩니다. 말 그대로 주워진 네트워크의 일부분입니다.
Clique는 complete한 subnetwork입니다.

3 - 3. Degree

노드 $i$ 의 degree $k_{i}$ 는 그 노드에 연결된 edge의 개수, 또는 인접한 node의 개수입니다. Edge가 하나도 연결되지 않은 node는 singleton 이라고 부릅니다.

Directed network에서 degree는 두 가지로 정의됩니다.
노드 $i$ 의 in-degree $k_{i}^{i n}$ 는 노드 $i$ 로 들어오는 edge의 개수이고, 노드 $i$ 의 out-degree $k_{i}^{o u t}$ 는 노드 $i$ 에서부터 나가는 edge의 개수 입니다.

3 - 4. Strength

Weighted network에서는 strength를 다음과 같이 정의할 수 있습니다.

$s_{i} = \sum_{j} w_{i j}$

즉, degree의 weighted sum이라고 볼 수 있습니다.

Weighted directed network에서는 strength가 두 가지로 정의됩니다.
in-strength: $s_{i}^{i n} = \sum_{j} w_{j i}$
out-strength: $s_{i}^{o u t} = \sum_{j} w_{i j}$

3 - 5. Average degree

네트워크의 평균 degree는 다음과 같이 정의됩니다.

$< k >= \frac{\sum_{i} k_{i}}{N}$

위에서 살펴본 개념들을 종합하면 average degree에 대해 다음과 같은 관계식을 얻을 수 있습니다.

$< k >= \frac{2 L}{N} = \frac{d N (N - 1)}{N} = d (N - 1)$

따라서, degree는 다음과 같이 자연스럽게 average degree로 표현됩니다.

$d = \frac{< k >}{N - 1}$

3 - 6. Multilayer network

네트워크는 여러개의 layer를 가질 수 있습니다. Layer는 네트워크가 정의 되는 또 다른 공간이라고 보시면 됩니다.
예를 들어, 하나의 layer엔 유저들의 페이스북 친구 관계 network을 나타내고, 다른 layer에는 유저들의 인스타그램 팔로우 network를 정의할 수 있습니다.
이 경우, interlayer link 또는 interlayer edge는 같은 layer 안에서 정의되는 edge이고, interlayer link 또는 interlayer edge는 서로 다른 layer 사이에 걸쳐서 연결된 edge를 의미합니다.

각각의 layer에 있는 node들이 동일한 경우, 이 네트워크를 multiplex라고 부릅니다.
Multiplex의 예로는 temporal network가 있습니다. 이 경우, 각 layer는 시간에 흐름에 따라 찍힌 네트워크의 snapshot이라고 이해하시면 됩니다.

4. 앞으로의 가정들 (assumptions)

1. single-layer 네트워크만 다루도록 하겠습니다.
2. 네트워크에 self-loop는 없습니다. 즉, 한 노드에서 같은 노드로 가는 edge는 존재하지 않습니다.
3. 노드와 노드 사이에는 최대 1개의 edge만 존재합니다. 물론, directed graph에서는 $i$ 와 $j$ 사이에 $(i, j)$ 와 $(j, i)$ 두개의 edge가 존재할 수 있습니다.

5. 네트워크의 표현 (representations)

5 - 1. Adjacency matrix

Adjacency matrix는 $N \times N$ 행렬로 각 요소 $a_{i j} = 1$ 은 node $i$ 와 node $j$ 가 연결되었음을 의미합니다. $a_{i j} = 0$ 은 i와 j가 연결되지 않았음을 나타냅니다. 위의 4의 가정을 만족한다면, adjacency matrix는 다음의 특징을 가집니다.

(1) 행렬의 대각선은 모두 0 이다. (self-loop이 없기 때문)
(2) Undirected network에서 adjacency matrix는 대칭이다. ( $a_{i j} = a_{j i}$ )
(3) Undirected network면, 주어진 node $i$ 의 degree는 adjacency matrix의 $i$ 번째 행 또는 열의 요소들의 합이다.
$k_{i} = \sum_{j} a_{i j} = \sum_{j} a_{j i}$
(4) Directed network이면, adjacency matrix는 대칭이 아닐 수도 있다.
(5) $i$ 의 out-degree는 행렬의 $i$ 번째 행의 요소들의 합이다.
$k_{i}^{o u t} = \sum_{j} a_{i j}$
(6) $i$ 의 in-degree는 행렬의 $i$ 번째 열의 요소들의 합이다.
$k_{i}^{i n} = \sum_{j} a_{j i}$

Directed unweighted network adjacency matrix

5 - 2. Adjacency list

Adjacency matrix의 경우, $N^{2}$ 의 데이터가 저장되어야 한다. 만약, 네트워크의 edge의 개수가 적다면 (sparse) adjacency matrix는 데이터 저장에 있어서 매우 비효율적일 수도 있습니다. 특히, 대규모 네트워크의 경우, adjacency matrix의 형태로 데이터를 저장한다는 것은 거의 불가능에 가깝죠. 따라서, 보통 edge에 대한 정보만 저장하면 데이터 저장에 있어서 효율적입니다. 왜냐하면 존재하지 않는 edge들은 저장을 할 필요가 없기 때문입니다.

Adjacency list는 각 노드의 이웃 (neighbor)을 리스트를 저장하는 형태입니다. 따라서, undirected network라면, 각 edge는 2번 기록됩니다. 만약 weighted network라면 각 노드의 이웃은 ( neighbor, weight)의 쌍으로 대체됩니다.

5 - 3. Edge list

Edge list는 말 그대로 연결된 노드들의 pair를 저장하는 방식입니다. Weighted network라면 각 pair는 $(i, j, w e i g h t)$ 의 triple로 대체됩니다.

저작자표시

현재글네트워크 데이터 분석 - 서론

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Skypainter

네트워크 데이터 분석 - 서론

1. 그래프의 구성 요소