Community Detection through Likelihood Optimization: In Search of a Sound Model

Community detection is one of the most important problems in network analysis. Among many algorithms proposed for this task, methods based on statistical inference are of particular interest: they are mathematically sound and were shown to provide partitions of good quality. Statistical inference methods are based on fitting some random graph model (a.k.a. null model) to the observed network by maximizing the likelihood. The choice of this model is extremely important and is the main focus of the current study. We provide an extensive theoretical and empirical analysis to compare several models: the widely used planted partition model, recently proposed degree-corrected modification of this model, and a new null model having some desirable statistical properties. We also develop and compare two likelihood optimization algorithms suitable for the models under consideration. An extensive empirical analysis on a variety of datasets shows, in particular, that the new model is the best one for describing most of the considered real-world complex networks according to the likelihood of observed graph structures.


INTRODUCTION
Among various properties shared by many real-world complex networks, community structure is extremely important. It is characterized by the presence of highly interconnected groups of vertices (communities or clusters) relatively well separated from the rest of the network. In social networks communities are formed by users with similar interests, in citation networks they represent papers on related topics, etc. The presence of communities highly affects, e.g., the promotion of products via viral marketing, the spreading of infectious diseases, computer viruses and information, and so on. Being able to identify communities in a network could help us to exploit this network more effectively: find similar scientific papers, discover users with similar interests for targeted advertisement, compress or visualize the network, etc.
Among other algorithms proposed for community detection, the notable ones are methods based on statistical inference. In such methods, some underlying random graph model is assumed, the evidence is represented by the observed graph, and hidden variables to be inferred are the parameters of the model together with community assignments. Such methods are appealing since they are theoretically sound and consistent: e.g., it has been proved that when the maximum-likelihood method is applied to networks generated from the same stochastic block model, it returns correct cluster assignments in the limit of large degrees [7]. Also, likelihood can be used to formalize the notion of a community [15].
The choice of the proper null model is essential for statistical inference algorithms as it highly affects their performance. There are two types of models: with fixed or non-fixed number of parameters. Direct likelihood optimization for models with non-fixed number of parameters leads to trivial partitions, as discussed in Section 4.1, and additional heuristics are needed to define the number of clusters. Hence, in this paper we focus on models with fixed number of parameters. We analyze strengths and weaknesses of two most popular models -planted partition model and its degree-corrected variant (they are discussed in Section 3). We also propose a new model, which has only one parameter, satisfies a desired statistical property of preserving the expected degree sequence, and shows the best fit for a variety of real-worlds networks according to the likelihood of observed structures.
Our research is similar in spirit to the recent paper by Yang and Leskovec [58], where the authors provided an extensive comparison of various community scoring functions. In contrast, we focus solely on the likelihood optimization methods and, particularly, on the comparison of the null models. Note that such models allow to score partitions on the global level instead of individual communities. To the best of our knowledge, we are the first to perform such thorough evaluation of the null models used for community detection.
To sum up, the contributions of this paper are the following: • We theoretically analyze two well-known null models used for community detection. Based on this analysis, we propose a new one-parameter model which has a desirable statistical property of preserving the expected degree sequence. • We empirically demonstrate that the new model gives the best fit to a variety of real-world complex networks. • We show that the likelihood based on the proposed model can be used as a new, more reliable, alternative to the wellknown modularity measure. • We develop several likelihood optimization algorithms suitable for all discussed models. We perform an extensive empirical comparison of all the algorithms on various synthetic and real-world datasets.

• The implementation of the proposed algorithms is available
as an open-source library. 1 The rest of the paper is organized as follows. In the next section we overview related papers and introduce the required background.
Then, in Section 3, we formally define and analyze all null models used in the current research. In Section 4, we discuss the method of statistical inference and present the likelihoods for all models. The proposed likelihood optimization algorithms are discussed in Section 5. Section 6 provides an extensive empirical analysis of all models and algorithms and Section 7 concludes the paper.

BACKGROUND AND RELATED WORK 2.1 Community Detection Methods
In this section, we briefly overview algorithms used for community detection. However, most of the related work will be discussed in the corresponding background sections: Section 2.2 discusses modularity measure; Section 2.3 defines the LFR bechmark; Sections 3.1 and 3.2 describe standard null models; Section 4.2 discusses papers on statistical inference; Section 5.1 deals with some optimization techniques. For a deeper overview of community detection area, we refer the reader to several survey papers, e.g., [10,16,19,21,33].
The problem of community detection has recently attracted a lot of attention and many algorithms were proposed to solve this problem. The proposed methods include: spectral algorithms [55]; methods based on statistical inference (see Section 4); methods based on optimization (see Section 5); methods based on dynamical processes on networks, like diffusion, spin dynamics, synchronization, and so on. Also, existing approaches differ by a particular task at hand: detecting overlapping communities [57], clustering in dynamic [51], directed [48], or weighted [3] networks, community detection in annotated [39] or layered [44] networks, and so on.
In this paper, we focus on the basic problem of detecting nonoverlapping communities in undirected and unweighted graphs. However, ideas discussed in this paper can be applied to more general cases, since there exist the corresponding generalizations of the null models. We leave this analysis for the future research, since there is a lot to be understood even for the basic case.

Modularity
Throughout this paper we assume that we are given a simple undirected graph G = (V (G), E(G)) and the task is to find a partition C = {C 1 , . . . , C k } of its vertex set V (G) such that C i = V (G) and C i C j = ∅ for i j. The notation used in the paper is summarized in Table 1.
For various problems related to community detection it is extremely important to have a quality functionQ(C, G) which measures a goodness of a partition C for a graph G. Having such a function, one can: • OptimizeQ(C, G) to detect good communities according to this measure; • UseQ(C, G) as a stopping criteria for a community detection algorithm (e.g., to choose the partition level in hierarchical algorithms); • Tune parameters of a parametric community detection algorithm; • Compare several community detection algorithms when no ground truth partition is available; • Compare several candidate partitions of G. The most well-known such measure is modularity which was first introduced by Newman and Girvan [40]. The basic idea is to number of intra-community edges m out = m out (C, G) number of inter-community edges P = n 2 number of pairs of vertices P in = C ∈C |C | 2 number of intra-community pairs of vertices P out = P − P in number of inter-community pairs of vertices number of edges between C q and C r or twice the number of intra-cluster edges if q = r e(i, j) number of edges between i and j consider the fraction of intra-community edges among all edges of G and penalize it in order to avoid trivial partitions like C = {V (G)}.
In its general form, modularity is where m = m(G) = |E(G)| is the number of edges in G; m in = m in (C, G) is the number of intra-community edges; m ′ in = m ′ in (C) is a (random) number of intra-community edges in a graph constructed according to some underlying random graph model; γ is the resolution parameter [47], which is usually added to get the possibility of varying the number of communities obtained after maximizing Q(C, G, γ ).
The simplest underlying model is the Erdős-Rényi random graph, i.e., we assume that G is sampled uniformly at random from the set of all graphs with n vertices and m edges. For this model, E(m ′ in ) = P in · m P , where P = n 2 is the number of pairs of vertices and P in = C ∈ C |C | 2 is the number of intra-community pairs. So, the formula for simple modularity is However, the Erdős-Rényi random graph model is known to be not a good descriptor of real-world networks since its Poisson degree distribution significantly differs from heavy-tailed degree distributions observed in real-world networks. A standard solution is to consider a random graph with a given expected degree sequence [12] as a null model, and to take the degree sequence from the observed graph. 2 For this model, the probability that vertices i and j are connected equals 2m , where d(i) is the degree of a vertex i. 3 In this case we have where D(C) = i ∈C d(i) is the degree of cluster C. So, the standard expression for modularity is Originally, modularity was introduced with γ = 1, but is was proven to have a resolution limit [20], i.e., it fails to detect communities smaller than a certain size; varying the resolution parameter helps to overcome this problem, but tuning γ is challenging.
Despite some known shortcomings [19], modularity remains the most popular way to measure the quality of a partition and many algorithms are based on direct modularity optimization (see Section 5). Also, as we discuss in Section 4, under certain assumptions, modularity maximization is equivalent to likelihood optimization [36]. In this paper we also propose a new quality function based on a more consistent one-parametric null model.

LFR Model
Let us now describe the LFR (Lancichinetti-Fortunato-Radicchi) model [29], which is the most widely used synthetic benchmark for comparison of community detection algorithms.
LFR generates a graph G on n vertices. The main parameters of the model are: the exponent of the power-law degree distribution γ , the exponent of the power-law community size distribution β, the average degreed, and mixing parameterμ. First, we generate the degrees of vertices by sampling them independently from the powerlaw distribution with exponent γ and meand. Each vertex shares a fraction 1 −μ of its edges with the vertices of its community and a fractionμ with the other vertices of the network. The sizes of the communities are sampled from the power-law distribution with exponent β, such that the sum of all sizes equals n. Then, vertices are assigned to communities such that the internal degree of any vertex is less than the size of its community. Finally, the configuration model [35] with rewiring steps is used to construct a graph with the given degree sequence and with the required fraction of internal edges. See [29] for the detailed description of this procedure.

NULL MODELS
In this section, we analyze several random graph models having community structure and suitable for using as null models for likelihood optimization.

Stochastic Block Model
The most well-known random graph model with community structure is the stochastic block model (SBM) [26]. In this model, the vertices are divided in k clusters and for each pair of vertices i, j 3 For technical purposes, it is more convenient (and conventional) to allow the underlying model to have loops and multiple edges and to assume that the number of edges between vertices i and j follows a Poisson distribution with the mean d (i )d (j) 2m if i i and the expected number of loops for a vertex i is d (i ) 2 4m . In particular, in this case we avoid problems when d (i)d (j) > 2m which can possibly occur. Note that usually d (i)d (j) ≪ 2m, so multiple edges rarely appear.
we draw an edge between them with probability p c(i),c(j) independently of all other edges; here c(i) is a community assignment for a vertex i. In other words, the probability of an edge between two vertices depends only on their community assignments. The values p q,r , 1 ≤ q, r ≤ k are parameters of the model, 0 ≤ p q,r ≤ 1 and p q,r = p r,q . The matrix of the probabilities p q,r is called the stochastic block matrix. If the diagonal elements are larger than the other ones, then generated graphs have community structure.
In many community detection algorithms a simplified version of SBM called planted partition model (PPM) is used [14]. PPM is a special case of SBM, where p q,q = p in for 1 ≤ q ≤ k and p q,r = p out for 1 ≤ q, r ≤ k, q r , p in and p out are parameters of PPM.

Degree-Corrected Stochastic Block Model
Similarly to the Erdős-Rényi random graph, SBM is unable to model heavy-tailed degree distributions, so community detection algorithms based on this model may have a poor quality. To overcome this issue, Karrer and Newman proposed the degree-corrected stochastic block model (DCSBM) [28]. In this model the vertices are again assigned to k clusters and edges are placed independently at random. The number of edges between vertices i and j follows a Poisson distribution with the mean 2m p c(i),c(j) or a half that number for self-loops. Let us show that DCSBM is able to generate graphs with desired expected degrees. Proposition 1. There exist such p q,r that in DCPPM we have Proof. Let us set where m(C q , C r ) is the number of edges between clusters C q and C r or twice the number of intra-cluster edges if q = r . Note that these parameters maximize the likelihood for DCSBM [28]. For such parameters we get the desired condition: So, we proved that in its general form DCSBM is able to preserve the desired degree sequence. □ The degree-corrected planted partition model (DCPPM) [36] is a simplified version of DCSBM, where p q,q = p in for 1 ≤ q ≤ k and p q,r = p out for 1 ≤ q, r ≤ k, q r . Let us prove the following "negative" proposition.
Proposition 2. If p in p out and for some q, r we have D(C q ) D(C r ), then E(d ′ (i)) d(i) for some i.
Proof. Let us compute the expected degree of i: To get E(d ′ (i)) = d(i) for all i, we need to have, for any cluster C, As we have at least two clusters with different values D(C), we have to take p in = p out = 1 , which leads to the standard configuration model without any community structure and contradicts the statement of the proposition. □ As a result, we obtain that the standard method of limiting the number of parameters in DCSBM leads to inability of the obtained model to preserve the expected degree sequence.

Independent LFR Model
Motivated by Proposition 2, we developed a one-parameter model which preserves the expected degree sequence. It is a special case of DCSBM and we call it independent LFR model (ILFR) due to its analogy to the LFR benchmark.
The core problem of DCPPM is the assumption that the probability of an internal edge is independent of the size of its community, so the fraction of internal edges for a vertex depends on the community size. On the contrary, we propose using the mixing parameter µ to control this fraction. Namely, we consider DCSBM with the following expected number of edges between two vertices i and j: if c(i) c(j) , (or half this number for the self loops). Note that making the probability of an internal edge dependent on the size of the community is very natural: e.g., if a community of people is very small, one would expect that its members are much closer related to each other than members of large communities. The following proposition holds for the proposed model.
Proof. Indeed, let us compute the expected degree of i: □ So, this model solves the problem with expected degrees. Another advantage of ILFR is that it has only one parameter µ instead of p in and p out in planted partition models.

STATISTICAL INFERENCE 4.1 Method
Having discussed possible options for the null models, we are ready to describe the statistical inference method. For community detection problem, this method consists of two ingredients: the evidence, expressed by a graph G, and a random graph null model with parameters θ (θ include community assignments and µ or p in and p out for the models under consideration). The goal is to find such parameters θ that maximize the posterior distribution where P(θ ) is the prior distribution of parameters and P(G) = ∫ P(G |θ )P(θ ) dθ is independent of θ , therefore arg max θ P(θ |G) = arg max θ P(G |θ )P(θ ) . The choice of the prior distribution P(θ ) is usually not obvious. Therefore, in the community detection literature, the likelihood P(G |θ ) that the model is consistent with the observed graph structure is often maximized.
Let us also stress that in Section 3 we discussed two types of models: SBM/DCSBM having non-fixed number of parameters and PPM/DCPPM/ILFR with a fixed number of parameters. If the number of parameters is fixed, then the likelihood optimization can be applied directly. Otherwise, one needs another tool to find the optimal number of clusters, since direct likelihood maximization would lead to a trivial partition with all vertices forming their own clusters and the probability of an edge between two vertices equals 1 if they are connected and 0 otherwise. To avoid this problem, we further focus only on the models with fixed number of parameters.

Related Work on Statistical Inference
Let us briefly describe previous literature on statistical inference in community detection. Hastings [24] considers PPM, as defined in Section 3.1. He shows a connection between the obtained likelihood and the Hamiltonian of a Potts model with short-and long-range interactions. For p in > p out , the model is a spin glass with ferromagnetic nearest-neighbor interactions and antiferromagnetic longrange interactions. Belief propagation is used to find the ground state of the spin model. Another method based on the directed SBM is presented by Newman and Leicht [41], they use the expectationmaximization technique to optimize the parameters. These ideas are close to the a posteriori blockmodel proposed in [42]. A variational approach to parameter estimation is adopted in [17]. Some improvements and modifications of these approaches are introduced in, e.g., [11,25,45,60]. A generalization to the overlapping SBM is proposed by McDaid and Hurley [34]. As we discussed, DCSBM is defined in [28] and communities are detected based on the likelihood in this model. Copic et al. [15] define an axiomatization for the problem of community detection based on PPM. Likelihood is used as a quality function to define rankings between graph partitions and it is shown that such rankings satisfy a number of desired properties. The authors also propose an algorithm to find (approximately) the maximum likelihood partition.
Finally, if the number of parameters in the model is not fixed, some additional tools are required to figure out the optimal number of clusters. Here the average entropy of the classification [45] or the Integrated Classification Likelihood [17,60] can be used.

Likelihood for PPM and Simple Modularity
The log-likelihood for PPM can be easily written: Although it can be optimized directly using the algorithms discussed further in the paper, in order to demonstrate a connection of the loglikelihood to simple modularity defined in (1) and to deal with all models in a unified way, we use the conventional trick and say that the number of edges between i and j follows a Poisson distribution with parameter p in or p out . Then we get: where e(i, j) is the number of edges between i and j, so Note that the values p in and p out maximizing (3) are In a resent paper by Newman [36] it was shown that if we assume p in and p out to be fixed, then maximizing (3) is equivalent to maximizing simple modularity (1). Indeed, So, we get the equivalence with

Likelihood for DCPPM and Modularity
Let us compute the log-likelihood for the DCPPM [36]: The values of parameters maximizing this likelihood are: As shown in [36], if p in and p out are fixed, then maximizing log L DC P P M (C, G, p in , p out ) is exactly equivalent to maximizing modularity (2) with

Likelihood for ILFR
Let us compute the likelihood for the proposed ILFR model: is twice the number of edges induced by C. Note that the optimal value of µ is hard to find analytically, but it can be approximated numerically by optimizing (9). The following approximation helps to speed up the optimization algorithms and to make formulas more concise: (1−µ) 2 m . This leads to another quality function, which we further refer to as ILFRS (S stands for "simplified"): The optimal µ according to (10) can now be computed analytically: Note that now we can substitute µ in (10) by the optimal value (11) and obtain a non-parametric quality function: The obtained function is fairly simple and, as we show by further experiments, it can successfully replace the standard modularity function in many applications. Let us also note that in contrast to ILFR, the likelihood for the standard LFR model cannot be computed. First, LFR is based on the configuration model, which introduces complex dependences between all edges, making the likelihood intractable. Second, and most importantly, the number of iter-community edges for each vertex is deterministic (the fraction of such edges is µ); as a result, for most of graphs and partitions the likelihood is equal to zero.

OPTIMIZATION 5.1 Related Work on Modularity Optimization
First, let us discuss some optimization approaches used in community detection. The most widely used measure to be optimized is modularity (2). The following types of approaches are known.
Greedy optimization. Newman and Girvan [40] proposed a greedy algorithm for modularity optimization, where the clusters are iteratively merged by choosing the pair which leads to a greater modularity increase (while it is positive). A speedup of the greedy algorithm was proposed by Clauset et al. [13]. Some other modifications were also suggested in, e.g., [49,56]. Probably the most well-known and widely used greedy algorithm is called Louvain [8]. At the beginning each vertex forms its own cluster. Then we create the first level of the partition by iterating through all vertices: for each vertex i we compute the gain in modularity coming from putting i to the community of its neighbor and pick the community with the largest gain, as long as it is positive. After that the first level is formed and we replace the obtained communities by supervertices, and two supervertices are connected by a (weighted) edge if there is at least one edge between vertices of the corresponding communities. Then the process is repeated with the supervertices, and so on, as long as modularity increases. This algorithm was shown to be fast and provide partitions of good quality. We choose Louvain algorithm as the basis for our experiments, the detailed description of its application to our problem is given in Section 5.2.
Simulated annealing. Simulated annealing was first applied to modularity optimization in [23]. This method combines two types of moves: local moves, where a single vertex is shifted from one cluster to another; global moves, consisting of merges and splits of communities. Methods based on simulated annealing are relatively slow and cannot be applied to large datasets.
Spectral optimization. Spectral methods are quite popular in modularity optimization. Such methods use the eigenvalues and eigenvectors of a so-called modularity matrix. Some examples can be found in [37,53].

Proposed Likelihood Optimization Methods
In Section 4, we presented four quality functions based on the likelihood: PPM (3), DCPPM (6), ILFR (9), and ILFRS (10). All functions are parametric: PPM and DCPPM have parameters p in and p out , ILFR and ILFRS have one parameter µ. In this section, we discuss the possible ways to maximize these likelihoods. Below we assume that we are given an arbitrary algorithm FindPartition(Q, G) which is able to find a partition by maximizing some quality functionQ(C, G).
Although the optimization strategies proposed below are able to work with any algorithm FindPartition, let us first discuss our particular choice. As we already mentioned, we choose Louvain algorithm [8], which is arguably the most widely used method for community detection. Louvain is fast and allows to process large datasets. Importantly, it can be adapted to all quality functions discussed in this paper. Initially the method is designed to optimize modularity, so it can be directly applied to the likelihood of DCPPM due to their equivalence. To adapt Louvain to other likelihoods, we have to change one part of the original algorithm: when we try to remove a vertex (or supervertex) from one community an add to another, we need to efficiently compute the difference in likelihood. This can be done for any of the considered quality functions: for ILFR and ILFRS the differences can be computed using (9) and (10); for PPM we have to additionally store the sizes of supervertices in order to compute the difference for P in in (1). The rest of the Louvain algorithm remains the same. 4 Therefore, the asymptotic time complexity of our Louvain-based FindPartition and of the original Louvain are the same, up to a constant multiplier (the complexity of Louvain is empirically evaluated to be O(n log n)).
Note that both the original Louvain and our modifications can be applied to the likelihoods with fixed values of parameters p in , p out or µ. Therefore, the key question is how to find the optimal values of these parameters.
Iterative strategy. The simplified version of this strategy was initially proposed in [36] for PPM and DCPPM models. Detailed description of our method is presented in Algorithm 1. Initially, we fix γ = 1 or µ = 0.5 depending on the null model. Then, we apply Find-Partition to the corresponding log-likelihood function. Using the obtained partition we can re-estimate the parameters and continue this procedure until convergence or until some maximum allowed number of steps is reached. In our experiments we noticed that for any null model the parameters may end up cyclically varying near some value. Therefore, at each iteration we additionally check if we obtain an already seen parameter and stop in this case. This additional trick allows to significantly reduce the overall number of iterations. In our experiments we observed that we never need more than 50 iterations and the mean value is much smaller, see Section 6 for more details.
Maximization strategy. An alternative strategy is to directly search for parameters which maximize likelihood of the obtained partition. Here we can use any black-box optimization method. At each iteration of optimization, for some value of γ or µ, we run FindPartition to obtain a partition C, then, using C, we find the optimal parameters according to (4), (7), (11) or by optimizing (9). Finally, we compute the likelihood to be maximized using (3), (6), (9), or (10). In our experiments, for simplicity and reproducibility, we use grid search in this strategy. However, any other method of black-box parameter optimization can be used instead, e.g., random search [5], Bayesian optimization [50], Gaussian processes [22], sequential model-based optimization [6,27], and so on. if Model is PPM or DCPPM then Compute p in and p out according to (4) or (7); Compute param new according to (5)  To summarize, the maximization strategy directly maximizes the obtained likelihood, while the iterative one searches for a "stable" parameter, i.e., the one which does not change after applying FindPartition. Note that the convergence of the iterative strategy is not guaranteed for real-world networks. Therefore, initially we expected the maximization strategy to be more stable. However, our experiments show that these two strategies demonstrate similar performance, but the iterative one is faster.
Let us mention another possible optimization strategy, which we do not use in our experiments. Given a partition C, for each likelihood function except ILFR, we can compute the optimal values of parameters according to (4), (7), and (11). Therefore, for the corresponding models we can substitute these parameters and obtain non-parametric likelihoods, as we did in (12) for ILFRS. Namely, for PPM we can replace p in and p out in (3) by (4) and obtain log L P P M (C, G) = m in log m in P in + m out log m out P out − m .
For DCPPM, we replace p in and p out in (6) by (7) and get All obtained non-parametric quality functions can potentially be optimized directly since they do not have free parameters. However, we do not consider such strategy since: 1) it cannot be applied to ILFR as there is no analytical formula for optimal µ, 2) this strategy cannot be easily combined with the Louvain algorithm. The reason is that Louvain has several partition levels and partitions obtained on earlier levels cannot be changed later. At the beginning of the algorithm our estimates of µ, p in , and p out are far from optimal: all vertices form their own communities, so µ = 1, p out = 1, and p in = 0. As a result, the first level of the partition, which has a big impact on the final quality, is constructed based on non-optimal parameters. In fact, in most cases the algorithm does not even start optimization due to the huge overestimate of µ or p out .

EXPERIMENTS
In this section, we conduct an extensive experimental study to compare the discussed models. We start with some preliminaries and discuss evaluation metrics and datasets. In Section 6.3, we measure how well the models describe various real-world networks. Next, we compare all proposed community detection algorithms. Finally, Section 6.5 presents some negative results on the limits of statistical inference algorithms when applied to real-world networks.

Evaluation Metrics
In order to evaluate the performance of any algorithm, we have to compare the partition C obtained by this algorithm with the ground truth partition C GT . The problem of choosing a good similarity measure for this comparison does not have any standard solution in community detection literature. Different similarity measures can possibly give preferences to different algorithms. Usually, a suitable measure is chosen according to a practical problem at hand. That is why in this work we compute and compare several standard similarity measures.
In particular, we use Normalized Mutual Information (NMI) of two partitions C and C GT , which is often used for the comparison of community detection algorithms [4,19]. The idea behind NMI is that if two partitions are similar, one needs very little information to infer C GT given C. Assume that cluster labels for C GT and C are values of two random variables ξ GT and ξ . Then, where I (ξ GT , ξ ) = H (ξ ) − H (ξ GT |ξ ) is the mutual information of ξ GT and ξ , H (ξ ) is the Shannon entropy of ξ , H (ξ GT |ξ ) is the conditional entropy of ξ GT given ξ . We also use two well-known similarity measures based on counting correctly and incorrectly classified pairs of vertices. Let n 11 denote the number of pairs of vertices which are in the same community in both partitions C and C GT , n 01 (n 10 ) the number of pairs which are in the same community in C (C GT ) and in different communities in C GT (C), and n 00 the number of pairs that are in different communities in both partitions. By combining the introduced values one can obtain several similarity measures. We use two most popular ones, the first is Rand index [46]: n 11 +n 00 n 11 +n 10 +n 01 +n 00 , i.e., the fraction of the number of correctly classified pairs of vertices to the total number of pairs. One problem of the Rand index is that its value is usually close to 1, since n 00 is typically very high. The well-known Jaccard index does not suffer from this problem, it is defined as n 11 n 11 +n 10 +n 01 , i.e., the fraction of the number of vertex pairs classified in the same cluster in both partitions to the number of pairs classified in the same cluster in at least one partition. Table 2: Real-world datasets; µ, γ 0 , and γ 1 are computed for ground truth partitions according to (11), (4,5) and (7,8)   We use the LFR model described in Section 2.3 to generate synthetic networks. The parameters of the generated graphs are the following: the number of vertices n = 10 4 ; the parameter of the power-law degree distribution γ = 2.5; the average degreed = 30; the parameter of the community size distribution β = 1.5, with the minimum cluster size 50 and the maximum 600; the mixing parameterμ is varied in range [0, 1]. We additionally experimented with synthetic graphs of different edge densities obtained by varying the average degree. The results are omitted since the only difference observed is that the qualities of all algorithms are usually larger for denser graphs. Finally, note that there are other benchmark models proposed in the literature. However, community detection in synthetic networks is not the main focus in this paper, therefore we do not consider such models.

Real-world networks.
We collected several networks with different structural properties (see Table 2). In addition to widely used networks, such as Zachary's karate club, dolphin social network, and American college football, we also used annotated books about politics 5 and political blogs [1]. The dataset email-Eu-core is obtained from SNAP, 6 here the ground truth communities correspond to the departments of a research institute. In Cora citation dataset communities correspond to subjects of research papers, while in AS [9] the vertices are annotated with their countries. These are all publicly available datasets we found for non-overlapping community detection. 7

Comparison of Likelihoods
Since the main aim of this paper is to analyze and compare several null models having community structure, we start with the following research question: Which model gives the best fit for realworld complex networks? To answer this question, we compare the probabilities that real-world networks were generated by each of the null models. Namely, we compared the log-likelihoods (3) for PPM, (6) for DCPPM and (9) for ILFR. 8 Note that (10) is a simplified expression for (9), so we consider it only as a quality function but not as log-likelihood.
In the first experiment, we took the datasets described in Section 6.2.2 and assumed that the partitions are defined by the ground truth cluster assignments provided for these datasets. Then, we computed the optimal parameters p in , p out or µ and used them to compute the corresponding log-likelihood (see Table 3). One can see that PPM is the best model describing the Football dataset, DCPPM is the best for Pol-books, while for all other datasets ILFR has the largest likelihood. Note that ILFR has only one parameter to be tuned while DCPPM has two. Therefore, we initially expected that for many datasets DCPPM may have a larger likelihood. In this case, to decide which model better describes the data, we would have to adapt some information criterion (e.g., the Bayesian information criterion) to our problem, which is a nontrivial task for the models under consideration. Surprisingly, for most of the datasets ILFR has a larger likelihood, which clearly indicates that this model is more suitable for describing real-world networks. 9 However, even though for each dataset under consideration we have a ground truth partition (a.k.a. attributes or metadata), this partition can be not an ideal division of vertices into communities and also can be not the only ground truth partition possible. For example, many complex networks have hierarchical community structure: e.g., for Cora dataset we can use original attributes (/Ar-tificial_Intelligence/Machine_Learning/Probabilistic_Methods/ ), or second-level ones (/Artificial_Intelligence/Machine_Learning/ ), or just first-level (Artificial_Intelligence). 10 We further discuss this problem in Section 6.4.2.
Fortunately, likelihoods can be compared even for datasets without any knowledge about community structure, which allows to compare null models on a much larger variety of datasets. In order to measure the likelihood for any graph, we first have to find a partition that maximizes this value (among all possible partitions), which is feasible only for very small datasets. However, the optimal partition (and the corresponding likelihood) can be approximately found by applying the corresponding maximization algorithm: PPM-max, DCPPM-max or ILFR-max. We performed such comparison on the datasets introduced in Section 6.2.2 as well as on 8 new datasets of various nature downloaded from http://snap.stanford.edu/data/index.html (see Table 4). According to this experiment, for almost all datasets the largest likelihood is again obtained for ILFR model, despite it has fewer free parameters, which means that this model is the best one for describing realworld datasets, which is the main empirical result supporting the introduction of ILFR and the corresponding log-likelihood quality function.
Let us note that the log-likelihoods presented in Table 4 can be underestimated, since we cannot guarantee that our optimization algorithms find exactly the maximum likelihood partition. However, we believe that this does not introduce any bias into this experiment (i.e., does not change the conclusions) since the same optimization procedure is applied for all models. Also, note that in all cases the log-likelihoods in Table 3 are smaller than the corresponding ones in Table 4, which means that our optimization algorithms found partitions providing better likelihoods for the corresponding models than the ground truth ones, which is expected (since partitions were tuned).

Community Detection Algorithms
In this section, we compare all algorithms proposed in Section 5.2. Note that we intentionally use only methods based on the likelihood optimization since this paper focuses on the analysis and comparison of null models.
6.4.1 Synthetic networks. First, we compared all algorithms on synthetic networks described in Section 6.2.1. For eachμ we generated 5 random samples of LFR and averaged the results. Figure 1 shows the results obtained for all similarity measures under consideration (Rand, Jaccard and NMI). Note that in most cases these similarity measures are consistent, i.e., for a given mixing parameter they rank the algorithms similarly. However, Jaccard index is less descriptive for large mixing parameters.
Based on the obtained results, several important observations can be made. For all values ofμ, the best (or very close to the best) quality is obtained by ILFRS-max and ILFR-max strategies. For both ILFR and ILFRS it turns out that maximizing the likelihood is better than iteratively estimating the parameters, which supports 10 By measuring the likelihood for all such partitions of Cora, we notices that original attributes provide the highest likelihood for all null models, therefore we further analyze only this partition.  We also measured statistical significance of the obtained improvements: for eachμ, we applied the algorithms to 5 random samples of LFR and used the paired t-test. For instance, it turns out that according to NMI ILFRS-max never looses significantly and it is significantly better (p-value < 0.05) than: DCPPM-max for µ ∈ {0.7, 0.9, 1}; DCPPM-iterate forμ ∈ {0.7, 0.8}; PPM-max and PPM-iterate for allμ ∈ [0.2, 1]; ILFR-iterate and ILFRS-iterate for    (12) for community detection instead of the standard modularity function.
6.4.2 Real-world complex networks. It is argued in several papers that ground truth community labels (a.k.a. metadata) available for some real-world networks should not be used to analyze and compare community detection algorithms [43]. Indeed, such labels are usually obtained using some discrete-valued vertex attributes which are not guaranteed to be reasonable community assignments. For example, users in a social network can be split by gender, city, or interests, and each of these partitions could be treated as ground truth cluster assignments. An algorithm performing better for "city" labels can be worse for "interests" ones. As a result, no meaningful conclusion can be made based on such comparison. However, for the sake of completeness, we compare all algorithms on real-world networks, since it is still a standard practice in community detection literature. Tables 5 and 6 present the results for the iterative and maximization strategies, respectively (in both cases we add Louvain for comparison). 11 Note that we cannot properly measure statistical significance since we cannot sample several copies for each dataset. However, we can account for the randomness included in the algorithms: they all order vertices at each iteration randomly. To do this, for each dataset we run all algorithms 5 times and then apply the unpaired t-test to compare them. We put numbers in bold in Tables 5 or 6 if there is a group of algorithms without significant differences (p-value > 0.05) inside the group and with significant differences with the rest of the algorithms.
The results in general are not consistent: although DCPPM is often the best, the winning model may depend on a graph under consideration and on a target metric. For example, Louvain wins on Cora and AS according to Jaccard index, but it is the worst on the same datasets according to Rand index. This supports the claim that ground truth community assignments can be noisy or irrelevant.
We also noticed that iterative and maximization strategies usually have similar performance and the choice between them is not straightforward. For example, for ILFRS it is often better to apply maximization strategy, while for PPM iterative one should be preferred. Based on this observation, we propose using the iterative strategy, which is faster (it converges after a small number of iteration, as discussed below).
The performance of ILFRS is in general slightly better than of ILFR. Taking into account our results on synthetic networks, we propose using the faster ILFRS instead of ILFR in all practical applications.
Finally, we analyzed the speed of convergence for iterative strategies on real-world datasets. Namely, we measured the number of iterations made by Algorithm 1 before some stopping criteria is reached. Note that the algorithm never stopped because of reaching the maximum allowed number of iterations N = 50, so we either observed a convergence or applied the cycling criteria (i.e., encountered an already seed parameter). The average number of iterations obtained for PPM is 12.6 (in all cases the algorithm converged). For DCPPM we got 6.2 (converged in all cases except AS, where we applied cycling stopping criteria after 18 iterations). For ILFRS we have 5.4 iterations (cycling criteria is applied to 3 datasets). For ILFR we got 4.4 (again, with 3 applications of cycling criteria).

Statistical Inference, Negative Result
Having noticed unstable results for real-world datasets, we tried to answer the following research question: Is any of the null models suitable for community detection in real-world graphs?
In order to answer this question, for each quality function we compare its value for the ground truth partition with its value for the partition obtained by the corresponding maximization algorithm (see Table 7). For all quality functions, including the widely used modularity, and for all datasets the ground truth partition has a lower value of the quality function. This means that further optimization of any quality function would not lead us towards the ground truth partition, which is a negative observation. In particular, there is no hope in improving the results obtained by our algorithms by replacing Louvain-based FindPartition with some more effective maximization algorithm.
Note that in the literature it is often assumed that a partition with larger modularity is better and, as a result, an algorithm which leads to a partition with larger modularity is better. However, our observation above demonstrates that on the considered real-world datasets it is not the case. We also performed additional experiments and noticed that in almost all cases the value of a quality function for the ground truth partition is lower than for the partition obtained by any discussed optimization algorithm (not necessary optimizing the same quality function), which is an even stronger negative observation.
The following conclusion can be made: either the ground truth metadata contained in the considered real-world networks is not a good descriptor for a community structure or statistical inference algorithms based on all null models discussed in this paper are unable to detect real-world communities.

CONCLUSION
In this paper, we focused on the comparison of null models which can be used by likelihood optimization algorithms for community detection. We compared two well-known models, PPM and DCPPM, and a new model, ILFR, which has only one parameter and is proved to preserve the desired expected degree sequence. For the new model we have written the log-likelihood, both in parametric and self-contained forms. To maximize the parametric log-likelihood functions, we proposed and compared two optimization strategies: maximization and iterative.
The most important conclusion is that the proposed model, ILFR, is the best one for describing most of the considered real-world complex networks according to the likelihood of the observed graph structures, despite the fact that it has only one free parameter. We argue that the likelihood can be considered as the main argument in evaluating the null models instead of the direct comparison of community detection algorithms. The reason is that one cannot fully rely on ground truth cluster labels available for real-world networks. Also, we demonstrated that ILFR-based algorithms have the best performance on synthetic networks. Based on the obtained results, we believe that the proposed ILFR-based quality function (12) can be successfully used as a target for optimization algorithms, instead of the widely adopted modularity.
A natural direction for the future research is to analyze null models for overlapping community detection. This would be useful since many observed networks have overlapping communities. However, fundamental analysis of this problem is complicated by the fact that null models with overlapping communities are less developed and more complex for mathematical analysis.