We investigate the detectability of modules in large networks when the number of modules is not known in advance. We employ the minimum description length (MDL) principle which seeks to minimize the total amount of information required to describe the network, and avoid overfitting. According to this criterion, we obtain general bounds on the detectability of any prescribed block structure, given the number of nodes and edges in the sampled network. We also obtain that the maximum number of detectable blocks scales as √ N , where N is the number of nodes in the network, for a fixed average degree k . We also show that the simplicity of the MDL approach yields an efficient multilevel Monte Carlo inference algorithm with a complexity of O(τ N log N ), if the number of blocks is unknown, and O(τ N ) if it is known, where τ is the mixing time of the Markov chain. We illustrate the application of the method on a large network of actors and films with over 10 6 edges, and a dissortative, bipartite block structure. The detection of modules -or communities -is one of the most intensely studied problems in the recent literature of network systems [1, 2]. The use of generative models for this purpose, such as the stochastic blockmodel family [3] [4] [5] [6] [7][8][9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] , has been gaining increasing attention. This approach contrasts drastically with the majority of other methods thus far employed in the field (such as modularity maximization [21]), since not only it is derived from first-principles, but also it is not restricted to purely assortative and undirected community structures. However, most inference methods used to obtain the most likely blockmodel assume that the number of communities is known in advance [14, 18, [22] [23] [24] [25] . Unfortunately, in most practical cases this quantity is completely unknown, and one would like to infer it from the data as well. Here we explore a very efficient way of obtaining this information from the data, known as the minimum description length principle (MDL) [26, 27] , which predicates that the best choice of model which fits a given data is the one which most compresses it, i.e. minimizes the total amount of information required to describe it. This approach has been introduced in the task of blockmodel inference in Ref. [28] . Here we generalize it to accommodate an arbitrarily large number of communities, and to obtain general bounds on the detectability of arbitrary community structures. We also show that, according to this criterion, the maximum number of detectable blocks scales as √ N , where N is the number of nodes in the network. Since the MDL approach results in a simple penalty on the log-likelihood, we use it to implement an efficient multilevel Monte Carlo algorithm with an overall complexity of O(τ N log N ), where τ is the average mixing time of the Markov chain, which can be used to infer arbitrary block structures on very large networks. The model -The stochastic blockmodel ensemble is composed of graphs with N nodes, each belonging to one of B blocks, and the number of edges between nodes of blocks r and s is given by the matrix e rs (or twice that number if r = s). The degree-corrected variant [14] further imposes that each node i has a degree given by k i , where the set {k i } is an additional parameter set of the model. The directed version of both models is analogously defined, with e rs becoming asymmetric, and {k − i } together with {k + i } fixing the in-and out-degrees of the nodes, respectively. These ensembles are characterized by their microcanonical entropy S = ln Ω, where Ω is the total number of network realizations [29] . The entropy can be computed analytically in both cases [30] , for the traditional blockmodel ensemble and, for the degree corrected variant, where in both cases E = rs e rs /2 is the total number of edges, n r is the number of nodes which belong to block r, and N k is the total number of nodes with degree k, and e r = s e rs is the number of half-edges incident on block r. The directed case is analogous [30] (see Supplemental Material for an overview). The detection problem consists in obtaining the block partition {b i } which is the most likely, when given an unlabeled network G, where b i is the block label of node i. This is done by maximizing the log-likelihood ln P that the network G is observed, given the model compatible with a chosen block partition. Since we have simply P = 1/Ω, maximizing ln P is equivalent to minimize the entropy S t/c , which is the language we will use henceforth. Entropy minimization is well-defined, but only as long as the total number of blocks B is known beforehand. Otherwise, the optimal value of S t/c becomes a strictly decreasing function of B. Thus, simply minimizing the entropy will lead to the trivial B = N partition, and the block matrix e rs becomes simply the adjacency matrix. A principled way of avoiding such overfitting is to consider the total amount of information necessary to describe the data, which includes not only the entropy arXiv:1212.4794v4 [physics.data-an]
Under the MDL principle, the trade-off takes the from of balancing between the description length of the coding scheme and that of the message body given the code REF .
Parsimonious module inference in large networks
Phys. Rev. Lett. 110, 148701 (2013)
Physics Mathematics Medicine