Stochastic block model: Difference between revisions

Revision as of 09:39, 19 May 2022

Latest revision as of 22:46, 23 June 2025

(13 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Concept in network science}}

{{Network science}}

The '''stochastic [[Blockmodel|block model]]''' is a [[generative model]] for random [[Graph (discrete mathematics)|graphs]]. This model tends to produce graphs containing ''communities'', subsets of nodes characterized by being connected with one another with particular edge densities. For example, edges may be more common within communities than between communities. Its mathematical formulation haswas been firstlyfirst introduced in 1983 in the field of social network analysis by [[Paul W. Holland]] et al.<ref name="hol" /> The stochastic block model is important in [[statistics]], [[machine learning]], and [[network science]], where it serves as a useful benchmark for the task of recovering [[community structure]] in graph data.

== Definition ==

Line 61 ⟶ 62:

== Extensions to signed graphs ==

Signed graphs allow for both favorable and adverse relationships and serve as a common model choice for various data analysis applications, e.g., correlation clustering. The stochastic block model can be trivially extended to signed graphs by assigning both positive and negative edge weights or equivalently using a difference of adjacency matrices of two stochastic block models.

<ref>{{cite journalbook

| author1=Alyson Fox |author2=Geoffrey Sanders |author3=Andrew Knyazev

| title =2018 IEEE High Performance extreme Computing Conference (HPEC) |chapter=Investigation of Spectral Clustering for Signed Graph Matrix Representations | date = 2018 |pages=1–7 |doi = 10.1109/HPEC.2018.8547575|osti=1476177 |isbn=978-1-5386-5989-2 |s2cid=54443034 }}</ref>

| journal=2018 IEEE High Performance extreme Computing Conference (HPEC)

| date = 2018 |doi = 10.1109/HPEC.2018.8547575}}</ref>

== DARPA/MIT/AWS Graph Challenge: streaming stochastic block partition ==

GraphChallenge<ref>[http://graphchallenge.mit.edu] {{Webarchive|url=https://web.archive.org/web/20230204160402/http://graphchallenge.mit.edu/|date=2023-02-04}} DARPA/MIT/AWS Graph Challenge</ref> encourages community approaches to developing new solutions for analyzing graphs and sparse data derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field. Streaming stochastic block partition is one of the challenges since 2017.

<ref>[http://graphchallenge.mit.edu/champions] {{Webarchive|url=https://web.archive.org/web/20230204160403/http://graphchallenge.mit.edu/champions|date=2023-02-04}} DARPA/MIT/AWS Graph Challenge Champions</ref> [[Spectral clustering]] has demonstrated outstanding performance compared to the original and even improved<ref>{{cite journalbook

| author1 = A. J. Uppal |author2 = J. Choi |author3 = T. B. Rolinger |author4 = H. Howie Huang

| title = 2021 IEEE High Performance Extreme Computing Conference (HPEC) |chapter = Faster Stochastic Block Partition Using Aggressive Initial Merging, Compressed Representation, and Parallelism Control | date = 2021 |pages = 1–7 |doi = 10.1109/HPEC49654.2021.9622836|isbn = 978-1-6654-2369-4 |s2cid = 244780210 }}</ref>

base algorithm, matching its quality of clusters while being multiple orders of magnitude faster.<ref>{{cite journalbook

| journal=2021 IEEE High Performance Extreme Computing Conference (HPEC)

| date = 2021 |doi = 10.1109/HPEC49654.2021.9622836}}</ref>

base algorithm, matching its quality of clusters while being multiple orders of magnitude faster.<ref>{{cite journal

| author1 = David Zhuzhunashvili |author2 = Andrew Knyazev

|title journal=2018 2017 IEEE High Performance extremeExtreme Computing Conference (HPEC)

| titlechapter = Preconditioned spectral clustering for stochastic block partition streaming graph challenge (Preliminary version at arXiv.)

| journal=2017 IEEE High Performance Extreme Computing Conference (HPEC)

| date = 2017 |doipages = 10.1109/HPEC.2017.8091045}}</ref>1–6

|doi = 10.1109/HPEC.2017.8091045|arxiv = 1708.07481

<ref>{{cite journal

|isbn = 978-1-5386-3472-1

|s2cid = 19781504

}}</ref>

<ref>{{cite journalbook

| author1 = Lisa Durbeck |author2 = Peter Athanas

|title journal=2021 2020 IEEE High Performance Extreme Computing Conference (HPEC)

| titlechapter = Incremental Streaming Graph Partitioning

| journal=2020 IEEE High Performance Extreme Computing Conference (HPEC)

| date = 2020 |doipages = 10.1109/HPEC43674.2020.9286181}}</ref>1–8

|doi = 10.1109/HPEC43674.2020.9286181|isbn = 978-1-7281-9219-2

|s2cid = 229376193

}}</ref>

==See also==

Line 105 ⟶ 109:

<ref name="lr15">{{Cite journal| doi = 10.1214/14-AOS1274| issn = 0090-5364| volume = 43| issue = 1| pages = 215–237| last1 = Lei| first1 = Jing| last2 = Rinaldo| first2 = Alessandro| title = Consistency of spectral clustering in stochastic block models| journal = The Annals of Statistics| date = February 2015 | arxiv = 1312.2050| s2cid = 88519551}}</ref>

<ref name="gbm">{{Cite journal| last1 = Galhotra| first1 = Sainyam| last2 = Mazumdar| first2 = Arya| last3 = Pal| first3 = Soumyabrata|

last4 = Saha| first4 = Barna|author4-link=Barna Saha| title = The Geometric Block Model| journal = AAAI| date = February 2018 | volume = 32| doi = 10.1609/aaai.v32i1.11905| arxiv = 1709.05510| s2cid = 19152144}}</ref>

<ref name="krzakala-pnas">{{cite journal|

last1 = Krzakala| first1 = Florent|

Line 126 ⟶ 130:

title = Mixed membership stochastic blockmodels| journal = Journal of Machine Learning Research |arxiv = 0705.4485| date = May 2007 | volume = 9| pages = 1981–2014| pmid = 21701698| pmc = 3119541| bibcode = 2007arXiv0705.4485A}}</ref>

<ref name="fat19">{{cite arXiv| last = Fathi| first = Reza| title = Efficient Distributed Community Detection in the Stochastic Block Model|eprint= 1904.07494| date = April 2019 | class = cs.DC}}</ref>

<ref name="hol">{{cite journal |title=Stochastic blockmodels: First steps |journal=[[Social Networks]] |year=1983 |last1=Holland |first1=Paul W |last2=Laskey |first2=Kathryn Blackmond |last3=Leinhardt |first3=Samuel |volume=5 |issue=2 |pages=109–137 |issn=0378-8733 |doi=10.1016/0378-8733(83)90021-7 |s2cid=34098453 |url=https://doi.org/10.1016/0378-8733(83)90021-7 |accessdate=2021-06-16 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204160405/https://www.sciencedirect.com/science/article/abs/pii/0378873383900217?via%3Dihub |url-status=live |url-access=subscription }}</ref>

<ref name="ker">{{cite journal |title=Stochastic blockmodels and community structure in networks |journal=Physical Review E |year=2011 |last1=Karrer |first1=Brian |last2=Newman |first2=Mark E J |volume=83 |issue=1 |page=016107 |doi=10.1103/PhysRevE.83.016107 |pmid=21405744 |url=https://link.aps.org/doi/10.1103/PhysRevE.83.016107 |accessdate=2021-06-16 |arxiv=1008.3926 |bibcode=2011PhRvE..83a6107K |s2cid=9068097 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204160406/https://journals.aps.org/pre/abstract/10.1103/PhysRevE.83.016107 |url-status=live }}</ref>

<ref name="pei">{{cite journal |title=Hierarchical block structures and high-resolution model selection in large networks |journal=Physical Review X |year=2014 |last=Peixoto |first=Tiago |volume=4 |issue=1 |page=011047 |doi=10.1103/PhysRevX.4.011047 |url=https://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.011047 |accessdate=2021-06-16 |arxiv=1310.4377 |bibcode=2014PhRvX...4a1047P |s2cid=5841379 |archive-date=2021-06-24 |archive-url=https://web.archive.org/web/20210624195430/https://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.011047 |url-status=live }}</ref>

}}

[[Category:Machine learning]]

[[Category:Random graphs]]

[[Category:Networks]]

[[Category:Machine learningBlockmodeling]]