Entropy of stochastic blockmodel ensembles

Research output: Contribution to journalArticlepeer-review

65 Citations (SciVal)

Abstract

Stochastic blockmodels are generative network models where the vertices are separated into discrete groups, and the probability of an edge existing between two vertices is determined solely by their group membership. In this paper, we derive expressions for the entropy of stochastic blockmodel ensembles. We consider several ensemble variants, including the traditional model as well as the newly introduced degree-corrected version [ Karrer et al. Phys. Rev. E 83 016107 (2011)], which imposes a degree sequence on the vertices, in addition to the block structure. The imposed degree sequence is implemented both as “soft” constraints, where only the expected degrees are imposed, and as “hard” constraints, where they are required to be the same on all samples of the ensemble. We also consider generalizations to multigraphs and directed graphs. We illustrate one of many applications of this measure by directly deriving a log-likelihood function from the entropy expression, and using it to infer latent block structure in observed data. Due to the general nature of the ensembles considered, the method works well for ensembles with intrinsic degree correlations (i.e., with entropic origin) as well as extrinsic degree correlations, which go beyond the block structure.
Original languageEnglish
Article number056122
JournalPhysical Review E
Volume85
Issue number5
DOIs
Publication statusPublished - 1 May 2012

Fingerprint

Dive into the research topics of 'Entropy of stochastic blockmodel ensembles'. Together they form a unique fingerprint.

Cite this