## 3 The k-Beta Model  
The maximum likelihood equations for the parameters \(b(.,.)\) in (5) say that the expected values of degrees _inside_ all the subgraph with a given pair of labels should be the same us in the given graph. This is the case when the labels are known. With unknown labels we can form a two-level optimization: for each label set, first determine the parameters \(b(.,.)\), then change a small number of labels and repeat the calculation of the parameters. But the procedure is slow even for graphs of moderate size. Spectral methods available for block models fail for coloring k-beta models because the model lose the well-pronounced checkerboard character of block models. It is the ANOVA that offers an applicable algorithm. For any set \(C\) of labels \(c(.)\), let us calculate the statistic  
\[Q(C)=\sum_{i=2}^{n}\sum_{j=1}^{i-1}(\varepsilon(i,j)-u(c(i),c(j))-v(i,c(j))-v( j,c(i)))^{2} \tag{10}\]  
where  
\[u(s,t)=\frac{\sum_{c(i)=s}\sum_{c(j)=t}\varepsilon(i,j)}{\sum_{c(i)=s}\sum_{c (j)=t}1} \tag{11}\]  
and  
\[v(i,t)=\frac{\sum_{c(j)=t}(\varepsilon(i,j)-u((c(i),t))}{\sum_{c(j)=t}1} \tag{12}\]  
\(Q(C)\) is the sum of two way ANOVA sum of squares calculated independently for subgraphs defined for pairs of labels. Starting from a uniform random set \(C\) of labels on the vertices and perturbing small number of labels in the individual steps, a simple greedy optimization results in a good set of labels, which is close to the original (true) labels.  
For evaluating the character of a random graph, we use the number  
\[\exp(-\frac{\sum_{i=2}^{n}\sum_{j=1}^{i-1}(p(i,j)\log p(i,j)+(1-p(i,j))\log(1- p(i,j))}{n(n-1)/2}) \tag{13}\]  
We call it _delocarithmed average entropy_ or DAE. This is a number between \(1\) and \(2\). If it is close to one, the graph is almost deterministic: the probabilities are close to \(0\) or \(1\). In checkerboard block models it means that empty and full subgraphs are amalgamated together. If DAE is close to \(2\), then the graph has no structure at all. DAE depends on edge density, too. The above tendency is valid for edge density \(\frac{1}{2}\), for other edge densities the cut point is closer to \(1\). According to our experience, if DAE is smaller than \(1.9\) while edge density is half, then we are able to reconstruct the original labels. For these graphs, the number of non-trivial eigenvalues is \(2k-1\), thus the spectrum determines the number of different labels.  
The k-beta model has a sister model  
\[r_{i,j}=\sum_{s=1}^{k}b(i,s)b(j,s) \tag{14}\]which we call _small odds rank_ model. Strictly speaking, we ought to redefine the diagonal of odds matrix, but perhaps the name is permissible without doing so. The maximum likelihood estimation of parameters in small odds rank models is straightforward and the block structure is detectable in the estimated parameters. Actually the block model is in the intersection of k-beta and small odds rank models, thus if there is any block structure in the graph, it is detectable even in fitting k-beta model to the graph. But if there is no block structure and we are trying to use ANOVA coloring for a small odds rank graph, then the algorithm is no longer stable--it results in different local minima in each run.