Dynamic Stochastic Block Models for Community Detection and Network Analysis
"Explore the application of Dynamic Bi-Partite Stochastic Block Models in community detection for network data such as corporate board memberships and academic paper co-authorships. Learn about Stochastic Block Models for graph clustering and challenges presented by bipartite networks. Discover the efficiency gains of Bipartite Formulation of SBM and extensions to address practical issues in network structure analysis. Dive into the Dynamic Stochastic Block Model (DSBM) for spectral clustering in dynamic settings. Uncover the capabilities of the dbisbm package for Dynamic Bi-Partite SBM Algorithm."
Uploaded on Mar 19, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Dynamic Bi-Partite Stochastic Block Models
Community detection in network data 1. Corporate board memberships 2. Academic paper co-authorships 3. Network of exposures in the banking sector Source: danlarremore.com; Reserve Bank of Australia
Stochastic Block Model (SBM) Generative models for graph clustering Given a network, find parameter MLEs to infer community structure Model: ? ~ ???(?,?,?) ? = random unlabeled graph on vertex set ? ?1, ,??~??? ? ? = ?1, ,??, ?? 1, ,? ? = ?1, ,??, ?? initial proportion of ? in cluster ? ? = symmetric 0,1? ? , connectivity probabilities
Bipartite networks present a special challenge Government Contracting Contractors Firms One-Mode Projection Government Contracts Issues with the traditional approach 1) Loss of dimensionality Loss of information 2) Based on overlapping cliques exaggerates assortativity 3) Inefficient search for local optima in likelihood surface
Bipartite formulation of SBM1 If we know the graph is bipartite, then we can formulate SBM (i.e., biSBM) for efficiency and accuracy gains 1) Just look for disassortative clusters 2) Time complexity comparison a) SBM: ?? ? + ? a) biSBM: ?1?1?1+ ? + ?2?2?2+ ? 1. Daniel Larremore (danlarremore.com)
Extensions to address practical issues Network structure can change over time Model-dependent likelihood surfaces Limited scalability Finding the optimal ?
Dynamic Stochastic Block Model (DSBM)2 Spectral clustering in dynamic setting Degree correction for empirical graphs with broad degree distributions Scalable, model-agnostic Model: ? ~ ????(?,?,?), where ? (??:1 ? ?) 1. Chatterjee (2017). Spectral Clustering for Dynamic Stochastic Block Model
dbisbm package (c. August 2018) Dynamic bi-Partite SBM Algorithm1 1) Find the optimal ? using minimum description length principle 2) Compute adjacency matrices at discrete times, ? = 1, ,? ?1,?2, ,?? 2) Compute sum of squared adjacency matrices without the diagonal 3) Compute ? eigenvectors corresponding to the ? largest eigenvalues 4) Until a desired ? of accuracy is reached Repeatedly applying k-means clustering algorithm on the ? eigenvectors 1. Adapted in part from DSBM (Chatterjee 2017), biSBM (Larremore 2014), and Parsimonious Module Inference in Large Networks (Peixoto, 2013).
