쌍곡선 기하 그래프

쌍곡선 기하학 그래프(HGG) 또는 쌍곡선 기하학 네트워크(HGN)는 (1) 확률밀도 함수에 따라 일정한 음의 곡률의 쌍곡선 공간에 노드의 잠재 좌표를 살포하고 (2) 함수 o에 가까운 경우 두 노드 사이에 에지가 존재하는 특수한 유형의 공간 네트워크이다.f 메트릭^[1]^[2](일반적으로 특정 임계값 거리보다 가까운 정점 간의 결정론적 연결을 초래하는 헤비사이드 스텝 함수 또는 연결 확률을 생성하는 쌍곡선 거리의 감소 함수 중 하나).HGG는 임베딩 공간이 유클리드인 랜덤 기하 그래프(RGG)를 일반화한다.

수학 공식화

수학적으로 HGG는 정점 집합 V( $심도$ N $N=|V|$ (\ $displaystyle$ N = $V$ 와 $G(V,E)$ 노드를 2차원 쌍곡선 공간 $\mathbb {H} _{\zeta }^{2}$ 에 배치하여 구성된 에지 집합 E를 $G(V,E)$ 그래프 G $(V,$ $)$ 입니다 $.$ Auss 곡률 $-\zeta ^{2}$ - $-\zeta ^{2}$ 2 {\ $displaystyle -\zeta$ ^{ $2}}$ 및 $-\zeta ^{2}$ 컷오프 $반지름$ R {\ $displaystyle$ R $R$ 즉 쌍곡면 모델을 사용하여 시각화할 수 있는 Poincaré 디스크의 반지름.각 $점$ i(\ $displaystyle$ i $)$ 에는 $i$ $(r_{i},\theta _{i})$ 0 $0\leq r_{i}\leq R$ $0\leq r_{i}\leq R$ R $(\displaystyle$ 0 $\leq r_{i}\leq$ R $}$ $0\leq \theta _{i}<2\pi$ 0 $0\leq \theta _{i}<2\pi$ i < ${\$ \ $displaystyle$ 0 $\leq \ta$ { $i})$ 의 쌍곡선 극좌표 $r$ i $(r_{i},\theta _{i})$ 、 r_ ${i$ $0\leq \theta _{i}<2\pi$ 가 $있습니다.$

쌍곡선 코사인 법칙을 통해 두 $점$ $displaystyle$ $j$ 와 $i$ j $\displaystyle$ j 사이의 $j$ ^[2]거리 $}$ 를 $d_{ij}$ 측정할 수 있습니다 $.$

\cosh(\zeta d_{ij})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})}

(*displaystyle -\sinh(\zeta r_{i})\sinh(\zeta r_{j})\cos(\bigg (})\bracked underbrace \pi \!-!'빅' - '세타)\theta _{j} {\delta } {\bigg}}.}

각도 $\Delta$ (\ $displaystyle \Delta)$ 는 $\Delta$ 두 위치 벡터 사이의 (가장 작은) 각도입니다.

가장 단순한 경우 엣지 $(i,j)$ $)\displaystyle(i, j$ )\ $displaystyle$ i, $j)}$ 가 $(i,j)$ $확립됩니다.이거$ 는 $d_{ij}\leq r$ 임계값에 해당합니다 $.$

연결성 붕괴 함수

일반적으로 링크는 $d_{ij}$ $di$ $j$ 에 따라 확률로 확립됩니다.접속성 붕괴 $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ ( $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ s ) $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ : R + $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ [ $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ 0 $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ , $1$ ]{ $displaystyle$ \ s $d_{ij}$ : \ $mathbb$ { R }^ { + $}$ \ $to$ [ 0 $d_{ij}$ , 1 $]$ 는 $디스플레이$ 쌍으로 에지를 할당할 확률을 나타냅니다 $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ . $e$ s $s$ 이 프레임워크에서는 랜덤 기하학 그래프와 같은 하드 코드 근방의 단순한 경우를 잘라내기 붕괴 ^[3]함수라고 한다.

쌍곡선 기하학 그래프 생성

Krioukov ^[2]등은 H $\mathbb {H} _{\zeta }^{2}$ 2 \ $displaystyle \mathbb {H} _{\zeta$ }의 $반지름$ R {\ $displaystyle$ R $}$ 의 $R$ 디스크에 균일하게 랜덤 노드 분포(및 일반화된 버전)를 갖는 쌍곡선 기하학 그래프를 생성하는 방법을 설명합니다.이러한 그래프는 노드 정도에 대한 멱함수 분포를 제공합니다.각 점/노드의 각도 좌표 $\theta$ (\ $displaystyle \theta)$ 는 $\theta$ [ $[0,2\pi ]$ $†](\displaystyle [0,2\pi$ 에서 $[0,2\pi ]$ 균일하게 랜덤으로 선택되며 r의 밀도 함수는 확률 분포 $\rho$ (\ $displaystyle \rho$ 에 따라 선택됩니다.

\rho (r)=\alpha {frac {sinh (\alpha r)}{\cosh(\alpha R)

성장 $\alpha >0$ > $(\displaystyle \alpha$ > $0)$ 은 $\alpha >0$ 분포를 제어합니다. $\alpha =\zeta$ $\alpha =\zeta$ {\ { $displaystyle \$ $alpha =$ \ $zeta$ 의 경우 $\mathbb {H} _{\zeta }^{2}$ 는 H $\mathbb {H} _{\zeta }^{2}$ 2로 균일합니다. 값이 작을수록 노드는 디스크의 중앙으로, 값이 클수록 경계로 분산됩니다.이 모델에서는 $u$ 와 $v$ { $displaystyle$ v $d_{uv}<R$ 사이의 $u$ $v$ $d_{uv}<R$ 가장자리는 f $d_{uv}<R$ v < $R$ \ $displaystyle d_{uv}$ < R $d_{uv}<R$ }의 경우 또는 보다 일반적인 연결 붕괴 함수를 사용하는 경우 $\gamma (d_{uv})$ $\gamma (d_{uv})$ ( $\gamma (d_{uv})$ v $\gamma (d_{uv})$ ) \ $displaystyle \gamma$ ( $d_{uv$ }의 $\gamma (d_{uv})$ 경우 존재합니다.평균도는 쌍곡선 디스크의 $반지름$ R(\ $displaystyle$ R $)$ 에 $R$ 의해 제어됩니다.α $\alpha /\zeta >1/2$ / $\alpha /\zeta >1/2$ > $\alpha /\zeta >1/2$ / $\alpha /\zeta >1/2$ {\ $displaystyle \alpha /\zeta > 1/$ 2}의 $\alpha /\zeta >1/2$ 경우 노드 도수는 $\gamma =1+2\alpha /\zeta$ $\gamma =1+2\alpha /\zeta$ + $\gamma =1+2\alpha /\zeta$ / $\gamma =1+2\alpha /\zeta$ {\ {\ $displaystyle$ \ $displaystyle = 1+2\alpha /\zeta$ $\gamma =1+2\alpha /\zeta$ 의 멱함수 분포를 따르는 것으로 볼 수 있습니다.

이미지는 $\mathbb {H} _{1}^{2}$ 의 $\mathbb {H} _{1}^{2}$ α $(\$ $displaystyle$ $\alpha})$ 와 $\alpha$ R $(\displaystyle$ R $)$ 의 $R$ 다른 값에 대해 무작위로 생성된 그래프를 나타냅니다. α $(\displaystyle \mathbb$ ${H}_{1$ }^2 $\mathbb {H} _{1}^{2}$ 가 $\alpha$ 노드 및 $(\displaystyle$ R $)$ 의 $R$ 연결 분포에 어떤 $\alpha$ 을 미치는지 알 수 있습니다.그래프가 표시됩니다.거리 변수가 실제 쌍곡선 값을 갖는 기본 표현은 그래프의 시각화에 사용되므로 모서리는 직선입니다.

알파와 R의 다른 값에 대해 각각 N=100개의 노드를 갖는 랜덤 쌍곡 기하 그래프

이차 복잡도^[4] 발생기

쌍곡선 기하학 그래프 생성을 위한 Naigive 알고리즘은 각 점의 각도 및 반지름 좌표를 선택하여 쌍곡선 디스크의 노드를 무작위로 분포시킵니다.노드 쌍마다 에지가 각 거리의 접속 붕괴 함수 값의 확률로 삽입된다.의사 코드는 다음과 같습니다.

 $V=\{\}, E=\{\}$  위해서  $i\gets 0$  로.  $N-1$  하다      $\displaystyle \theta \gets U [ 0 , 2 \ pi ] }$       $r\gets\frac {1}{\alpha }{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])$       $(\displaystyle V=V\cup\{(r,\theta)\})$  한 쌍 한 쌍 한 쌍으로  $\displaystyle (u,v)\in V\times V,u\neq v}$  하다     한다면  $\displaystyle U[0,1]\leq \gamma (d_{uv})}$  그리고나서          $(\displaystyle E=E\cup\{(u,v)\})$  돌아가다  $V,E$

$N$ {\ $displaystyle$ N $}$ 은 $N$ 생성할 노드의 수이며, 확률밀도함수 $\rho$ {\ $displaystyle \rho}$ 에 $\rho$ 의한 반경 좌표 분포는 역변환 샘플링을 사용하여 구합니다.U{\ $displaystyle$ U $}$ 는 $U$ 지정된 간격 내의 균일한 값 샘플링입니다.알고리즘은 모든 노드 쌍의 에지를 체크하기 때문에 실행 시간은 2차입니다. $(\displaystyle$ N $)$ 이 $N$ 큰 어플리케이션에서는 더 이상 실행할 수 없으며 2차 이하의 런타임 알고리즘이 필요합니다.

이차 생성

모든 노드 쌍 사이의 모서리를 확인하지 않기 위해 최신 생성기에서는 그래프를 ^[5]^[6]밴드로 분할하는 추가 데이터 구조를 사용합니다.이를 시각화하면 주황색으로 표시된 밴드의 경계를 가진 쌍곡선 그래프를 볼 수 있습니다.이 경우 파티션은 반경 축을 따라 수행됩니다.점은 각 밴드에서 각도 좌표별로 정렬되어 저장됩니다.각 $점$ u {\ $displaystyle$ u $u$ 에 대해 $반지름$ R {\ $displaystyle$ R $}$ 의 $R$ 쌍곡선 원의 한계를 (과잉) 추정할 수 있으며 원을 교차하는 대역에 있는 점에 대해서만 에지 검사를 수행하는 데 사용할 수 있습니다.또한 각 밴드 내의 정렬을 사용하면 각도좌표가 u\ $displaystyle$ u의 $u$ 에 있는 특정 범위에 있는 점만 고려함으로써 볼 포인트 수를 더욱 줄일 수 있습니다(이 범위도u\ $displaystyle$ u 주변의 쌍곡선 원을 과대 추정하여 계산됩니다). $u$

알고리즘의 기타 확장을 사용하여 O ${\mathcal {O}}(n\log \log n+m)$ log ${\mathcal {O}}(n\log \log n+m)$ log ${\mathcal {O}}(n\log \log n+m)$ n + ${\mathcal {O}}(n\log \log n+m)$ ) ${\mathcal {O}}(n\log \log n+m)$ { $display$ style ${O}(n\log \log$ n $+m$ ( $n$ 서n { $displaystyle$ n $}$ 은 $n$ 노드 수, $m$ { $displaystyle$ m $}$ 은 $m$ 에지 수)의 시간 복잡도는 높은 ^[7]확률로 가능합니다.

쌍곡선 그래프는 각각의 점 수가 거의 동일하도록 밴드로 분할됩니다.

조사 결과

$\zeta =1$ $\zeta =1$ 1 { $displaystyle \zeta =1}($ 가우스 $K=-1$ K $=$ - $K=-1$ { $displaystyle$ K=- $1})$ 에 대해 HGG는 다수의 ^[2]노드 제한 사례에 대해 정도 분포를 닫힌 형태로 해석적으로 표현할 수 있는 네트워크 앙상블을 형성한다.이것은 많은 그래프 앙상블에 해당되지 않기 때문에 언급할 가치가 있다.

적용들

HGG는 개인의 ^[8]유사성과 인기 사이의 경쟁을 통해 쌍곡선이 나타나는 소셜 네트워크의 유망한 모델로 제안되어 왔다.

레퍼런스

^ Barthélemy, Marc (2011). "Spatial networks". Physics Reports. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID 4627021.
^ ^a ^b ^c ^d Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián (2010). "Hyperbolic geometry of complex networks". Physical Review E. 82 (3): 036106. arXiv:1006.5169. Bibcode:2010PhRvE..82c6106K. doi:10.1103/PhysRevE.82.036106. PMID 21230138. S2CID 6451908.
^ Barnett, L.; Di Paolo, E.; Bullock, S. (2007). "Spatially embedded random networks" (PDF). Physical Review E. 76 (5): 056115. Bibcode:2007PhRvE..76e6115B. doi:10.1103/PhysRevE.76.056115. PMID 18233726.
^ Krioukov, Dmitri; Orsini, Chiara; Aldecoa, Rodrigo (2015-03-17). "Hyperbolic Graph Generator". Computer Physics Communications. 196: 492–496. arXiv:1503.05180. Bibcode:2015CoPhC.196..492A. doi:10.1016/j.cpc.2015.05.028. S2CID 8454036.
^ von Looz, Moritz; Meyerhenke, Henning; Prutkin, Roman (2015). Elbassioni, Khaled; Makino, Kazuhisa (eds.). "Generating Random Hyperbolic Graphs in Subquadratic Time". Algorithms and Computation. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 9472: 467–478. doi:10.1007/978-3-662-48971-0_40. ISBN 9783662489710.
^ Meyerhenke, Henning; Laue, Sören; Özdayi, Mustafa; von Looz, Moritz (2016-06-30). "Generating massive complex networks with hyperbolic geometry faster in practice". arXiv.org. arXiv:1606.09481. Bibcode:2016arXiv160609481V. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Penschuck, Manuel (2017). "Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory". Schloss Dagstuhl - Leibniz-Zentrum für Informatik GMBH, Wadern/Saarbruecken, Germany. Leibniz International Proceedings in Informatics (LIPIcs). 75: 26:1–26:21. doi:10.4230/lipics.sea.2017.26. ISBN 9783959770361.
^ Papadopoulos, Fragkiskos; Kitsak, Maksim; Serrano, M. Ángeles; Boguñá, Marián; Krioukov, Dmitri (12 September 2012). "Popularity versus similarity in growing networks". Nature. 489 (7417): 537–540. arXiv:1106.0286. Bibcode:2012Natur.489..537P. doi:10.1038/nature11459. PMID 22972194. S2CID 4424179.

[RefSpatialReview-1] Barthélemy, Marc (2011). "Spatial networks". Physics Reports. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID 4627021.

[RefDimaPre-2] Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián (2010). "Hyperbolic geometry of complex networks". Physical Review E. 82 (3): 036106. arXiv:1006.5169. Bibcode:2010PhRvE..82c6106K. doi:10.1103/PhysRevE.82.036106. PMID 21230138. S2CID 6451908.

[RefConnectivityDecay-3] Barnett, L.; Di Paolo, E.; Bullock, S. (2007). "Spatially embedded random networks" (PDF). Physical Review E. 76 (5): 056115. Bibcode:2007PhRvE..76e6115B. doi:10.1103/PhysRevE.76.056115. PMID 18233726.

[4] Krioukov, Dmitri; Orsini, Chiara; Aldecoa, Rodrigo (2015-03-17). "Hyperbolic Graph Generator". Computer Physics Communications. 196: 492–496. arXiv:1503.05180. Bibcode:2015CoPhC.196..492A. doi:10.1016/j.cpc.2015.05.028. S2CID 8454036.

[5] von Looz, Moritz; Meyerhenke, Henning; Prutkin, Roman (2015). Elbassioni, Khaled; Makino, Kazuhisa (eds.). "Generating Random Hyperbolic Graphs in Subquadratic Time". Algorithms and Computation. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 9472: 467–478. doi:10.1007/978-3-662-48971-0_40. ISBN 9783662489710.

[6] Meyerhenke, Henning; Laue, Sören; Özdayi, Mustafa; von Looz, Moritz (2016-06-30). "Generating massive complex networks with hyperbolic geometry faster in practice". arXiv.org. arXiv:1606.09481. Bibcode:2016arXiv160609481V. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[7] Penschuck, Manuel (2017). "Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory". Schloss Dagstuhl - Leibniz-Zentrum für Informatik GMBH, Wadern/Saarbruecken, Germany. Leibniz International Proceedings in Informatics (LIPIcs). 75: 26:1–26:21. doi:10.4230/lipics.sea.2017.26. ISBN 9783959770361.

[RefPapaNature-8] Papadopoulos, Fragkiskos; Kitsak, Maksim; Serrano, M. Ángeles; Boguñá, Marián; Krioukov, Dmitri (12 September 2012). "Popularity versus similarity in growing networks". Nature. 489 (7417): 537–540. arXiv:1106.0286. Bibcode:2012Natur.489..537P. doi:10.1038/nature11459. PMID 22972194. S2CID 4424179.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

쌍곡선 기하 그래프

네임스페이스

더

목차