계층형 네트워크 모델

계층형 네트워크 모델은 스케일프리 토폴로지의 고유한 특성과 노드의 높은 클러스터링을 동시에 재현할 수 있는 네트워크를 작성하기 위한 반복 알고리즘입니다.이러한 특성은 생물학에서 언어, 일부 소셜 네트워크에 이르기까지 자연에서 널리 관찰됩니다.

개념.

계층형 네트워크 모델은 노드 간에 랜덤 생성보다 비례적으로 더 많은 허브가 있다는 주요 속성을 공유하는 스케일 프리 모델 패밀리의 일부입니다.다만, 노드의 클러스터링 계수의 분포에 있어서 다른 유사한 모델(Barabasi-Albert , Watts-Strogatz)과는 크게 다릅니다.다른 모델 w와 같이.링크 수가 많은 계층형 모델 노드에서는 클러스터 계수가 낮을 것으로 예상되므로 노드 수준의 함수로 일정한 클러스터 계수를 예측합니다.또한 BarabaaSi-Albert 모델은 노드 수가 증가함에 따라 평균 클러스터링 계수가 감소할 것으로 예측하지만 계층 모델의 경우 네트워크의 크기와 평균 클러스터링 계수 사이에는 아무런 관계가 없습니다.

계층형 네트워크 모델의 개발은 주로 스케일 프리 토폴로지와 높은 클러스터링을 하나의 모델에 통합하는 데 있어 다른 스케일 프리 모델의 실패에 의해 동기 부여되었습니다.여러 실제 네트워크(메타볼릭 네트워크, 단백질 상호작용 네트워크, 월드 와이드 웹 또는 일부 소셜 네트워크)가 이러한 특성을 나타내기 때문에, 이러한 다양한 특성을 설명하기 위해 다양한 계층 토폴로지가 도입되었다.

알고리즘.

계층형 네트워크 모델은 보통 특정 규칙에 따라 네트워크의 초기 클러스터를 복제함으로써 반복적인 방법으로 도출됩니다.예를 들어, 완전히 상호 연결된 5개의 노드(N=5)로 구성된 초기 네트워크를 고려합니다.다음 단계로 이 클러스터의 복제본 4개를 만들고 각 복제본의 주변 노드를 원래 클러스터의 중앙 노드에 연결합니다(N=25).이 단계를 무한히 반복할 수 있으므로, 임의의 k단계에 대해 시스템의 노드 수를^k+1 N=^[1]5로 도출할 수 있습니다.

물론 문헌에서 제안된 계층적 시스템을 만드는 데는 몇 가지 다른 방법이 있었다.이러한 시스템은 일반적으로 초기 클러스터의 구조와 모델의 ^[2]^[3]복제 팩터라고 불리는 확장 정도가 다릅니다.

계층형 네트워크 구조의 예.

특성.

학위 분포

스케일 프리 모델 패밀리의 일부이므로 계층형 네트워크 모델의 정도 분포는 멱함수의 법칙을 따릅니다.즉, 네트워크 내에서 랜덤으로 선택된 노드가 k개의 에지를 가지며 확률은

{\displaystyle P\left(k\right)\sim ck^{-\gamma},

여기서 c는 상수이고 θ는 도지수입니다.스케일 프리 특성을 나타내는 대부분의 실제 네트워크에서는 §가 [2,3]^[4] 간격에 있습니다.

계층적 모델에 대한 특정 결과로서 분포 함수의 정도 지수가 다음과 같이 계산될 수 있는 것으로 나타났습니다.

{\displaystyle\flac=1+{\ln M}{\ln(M-1)}}

여기서 M은 ^[5]모형의 복제 팩터를 나타냅니다.

군집화 계수

클러스터화 계수가 특정 노드의 정도에 의존하지 않는 다른 스케일프리 모델(Erdss-Rényi, Barabashi-Albert, Watts-Strogatz)과 달리 계층형 네트워크에서는 클러스터화 계수는 다음 방법으로 해당 수준의 함수로 나타낼 수 있습니다.

{\displaystyle C\left(k\right)\sim k^{-\beta},

결정론적 스케일 프리 네트워크에서 지수 β가 ^[2]1의 값을 취하는 것으로 분석적으로 나타났다.

예

액터 네트워크

www.IMDB.com에서 구할 수 있는 배우 데이터베이스를 기반으로, 네트워크는 할리우드 배우들이 같은 영화에 출연할 경우 서로 연결된 배우들에 의해 정의되며, 그 결과 392,134개의 노드와 15,347,957개의 엣지로 구성된 데이터 세트가 생성됩니다.이전 연구에서 알 수 있듯이, 이 네트워크는 적어도 k의 높은 값에 대해 스케일 프리 특성을 나타낸다.더욱이, 클러스터링 계수는 네트워크의 계층적 토폴로지에 대한 증거를 제공하는 매개변수 -1과 함께 필요한 스케일링 법칙을 따르는 것으로 보인다.직관적으로 단역 배우의 클러스터 계수는 정의상 1이지만, 여러 영화에 출연하는 배우들은 같은 크루와 함께 일할 가능성은 매우 낮으며, 일반적으로 공동 주연 배우의 ^[1]수가 증가함에 따라 클러스터 계수가 감소합니다.

언어 네트워크

단어 간의 연결 기준을 지정하면 단어를 네트워크로 간주할 수 있습니다.링크를 Merriam-Webster 사전에서 동의어로 정의함으로써 317,658개의 에지를 가진 182,853개의 노드의 의미 웹이 구성되었다.밝혀진 바와 같이, 얻어진 단어 네트워크는 그 정도 분포에서 멱함수 법칙을 따르는 반면, 군집화 계수의 분포는 기초 웹이 θ=3.25 및 β=^[1]1의 계층 구조를 따르는 것을 나타낸다.

웹 페이지 네트워크

www.nd.edu 도메인을 매핑함으로써 325,729개의 노드와 1,497,135개의 에지로 이루어진 네트워크를 얻었으며, 이들의 도 분포는 각각 =2_out.45와 =2_in.1의 멱함수 법칙을 따랐다.C(k) 분포에 뚜렷하게 눈에 띄는 감소 패턴이 있지만 클러스터링 계수의 스케일링 법칙 분포에 대한 증거는 이전 사례보다 상당히 약하다. 이는 도메인이 더 많은 링크를 가질수록 링크/링크 웹 페이지는 ^[1]^[6]덜 연결되어 있음을 나타낸다.

도메인 네트워크

도메인 네트워크, 즉 관리 도메인이 접속되어 있는 경우, AS(Autonomous System) 레벨의 인터넷에서는 65,520개의 노드와 24,412개의 링크로 구성되어 있으며 스케일 프리 네트워크의 속성을 나타내고 있습니다.군집화 계수의 표본 분포는 결정론적 스케일 프리 ^[1]^[7]네트워크에 대한 이론적 매개변수보다 지수가 (절대적으로) 다소 작은 스케일링 함수 C(k)~k에^−0.75 의해 적합되었다.

레퍼런스

^ ^a ^b ^c ^d ^e Ravasz, E. B.; Barabási, A. L. S. (2003). "Hierarchical organization in complex networks". Physical Review E. 67 (2): 026112. arXiv:cond-mat/0206130. Bibcode:2003PhRvE..67b6112R. doi:10.1103/PhysRevE.67.026112. PMID 12636753.
^ ^a ^b Dorogovtsev, S.; Goltsev, A.; Mendes, J. (2002). "Pseudofractal scale-free web". Physical Review E. 65 (6): 066122. arXiv:cond-mat/0112143. Bibcode:2002PhRvE..65f6122D. doi:10.1103/PhysRevE.65.066122. PMID 12188798.
^ Barabási, A. L. S.; Ravasz, E. B.; Vicsek, T. S. (2001). "Deterministic scale-free networks". Physica A: Statistical Mechanics and its Applications. 299 (3–4): 559. arXiv:cond-mat/0107419. Bibcode:2001PhyA..299..559B. doi:10.1016/S0378-4371(01)00369-7.
^ Barabási, A.; Albert, R. (1999). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342.
^ Noh, J. (2003). "Exact scaling properties of a hierarchical network model". Physical Review E. 67 (4). arXiv:cond-mat/0211399. Bibcode:2003PhRvE..67d5103N. doi:10.1103/PhysRevE.67.045103.
^ Barabási, A. L. S.; Albert, R. K.; Jeong, H. (1999). "Internet: Diameter of the World-Wide Web". Nature. 401 (6749): 130. arXiv:cond-mat/9907038. Bibcode:1999Natur.401..130A. doi:10.1038/43601.
^ Vázquez, A.; Pastor-Satorras, R.; Vespignani, A. (2002). "Large-scale topological and dynamical properties of the Internet". Physical Review E. 65 (6): 066130. arXiv:cond-mat/0112400. Bibcode:2002PhRvE..65f6130V. doi:10.1103/PhysRevE.65.066130. PMID 12188806.

[RB-2003-1] Ravasz, E. B.; Barabási, A. L. S. (2003). "Hierarchical organization in complex networks". Physical Review E. 67 (2): 026112. arXiv:cond-mat/0206130. Bibcode:2003PhRvE..67b6112R. doi:10.1103/PhysRevE.67.026112. PMID 12636753.

[DGM-2002-2] Dorogovtsev, S.; Goltsev, A.; Mendes, J. (2002). "Pseudofractal scale-free web". Physical Review E. 65 (6): 066122. arXiv:cond-mat/0112143. Bibcode:2002PhRvE..65f6122D. doi:10.1103/PhysRevE.65.066122. PMID 12188798.

[BRV-2001-3] Barabási, A. L. S.; Ravasz, E. B.; Vicsek, T. S. (2001). "Deterministic scale-free networks". Physica A: Statistical Mechanics and its Applications. 299 (3–4): 559. arXiv:cond-mat/0107419. Bibcode:2001PhyA..299..559B. doi:10.1016/S0378-4371(01)00369-7.

[BA-1999-4] Barabási, A.; Albert, R. (1999). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342.

[N-2003-5] Noh, J. (2003). "Exact scaling properties of a hierarchical network model". Physical Review E. 67 (4). arXiv:cond-mat/0211399. Bibcode:2003PhRvE..67d5103N. doi:10.1103/PhysRevE.67.045103.

[AJB-1999-6] Barabási, A. L. S.; Albert, R. K.; Jeong, H. (1999). "Internet: Diameter of the World-Wide Web". Nature. 401 (6749): 130. arXiv:cond-mat/9907038. Bibcode:1999Natur.401..130A. doi:10.1038/43601.

[VSPV-2002-7] Vázquez, A.; Pastor-Satorras, R.; Vespignani, A. (2002). "Large-scale topological and dynamical properties of the Internet". Physical Review E. 65 (6): 066130. arXiv:cond-mat/0112400. Bibcode:2002PhRvE..65f6130V. doi:10.1103/PhysRevE.65.066130. PMID 12188806.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search