중심성

_{j=1} [C_D(y*)-C_D(y_j)]

이에 따라 그래프 $G$의 차수 집중화는 다음과 같다.

:$C\_D(G)=\; \backslash frac\{\backslash sum^$

_{i=1} [C_D(v*)-C_D(v_i)]}{H}

그래프 $X$가 모든 다른 노드가 연결된 하나의 중심 노드(별 그래프)를 포함할 때 $H$의 값이 최대화되며, 이 경우

:$H=(n-1)\backslash cdot((n-1)-1)=n^2-3n+2.$

따라서 모든 그래프 $G:=(V,E),$에 대해

:$C\_D(G)=\; \backslash frac\{\backslash sum^$

_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}

허브를 만들려는 경향(TMH)이라는 새로운 광범위한 차수 중심성 측정은 다음과 같이 정의된다.^[2]

:$\backslash text\{TMH\}\; =\; \backslash frac\{\backslash sum^$

_{i=1} \deg(v)^2 }{\sum^

_{i=1} \deg(v) }

여기서 TMH는 네트워크에서 차수 중심성이 나타남에 따라 증가한다.

4. 2. 근접 중심성 (Closeness Centrality)

연결된 그래프에서, 어떤 노드의 정규화된 '''근접 중심성''' (또는 '''근접성''')은 그 노드와 그래프의 다른 모든 노드 사이의 최단 경로의 평균 길이이다. 따라서 한 노드가 중심에 가까울수록 다른 모든 노드에 더 가깝다.^[19][20]

근접성은 알렉스 바벨라스 (1950)가 '''원거리'''의 역수로 정의했으며, $C\_B(v)=\; (\backslash sum\_u\; d(u,v))^\{-1\}$으로 표현된다. 여기서 $d(u,v)$는 정점 ''u''와 ''v'' 사이의 거리이다. 그러나 근접 중심성을 이야기할 때는 보통 이전 공식에 $N-1$을 곱하여 구한 정규화된 형태를 사용하는데, 여기서 $N$은 그래프의 노드 수이다.

:$C(v)=\; \backslash frac\{N-1\}\{\backslash sum\_u\; d(u,v)\}\; .$

이 정규화를 통해 서로 다른 크기의 그래프 노드들을 비교할 수 있다. 많은 그래프에서 근접성의 역수와 차수의 로그 사이에는 강한 상관관계가 있으며,^[21]$(C(v))^\{-1\}\; \backslash approx\; -\backslash alpha\; \backslash ln(k\_v)\; +\; \backslash beta$ 여기서 $k\_v$는 정점 ''v''의 차수이고, α와 β는 각 네트워크에 대한 상수이다.

무방향 그래프에서는 모든 다른 노드 ''로부터'' 또는 ''로''의 거리를 계산하는 것이 큰 의미가 없지만, 방향 그래프에서는 완전히 다른 결과를 낳을 수 있다. 예를 들어, 웹사이트는 나가는 링크에서 높은 근접 중심성을 가질 수 있지만, 들어오는 링크에서는 낮은 근접 중심성을 가질 수 있다.

4. 3. 조화 중심성 (Harmonic Centrality)

마르키오리와 라토라가 2000년에 처음 제안한 조화 중심성은 그래프에서 근접 중심성을 계산하는 방법의 변형이다.^[22] 연결되지 않은 그래프에서도 사용할 수 있도록, 합과 역수 연산을 반전시켜 다음과 같이 정의한다.

:$H(v)=\; \backslash sum\_\{u\; |\; u\; \backslash neq\; v\}\; \backslash frac\{1\}\{d(u,v)\}$

여기서 ''u''에서 ''v''까지의 경로가 없으면 $1\; /\; d(u,v)\; =\; 0$으로 처리한다. 즉, 연결되지 않은 노드 쌍의 거리는 무한대가 아닌 0으로 처리한다.

조화 중심성은 데커(2005)에 의해 "가치 중심성"이라는 이름으로,^[23] 그리고 로샤(2009)에 의해 독립적으로 제안되기도 했다.^[24] 필요에 따라 그래프의 노드 수 ''N''으로 나누어 정규화할 수 있다.

4. 4. 매개 중심성 (Betweenness Centrality)

'''매개 중심성'''(Betweenness Centrality)은 그래프 내의 정점에 대한 중심성 척도이다. 매개 중심성은 한 노드가 다른 두 노드 사이의 최단 경로 역할을 하는 횟수를 나타낸다. 린턴 프리먼은 사회 네트워크에서 다른 사람들 간의 의사소통에 대한 인간의 통제력을 정량화하는 척도로 매개 중심성을 도입하였다.^[25] 그의 개념에 따르면, 임의로 선택된 두 정점 사이의 임의로 선택된 최단 경로에 나타날 확률이 높은 정점은 매개 중심성이 높다.

$V$개의 정점을 가진 그래프 $G:=(V,E)$에서 정점 $v$의 매개 중심성은 다음과 같이 계산된다.

# 각 정점 쌍(''s'',''t'')에 대해, 그들 사이의 최단 경로를 계산한다.

# 각 정점 쌍(''s'',''t'')에 대해, 문제의 정점(여기서는 정점 ''v'')을 통과하는 최단 경로의 비율을 결정한다.

# 모든 정점 쌍(''s'',''t'')에 대해 이 비율을 더한다.

더 간결하게 매개 중심성은 다음과 같이 표현할 수 있다.^[26]

:$C\_B(v)=\; \backslash sum\_\{s\; \backslash neq\; v\; \backslash neq\; t\; \backslash in\; V\}\backslash frac\{\backslash sigma\_\{st\}(v)\}\{\backslash sigma\_\{st\}\}$

여기서 $\backslash sigma\_\{st\}$는 노드 $s$에서 노드 $t$까지의 최단 경로의 총 개수이고, $\backslash sigma\_\{st\}(v)$는 $v$를 통과하는 경로의 개수이다. 매개 중심성은 유향 그래프의 경우 $(n-1)(n-2)$, 무향 그래프의 경우 $(n-1)(n-2)/2$인 ''v''를 포함하지 않는 정점 쌍의 수로 나누어 정규화할 수 있다. 예를 들어, 무향 별 그래프에서 중심 정점(모든 가능한 최단 경로에 포함됨)은 $(n-1)(n-2)/2$ (정규화된 경우 1)의 매개 중심성을 갖는 반면, 잎(어떤 최단 경로에도 포함되지 않음)은 0의 매개 중심성을 갖는다.

계산 측면에서 그래프의 모든 정점의 매개 중심성을 계산하는 것은 그래프의 모든 정점 쌍 사이의 최단 경로를 계산하는 것을 포함하며, 이는 $O(V^3)$ 시간의 플로이드-워셜 알고리즘이 필요하다. 그러나 희소 그래프에서는 존슨 알고리즘이 더 효율적일 수 있으며, $O(\; 시간이\; 걸린다.\; 가중치가\; 없는\; 그래프의\; 경우,\; 계산은\; 브란데스\; 알고리즘[26]으로\; 수행할\; 수\; 있으며,\; 이는$ O(\; 시간이\; 걸린다.$$

4. 5. 고유벡터 중심성 (Eigenvector Centrality)

'''고유벡터 중심성'''(eigenvector centrality)은 네트워크에서 노드의 영향력을 측정하는 지표이다. 연결된 노드의 중요성을 함께 고려하여, 중요한 노드와 많이 연결될수록 해당 노드의 고유벡터 중심성이 높아진다. 구글의 페이지랭크(PageRank)는 고유벡터 중심성을 활용한 알고리즘의 예시이다.^[27][6]

주어진 그래프 $G:=(V,E)$에서 $|V|$를 정점의 개수, $A\; =\; (a\_\{v,t\})$를 인접 행렬이라고 하자. 정점 $v$가 정점 $t$와 연결되어 있으면 $a\_\{v,t\}\; =\; 1$, 그렇지 않으면 $a\_\{v,t\}\; =\; 0$이다. 이때 정점 $v$의 상대적인 중심성 점수 $x\_v$는 다음 방정식을 만족하는 음이 아닌 해로 정의할 수 있다. (단, $M(v)$는 $v$의 이웃 집합, $\backslash lambda$는 상수)^[27]

:$x\_v\; =\; \backslash frac\{1\}\{\backslash lambda\}\; \backslash sum\_\{t\; \backslash in\; M(v)\}x\_t\; =\; \backslash frac\{1\}\{\backslash lambda\}\; \backslash sum\_\{t\; \backslash in\; G\}\; a\_\{v,t\}x\_t$

위 식을 고유 벡터 방정식으로 표현하면 다음과 같다.

:$\backslash mathbf\{Ax\}\; =\; \{\backslash lambda\}\backslash mathbf\{x\}$

일반적으로 이 방정식은 여러 개의 고유값 $\backslash lambda$에 대해 해를 가진다. 페론-프로베니우스 정리에 따르면, 인접 행렬의 항목이 음수가 아닐 때 가장 큰 고유값이 존재하며, 이 고유값은 실수이고 양수이다. 이 가장 큰 고유값에 해당하는 고유 벡터의 $v^\{th\}$ 구성 요소가 정점 $v$의 상대적인 중심성 점수가 된다. 고유 벡터는 정규화를 통해 절대적인 점수로 정의할 수 있다. 멱승법은 이 고유 벡터를 찾는 고유값 알고리즘 중 하나이다.^[28]

4. 6. 카츠 중심성 (Katz Centrality)

'''카츠 중심성'''^[29]은 [도수 중심성]의 일반화된 형태이다. 도수 중심성은 직접적인 이웃의 수만을 고려하지만, 카츠 중심성은 경로를 통해 연결될 수 있는 모든 노드의 수를 측정하며, 멀리 떨어진 노드의 영향력은 감소시킨다. 수학적으로 다음과 같이 정의된다.

:$x\_i\; =\; \backslash sum\_\{k=1\}^\{\backslash infin\}\backslash sum\_\{j=1\}^N\; \backslash alpha^k\; (A^k)\_\{ji\}$

여기서 $\backslash alpha$는 $(0,1)$ 범위의 감쇠 인자이다.

카츠 중심성은 [고유 벡터 중심성]의 변형으로 볼 수 있다. 카츠 중심성의 또 다른 형태는 다음과 같다.

:$x\_i\; =\; \backslash alpha\; \backslash sum\_\{j\; =1\}^N\; a\_\{ij\}(x\_j+1).$

고유 벡터 중심성의 표현식과 비교하면, $x\_j$는 $x\_j+1.$로 대체된다.

$\backslash alpha$가 $\backslash tfrac\{1\}\{\backslash lambda\}$보다 작은 값으로 접근할 때 (인접 행렬인 $A$의 가장 큰 고유값과 관련된) 주 고유 벡터는 카츠 중심성의 극한값이다.^[30]

4. 7. 페이지랭크 (PageRank)

페이지랭크는 다음 방정식을 만족한다.

:$x\_i\; =\; \backslash alpha\; \backslash sum\_\{j\; \}\; a\_\{ji\}\backslash frac\{x\_j\}\{L(j)\}\; +\; \backslash frac\{1-\backslash alpha\}\{N\},$

여기서

:$L(j)\; =\; \backslash sum\_\{i\}\; a\_\{ji\}$

는 노드 $j$의 이웃 수(또는 방향 그래프에서 발신 링크 수)이다. 고유벡터 중심성 및 카츠 중심성과 비교했을 때, 한 가지 주요 차이점은 스케일링 팩터 $L(j)$이다. 페이지랭크와 고유 벡터 중심성의 또 다른 차이점은 페이지랭크 벡터가 왼쪽 고유 벡터라는 것이다(요소 $a\_\{ji\}$의 인덱스가 반전되어 있음에 유의).^[31]

4. 8. 침투 중심성 (Percolation Centrality)

침투 중심성은 네트워크를 통한 전염 과정에서 특정 노드의 중요성을 측정하는 지표이다. 이 지표는 주어진 노드를 통과하는 '침투 경로'의 비율을 계산하여, 네트워크 전체의 전염에 얼마나 기여하는지를 나타낸다.^[32] 여기서 '침투 경로'는 노드 쌍 간의 최단 경로이며, 소스 노드(전염의 시작점)는 전염된 상태이고, 대상 노드(전염의 도착점)는 전염되었거나, 전염되지 않았거나, 부분적으로 전염된 상태일 수 있다.

침투 중심성은 다음 수식으로 계산된다.

:$PC^t(v)=\; \backslash frac\{1\}\{N-2\}\backslash sum\_\{s\; \backslash neq\; v\; \backslash neq\; r\}\backslash frac\{\backslash sigma\_\{sr\}(v)\}\{\backslash sigma\_\{sr\}\}\backslash frac\{\{x^t\}\_s\}\{\{\backslash sum\; \{[\{x^t\}\_i\}]\}-\{x^t\}\_v\}$

위 식에서 $\backslash sigma\_\{sr\}$는 노드 $s$에서 노드 $r$까지의 총 최단 경로 수이고, $\backslash sigma\_\{sr\}(v)$는 그 경로 중 노드 $v$를 통과하는 경로 수이다. $\{x^t\}\_i$는 시간 $t$에서 노드 $i$의 침투(전염) 상태를 나타내며, $\{x^t\}\_i=0$이면 비침투 상태, $\{x^t\}\_i=1$이면 완전 침투 상태를 의미한다. 그 사이의 값은 부분 침투 상태를 나타낸다.

침투 경로에 부여되는 가중치는 소스 노드의 침투 수준에 따라 결정된다. 즉, 소스 노드의 침투 수준이 높을수록 해당 노드에서 시작하는 경로가 더 중요하다고 간주한다. 따라서 침투 수준이 높은 노드에서 시작하는 최단 경로 상에 있는 노드들은 네트워크 전염에 더 큰 영향을 미칠 가능성이 높다.

침투 중심성 계산은 Brandes의 빠른 알고리즘을 사용하여 효율적으로 수행할 수 있으며, $O(NM)$ 시간이 소요된다. 대상 노드의 가중치까지 고려해야 하는 경우에는 계산 복잡도가 $O(N^3)$까지 증가할 수 있다.

4. 9. 교차 클리크 중심성 (Cross-clique Centrality)

'''교차 클리크 중심성'''은 복잡한 그래프에서 한 노드가 서로 다른 클리크에 얼마나 연결되어 있는지를 나타낸다. 교차 클리크 연결성이 높은 노드는 그래프에서 정보나 질병 확산에 중요한 역할을 한다.^[33] 클리크는 하위 그래프의 한 종류로, 클리크 내의 모든 노드는 서로 연결되어 있다. $|V|$개의 정점과 $|E|$개의 간선을 가진 그래프 $G:=(V,E)$에서 노드 $v$의 교차 클리크 연결성은 $X(v)$로 나타낼 수 있다. 이 때 $X(v)$는 정점 $v$가 속한 클리크의 개수를 의미한다. 이 개념은 2013년 Faghani가 사용했지만^[33], 1998년 Everett와 Borgatti가 처음 제안했으며, 그들은 이것을 클리크 중첩 중심성이라고 불렀다.

4. 10. 프리먼 집중도 (Freeman Centralization)

네트워크의 '''집중도'''는 가장 중심적인 노드가 다른 모든 노드와 비교하여 얼마나 중심적인지를 측정하는 지표이다.^[34] 집중도 측정은 네트워크에서 가장 중심적인 노드와 다른 모든 노드 간의 중심성 차이의 합을 계산하고, 이 값을 동일한 크기의 모든 네트워크에서 이론적으로 가장 큰 차이의 합으로 나눈다.^[34] 따라서 모든 중심성 측정은 자체적인 집중도 측정을 가질 수 있다. 린턴 프리먼이 이 개념을 제시했다.

공식적으로 정의하면, $C\_x(p\_i)$가 점 $i$의 임의의 중심성 측정이고, $C\_x(p\_*)$가 네트워크에서 가장 큰 측정값이며, 다음 식이 성립할 때:

:$\backslash max\; \backslash sum\_\{i=1\}^\{N\}\; (C\_x(p\_*)-C\_x(p\_i))$

이는 동일한 노드 수를 가진 그래프에서 점 중심성 $C\_x$의 가장 큰 차이의 합이므로, 네트워크의 집중도는 다음과 같다:^[34]

:$C\_x=\backslash frac\{\backslash sum\_\{i=1\}^\{N\}\; (C\_x(p\_*)-C\_x(p\_i))\}\{\backslash max\; \backslash sum\_\{i=1\}^\{N\}\; (C\_x(p\_*)-C\_x(p\_i))\}.$

주어진 네트워크의 노드 순위에서 더 나은 결과를 얻기 위해, ^[35]에서는 복잡한 네트워크의 중심성 측정을 풍부하게 하기 위해 분류 및 데이터 마이닝 이론에 특정한 비유사성 측정값을 사용한다. 이는 고유값 문제를 해결하여 각 노드의 중심성을 계산하는 고유 벡터 중심성을 통해 설명된다.

:$W\backslash mathbf\{c\}=\backslash lambda\; \backslash mathbf\{c\}$

여기서 $W\_\{ij\}=A\_\{ij\}D\_\{ij\}$ (좌표 간 곱)이고 $D\_\{ij\}$는 비유사성 측정값을 통해 정의된 임의의 비유사성 행렬이다. 예를 들어, 다음과 같은 자카드 비유사성이 있다.

:$D\_\{ij\}=1-\backslash dfrac$

이 측정값은 각 노드가 주어진 노드의 중심성에 기여하는 정도(따라서 기여 중심성이라고 함)를 정량화할 수 있게 해준다. 비유사성이 클수록 가중치/관련성이 커지는데, 이는 주어진 노드가 직접 접근할 수 없는 노드에 접근할 수 있도록 해주기 때문이다.

$W$는 $A$와 $D$가 음이 아닌 행렬이므로 음이 아닌 값임을 주목할 필요가 있다. 따라서 위의 문제에 대해 '''c'''가 음이 아닌 경우 ''λ'' = ''λ_max''에 대한 고유한 해가 있음을 보장하기 위해 페론-프로베니우스 정리를 사용할 수 있으며, 이를 통해 네트워크의 각 노드의 중심성을 추론할 수 있다. 따라서 i번째 노드의 중심성은 다음과 같다.

:$c\_i=\backslash dfrac\{1\}\{n\}\backslash sum\_\{j=1\}^\{n\}W\_\{ij\}c\_\{j\},\; \backslash ,\backslash ,\backslash ,\backslash ,\backslash ,\backslash ,\; i=1,\backslash cdots,n$

여기서 $n$은 네트워크의 노드 수이다. ^[36]에서 여러 비유사성 측정값과 네트워크를 테스트하여 연구된 경우에 개선된 결과를 얻었다.

5. 수송망에서의 중심성

수송망(교통망) 분석에는 일반적인 중심성 지표 외에도 수송 중심성(transport centrality^영어)과 같이 특화된 중심성 지표가 활용된다.^[37] 수송 중심성은 특정 노드를 통과하는 모든 경로의 비율을 고려하여, 네트워크 내 이동 흐름에 대한 노드의 중요성을 평가한다.

수송 중심성은 고려 대상 노드를 통과하는 네트워크 내 노드 쌍 간의 경로 비율 합계를 측정한다는 점에서 매개 중심성과 유사하다. 그러나 최단 경로만 고려하는 매개 중심성과 달리 수송 중심성은 노드 쌍 간의 모든 가능한 경로를 고려한다. 따라서 수송 중심성은 매개 중심성의 일반적인 버전이며, 특정 조건에서는 실제로 매개 중심성으로 축소된다.^[37]

참조

_[1] 논문 Network hubs in the human brain 2013-12
_[2] 논문 Topological impact of negative links on the stability of resting-state brain network 2021-01
_[3] 서적 Networks: An Introduction. Oxford University Press 2010
_[4] 논문 Power and Centrality: A Family of Measures
_[5] 논문 Centrality and Network Flow
_[6] 논문 Eigenvector centrality for characterization of protein allosteric pathways
_[7] 논문 A Graph-Theoretic Perspective on Centrality
_[8] 논문 A matrix analysis of different centrality measures
_[9] ArXiv
_[10] 논문 On Authority Distributions in Organizations
_[11] 논문 Sorting big data by revealed preference with application to college ranking
_[12] 논문 Assessing the Political Landscape: Structure, Cognition, and Power in Organizations 1990-06
_[13] 논문 Predicting epidemic outbreak from individual features of the spreaders
_[14] 논문 Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach
_[15] 논문 Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes?
_[16] 논문 Ranking stability and super-stable nodes in complex networks.
_[17] 논문 Understanding the spreading power of all nodes in a network: a continuous-time perspective
_[18] 문서 Centrality in social networks conceptual clarification. 1979
_[19] 문서 Communication patterns in task-oriented groups. 1950
_[20] 논문 The centrality index of a graph
_[21] 논문 Linking the network centrality measures closeness and degree 2022
_[22] 논문 Harmony in the small-world
_[23] 논문 Conceptual Distance in Social Network Analysis http://www.cmu.edu/j[...] 2017-02-18
_[24] 간행물 Closeness centrality extended to unconnected graphs: The harmonic centrality index http://infoscience.e[...] 2017-02-19
_[25] 논문 A set of measures of centrality based upon betweenness
_[26] 논문 A faster algorithm for betweenness centrality http://citeseer.ist.[...] 2011-10-11
_[27] 백과사전 The mathematics of networks http://www-personal.[...] Springer 2006-11-09
_[28] 웹사이트 How Google Finds Your Needle in the Web's Haystack http://www.ams.org/s[...] American Mathematical Society 2006-12
_[29] 문서 A New Status Index Derived from Sociometric Index. 1953
_[30] 논문 Simultaneous group and individual centralities
_[31] 웹사이트 How does Google rank webpages? http://scenic.prince[...] 2012-01-31
_[32] 논문 Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks
_[33] 논문 A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks
_[34] 논문 centrality in social networks: Conceptual clarification http://leonidzhukov.[...] 2014-07-31
_[35] 논문 Eigencentrality based on dissimilarity measures reveals central nodes in complex networks 2015-11-25
_[36] 웹사이트 Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks http://www.nature.co[...] Nature Publishing Group 2015-12-29
_[37] 간행물 Transportation Centrality: Quantifying the Relative Importance of Nodes in Transportation Networks Based on Traffic Modeling 2023

---

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com