캣츠 중심성

네트워크 과학
이론
그래프 복잡한 네트워크 전염 소세계 스케일 프리 공동체 구조 퍼콜레이션 진화 제어 가능성 그래프 그리기 사회자본 링크분석 최적화 상호주의 폐쇄 동음이의어 트란시즘 우선부착 균형이론 네트워크 효과 사회적 영향
네트워크 유형
정보(컴퓨터) 통신 운송 사교적인 과학적 협업 생물학적 인공신경 상호의존적 의미론 공간적 의존 흐름 온칩
그래프
특징들 클라이크 구성 요소 잘라내다 사이클 데이터 구조 가장자리 루프 이웃 사람들 경로 꼭지점 인접 리스트/매트릭스 발생 목록/행렬 종류들 양립자 완성하다 연출된 들뜬 멀티 무작위 가중치
측정지표 알고리즘
중심성 정도 모티프 클러스터링 학위분포 어소타티비티 거리 모듈성 효율성
모델
위상 랜덤 그래프 에르드스-레니 바라바시알베르트 피트니스 모델 와츠-스트로가츠 지수 랜덤(ERGM) 무작위 기하학(RGG) 쌍곡선(HGN) 계층적 확률블록 블록모델링 최대 엔트로피 소프트 구성 LFR 벤치마크 역학 부울 네트워크 에이전트 기반 전염병/SIR
목록 분류
주제 소프트웨어 네트워크 과학자 범주:네트워크 이론 범주:그래프 이론
v t

그래프 이론에서, 노드의 Katz 중심성은 네트워크의 중심성의 척도다. 1953년 레오 카츠에 의해 도입되었으며, 소셜 네트워크 내에서 배우(또는 노드)의 상대적인 영향 정도를 측정하는 데 사용된다.^[1] 배우 한 쌍 사이의 최단 경로(지오데틱)만 고려하는 전형적인 중심성 측정과 달리, 캣츠 중심성은 한 쌍의 배우들 사이의 총 보행 수를 고려하여 영향력을 측정한다.^[2]

구글의 페이지랭크와 유사하며 고유벡터 중심성과 유사하다.^[3]

측정

Katz 중앙성은 네트워크 내의 노드의 상대적 영향을 계산한다. 즉, 인접 노드(제1도 노드)의 수와 이러한 인접 노드들을 통해 고려 중인 노드에 연결되는 네트워크의 다른 모든 노드의 수를 측정한다. 그러나 먼 이웃과의 연결은 감쇠 계수 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$에 의해 불이익을 받는다$.$^[4] 한 쌍의 노드 사이의 각 경로나 연결에는 $\alpha {\displaystyle }$ ${\$$displaystyle$ $\$$alpha }$에 의해 결정되는 중량과 노드 사이의 거리는 ${\displaystyle {\alpha d}^{}}${\d}로 할당된다$.$

예를 들어, 오른쪽 그림에서 존의 중심성이 측정되고 있고 $\alpha {\displaystyle }$= 0.5${\displaystyle \alpha$=$0$.$5}$이라고 가정해 보자$.$ The weight assigned to each link that connects John with his immediate neighbors Jane and Bob will be ${\displaystyle (0.5)^{1}=0.5}$. Since Jose connects to John indirectly through Bob, the weight assigned to this connection (composed of two links) will be ${\displaystyle (0.5)^{2}=0.25}$. Similarly, the weight assigned to the connection between Agneta and John through Aziz and Jane will be ${\displaystyle (0.5)^{3}=0.125}$ and the weight assigned to the connection between Agneta and John through Diego, Jose and Bob will be ${\displaystyle (0.5)^{4}=0.0625}$.

수학적 공식화

A를 네트워크의 인접 행렬로 간주한다. A의 요소$({\displaystyle i_{}}$ ${\displaystyle j_{}}$) ${\displaystyle(a_{ij}})$는 노드 i가 노드 j에 연결되어 있으면 값 1을, 그렇지 않으면 0을 취하는 변수다. A의 힘은 중개자를 통한 두 노드 사이의 연결의 존재(또는 부재)를 나타낸다. 예를 들어, 행렬 ${\displaystyle {A\mathrm{}}^{}}$ 3 ${\$ A$^{3}$에서$$${\displaystyle \mathrm{요소}}({\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle {12}_{}}$)${\displaystyle }$= 1 ${\displaystyle(a_{2,12})=1$}인 경우 노드 2와 노드 12가 길이 3의 일부 보행을 통해 연결되었음을 나타낸다$.$ $C{\displaystyle {}_{}}$ ${\displaystyle {K\mathrm{}}_{}}$ ${\displaystyle {\mathrm{a}}_{}}$ t ${\displaystyle {\mathrm{z}}_{}}$( ${\displaystyle i}$) ${\displaystyle C_{\mathrm {Katz} }(i)}$이(가) Katz의 노드 i의 중심성을 나타내는$$ 경우 수학적으로 다음을 수행하십시오.

${\displaystyle C_{\mathrm {Katz}}}}(i)=\sum _{k=1}^{n}}\sum _{j=1}^{n}\알파 ^{k}(A^{k})_{ji}}}$

위의 정의는 A ${\displaystyle k^{}}$ ${\$의 위치$({\displaystyle i}$, j${\displaystyle }$) ${\displaystyle(i,j)}$에 있는 요소가 $노드{\displaystyle }$ i ${\displaystyle i}$과 $j{\displaystyle }$ ${\displaystyle j}$ 사이의 총 $k{\displaystyle }$ ${\displaystyle k}$도 연결 수를 반영한다는$$ 사실을 사용한다는 점에 유의하십시오$.$ 감쇠 계수 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$의 값은 A의 가장 큰 고유값의 절대값의 역수보다 작도록 선택해야 한다$$.^[5] 이 경우 다음 식을 사용하여 Katz 중심성을 계산할 수 있다.

${\displaystyle {\overrightarrow {C}_{\mathrm {Katz}}}}=((I-\alpha A^{T})^{-1-I){\overrightarrow {I}}}}$

여기서 $I{\displaystyle }$ ${\displaystyle I}$은(는) ID 매트릭스, I${\displaystyle \stackrel{}{}}$→ ${\$은(는) n(n은 노드 수)로 구성된 벡터다. ${\$$T}}$은 A의 전치 행렬과${\displaystyle }$(${\displaystyle I}$- ${\displaystyle {}^{}}$ ${\displaystyle T^{}{}^{}}$)${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$ A$^{T})^{-1}$은 용어의 역행 행렬$({\displaystyle I}$ -${\displaystyle \alpha }$ $){\displaystyle (I-\alphA^{T})}$을 나타낸다$$$$$.$^[5]

이 프레임워크의 확장은 걷기를 역동적인 설정으로 계산할 수 있게 한다.^[6][7] 과도 에지의 네트워크 인접 스냅샷의 시간 의존적 시리즈를 취함으로써, 누적 효과에 기여하는 보행에 대한 의존성이 제시된다. 시간의 화살표는 정보 전파 방향에서 활동의 기여도가 비대칭이 되도록 보존한다.

양식의 네트워크 생성 데이터:

$\displaystyle \왼쪽\{A^{{[k]}\in \mathb {R} ^{N\time N}\right\}\qquad {\text{for}}\quad k=0,1,2,\ldots,M,}$

각 시간 $t{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에서 인접 행렬을 나타냄$.$ 따라서,

${\displaystyle \left(A^{[k]}\right)_{ij}={\begin{case}1&{\text}{}}{}t_{k}\0&}{\text}\datawise}\end{case}}}}}}}}노드에서 노드로 가는 에지가 있다.$

은t < 1> < M {\$displaystyle t_{0}<t_{$1}<\$cdots <t_{M$})가 순서지만 반드시 같은 간격은 아니다. ${\displaystyle }$$Q{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\displaystyle {\times }^{}}$ ${\displaystyle N^{}}$ ${\displaystyle Q$$\in \mathb {R} ^{N\time N}$에 대한$$${\displaystyle }$(${\displaystyle Q{}_{}}$) ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle$$(Q)_$$$${ij}}$의 길이가 ${\displaystyle$ $w$$}$인 동적 보행 수를 가중 카운트로 한다$$$.$ 참여 노드 간의 동적 통신성을 위한 형식은 다음과 같다.

${\displaystyle {\mathcal{Q}=\왼쪽(I-\alpha A^{[0]}\오른쪽)^{-1}\cdots \left(I-\alpha A^{[M]}\오른쪽)^{-1}.}$

이는 다음을 통해 정규화할 수 있다.

${\displaystyle {\hat {\mathcal {Q}}}^{[k]}={\frac {{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}}{\left\ {\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}\right\ }}.}$

따라서 노드 $n{\displaystyle }$ ${\displaystyle n}$이(가) 네트워크를 통해 동적 메시지를 얼마나 효과적으로 '방송'하고 '수신'할$$ 수 있는지를 수량화하는 중앙 집중성 측정,

${\displaystyle C_{n}^{\mathrm {broadcast} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad \mathrm {and} \quad C_{n}^{\mathrm {receive} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}}$.

적용들

Katz 중심성은 인용 네트워크와 월드 와이드 웹과 같은 지시된 네트워크의 중심성을 계산하는 데 사용될 수 있다.^[8]

Katz 중심성은 고유 벡터 중심성과 같이 전통적으로 사용된 측정치가 무용지물이 되는 지시된 반복 그래프의 분석에 더 적합하다.^[8]

Katz 중심성은 소셜 네트워크에서 행위자들의 상대적 지위나 영향력을 추정하는데도 사용될 수 있다. 에 제시된 작업은 트위터의 데이터에 Katz 중심성의 동적 버전을 적용하는 사례 연구를 보여주며, 안정적인 토론 리더가 있는 특정 브랜드에 초점을 맞추고 있다. 이 애플리케이션은 해당 분야의 인적 전문가와 방법론을 비교하고 그 결과가 소셜미디어 전문가 패널과 어떻게 일치하는지 비교할 수 있다.

신경과학에서 캣츠 중심성은 신경망에서 뉴런의 상대적 발화율과 상관관계가 있는 것으로 밝혀졌다.^[10] Katz 중심성의 시간적 확장은 학습과정 전후에 피험자로부터 데이터를 수집하는 음악 학습 실험에서 얻은 fMRI 데이터에 적용된다. 그 결과는 각 세션에서 음악적 노출에 대한 네트워크 구조의 변화가 학습의 성공에 따라 클러스터를 생성하는 교차 전달성의 정량화를 생성했다는 것을 보여준다.

일반화된 형태의 캣츠 중심성은 대학 축구와 같은 스포츠 팀을 위한 직관적인 순위 시스템으로 사용될 수 있다.^[12]

참조