네트워크 이론

3. 네트워크의 속성

많은 네트워크는 그 특성을 분석하는 데 사용되는 속성을 가지고 있다. 이러한 속성은 대부분 네트워크 모델을 정의하여 특정 모델과의 비교 분석에 사용된다. 네트워크 과학에서 사용되는 용어 정의의 상당수는 그래프 이론에서도 사용된다.

3. 1. 기본 속성

• 노드(Node): 네트워크를 구성하는 기본 단위이다.
• 엣지(Edge): 노드 간의 연결을 의미한다.
• 차수(Degree): 한 노드에 연결된 엣지의 수이다.
• 평균 차수: 네트워크 내 모든 노드의 차수 평균값으로, $\backslash langle\; k\backslash rangle\; =\; \backslash tfrac\{2E\}\{N\}$로 계산된다.
• 평균 경로 길이(Average path length): 네트워크 내 임의의 두 노드 사이의 최단 거리 평균값이다.
• 지름(Diameter): 네트워크 내에서 가장 멀리 떨어진 두 노드 사이의 최단 거리이다.

3. 2. 밀도와 연결성

• 완전 그래프 · 클리크: 모든 노드가 다른 모든 노드와 링크로 직접 연결된 네트워크를 완전 그래프라고 하며, 네트워크에 포함된, 완전 그래프를 이루는 부분 그래프를 클리크라고 한다.
• 거대 연결 성분: 네트워크의 일정 비율을 차지하는 연결 성분. 엄밀히는 크기가 네트워크 전체 크기에 비례하는 연결 성분을 가리킨다. 랜덤 그래프에서는 거대 연결 성분이 기껏해야 1개만 존재한다는 것이 알려져 있다.
• 약 연결 성분: 유향 네트워크에서 에지의 방향을 무시했을 때, 어느 노드에서든 다른 노드로의 경로가 존재하는 연결 성분.
• 강 연결 성분: 유향 네트워크에서 에지의 방향을 고려했을 때, 어느 노드에서든 다른 노드로의 경로가 존재하는 연결 성분.

3. 3. 군집성

3. 4. 중심성 척도

3. 5. 동류 연결과 이류 연결

4. 네트워크 분석

네트워크 분석은 사회, 생물학, 통신 등 다양한 분야에서 활용된다.

사회 네트워크 분석은 개인, 집단, 조직, 국가, 웹사이트 등 사회적 실체 간의 관계 구조를 연구한다. 1970년대 이후 사회 과학의 핵심적인 역할을 해왔으며, 혁신의 확산, 뉴스 및 소문, 질병 및 건강 관련 행동의 확산, 시장 연구, 정치 운동 및 사회 조직 연구, 학문적 불일치 및 명성 개념화 등 다양한 분야에 활용된다.

생물학적 네트워크 분석은 분자 네트워크 분석에 중점을 두며, 네트워크 모티프, 활동 모티프 등을 통해 생물학적 시스템의 패턴을 분석한다. 푸드 웹과 같은 시스템에서 종 간 상호 작용을 시각화하고, 질병 관련 네트워크 분석을 통해 네트워크 의학 분야 발전을 이끌었다. 세포 주기 및 발달 과정 이해에도 활용된다.

내러티브 네트워크 분석은 텍스트 코퍼스를 자동 구문 분석하여 행위자와 관계 네트워크를 추출한다. 이를 통해 주요 행위자, 커뮤니티, 네트워크의 견고성 등을 파악한다.

링크 분석은 객체 간 연관성을 탐구하는 네트워크 분석의 하위 집합이다. 경찰 수사, 사기 탐지, 통신 사업자에서 통신 네트워크 분석, 의료 부문에서 역학 및 약리학, 법 집행 수사, 검색 엔진에서 관련성 평가 등 다양한 분야에서 활용된다.

웹 검색 랭킹 알고리즘에는 구글의 PageRank, 클라인버그의 HITS 알고리즘 등 링크 기반 중심성 지표가 사용된다. 링크 분석은 정보 과학 및 커뮤니케이션 과학에서 웹 페이지 구조를 이해하고 정보를 추출하는 데에도 사용된다.

전력 시스템 분석은 네트워크 이론을 통해 추상적인 관점과 가중치 그래프 관점에서 수행될 수 있다. 추상적인 관점에서는 송전선 임피던스 등을 고려하지 않고 전력망의 취약성을 평가하고, 가중치 그래프 관점에서는 복잡한 네트워크 이론과 전력 시스템 속성을 결합하여 분석한다.

4. 1. 사회 네트워크 분석

4. 2. 생물학적 네트워크 분석

4. 3. 내러티브 네트워크 분석

4. 4. 링크 분석

4. 5. 전력망 분석

5. 네트워크 모형

네트워크 모델은 현실 세계의 복잡한 네트워크에서 발생하는 상호작용을 이해하고, 랜덤 그래프에서 생성된 네트워크 구조 모델을 실제 복잡 네트워크와 비교하는 데 사용된다.

• 에르되시-레니 무작위 그래프 모형: 폴 에르되시와 앨프레드 레니의 이름을 딴 모형으로, 노드 사이에 동일한 확률로 에지(연결)가 설정된 랜덤 그래프를 생성한다. 확률론적 방법을 사용하여 그래프의 속성을 증명하거나 정의하는 데 사용된다.
• 왓츠-스트로가츠 스몰 월드 네트워크 모형: 스몰 월드 네트워크의 특징인 높은 군집 계수(노드들이 서로 연결된 정도)와 짧은 평균 거리(두 노드 사이의 평균 거리)를 갖는 네트워크를 생성한다. 격자 구조에서 시작하여, 각 에지를 일정 확률로 무작위로 재배선하는 방식으로 만들어진다.
• 바라바시-알버트 척도 없는 네트워크 모형: 선호적 연결(preferential attachment) 또는 "부익부" 현상을 보여주는 랜덤 네트워크 모델이다. 연결이 많은 노드(허브)가 새로운 연결을 얻을 가능성이 더 높다. 이 모델의 차수 분포는 멱법칙을 따르며, 허브 노드는 짧은 경로를 가능하게 하여 네트워크의 평균 거리를 짧게 만든다.
• 피트니스 모형: 각 노드의 적합도(fitness)가 중요하게 고려되는 모델이다. 두 노드 사이의 연결 확률은 적합도 함수에 의해 결정되며, 적합도가 멱법칙으로 분포하면 노드 차수도 멱법칙을 따르게 된다. 이 모델은 국가 간 무역을 설명하는 데 사용되기도 한다.^[54][55]
• 중개 기반 연결 (MDA) 모형: 새로운 노드가 기존 노드를 무작위로 선택하고, 선택된 노드뿐만 아니라 그 이웃 노드에도 무작위로 연결되는 모델이다. 이 모델은 "부익부" 현상을 설명하며, 특정 조건에서 한 노드가 대부분의 연결을 독점하는 현상이 나타나기도 한다.^[51]

5. 1. 에르되시-레니 무작위 그래프 모형

5. 2. 왓츠-스트로가츠 스몰 월드 네트워크 모형

이 모델은 초기에는 비무작위 격자 구조이므로 평균 거리가 높고 클러스터 계수가 매우 높다. 재배선 확률이 높아짐에 따라 클러스터 계수는 평균 거리보다 느리게 감소한다. 이러한 특징은 클러스터 계수의 감소를 억제하면서 네트워크의 평균 거리가 크게 감소하는 것을 가능하게 한다. 확률 $p$의 값이 높을수록 더 많은 엣지가 재배선되어 와츠-스트로가츠 모델은 실질적으로 무작위 네트워크가 된다.

5. 3. 바라바시-알버트 척도 없는 네트워크 모형

BA 모델은 선호적 연결(preferential attachment) 또는 "부익부" 현상을 실증할 수 있는 랜덤 네트워크 모델이다. 이 모델에서는 엣지가 더 높은 차수의 노드에 연결될 가능성이 높다.^[50] 네트워크는 처음에 ''m''₀ 개의 노드를 가지며, ''m''₀ ≥ 2이고 네트워크의 각 노드의 차수는 1 이상이어야 한다. 그렇지 않으면 네트워크의 나머지 부분에서 항상 고립된 상태가 된다.

BA 모델에서는 새로운 노드가 하나씩 네트워크에 추가된다. 각 새로운 노드는 기존 노드가 이미 가진 링크의 수에 비례하는 확률로 기존 노드 $m$개에 연결된다. 요약하면, 새로운 노드가 노드 $i$에 연결될 확률 $p\_i$는 다음과 같다. $k\_i$는 노드 $i$의 차수이다.

:$p\_i\; =\; \backslash frac\{k\_i\}\{\backslash sum\_j\; k\_j\}$

여기서, 많은 링크를 가진 노드(허브라고 불림)는 더 많은 링크를 축적하는 경향이 있지만, 소수의 링크만 가진 노드는 새로운 링크의 대상으로 선택될 가능성이 낮다. 즉, 새로운 노드는 이미 많은 링크가 연결된 노드에 연결되는 경향이 있다.

BA 모델에서 얻어지는 차수 분포는 스케일 프리이며, 멱법칙으로 표시된다.

:$P(k)\backslash sim\; k^\{-3\}\; \backslash ,$

허브가 되는 많은 링크를 가진 노드는 노드 간의 짧은 경로 (Path)의 존재를 가능하게 하는 높은 중간 중심성을 나타낸다. 결과적으로 BA 모델은 평균 거리가 매우 짧아지는 경향이 있다. 이 모델의 클러스터 계수도 0이 되는 경향이 있다. 에르되시-레니 모델과 스몰 월드 네트워크를 포함한 많은 모델의 지름 D는 log N에 비례하지만, BA 모델은 D~loglogN이 된다. 이 때 평균 거리는 N을 지름으로 하는 척도임에 주의해야 한다.

5. 4. 피트니스 모형

스몰 월드 현상의 네트워크 모델도 참고하라.

네트워크 모델은 복잡 네트워크 내에서 일어나는 상호 작용을 이해하는 데 도움이 된다. 또한, 랜덤 그래프에서 생성된 네트워크 구조 모델은 실제 복잡 네트워크와 비교하여 사용된다.

Caldarelli 등이 도입한 피트니스 모델에서는 정점의 성질이 중시된다.^[52] 이 모델에서는 두 정점 $i,j$ 사이의 링크가 함수 $f(\backslash eta\_i,\backslash eta\_j)$에 의해 산출되는 확률을 가진다. 정점 $i$의 차수는 다음과 같이 나타낼 수 있다.^[53]

:$k(\backslash eta\_i)=N\backslash int\_0^\backslash infty\; f(\backslash eta\_i,\backslash eta\_j)\; \backslash rho(\backslash eta\_j)\; \backslash ,\; d\backslash eta\_j$

$k(\backslash eta\_i)$가 $\backslash eta\_i$에 역수를 가지며 증가하는 함수인 경우, 확률 분포 $P(k)$는 다음과 같다.

:$P(k)=\backslash rho(\backslash eta(k))\; \backslash cdot\; \backslash eta\text{'}(k)$

결과적으로, $\backslash eta$가 멱함수 법칙으로 분배되는 경우, 노드 차수도 마찬가지가 된다. 빠른 붕괴 확률 분포에서는 링크 함수와 함께, $\backslash rho(\backslash eta)=e^\{-\backslash eta\}$와 $f(\backslash eta\_i,\backslash eta\_j)=\backslash Theta(\backslash eta\_i+\backslash eta\_j-Z)$가 된다.

헤비사이드 함수의 $Z$ 상수와 $\backslash Theta$를 사용하면, 스케일 없는 네트워크가 된다.

이 모델은 다양한 노드 $i,j$에 대한 피트니스에 GDP를 사용함으로써 국가 간의 무역을 기술하는 데 성공했다.^[54][55]

:$\backslash frac\{\backslash delta\; \backslash eta\_i\backslash eta\_j\}\{1+\; \backslash delta\; \backslash eta\_i\backslash eta\_j\}$

5. 5. 중개 기반 연결 (MDA) 모형

중개 주도형 연결(MDA, Mediation-Driven Attachment) 모델에서는 m개의 에지를 가진 새로운 노드가 이미 링크된 노드를 무작위로 선택하고, 해당 노드뿐만 아니라 그 이웃 노드 m개에 무작위로 링크한다. 기존 노드 i가 새로운 노드로 선택될 확률 Π(i)는 다음과 같다.

:$\backslash Pi(i)\; =\; \backslash frac\{k\_i\}\; N\; \backslash frac\{\; \backslash sum\_\{j=1\}^\{k\_i\}\; \backslash frac\; 1\; \{k\_j\}\; \}\{k\_i\}$

이 식의 두 번째 인수는 조화 평균(IHM)의 역수이다. 노드 i의 k_i 근방의 차수 (IHM)를 계산한다. 대규모의 수치 연구에 따르면 m>14인 경우, 큰 한도 N에서의 조화 평균은 상수가 되며, 이는 Π(i)∝k_i로 나타낼 수 있다. 이는 노드가 가진 링크(차수)가 높을수록 더 많은 링크를 얻는 경향을 의미하며, "부유층이 더 부유해지는" 현상을 설명한다. 따라서 MDA 네트워크는 PA의 법칙에 암묵적으로 따른다.^[51]

m=1인 경우 "1명이 모든 것을 얻는" 메커니즘이 나타난다. 여기에서는 노드의 거의 99%가 차수 1을 가지며, 1명이 초부유층이 된다. "부유층이 더 부유해지는" 현상은 m>14부터 나타난다.

6. 네트워크 최적화

조합 최적화를 통해 네트워크에서 최적의 방법을 찾는 연구가 이루어진다. 예시로는 네트워크 흐름, 최단 경로 문제, 수송 문제, 환적 문제, 입지 문제, 매칭 문제, 할당 문제, 패킹 문제, 라우팅 문제, 임계 경로 분석, 프로그램 평가 및 검토 기법 등이 있다.

7. 추가 주제

네트워크 이론에는 재귀 네트워크, 네트워크 확산 등 여러 추가 주제가 있다.

7. 1. 재귀 네트워크

7. 2. 네트워크 확산

참조

_[1] 논문 Quantitative analysis of intracellular communication and signaling errors in signaling networks 2014-08
_[2] 서적 Networks and nodal points: the emergence of towns in early Viking Age Scandinavia - Antiquity 81(311) Cambridge University Press
_[3] 논문 Selected poster presentations from the American Association of Applied Linguistics conference, Denver, USA, March 2020: Out-of-class peer interactions matter for second language acquisition during short-term overseas sojourns: The contributions of Social Network Analysis 2021
_[4] 서적 Language, Mobility and Study Abroad in the Contemporary European Context Routledge
_[5] 논문 How output outweighs input and interlocutors matter for study-abroad SLA: Computational Social Network Analysis of learner interactions https://www.reposito[...] 2022
_[6] 논문 Forty years of secondhand smoke research: the gap between discovery and delivery 2009-06
_[7] 논문 Social Network Methodology in the Study of Disasters: Issues and Insights Prompted by Post-Katrina Research 2009
_[8] 논문 Care and support networks of community-dwelling frail individuals in North West London: a comparison of patient and healthcare workers' perceptions 2022-12
_[9] 서적 Social Movements 2e: An Introduction Wiley-Blackwell
_[10] 논문 The predictors of L2 grit and their complex interactions in online foreign language learning: Motivation, self-directed learning, autonomy, curiosity, and language mindsets
_[11] 논문 Network neuroscience 2017-02
_[12] 논문 La connaissance est un réseau http://www.cairn.inf[...] 2014-10-15
_[13] 문서 Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. Rainie, Lee and Barry Wellman, Networked: The New Social Operating System. Cambridge, MA: MIT Press, 2012.
_[14] 문서 Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
_[15] 서적 Python for Graph and Network Analysis 2017
_[16] 논문 Network analysis in public health: history, methods, and applications 2007-04
_[17] 논문 Markets as Governance Environments for Organizations at the Edge of Illegality: Insights From Social Network Analysis 2017-10
_[18] 논문 Networks of Conflict and Cooperation 2021-05-11
_[19] 논문 A network analysis of the propagation of evidence regarding the effectiveness of fat-controlled diets in the secondary prevention of coronary heart disease (CHD): Selective citation in reviews 2018-05-24
_[20] 논문 The Academic Caste System: Prestige Hierarchies in PhD Exchange Networks https://journals.sag[...] 2021-09-22
_[21] 논문 Strategies for Combating Dark Networks https://www.cmu.edu/[...] 2021-09-22
_[22] 논문 Advanced fault diagnosis methods in molecular networks 2014-10-07
_[23] 논문 Network medicine: a network-based approach to human disease 2011-01
_[24] 논문 Delineation of key regulatory elements identifies points of vulnerability in the mitogen-activated signaling network 2011-12
_[25] 논문 Network-based approaches to quantify multicellular development 2017-10
_[26] 논문 Automated analysis of the US presidential elections using Big Data and network analysis http://journals.sage[...] 2015
_[27] 간행물 Network analysis of narrative content in large corpora http://orcp.hustoj.c[...] S Sudhahar, G De Fazio, R Franzosi, N Cristianini 2013
_[28] 문서 Quantitative Narrative Analysis Roberto Franzosi 2010
_[29] 논문 What Do Networks Have to Do with Climate?
_[30] 논문 Prediction of extreme floods in the eastern Central Andes based on a complex networks approach 2014-10
_[31] 논문 Categorization by Context http://www.jucs.org/[...]
_[32] 논문 Characterizing the dynamical importance of network nodes and links 2006-09
_[33] 논문 Mixing patterns in networks 2003
_[34] 논문 Complex network approach for recurrence analysis of time series
_[35] 논문 The Geometry of Chaotic Dynamics – A Complex Network Perspective
_[36] 논문 Geometric signature of complex synchronisation scenarios
_[37] 논문 Routing of multipoint connections 1988
_[38] 서적 The Structure and Dynamics of Networks. Princeton University Press 2006
_[39] 논문 Network robustness and fragility: percolation on random graphs 2000-12
_[40] 간행물 Network Science http://www.nap.edu/c[...] National Research Council 2006
_[41] 문서 シルベスター 1878
_[42] 문서 モレノ 1953
_[43] 논문 Understanding the spreading power of all nodes in a network http://www.nature.co[...] 2015-03
_[44] 논문 Understanding the spreading power of all nodes in a network http://www.nature.co[...] 2015-03
_[45] 논문 Centrality and Network Flow Elsevier 2005
_[46] 논문 From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks 2006
_[47] 논문 Dynamic Model of Time-Dependent Complex Networks 2010
_[48] 서적 Temporal Networks. Springer 2013
_[49] 논문 Accessibility in complex networks 2008
_[50] 논문 Statistical mechanics of complex networks http://www.nd.edu/~n[...] 2002
_[51] 논문 Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks 2017
_[52] 논문 2002
_[53] 논문 2004
_[54] 논문 2004
_[55] 논문 2015
_[56] 문서 복잡계 네트워크에 대한 최근 연구 동향 http://www.kps.or.kr[...] 2007