### Abstract

We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph G from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit 'single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph, when the graph average degree diverges. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and -in particular- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent of the vertex labels. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 185-189 |

Number of pages | 5 |

ISBN (Electronic) | 9781509018062 |

DOIs | |

State | Published - Aug 10 2016 |

Event | 2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2016-August |

ISSN (Print) | 2157-8095 |

### Other

Other | 2016 IEEE International Symposium on Information Theory, ISIT 2016 |
---|---|

Country | Spain |

City | Barcelona |

Period | 7/10/16 → 7/15/16 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Asymptotic mutual information for the binary stochastic block model'. Together they form a unique fingerprint.

## Cite this

*Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory*(pp. 185-189). [7541286] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541286