Phys. Rev. E 98, 032309 (2018) - Universality of the stochastic block model

Loading [MathJax]/extensions/MathMenu.js

Universality of the stochastic block model

Jean-Gabriel Young, Guillaume St-Onge, Patrick Desrosiers, and Louis J. Dubé

Phys. Rev. E 98, 032309 – Published 24 September 2018

Abstract

Mesoscopic pattern extraction (MPE) is the problem of finding a partition of the nodes of a complex network that maximizes some objective function. Many well-known network inference problems fall in this category, including, for instance, community detection, core-periphery identification, and imperfect graph coloring. In this paper, we show that the most popular algorithms designed to solve MPE problems can in fact be understood as special cases of the maximum likelihood formulation of the stochastic block model (SBM) or one of its direct generalizations. These equivalence relations show that the SBM is nearly universal with respect to MPE problems.

Received 15 June 2018
Revised 1 September 2018

DOI:https://doi.org/10.1103/PhysRevE.98.032309

©2018 American Physical Society

Physics Subject Headings (PhySH)

Network structure

Social networks

Block models Metropolis algorithm Simulated annealing

Networks

Authors & Affiliations

Jean-Gabriel Young^1,2,*, Guillaume St-Onge^1,2, Patrick Desrosiers^1,2,3, and Louis J. Dubé^1,2,†

¹Département de physique, de génie physique et d'optique, Université Laval, Québec (Québec), Canada G1V 0A6
²Centre interdisciplinaire de modélisation mathématique de l'Université Laval, Québec (QC), Canada G1V 0A6
³Centre de recherche de CERVO, Québec (QC), Canada G1J 2G3

^*jean-gabriel.young.1@ulaval.ca
^†ljd@phy.ulaval.ca

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 98, Iss. 3 — September 2018

Reuse & Permissions

1988: Giant magnetoresistance is discovered

View timeline|#PhysRev125

Access Options

Images

Figure 1
Four examples of mesoscopic pattern extraction problems on artificial networks. (a) Community detection [22, 25], (b) community detection with further structure, (c) the identification of a simple core-periphery split [15, 26], (d) identification of a core with a structured periphery. The targeted patterns are identified with colors.
Reuse & Permissions
Figure 2
Two-part algorithms in practice. We apply different combinations of maximizers and objective functions to a simple network with a clear block structure, generated using the SBM. Different MPE algorithms reveal different mesoscopic structures, but changing the objective function has the largest impact. (a, b) Same objective functions (modularity, see Sec. 3b3) and different maximizers [(a) spectral, (b) greedy]. (b, c) Same maximizer (greedy) with two different objective functions [(b) modularity, (c) core-periphery see Sec. 3a3]. The greedy maximizer is adapted from the Kernighan-Lin algorithm [30], in the spirit of Ref. [12], and the spectral maximizer relies on the embedding of the $q - 1$ $q - 1$ leading eigenvectors of the modularity matrix [25, 31] in $R^{q - 1}$ $R^{q - 1}$ , followed by a clustering step, here implemented using a Gaussian mixture [32].
Reuse & Permissions
Figure 3
Partial hierarchy of objective functions. The pairwise score function of MPE methods are shown with the range of parameters below. Arrows denote specialization; doubled–sided arrows denote equivalence. Only the most direct arrows are drawn for the sake of clarity; specialization and equivalence are transitive operations. The abbreviations are: stochastic block model (SBM), with side information (SISBM); and general modular graph modular model (GMGM), with side information (SIGMGM). Functions derived from the perspective of statistical inference are colored in blue (general classification) and red (binary classification).
Reuse & Permissions
Figure 4
Mesoscopic patterns learned from and imposed on a real complex network. All results are obtained on the polblog dataset, a directed network of hyperlinks between weblogs on U.S. politics, recorded shortly after the 2004 presidential election. There are a total of $1222$ $1 222$ nodes (weblogs) and $16714$ $16 714$ edges. We use an undirected, self-loop free version of the network. All subfigures show (top) the network with nodes colored according to the identified partition, (center) a cartoon of the matrix $ω$ $ω$ imposed for the equivalent SBM [darker shades of blue represent larger values of $ω_{r s}$ $ω_{r s}$ ], and (bottom) the adjacency matrix with the limit of blocks indicated as colored lines and edges as white dots. The optima of the objective functions are found via simulated annealing and greedy search [46]. (a) Natural partition of the network in $q = 2$ $q = 2$ blocks, as found with the classical Bernoulli SBM via expectation–maximization (EM) on $B$ $B$ and $ω$ $ω$ . In this case alone, $ω$ $ω$ is learned and not imposed. (b) Balanced cut obtained with $γ \approx - 25$ $γ \approx - 25$ and the GMGM. The two blocks have size $n^{⊺} = [650, 572]$ $n^{⊺} = [650, 572]$ . A similar partition is identified by the modularity. (c) Double core-periphery found with $γ \approx - 9$ $γ \approx - 9$ . The cores are of sizes 98 and 87 while their respective peripheries contain 396 and 641 nodes. There are only $3703$ $3 703$ edges between nodes of the peripheries (out of a maximum of $283330$ $283 330$ possible edges).
Reuse & Permissions

2 of 4

Sign up to receive regular email alerts from Physical Review E