  With the rapid expansion of graphs and networks and the growing magnitude of
data from all areas of science, effective treatment and compression schemes of
context-dependent data is extremely desirable. A particularly interesting
direction is to compress the data while keeping the "structural information"
only and ignoring the concrete labelings. Under this direction, Choi and
Szpankowski introduced the structures (unlabeled graphs) which allowed them to
compute the structural entropy of the Erd\H{o}s--R\'enyi random graph model.
Moreover, they also provided an asymptotically optimal compression algorithm
that (asymptotically) achieves this entropy limit and runs in expectation in
linear time.
  In this paper, we consider the Stochastic Block Models with an arbitrary
number of parts. Indeed, we define a partitioned structural entropy for
Stochastic Block Models, which generalizes the structural entropy for unlabeled
graphs and encodes the partition information as well. We then compute the
partitioned structural entropy of the Stochastic Block Models, and provide a
compression scheme that asymptotically achieves this entropy limit.
