확률 블록 모형

확률 블록 모델은 랜덤 그래프에 대한 생성 모델입니다.이 모델은 특정 에지 밀도로 서로 연결된 것이 특징인 노드의 하위 집합인 커뮤니티를 포함하는 그래프를 생성하는 경향이 있습니다.예를 들어, 에지는 커뮤니티 간보다 커뮤니티 내에서 더 일반적일 수 있습니다.이 수학 공식은 1983년 Holland ^[1]등에 의해 소셜 네트워크 분야에서 처음 도입되었다.확률 블록 모델은 통계, 기계 학습 및 네트워크 과학에서 중요한데, 여기서 그래프 데이터의 커뮤니티 구조를 복구하는 작업에 유용한 벤치마크로 기능한다.

정의.

확률적 블록 모델은 다음 매개변수를 취합니다.

꼭지점 $수$ n(\ $displaystyle$ n $)$
정점 $\{1,\ldots ,n\}$ 세트 { $\{1,\ldots ,n\}$ , $\{1,\ldots ,n\}$ $}{displaystyle \{1,\ldots,n\}}$ 을 $\{1,\ldots,n\}$ (를) 커뮤니티라고 불리는 분리된 $C_{1},\ldots ,C_{r}$ $C_{1},\ldots ,C_{r}$ $C_{1},\ldots ,C_{r}$ { $style$ C_ ${1},\ldots,C_{r$ 로 분할한다.
$대칭$ $r\times r$ × $r\times r$ {\ $displaystyle r\times$ r $r\times r$ $P$ } $행렬$ P {\displaystyle P $}$ 의 에지 확률입니다.

다음으로 엣지 세트는 다음과 같이 랜덤하게 샘플링됩니다.u $u\in C_{i}$ $u\in C_{i}$ ${\$ C 、 \ $displaystyle$ u \ $in$ C _ { $i$ } 、 $v\in C_{j}$ $v\in C_{j}$ ${\$ C j \ $displaystyle$ v \ $in$ C _ { $j$ $}$ $P_{ij}$ edge $v\in C_{j}$ $n$ two two $P_{ij}$ vertices vertices vertices by by by by by by by by by by by by by by byby by by by the the the the the the the by $P_{ij}$ by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by by $P_{ij}$ by by by by설명에 따라 샘플링하여 그룹 $C_{1},\ldots ,C_{r}$ $(\$ 을 회복합니다.

특수한 경우

확률적 블록 모형에 대한 분류 사례의 예제입니다.

확률행렬이 상수일 경우, $모든$ i $j$ j에 $P_{ij}=p$ Pi $=$ p { $displaystyle$ $P_$ {ij $}=p$ }의 $P_{ij} = p$ 의미에서는 그 결과는 Erdss – Rényi $G(n,p)$ G $(n,$ p $G(n,p)$ 가 됩니다. $그러나$ 이 경우 파티션은 무관합니다.Erdrs-Rényi 모델

심어진 파티션모델은 $확률행렬 P$ 의 $P$ 값이 $대각선상$ $상수$ p와 대각선상 $q$ 인 $p$ $q$ 특수한 경우입니다.따라서 동일한 커뮤니티 내의 두 정점은 $확률$ p $\displaystyle$ p $p$ 인 에지를 공유하며, 다른 커뮤니티의 두 정점은 $확률$ q\ $display$ q $q$ display q\인 에지를 공유합니다. 경우에 따라 확률 블록 모델이라고 불리는 것이 이 제한된 모델입니다. $p<q$ $p>q$ > $p>q$ < $display$ $style$ p $> q$ 의 경우는 어소시에이션 모델이라고 불리며, $p<q$ p < $p<q$ < display p < $q >$ 는 $p<q$ 어소시에이션 모델이라고 불립니다.

일반 확률 블록 모델로 돌아가면, $P_{ii}>P_{jk}$ > $P_{ii}>P_{jk}$ k { $style P_{ii}$ >의 경우, 모델을 강구색체라고 부른다. $P_{jk}$ : $j\neq k$ k \ $displaystyle$ j \ $neq$ k $j\neq k$ : 모든 대각 엔트리가 모든 오프 대각 엔트리를 지배합니다. $P_{ii}>P_{ij}$ 은 $P_{ii}>P_{ij}$ i > $P_{ii}>P_{ij}$ j { $display style$ P_ ${ii}$ >의 $P_{ii}>P_{ij}$ 약하게 분류됩니다. $P_{$ $ij$ $i\neq j$ 대각선 엔트리는 다른 행과 ^[2] $열$ 을 지배하기 위해서만 $i\neq j$ 합니다 $.$ 모든 불평등을 뒤집음으로써 이 용어의 불협화음이 존재한다.알고리즘에 따라서는 이 ^[2]형식의 정렬 또는 분리 조건을 가진 블록 모델의 복구가 더 쉬울 수 있습니다.

일반적인 통계 태스크

알고리즘 커뮤니티 검출에 관한 문헌의 대부분은 검출, 부분 회복 및 정확한 회복의 3가지 통계 태스크를 다루고 있습니다.

검출

검출 알고리즘의 목적은 단순히 샘플 그래프를 통해 그래프가 잠재된 커뮤니티 구조를 가지고 있는지 여부를 결정하는 것이다.좀 더 정확하게는, 그래프는 알려진 확률적 블록 모델, 그리고 유사한 에르도-레니 모델로부터 알려진 사전 확률과 함께 생성될 수 있다.알고리즘 작업은 ^[3]이 두 가지 기본 모델 중 어떤 모델이 그래프를 생성했는지 정확하게 식별하는 것입니다.

부분 복구

부분 회복에서는 임의의 ^[4]추측보다 실제 파티션과 훨씬 더 잘 연관된 파티션을 찾는다는 의미에서 커뮤니티에 잠재된 파티션을 대략적으로 결정하는 것이 목표입니다.

정확한 복구

정확한 복구에서는 잠재된 파티션을 커뮤니티로 정확하게 복구하는 것이 목표입니다.커뮤니티의 크기와 확률 행렬은 알려져^[5] 있거나 ^[6]알려져 있지 않을 수 있습니다.

통계 하한 및 임계값 동작

확률적 블록 모델은 침투 ^[7]^[3]^[8]임계값을 연상시키는 뚜렷한 역치 효과를 보인다.그래프의 크기 $n$ (\ $style$ n $)$ 을 $n$ 증가시켜 커뮤니티 크기를 일정한 비율로 유지한다고 가정합니다.확률 행렬이 고정된 상태로 유지되면 모든 비퇴행 매개 변수 설정에 대해 부분적 및 정확한 복구와 같은 작업을 수행할 수 있습니다.그러나 n $(\displaystyle$ n $)$ 이 $n$ $n$ 에 따라 확률 매트릭스를 적절한 속도로 축소하면 급격한 단계 전이를 볼 수 있습니다. 파라미터의 특정 설정에 대해서는 1이 되는 확률로 회복할 수 있는 반면 파라미터 임계값의 반대편에서는 회복할 가능성이 높아집니다.nds ~0 이 됩니다.

부분 회복의 경우, 적절한 스케일은 고정 ${\tilde {P}}$ ~ {\ $displaystyle P_$ ${ij$ $}$ {ij $}$ $_{$ $ij$ }/ $n}$ 에 $P_{ij} = \tilde P_{ij} / n$ 대해 $P_{ij}={\tilde {P}}_{ij}/n$ j $P_{ij}={\tilde {P}}_{ij}/n$ ~ $P_{ij}={\tilde {P}}_{ij}/n$ $P_{ij}={\tilde {P}}_{ij}/n$ 을 $P_{ij}={\tilde {P}}_{ij}/n$ 으로써 일정한 평균 정도의 그래프가 생성됩니다.크기가 동일한 두 커뮤니티의 경우 확률 행렬이 있는 분류식 분할 모델에서

{\displaystyle P=\left({\begin{array}{cc}}{\tilde {q}}/n\{\tilde {q}}/n&{\tilde {p}}/n\end {array}}\right})

반면에 어떤 추정자 −(1){\displaysty입니다 확률 1에 다소 회복 fails[3]부분 회복은 −(1){1-o(1)\displaystyle} 때마다(p~ − q ~)2을입니다 확률 1;2(p~+q~){\displaystyle({\tilde{p}}-{\tilde{q}})^{2}>, 2({\tilde{p}}와{\tilde{q}})}, feasible[4].르 1-o(1)}

1-o(1)

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

~ -

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

~ )

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

<

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

(

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

~ +

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

q

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

~

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

) {

displaystyle

{ \

tilde

{

p

} - { \

tilde

{ q } } {

2 \({

} + { \

tilde

{

q

}

({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})

} 。

정확한 복구를 위해 $P_{ij}={\tilde {P}}_{ij}\log n/n$ 스케일링은 P $P_{ij}={\tilde {P}}_{ij}\log n/n$ j $P_{ij}={\tilde {P}}_{ij}\log n/n$ $P_{ij}={\tilde {P}}_{ij}\log n/n$ ~i $P_{ij}={\tilde {P}}_{ij}\log n/n$ $δ$ n / $P_{ij}={\tilde {P}}_{ij}\log n/n$ n { $display$ style P_ ${ij$ } = $philde {P}}_{ij}\log$ n $/n$ 을 취하여 로그 평균 차수의 그래프를 만드는 것입니다.여기에는 유사한 임계값이 존재합니다.r $\displaystyle$ r $}$ 개의 $r$ 동일한 크기의 커뮤니티를 $가진$ 모둠 식재 파티션모델의 경우 임계값은 ${\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}$ ~ - ${\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}$ ~ $=$ r { $displaystyle$ { $tilde$ {p $}}-{\displayrt$ { $tilde$ { $q$ displayrt ${r}$ 입니다.실제로 정확한 복구 임계값은 전체 확률에 대해 알려져 있습니다.블록 ^[5]모델

알고리즘

원칙적으로 정확한 복구는 최대우도를 사용하여 실현 가능한 범위에서 해결할 수 있지만, 이는 일반적으로 NP-완전인 최소 이등분 등 제약 또는 정규화된 절단 문제를 해결하는 것과 같습니다.따라서 알려진 효율적인 알고리즘은 최악의 경우 최대우도 추정치를 올바르게 계산하지 않습니다.

그러나 평균적인 경우 다양한 알고리즘이 잘 수행되며, 부분적인 복구 설정과 정확한 복구 설정 모두에서 알고리즘에 대해 높은 확률의 성능 보증이 많이 입증되었습니다.성공적인 알고리즘에는 ^[9]^[4]^[5]^[10]정점의 스펙트럼 클러스터링, 반무한 프로그래밍,^[2]^[8] 믿음 ^[7]^[11]전파의 형태, 그리고 다른 것 사이의 공동체^[12] 검출이 포함됩니다.

변종

모델에는 몇 가지 변형이 있습니다.하나의 사소한 수정은 고정 ^[5]파티션이 아닌 범주형 분포에 따라 정점을 커뮤니티에 무작위로 할당합니다.보다 중요한 변형에는 정도 보정 확률 블록 모델,^[13] 계층적 확률 블록 모델,^[14] 기하학적 블록 모델,^[15] 관측 중단 블록 모델 및 혼합 멤버십 블록 ^[16]모델이 포함된다.

토픽 모델

확률적 블록 모델은 초당적 ^[17]네트워크에서 주제 모델로 인식되어 왔다.문서와 단어의 네트워크에서 확률 블록 모델은 유사한 의미를 가진 단어 그룹이라는 주제를 식별할 수 있습니다.

서명된 그래프의 확장

부호 있는 그래프는 바람직한 관계와 불리한 관계 모두를 허용하며, 다양한 데이터 분석 애플리케이션(예: 상관 군집화)에 대한 공통 모델 선택으로 기능한다.확률 블록 모델은 양의 에지 가중치와 음의 에지 가중치를 모두 할당하거나 두 확률 블록 모델의 인접 행렬의 차이를 사용하여 서명된 그래프로 3차적으로 확장될 수 있다.^[18]

DARPA/MIT/AWS 그래프 챌린지: 스트리밍 확률 블록 파티션

Graph Challenge는^[19] 소셜 미디어, 센서 피드 및 과학 데이터에서 파생된 그래프 및 희박한 데이터를 분석하기 위한 새로운 솔루션을 개발하기 위한 커뮤니티 접근 방식을 장려하여 현장에서 전개되는 이벤트 간의 관계를 발견할 수 있도록 합니다.스트리밍 확률 블록 파티션은 2017년 이후 당면 과제 중 하나입니다.^[20] 스펙트럼 클러스터링은 원래의 개량된 베이스 알고리즘에^[21] 비해 뛰어난 성능을 보여 주었으며, 클러스터 품질과 일치하면서도 몇 배나 ^[22]빠른 속도를 보였다.^[23]

「」를 참조해 주세요.

블록 모델링
Girvan-Newman 알고리즘: 커뮤니티 검출 알고리즘
Lancichinetti – Fortunato – Radicchi 벤치마크 – 커뮤니티와 벤치마크 네트워크를 생성하는 알고리즘

레퍼런스

^ Holland, Paul W; Laskey, Kathryn Blackmond; Leinhardt, Samuel (1983). "Stochastic blockmodels: First steps". Social Networks. 5 (2): 109–137. doi:10.1016/0378-8733(83)90021-7. ISSN 0378-8733. Retrieved 2021-06-16.
^ ^a ^b ^c Amini, Arash A.; Levina, Elizaveta (June 2014). "On semidefinite relaxations for the block model". arXiv:1406.5647 [cs.LG].
^ ^a ^b ^c Mossel, Elchanan; Neeman, Joe; Sly, Allan (February 2012). "Stochastic Block Models and Reconstruction". arXiv:1202.1499 [math.PR].
^ ^a ^b ^c Massoulie, Laurent (November 2013). "Community detection thresholds and the weak Ramanujan property". arXiv:1311.3085 [cs.SI].
^ ^a ^b ^c ^d Abbe, Emmanuel; Sandon, Colin (March 2015). "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms". arXiv:1503.00609 [math.PR].
^ Abbe, Emmanuel; Sandon, Colin (June 2015). "Recovering communities in the general stochastic block model without knowing the parameters". arXiv:1506.03729 [math.PR].
^ ^a ^b Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborová, Lenka (September 2011). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". Physical Review E. 84 (6): 066106. arXiv:1109.3041. Bibcode:2011PhRvE..84f6106D. doi:10.1103/PhysRevE.84.066106. PMID 22304154. S2CID 15788070.
^ ^a ^b Abbe, Emmanuel; Bandeira, Afonso S.; Hall, Georgina (May 2014). "Exact Recovery in the Stochastic Block Model". arXiv:1405.3267 [cs.SI].
^ Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan; Neeman, Joe; Sly, Allan; Lenka, Lenka; Zhang, Pan (October 2013). "Spectral redemption in clustering sparse networks". Proceedings of the National Academy of Sciences. 110 (52): 20935–20940. arXiv:1306.5550. Bibcode:2013PNAS..11020935K. doi:10.1073/pnas.1312486110. PMC 3876200. PMID 24277835.
^ Lei, Jing; Rinaldo, Alessandro (February 2015). "Consistency of spectral clustering in stochastic block models". The Annals of Statistics. 43 (1): 215–237. arXiv:1312.2050. doi:10.1214/14-AOS1274. ISSN 0090-5364. S2CID 88519551.
^ Mossel, Elchanan; Neeman, Joe; Sly, Allan (September 2013). "Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models". The Annals of Applied Probability. 26 (4): 2211–2256. arXiv:1309.1380. Bibcode:2013arXiv1309.1380M. doi:10.1214/15-AAP1145. S2CID 184446.
^ Fathi, Reza (April 2019). "Efficient Distributed Community Detection in the Stochastic Block Model". arXiv:1904.07494 [cs.DC].
^ Karrer, Brian; Newman, Mark E J (2011). "Stochastic blockmodels and community structure in networks". Physical Review E. 83 (1): 016107. arXiv:1008.3926. doi:10.1103/PhysRevE.83.016107. PMID 21405744. S2CID 9068097. Retrieved 2021-06-16.
^ Peixoto, Tiago (2014). "Hierarchical block structures and high-resolution model selection in large networks". Physical Review X. 4 (1): 011047. arXiv:1310.4377. doi:10.1103/PhysRevX.4.011047. S2CID 5841379. Retrieved 2021-06-16.
^ Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; Saha, Barna (February 2018). "The Geometric Block Model". AAAI. arXiv:1709.05510.
^ Airoldi, Edoardo; Blei, David; Feinberg, Stephen; Xing, Eric (May 2007). "Mixed membership stochastic blockmodels". Journal of Machine Learning Research. 9: 1981–2014. arXiv:0705.4485. Bibcode:2007arXiv0705.4485A. PMC 3119541. PMID 21701698.
^ Martin Gerlach; Tiago Peixoto; Eduardo Altmann (2018). "A network approach to topic models". Science Advances. 4 (7): eaaq1360. arXiv:1708.01677. Bibcode:2018SciA....4.1360G. doi:10.1126/sciadv.aaq1360. PMC 6051742. PMID 30035215.
^ Alyson Fox; Geoffrey Sanders; Andrew Knyazev (2018). "Investigation of Spectral Clustering for Signed Graph Matrix Representations". 2018 IEEE High Performance extreme Computing Conference (HPEC). doi:10.1109/HPEC.2018.8547575.
^ [1] DARPA/MIT/AWS 그래프 챌린지
^ [2] DARPA/MIT/AWS 그래프 챌린지 챔피언
^ A. J. Uppal; J. Choi; T. B. Rolinger; H. Howie Huang (2021). "Faster Stochastic Block Partition Using Aggressive Initial Merging, Compressed Representation, and Parallelism Control". 2021 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC49654.2021.9622836.
^ David Zhuzhunashvili; Andrew Knyazev (2017). "Preconditioned spectral clustering for stochastic block partition streaming graph challenge". 2017 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC.2017.8091045.
^ Lisa Durbeck; Peter Athanas (2020). "Incremental Streaming Graph Partitioning". 2020 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC43674.2020.9286181.

[hol-1] Holland, Paul W; Laskey, Kathryn Blackmond; Leinhardt, Samuel (1983). "Stochastic blockmodels: First steps". Social Networks. 5 (2): 109–137. doi:10.1016/0378-8733(83)90021-7. ISSN 0378-8733. Retrieved 2021-06-16.

[al14-2] Amini, Arash A.; Levina, Elizaveta (June 2014). "On semidefinite relaxations for the block model". arXiv:1406.5647 [cs.LG].

[mns12-3] Mossel, Elchanan; Neeman, Joe; Sly, Allan (February 2012). "Stochastic Block Models and Reconstruction". arXiv:1202.1499 [math.PR].

[mas13-4] Massoulie, Laurent (November 2013). "Community detection thresholds and the weak Ramanujan property". arXiv:1311.3085 [cs.SI].

[as15a-5] Abbe, Emmanuel; Sandon, Colin (March 2015). "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms". arXiv:1503.00609 [math.PR].

[as15b-6] Abbe, Emmanuel; Sandon, Colin (June 2015). "Recovering communities in the general stochastic block model without knowing the parameters". arXiv:1506.03729 [math.PR].

[decelle11-7] Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborová, Lenka (September 2011). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". Physical Review E. 84 (6): 066106. arXiv:1109.3041. Bibcode:2011PhRvE..84f6106D. doi:10.1103/PhysRevE.84.066106. PMID 22304154. S2CID 15788070.

[abh14-8] Abbe, Emmanuel; Bandeira, Afonso S.; Hall, Georgina (May 2014). "Exact Recovery in the Stochastic Block Model". arXiv:1405.3267 [cs.SI].

[krzakala-pnas-9] Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan; Neeman, Joe; Sly, Allan; Lenka, Lenka; Zhang, Pan (October 2013). "Spectral redemption in clustering sparse networks". Proceedings of the National Academy of Sciences. 110 (52): 20935–20940. arXiv:1306.5550. Bibcode:2013PNAS..11020935K. doi:10.1073/pnas.1312486110. PMC 3876200. PMID 24277835.

[lr15-10] Lei, Jing; Rinaldo, Alessandro (February 2015). "Consistency of spectral clustering in stochastic block models". The Annals of Statistics. 43 (1): 215–237. arXiv:1312.2050. doi:10.1214/14-AOS1274. ISSN 0090-5364. S2CID 88519551.

[mns13-11] Mossel, Elchanan; Neeman, Joe; Sly, Allan (September 2013). "Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models". The Annals of Applied Probability. 26 (4): 2211–2256. arXiv:1309.1380. Bibcode:2013arXiv1309.1380M. doi:10.1214/15-AAP1145. S2CID 184446.

[fat19-12] Fathi, Reza (April 2019). "Efficient Distributed Community Detection in the Stochastic Block Model". arXiv:1904.07494 [cs.DC].

[ker-13] Karrer, Brian; Newman, Mark E J (2011). "Stochastic blockmodels and community structure in networks". Physical Review E. 83 (1): 016107. arXiv:1008.3926. doi:10.1103/PhysRevE.83.016107. PMID 21405744. S2CID 9068097. Retrieved 2021-06-16.

[pei-14] Peixoto, Tiago (2014). "Hierarchical block structures and high-resolution model selection in large networks". Physical Review X. 4 (1): 011047. arXiv:1310.4377. doi:10.1103/PhysRevX.4.011047. S2CID 5841379. Retrieved 2021-06-16.

[gbm-15] Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; Saha, Barna (February 2018). "The Geometric Block Model". AAAI. arXiv:1709.05510.

[ar1-16] Airoldi, Edoardo; Blei, David; Feinberg, Stephen; Xing, Eric (May 2007). "Mixed membership stochastic blockmodels". Journal of Machine Learning Research. 9: 1981–2014. arXiv:0705.4485. Bibcode:2007arXiv0705.4485A. PMC 3119541. PMID 21701698.

[gerlachnetwork-17] Martin Gerlach; Tiago Peixoto; Eduardo Altmann (2018). "A network approach to topic models". Science Advances. 4 (7): eaaq1360. arXiv:1708.01677. Bibcode:2018SciA....4.1360G. doi:10.1126/sciadv.aaq1360. PMC 6051742. PMID 30035215.

[18] Alyson Fox; Geoffrey Sanders; Andrew Knyazev (2018). "Investigation of Spectral Clustering for Signed Graph Matrix Representations". 2018 IEEE High Performance extreme Computing Conference (HPEC). doi:10.1109/HPEC.2018.8547575.

[19] [1] DARPA/MIT/AWS 그래프 챌린지

[20] [2] DARPA/MIT/AWS 그래프 챌린지 챔피언

[21] A. J. Uppal; J. Choi; T. B. Rolinger; H. Howie Huang (2021). "Faster Stochastic Block Partition Using Aggressive Initial Merging, Compressed Representation, and Parallelism Control". 2021 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC49654.2021.9622836.

[22] David Zhuzhunashvili; Andrew Knyazev (2017). "Preconditioned spectral clustering for stochastic block partition streaming graph challenge". 2017 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC.2017.8091045.

[23] Lisa Durbeck; Peter Athanas (2020). "Incremental Streaming Graph Partitioning". 2020 IEEE High Performance Extreme Computing Conference (HPEC). doi:10.1109/HPEC43674.2020.9286181.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Search

확률 블록 모형

네임스페이스

더

목차

정의.

특수한 경우

일반적인 통계 태스크

검출

부분 복구

정확한 복구

통계 하한 및 임계값 동작

알고리즘

변종

토픽 모델

서명된 그래프의 확장

DARPA/MIT/AWS 그래프 챌린지: 스트리밍 확률 블록 파티션

「」를 참조해 주세요.

레퍼런스

Search

확률 블록 모형

정의.

특수한 경우

일반적인 통계 태스크

검출

부분 복구

정확한 복구

통계 하한 및 임계값 동작

알고리즘

변종

토픽 모델

서명된 그래프의 확장

DARPA/MIT/AWS 그래프 챌린지: 스트리밍 확률 블록 파티션

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.