다차원 네트워크

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

네트워크 이론에서, 다층 네트워크의 특별한 형태인 다차원 네트워크는 여러 종류의 관계를 가진 네트워크다.^{[1][2][3][4][5][6]} 점점 더 정교한 시도 다차원 네트워크로 현실 세계의 시스템을 설계하기 위해 소셜 네트워크 analysis,[2][3][7][8][9][10]경제학, 도시와 국제 transport,[11][12][13]ecology,[14][15][16][17]psychology,[18][19]의학, biology,[20]상업, 기후학, physics,[21][22]의 분야에서 중요한 통찰력 주고 있다. 전산 neuroscience,[23][24][25][26]운영 관리, infrastructures[27]. 그리고 재정적인.

용어.

다양한 그룹들이 특정 네트워크 구성(예: 멀티플렉스, 다층, 다층, 다차원, 다차원, 다층, 상호연결)을 설명하기 위해 중복되고^[28][29] 모순되는 용어를 사용하기 때문에 최근 몇 년 동안 복잡한 네트워크의 신속한 탐구는 표준화된 명명 규칙의 결여에 시달려 왔다. 형식적으로 다차원 네트워크는 가장자리 레이블이 붙은 다중그래프다.^[30] 또한 "완전히 다차원적"이라는 용어는 다중접지 가장자리 레이블이 붙은 다중문자를 가리키는 데 사용되었다.^[31] 다차원 네트워크는 또한 다계층 네트워크의 특정 인스턴스로 최근에 다시 구성되었다.^[4][5][32] 이 경우 치수가 있는 만큼 많은 레이어가 존재하며, 각 레이어 내의 노드들 사이의 링크는 단순히 주어진 차원에 대한 링크일 뿐이다.

정의

가중치가 없는 다중 계층 네트워크

In elementary network theory, a network is represented by a graph ${\displaystyle G=(V,E)}$ in which ${\displaystyle V}$ is the set of nodes and ${\displaystyle E}$ the links between nodes, typically represented as a tuple of nodes ${\displaystyle u,v\in V}$. While this basic formalization is useful 많은 시스템을 분석하기 위해, 실제 세계 네트워크는 종종 시스템 요소들 간의 관계의 여러 가지 형태의 복잡성을 더한다. 이 아이디어의 초기 공식화는 소셜 네트워크 분석 분야(^[33]예: 소셜 네트워크의 관계형 알헤브라에 관한 논문 참조)에서 그 적용을 통해 이루어졌는데, 이 분야에서는 사람 사이의 여러 가지 형태의 사회적 연결이 여러 종류의 링크로 표현되었다.^[34]

To accommodate the presence of more than one type of link, a multidimensional network is represented by a triple ${\displaystyle G=(V,E,D)}$, where ${\displaystyle D}$ is a set of dimensions (or layers), each member of which is a different type of link, and ${\displaystyle E}$ consists of triples ${\displaystyle (u,v}$${\displaystyle ,}$ ${\displaystyle d}$)${\displaystyle }$u , v$($V${\$${\displaystyle \mathrm{displaystyle<img\; alt="(u,v,d)"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/18ca13b30f70664522c119b3a751b603a4e68ea8"\; style="vertical-align:\; -0.838ex;\; width:7.55ex;\; height:2.843ex;"\; papago-attr-id="242">}}$ $u,v\in V}$ 및$$ $d{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle D}$ ${\displaystyle d\in D$^[5]

모든 방향 그래프에서와 같이 링크$({\displaystyle u}$ ,${\displaystyle v}$, d${\displaystyle }$) ${\displaystyle (u,v,d)}$과$({\displaystyle v}$ ${\displaystyle ,}$u ,${\displaystyle d)}$ ${\displaystyle (v,u,d)}$은(는$$) 구별된다는 점에 유의하십시오.

관례에 따라, 주어진 차원에 있는 두 노드 사이의 링크 수는 다차원 네트워크에서 0 또는 1이다. 그러나 모든 차원에 걸쳐 두 노드 사이의 총 링크 수는 ${\displaystyle D}$ $displaystyle D}$보다 작거나 같다$.$

가중 다중 계층 네트워크

가중 네트워크의 경우, 이 트리플릿은 4중${\displaystyle }e{\displaystyle }$ =${\displaystyle }$(${\displaystyle u,}$ ${\displaystyle v,}$ ${\displaystyle d,}$ w$$) {\$displaystyle e=(u,v,d$,w$)\}$까지 확장되며, $여기$서$$w {\$displaystyle$ w$}$은 $치수$ d ${\d}$에서$$u {\$displaystyle$$$u}과 v$}$ 사이의 링크에 있는 중량이다$.$

또한, 소셜 네트워크 분석에서 종종 유용한 것처럼 링크 가중치는 긍정적이거나 부정적인 가치를 가질 수 있다. 그러한 서명된 네트워크는 친선이나 적대감 같은 관계를 소셜 네트워크에 더 잘 반영할 수 있다.^[31] 로 치수를, 예를 들어 themselves,[35]또는 링크를 알아낼 수 있다.G=}와 E){(u, v, d), u, v∈ V, d∈ D}{\displaystyle E=\{(u,v,d);u,v\in V,d\in D\}} 이러한 접근법을 이용할 때 무거운 짐을 고려하고 특정 값이 어디 D)({\displaystyle D=\{-1,0,1\}{G=(V,E,D)\displaystyle}(V, E, D). 네트워크.

다차원의 속성이 규격을 필요로 할 경우 차원성의 개념은 확장될 수 있다. 이 경우 링크는 n-tule $e{\displaystyle }$= ${\displaystyle (}$u, ${\displaystyle v,}$ ${\displaystyle {d\mathrm{}}_{}}$ ${\displaystyle {}_{}}$… d ${\displaystyle {}_{}}$- ${\displaystyle 2_{}}$) ${\displaystyle e=(u,v,d_{1}\dots d_{n-2$ 링크가 다차원 내에 존재할 수 있는 확장형식은 흔치 않지만 다차원 시간변량 네트워크를 연구하는 데 사용되어 왔다.^[36]

텐서 면에서의 일반 제형

Whereas unidimensional networks have two-dimensional adjacency matrices of size ${\displaystyle V\times V}$, in a multidimensional network with ${\displaystyle D}$ dimensions, the adjacency matrix becomes a multilayer adjacency tensor, a four-dimensional matrix of size ${\displaystyle (V\times D)\times$반면에 다층 인접 tensors Mj로 표시된다 지수 표기법을 사용함으로써(V\times D)}.[2], 인접 매트릭스 나는}{\displaystyle A_{j}^{나는} j에 의해, 나 그냥 j{j\displaystyle}{\displaystyle 나는}노드 간의 연결을 인코딩하는 데, β 나는}{\displaystyle M_{j\beta}^{i\alpha}α, en에 표시할 수 있다.co$\alpha {\displaystyle }$ ${\displaystyle \alpha}$ 계층의 $노드$ i ${\displaystyle$ \alpha }과$($와$$) 계층 $\beta {\displaystyle }$ ${\displaystyle \beta }$의 노드$$ j ${\\displaystyle j}$ 사이의 연결.$$단차원 행렬에서처럼 방향 링크, 서명 링크 및 가중치는 이 프레임워크에 의해 쉽게 수용된다.

In the case of multiplex networks, which are special types of multilayer networks where nodes can not be interconnected with other nodes in other layers, a three-dimensional matrix of size ${\displaystyle (V\times V)\times D}$ with entries ${\displaystyle A_{ij}^{\alpha }}$ is enough to represent the structur$\alpha {\displaystyle }$ ${\$$displaystyle i}$과($)$ j {\$displaystyle j}$ 사이의 연결을 계층 α {\$displaystyle \alpha }$에 인코딩하여 시스템의^[7][37] e$.$

다차원 네트워크별 정의

다층 이웃

다차원 네트워크에서 일부 노드 $v{\displaystyle }$ ${\displaystyle v}$의 인접 노드는 차원을 $가로질러$ v ${\displaystyle v}$에 연결된 모든 노드들이다$$.

다층 경로 길이

2개의 마디 사이에 다차원 네트워크에서 지정된 경로에서 i{\displaystyle 나는} 벡터 r)(r1, 쭉 펼쳐져 rD){\displaystyle =(r_{1},\dots r_{D})}링크 G{G\displaystyle}의 i{\displaystyle 나는}th치수 .[38]에 ove와 마찬가지로 횡단의 r에 그 입력은 숫자 표시할 수 있다.rlap핑 도, 이러한 요소의 합은 두 노드 사이의 경로 길이를 대략적으로 측정할 수 있다.

레이어 네트워크

다중 계층(또는 차원)의 존재는 다중 계층 네트워크 특유의 새로운 계층 네트워크 개념을 도입할 수 있게 한다.^[2] 사실, 계층들은 그림에서 보여지듯이 네트워크에 의해 그들의 구조가 설명될 수 있는 방식으로 상호 연결될 수 있다.

층 네트워크는 일반적으로 가중치가 부여되지만(그리고 지시될 수도 있다) 일반적으로 가중치는 관심의 적용에 따라 결정된다. 간단한 접근방법은 각 레이어 쌍에 대해 $매트릭스{\displaystyle {}_{}}$ ${\displaystyle q_{}}$ α ${\$에지 가중치를 얻기 위해 노드 사이의 연결에 있는 모든 가중치를 합하는 것이다$.$ R ${\displaystyle {}^{}}$ ${\displaystyle {\times }^{}}$ ${\displaystyle L^{}}$ ${\$ 공간에 있는 계층의 기본 네트워크를 나타내는 2등급 인접 텐서는 다음과$$ 같다.

${\displaystyle \psi \delta }^{\delta }^{\damma }=\sum \limits _{\alpha ,\beta =1}^{{\delta }^{\delta }^{\alpha \beta )}}$

여기서 $E{\displaystyle {}_{}^{}}$ ${\displaystyle {\Delta }_{}^{}}$ Δ${\displaystyle {}_{}^{}}$ (${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle )}$ ${\displaystyle E_{\delta$}^{\$gamma }(\alpha \$$beta$ $)}}$는$$1과 동일한 $\alpha {\displaystyle }$ 행 ${\displaystyle \alpha }$ 및 $\beta {\displaystyle }$ ${\displaystylease }$에 해당하는 항목을 제외한 모든 성분이 0인 표준 행렬이다$$. Using the tensorial notation, it is possible to obtain the (weighted) network of layers from the multilayer adjacency tensor as ${\displaystyle \Psi _{\delta }^{\gamma }=M_{j\delta }^{i\gamma }U_{i}^{j}}$.^[2]

중앙집중성

정도

In a non-interconnected multidimensional network, where interlayer links are absent, the degree of a node is represented by a vector of length ${\displaystyle D :\mathbf {k} =(k_{i}^{1},\dots k_{i}^{ D })}$. Here ${\displaystyle D }$ is an alternative way to denote th다중 계층 $네트워크$의 e 레이어 L ${\displaystyle L}.$ 그러나 일부 계산의 경우 모든 차원에 걸쳐 노드에 인접한 링크 수를 단순히 합하는 것이 더 유용할 수 있다.^[2][39] 겹치는 정도:$$^[3]α = ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{D}}}$ ${\displaystyle \underset{}{\overset{}{k}}{}_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ \sum $_{\alpha=1}^{D }k_{i}^{\alpha$ $\}\}\}\}\}\}\}\}.$ 단차원 네트워크와 마찬가지로 들어오는 링크와 나가는 링크 사이에 구분이 유사하게 그려질 수 있다. 층간 연계가 존재하는 경우, 위의 정의는 이들을 설명하기 위해 수정되어야 하며 다층 연계는 다음에 의해 주어진다.

${\displaystyle k^{i}=M_{j\beta }^{i\alpha }U_{\nalpha }^{j}=\sum _{\alpha,\beta =1}{{j=1}^{{n}M_{j\beta}}^{ialpha\}}}}}}}}$

여기서 텐서 $U{\displaystyle {}_{}^{}}$ ${\displaystyle {\alpha }_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ 및$$ ${\displaystyle u^{}}$ j ${\$은 모든 성분이 1과 같다$$. 서로 다른 계층에 걸친 노드 연결 수의 이질성은 참여 계수를 통해 고려할 수 있다.^[3]

다층적 중심성으로서의 다용도

상호연결된 다계층 네트워크, 즉 여러 계층에 걸쳐 노드가 연결되는 시스템으로 확장될 때, 중심성의 개념은 다용성 측면에서 더 잘 이해된다.^[9] 각 계층에서 중심이 아닌 노드는 특정 시나리오에서 다계층 시스템에 가장 중요할 수 있다. 예를 들어, 두 개의 계층이 하나의 노드만을 가지고 서로 다른 네트워크를 인코딩하는 경우: 그러한 노드는 계층 간의 정보 흐름을 책임지기 때문에 가장 높은 중심성 점수를 가질 가능성이 매우 높다.

고유벡터 다용도

단차원 네트워크의 경우, 고유벡터 $다용성$은 ${\displaystyle M_{}^{}}$ j ${\displaystyle {\beta }_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {\alpha }_{}^{}}$ ${\displaystyle {\alpha }_{}}$ α${\displaystyle {}_{}}$= ${\displaystyle {}_{}{\mathrm{}}_{}}$ 1 ${\displaystyle j_{}}$ j ${\displaystyle {\beta }_{}}${\$displaystyle M_{j$\beta$}^{i$\alpha }}\$theta _${i$\alpha$}=\$lambda _{$1}에 의해 주어진 고유값 문제의 해결책으로 정의할 수 있다.$세타 _{j\beta$ $\}\}$ 아인슈타인 요약 관례가 단순함을 위해 사용된다. Here, ${\displaystyle \Theta _{j\beta }=\lambda _{1}^{-1}M_{j\beta }^{i\alpha }\Theta _{i\alpha }}$ gives the multilayer generalization of Bonacich's eigenvector centrality per node per layer. 전체 고유 벡터 다용성은 단순히 층에 걸친 점수를 $\theta {\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {\mathrm{}}_{}}$ i ${\displaystyle {\alpha }_{}}$ ${\displaystyle {\alpha }^{}}$α {\$displaystyle \theta _${i$}=\$로 요약하면 얻을 수 있다.$세타 _{i\alpha }u^{\alpha$ $\}\}\}.$^[2][9]

캣츠 다재다능함

As for its unidimensional counterpart, the Katz versatility is obtained as the solution ${\displaystyle \Phi _{j\beta }=[(\delta -aM)^{-1}]_{j\beta }^{i\alpha }U_{i\alpha }}$ of the tensorial equation ${\displaystyle \Phi _{j$$\beta }=aM_{j\beta }^{i\alpha }\Phi _{i\alpha }+bu_{j\beta }}$, where ${\displaystyle \delta _{j\beta }^{i\alpha }=\delta _{j}^{i}\delta _{\beta }^{\alpha }}$, ${\displaystyle a}$ is a constant smaller than the largest eigenvalue and ${\displaystyle b}$ is another constant generally e1의 자격을 얻다. 전체적인 Katz 다재다능성은 단순히 층에 걸친 점수를 $\varphi {\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {\mathrm{}}_{}}$ i ${\displaystyle {}_{}{}^{}}$ ${\displaystyle {\alpha }^{}}$ α ${\$ $\}\}\}\}\}$^[9]로 요약하면 얻을 수 있다.

HITS 다용도

단차원 네트워크의 경우, HITS 알고리즘은 원래 존 클라인버그에 의해 웹페이지의 등급을 매기기 위해 도입되었다. 알고리즘의 기본적인 가정은 당국으로 명명된 관련 페이지는 허브로 명명된 특별한 웹페이지에 의해 가리킨다는 것이다. 이 메커니즘은 두 개의 고유값 문제로 축소되는 두 개의 결합된 방정식으로 수학적으로 설명할 수 있다. 네트워크가 리디렉션되지 않은 경우, 권한과 허브 중심성은 고유 벡터 중심성과 동일하다. These properties are preserved by the natural extension of the equations proposed by Kleinberg to the case of interconnected multilayer networks, given by ${\displaystyle (MM^{t})_{j\beta }^{i\alpha }\Gamma _{i\alpha }=\lambda _{1}\Gamma _{j\beta }}$ and ${\displaystyle (M^{t}M{)}_{j\beta }^{i\alpha }}$${\displaystyle (M^{t}M)_{j\beta }^{i\alpha }\Upsilon _{i\alpha }=\lambda _{1}\Upsilon _{j\beta }}$, where ${\displaystyle t}$ indicates the transpose operator, ${\displaystyle \Gamma _{i\alpha }}$ and ${\displaystyle \Upsilon _{i\alpha }}$ indicate hub and authority centrali각각 ty. By contracting the hub and authority tensors, one obtains the overall versatilities as ${\displaystyle \gamma _{i}=\Gamma _{i\alpha }u^{\alpha }}$ and ${\displaystyle \upsilon _{i}=\Upsilon _{i\alpha }u^{\alpha }}$, respectively.^[9]

페이지랭크 다용도

구글 검색 알고리즘으로 더 잘 알려진 페이지랭크는 복잡한 네트워크의 중심성을 측정하는 또 다른 척도로, 원래 웹 페이지의 순위를 매기기 위해 도입되었다. 상호 연결된 다계층 네트워크의 경우에 대한 그것의 확장은 다음과 같이 얻을 수 있다.

첫째, 페이지랭크는 네트워크 상단의 특별한 마르코프 프로세스의 안정적 상태적 해결책이라고 볼 수 있다는 점을 언급할 필요가 있다. 무작위 보행자는 특별한 전환 매트릭스에 따라 네트워크를 탐색하며 이들의 역학은 무작위 보행 마스터 방정식에 의해 제어된다. 이 방정식의 해법이 전환 행렬의 선도적 고유 벡터와 동일하다는 것을 쉽게 알 수 있다.

무작위 보도는 상호 연결된 다중 레이어^[13] 네트워크와 가장자리 색의 다중 그래프(멀티플렉스 네트워크라고도 함)의 경우에도 정의되었다.^[40] For interconnected multilayer networks, the transition tensor governing the dynamics of the random walkers within and across layers is given by ${\displaystyle R_{j\beta }^{i\alpha }=rT_{j\beta }^{i\alpha }+{\frac {(1-r)}{$$NL}u_{j\beta }^{i\alpha$ $\}\},$ $여기$서 r ${\displaystyle r}$은(는) 상수로 일반적으로$$ $0{\displaystyle }$.85로 설정되고, N ${\displaystyle N}$은(는) 노드 수, $L{\displaystyle }$ ${\displaystyle L}$은 레이어 또는 치수의 수입니다. 여기서 $R{\displaystyle {}_{}^{}}$ ${\displaystyle j_{}^{}}$ ${\displaystyle {\beta }_{}^{}}$ ${\displaystyle {\mathrm{i\alpha }}_{}^{}}$ ${\$은(는) Google 텐서라고 명명할 수 있으며$$ ${\displaystyle u_{}^{}}$ j ${\displaystyle {\beta }_{}^{}}$ ${\displaystyle {\mathrm{i\alpha }}_{}^{}}$ ${\$은 모든 성분이 1인 순위 4 텐서이다$$.

단차원적 대응책으로서 PageLank 다용성은 rate $r{\displaystyle }$ ${\displaystyle r}$이(가) 있는 고전적 랜덤 워크를 인코딩하는 것과 ${\displaystyle \mathrm{rate}}$ 1$$- r {\$displaystyle 1-r}$이${\displaystyle (}$가) 있는 노드와 레이어 간에 텔레포테이션을 인코딩하는 두 가지 기여로 구성된다$.$

If we indicate by ${\displaystyle \Omega _{i\alpha }}$ the eigentensor of the Google tensor ${\displaystyle R_{j\beta }^{i\alpha }}$, denoting the steady-state probability to find the walker in node ${\displaystyle i}$ and layer ${\displaystyle \alpha }$, the multilayer PageRank is obtained by s아이젠텐서 층 위로 유밍: $\Omega {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ =${\displaystyle {}_{}{\alpha }_{}}$ ${\displaystyle {}_{}{}^{}}$ ${\displaystyle {\alpha }^{}}$ ${\$

삼차 폐쇄 및 군집화 계수

다른 많은 네트워크 통계와 마찬가지로, 3배는 원래 있던 것과 다른 차원으로 닫힐 수 있기 때문에 다차원 네트워크에서 클러스터링 계수의 의미가 모호해진다.^[3][41][42] 몇몇 시도 지역 집단 형성 계수를 정의하지만 이러한 시도는 사실 개념이 근본적으로 높은 치수의 다른 사람들에 임의의 걷기와 3-cycles에 대한 서로 다른 정의와 실험을 해왔다 일부 단체들 비표준 definitions,[42]의 일이 있어서 다를 거 관심이 집중되고 있어 왔다. mul입체 ^[3][41]네트워크

커뮤니티 검색

교차 차원 구조는 이전에 연구되었지만,^[43][44] 일부 네트워크에서 발견되는 더 미묘한 연관성을 감지하지 못한다. 다차원 네트워크의 경우에 "커뮤니티"의 정의를 약간 다르게 받아들이면 노드가 서로 직접 접촉할 필요 없이 커뮤니티를 신뢰성 있게 식별할 수 있다.^{[2][7][8][45]} 예를 들어, 아직 직접적으로 소통하지 않고 여전히 많은 동일한 웹사이트를 탐색하는 두 사람이 이러한 종류의 알고리즘에 적합한 후보일 것이다.

모듈화 최대화

공동체 발견을 위한 잘 알려진 모듈화 최대화 방법의 일반화는 원래 무차 등이 제안한 것이다.^[7] 이 다중화 방법은 에지 색상의 다중 글자에 대해 계층 내 네트워크 연결에 대한 3차원 텐서 표현과 계층 간 네트워크 연결에 대한 3차원 텐서 표현을 가정한다. 계층 간 연결의 분해능 파라미터$parameter{\displaystyle }$ {\$displaystyle$ \gamma$$$}$ 및 중량$$ $\Omega {\displaystyle }$ ${\displaystyle \omega }$에 따라 달라진다. In a more compact notation, making use of the tensorial notation, modularity can be written as ${\displaystyle Q\propto S_{i\alpha }^{a}B_{j\beta }^{i\alpha }S_{a}^{j\beta }}$, where ${\displaystyle B_{j\beta }^{i\alpha }=M_{j\beta }^{i\a$$lpha }-P_{j\beta }^{i\alpha }}$, ${\displaystyle M_{j\beta }^{i\alpha }}$ is the multilayer adjacency tensor, ${\displaystyle P_{j\beta }^{i\alpha }}$ is the tensor encoding the null model and the value of components of ${\displaystyle S_{a}^{i\alpha }}$ is defined to be 1 when a node ${\displaystyle }$$레이어{\displaystyle }$ α$${\$displaystyle \alpha$}의$$i {\$displaystyle i}$은(^[2]는) 특정 커뮤니티에$$ 속하며, $인덱스$에 의해 ${\displaystyle a}$및 그렇지 않을 경우 0으로 레이블이 지정된다.

텐서 분해

시간적 네트워크의 공동체 활동 구조를 추출하기 위해 비 음성 행렬 인자화가 제안되었다.^[46] 다층 네트워크는 3차원 텐서 T ${\displaystyle i_{}^{}}$ ${\displaystyle j_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ 에지 컬러의 멀티그래프처럼 표현되며$,$ 층의 순서가 시간의 화살표를 인코딩한다. 따라서 Kruskal 분해에 의한 텐서 인자화는 ${\displaystyle {Ti}_{}^{}}$ ${\displaystyle j_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\${ij$}^{\tau$}}}}}에 적용되어 시간$$ 경과에 따른 커뮤니티에 각 노드를 할당한다.

통계적 추론

통계적 추론에 기초한 방법, 단차원 네트워크에 대해 도입된 기존 접근법을 일반화하는 방법이 제안되었다. 확률형 블록 모델은 다계층 네트워크의 경우에 적합하게 일반화된, 가장 많이 사용되는 생성 모델이다.^[47][48]

단차원 네트워크에 대해서는 정보 흐름에 따른 공동체 탐지 방법에서 최소한의 설명 길이와 같은 원칙적인 방법을 모델 선택에 사용할 수 있다.^[8]

구조 환원성

단차원적 네트워크에 관해서 다층적 네트워크의 높은 복잡성을 감안하여, 적극적인 연구 분야는 일종의 차원성 감소를 채택함으로써 그러한 시스템의 구조를 단순화하기 위해 헌신한다.^[20][49]

인기 있는 방법은 모든 계층 쌍들 간의 양자 젠슨-샨논 분리의 계산에 기초하고, 이 계산법은 거리 행렬을 구축하고 계층 구조적으로 계층구조화하는 메트릭 속성에 이용된다. 계층은 결과 계층 트리에 따라 연속적으로 집계되며, 네트워크의 엔트로피에 기초한 목표 기능이 글로벌 최대치를 얻을 때 집계 절차가 중단된다. 이러한 탐욕스러운 접근법은 근본적인 문제가 모든 크기의 가능한 계층 그룹을 검증할 것을 요구하기 때문에 필요하다. 이는 (벨 번호에 의해 제공되며 단위 수에 따라 초우량적으로 척도된다.) 그럼에도 불구하고, 층수가 적은 다계층 시스템의 경우, 그 방법이 대부분의 경우에 최적으로 수행되는 것으로 나타났다.^[20]

기타 다중 계층 네트워크 설명자

정도 상관

단차원적 네트워크에서 정도 상관에 대한 문제는 상당히 간단하다: 비슷한 수준의 네트워크들이 서로 연결되는 경향이 있는가? 다차원 네트워크에서는 이 질문이 무엇을 의미하는지 명확하지 않게 된다. 노드의 학위를 언급할 때, 우리는 노드의 정도를 1차원이라고 부르는 것인가, 아니면 전체적으로 붕괴된 것인가? 노드 간의 연결을 시도할 때 차원에 걸쳐 동일한 노드를 비교하고 있는가, 차원에 따라 다른 노드를 비교하고 있는가, 아니면 조합하고 있는가?^[5] 다른 네트워크 속성에 대한 이러한 각 통계의 변동은 어떤 결과를 초래하는가? 한 연구에서, 분류성은 이중 네트워크에서의 건전성을 감소시키는 것으로 밝혀졌다.^[50]

경로 우위

Given two multidimensional paths, r and s, we say that r dominates s if and only if: ${\displaystyle \forall d\in \langle 1, D \rangle ,r_{l}\leq s_{l}}$ and ${\displaystyle \exists i}$ such that ${\displaystyle r_{l}<s_{l}}$.^[38]

최단 경로 검색

다른 네트워크 통계 중에서, 많은 중앙집중성 측정은 노드에서 노드로의 최단 경로를 평가하는 능력에 의존한다. 이러한 분석을 다차원 네트워크로 확장하려면 노드 사이의 추가 연결을 현재 사용되는 알고리즘(예: Dijkstra)에 통합해야 한다. 현재 접근방식은 넓은 범위의 첫 번째 검색에서 변형을 수행하기 전에 사전 처리 단계에서 노드들 사이의 다중 링크 연결을 붕괴시키는 것을 포함한다.^[28]

다차원 거리

다차원 네트워크에서 두 노드 사이의 거리를 평가하는 한 가지 방법은 두 노드 사이의 모든 다차원 경로를 비교하고 경로 우위를 통해 최단거리로 정의한 하위 집합을 선택하는 것이다: $M{\displaystyle }$ ${\displaystyle P(u}$, v${\displaystyle }$) ${\displaystyle MP(u,v)}$을(를) $u{\displaystyle }$ ${\displaystystyle u}$와 $v{\displaystyle }$ ${\displaystystyle v}$ 사이의 모든 경로 집합으로 한다$$.$$. Then the distance between ${\displaystyle u}$ and ${\displaystyle v}$ is a set of paths ${\displaystyle P\subseteq MP}$ such that ${\displaystyle \forall p\in P,\nexists p'\in MP}$ such that ${\displaystyle p'}$ dominates ${\displaystyle p}$. 따라서 두 노드 사이의 최단 경로 집합에서 요소의 길이는 다차원 거리로 정의된다.^[38]

치수 관련성

다차원 네트워크 $G{\displaystyle }$=${\displaystyle }$(${\displaystyle V}$, E${\displaystyle }$, ${\displaystyle D}$) ${\displaystyle G=(V,E,D)}$에서$,$ 한 노드에 대한$$ 특정 치수(또는 치수 집합) $D{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 관련성은 다음 비율로 평가할 수 있다. ${\displaystyle \frac{\text{Neighbors}}{}}$(${\displaystyle \frac{{}^{}}{}}$, D${\displaystyle \frac{}{\text{neighbors}}}$ ) Neighbors${\displaystyle \frac{}{}}$(${\displaystyle \frac{v}{}}$, ${\displaystyle \frac{D}{}}$) ${\$,D$')}{{\text{Neighbors}}(v$,D$)\}\}\}\}\}\}.$^[39]

치수 연결

서로 다른 차원의 접속이 서로 다른 실제 가치를 갖는 다차원적 네트워크에서, 다양한 계층에 대한 링크의 분포를 특징짓는 통계가 관심사다. 따라서 이를 평가하는 두 가지 지표인 치수 연결과 에지 전용 치수 연결을 고려하는 것이 유용하다. 전자는 단순히 모든 차원에 있는 링크의 총 수에 대한 특정 차원의 링크 총수의 비율이다:${\displaystyle \frac{}{}}${ (${\displaystyle \frac{u}{}}$ , ${\displaystyle \frac{v}{}}$, d${\displaystyle \frac{}{}}$) ${\displaystyle \frac{\in }{}}$ ${\displaystyle \frac{E}{}}$ ${\displaystyle \frac{u}{}}$ ${\displaystyle \frac{,}{}}$ v ${\displaystyle \frac{\in }{}}$ ${\displaystyle \frac{V}{}}$ ${\displaystyle \frac{uu}{}}$ } E $daystyle {\{(u,v,d)\in$E$u,v\in V\}$$}.$ The latter assesses, for a given dimension, the number of pairs of nodes connected only by a link in that dimension: ${\displaystyle {\frac { \{(u,v,d)\in E u,v\in V\wedge \forall j\in D,j\neq d:(u,v,j)\notin E$$\}{{{{(u,v,d)\in$E$u,v\in V$^[39]

버스트 검출

버스트니스(Bursteness)는 이메일이나 다른 인간 통신 네트워크와 같은 많은 실생활 네트워크에서 잘 알려진 현상이다. 의사소통의 추가적인 차원은 현실의 보다 충실한 표현을 제공하며 이러한 패턴을 강조하거나 감소시킬 수 있다. 그러므로 네트워크에서 버스트 동작을 감지하는 우리의 방법이 다차원 네트워크를 수용하는 것은 매우 중요하다.^[51]

다계층 네트워크의 확산 프로세스

확산 과정은 물리학에 널리 사용되며, 사회과학, 신경과학, 도시 및 국제 교통 또는 금융과 같은 다른 학문에서도 사용된다. 최근에는 단순하고 복잡한 확산 프로세스가 다계층 네트워크로 일반화되고 있다.^[22][52] 많은 연구에서 공통적으로 나타나는 한 가지 결과는 다계층 시스템의 특수한 유형인 멀티플렉스 네트워크의 확산은 1) 계층간 링크의 무게가 충분히 높지 않고, 멀티플렉스 시스템이 두 개(또는 그 이상)의 비연결 네트워크처럼 동작한다. 2) 계층간 링크의 무게가 충분히 높아서 레이어간 링크의 무게가 레이어만큼 높다는 것이다.ers가 서로 결합하면서 예기치 않은 물리적 현상이 일어나고 있다.^[22] 이 두 정권 사이에 갑작스러운 전환이 있는 것으로 나타났다.^[53]

사실, 중앙집중성 조치에서 공동체 검출에 이르기까지 어떤 확산 과정에 의존하는 모든 네트워크 설명자들은 계층 계층 연결의 영향을 받는다. 예를 들어 공동체 탐지의 경우 낮은 결합(각 계층의 정보가 전체 구조보다 더 목적적합한 경우)은 계층 내의 클러스터를 선호하는 반면 높은 결합(모든 계층의 정보가 각 계층의 별도보다 동시에 더 목적적합한 경우)은 계층 간 클러스터를 선호한다.^[7][8]

다층 시스템의 확산 반응 프로세스는 Lazaridis 등이 연구했다.^[54] $프로세스{\displaystyle }$A + B →${\displaystyle }$0 {\디스플레이 스타일 $A+B\오른쪽$ ${\displaystyle \mathrm{화살표}}$ $0}$의 경우 A와 B가 처음에 서로 다른 층에 있는 경우$$ 랜덤하게 분산되며 두 층을 만나면 모두 사라지는 것으로 확인된다. 이 모델에서는 A와 B의 반응으로 인해 혼합을 지연시키는 일종의 반발과 그에 따른 반응을 알아냈다.

무작위 보행

일차원 네트워크에 대해서는 다층계 상단에서 무작위 보행을 정의할 수 있다. 그러나 기본 다층 구조로 볼 때, 무작위 워커는 동일한 계층(점프) 내에서 한 노드에서 다른 노드로 이동하는 데 제한되지 않고 계층 간 이동(스위치)도 허용된다.^[13]

임의의 걷는 궁극적인 목표로, 즉 communities,[7][8]에를 분할하여로 넘겨 최근 더 무작위 failures,[13]뿐만 아니라 topologie의 효율적으로 이 형식을 탐사하기 위해서에 다층 네트워크의 가항과 회복력을 이해하는 데 사용되었다의 중간 규모의 조직이 흐트러지는 것은 multilayer 시스템 탐사에 사용될 수 있다.s.[55]

In the case of interconnected multilayer systems, the probability to move from a node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$ to node ${\displaystyle j}$ in layer ${\displaystyle \beta }$ can be encoded into the rank-4 transition tensor ${\displaystyle T_{j\beta }^{i\alpha }}$ and 이산 시간 걷기는 마스터 방정식으로 설명할 수 있다.

${\displaystyle p_{j\beta }(t+1)=\sum _{\alpha =1}^{L}\sum _{i=1}^{N}T_{j\beta }^{i\alpha }p_{i\alpha }(t)=\sum _{\alpha =1}^{L}\sum _{i=1}^{N}(T^{t})_{j\beta }^{i\alpha }p_{i\alpha }(0)}$

$여기$서 $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {\alpha }_{}}$ ${\displaystyle t}$) ${\displaystyle p_{i\property }(t)$는 시간 t ${\displaystyle$ $\protect }$의 노드$$ $i{\displaystyle }$ ${\displaystyle i}$에서 워커를 찾을 확률을 $나타낸다$.^[2][13]

보행자가 점프하고 전환할 수 있는 방법에 따라 전환 ${\displaystyle {텐서}_{}^{}}$ T ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{i\alpha }}_{}^{}}$ {\$displaystyle T_{j$\beta$}^{i$\alpha$$}}}}}}로 인코딩할 수 있는 보행 유형은 매우 다양하다$.$ 예를 들어 워커는 층간 및 층간 연결(일반적인 무작위 보행)을 구분하지 않고 한 번에 점프하거나 전환할 수 있으며, 현재 레이어에 머무르며 점프하거나 레이어를 전환한 후 같은 시간 스텝(물리적 무작위 보행)에서 다른 노드로 점프할 수 있다. 풀어야 할 구체적인 문제에 해당하는 보다 복잡한 규칙은 문헌에서 찾을 수 있다.^[22] 어떤 경우에는, 마스터 방정식의 고정된 용액을 분석적으로 찾을 수 있다.^[13][55]

고전 확산

복잡한 네트워크에서 고전적 확산의 문제는 수량이 시스템을 통해 어떻게 흘러갈지, 정지 상태에 도달하는 데 얼마나 많은 시간이 걸릴지를 이해하는 것이다. 멀티플렉스 네트워크의 고전적 확산은 근접한 행렬의 개념을 도입하여 최근에 연구되었고,^[56] 후에 다층 인접 텐서의 특별한 평탄화로 인식되었다.^[2] 십이법 표기법에서는 일반 다층계 상단의 확산방정식을 다음과 같이 간결하게 쓸 수 있다.

${\dfrac {dX_{j\beta }(t)}{dt}=-L_{j\beta }^{i\alpha }X_{i\alpha }(t)}$

where ${\displaystyle X_{i\alpha }(t)}$ is the amount of diffusing quantity at time ${\displaystyle t}$ in node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$. The rank-4 tensor governing the equation is the Laplacian tensor, generalizing the combinatorial Laplacian matrix of unidimensional netw오크. 비원론적 표기법에서는 방정식이 더 복잡한 형태를 취한다고 말할 만하다.

이 확산 과정의 많은 특성들은 라플라시안 텐서 중 두 번째로 작은 고유값의 관점에서 완전히 이해된다. 멀티플렉스 시스템에서의 확산은 특정 스펙트럼 특성을 만족시킨다면 각 층에서 개별적으로 또는 그 집합에서 확산 속도보다 빠를 수 있다는 점이 흥미롭다.^[56]

정보 및 전염병 확산

최근에는 다층계를 통해 정보(또는 질병)가 어떻게 전파되는지가 강도 높은 연구의 대상이 되고 있다.^[57][58][59]

다계층 상호의존적 네트워크의 퍼콜레이션

Buldyrev 등은 계층들 사이의 종속성 링크를 가진 다계층 네트워크에서 퍼콜레이션을 연구하기 위한 프레임워크를 개발했다.^[27] 갑작스러운 전환과 계단식 실패 등 새로운 물리적 현상이 발견됐다.^[60][61] 네트워크가 공간에 내장되면, 그들은 매우 작은 종속성 링크의^[62] 부분과 0개의 노드에 대한 국부적 공격에도 매우 취약해진다.^[63][64] 노드 복구가 도입되면 다지점, 이력 및 전이 가능한 체계가 포함된 리치 위상 다이어그램이 발견된다.^[65][66]

지역사회와의 상호의존성

다계층 상호의존적 네트워크(그림 참조)는 서로 다른 네트워크 내의 공동체 존재에서도 연구되었다.^[67] 다차원 상호의존적 네트워크의 공간 공동체는 Vakinnin 등을 참조한다.^[68]

다계층 네트워크에서 동적 상호의존성

동기화와 확산과 같은 동적 시스템의 상호의존성을 나타내는 동적 종속성 접근법이 다계층 네트워크에 기초하여 개발되었다.^[69] 이 연구는 다중성, 이력, 공존 지역, 거시적 혼란 등 결합된 집단 현상과 같은 현상을 발견했다.

소프트웨어

• 멀티레이어 네트워크의 분석 및 시각화를 위한 자유롭고 효율적인 프레임워크인 muxViz [1]
• Mikko Kivelae의 Python용 멀티레이어 네트워크 라이브러리(Pymnet)
• MAMULT 메트릭 및 Multilayer 네트워크 모델(C/Python 코드 모음)^[3][6]
• 다중 이슬람 모듈화 최대화에^[7] 기반한 커뮤니티 탐지를 위한 GenLouvain MATLAB 코드
• 다중 계층 네트워크 분석을 위한 다중 집합 R 및 C++ 라이브러리.

참조