Skip to content

random graphs with communities and arbitrary degrees

January 19, 2010

Classical Erdös-Renyi random graphs lack many of the properties commonly associated with networks observed in the real world. In particular, they are restricted to binomial or Poisson degree distributions and are generated without a particular modular structure in mind (i.e., no group of nodes is treated any differently than any other group). Several additional random graph models have been proposed over the years that seek to alleviate these shortcomings. On the one hand, we have the configuration and G(\mathbf{w}) models that produce random graphs with an arbitrary degree sequence (or expected degree sequence). There are also random graphs that incorporate community structure, such as the hierarchical random graph (HRG) or the stochastic block model (SBM). In fact, these models can produce non-Poisson degree distributions as well, but they often suffer from overfitting problems. In the case of the SBM the maximum likelihood estimator for a particular graph is one in which each edge exists with probability p_{ij} = 1 if those nodes are connected in the observed network and p_{ij} = 0 if they are not, so the overfitting is particularly bad.

We can avoid the overfitting problems by restricting our attention to the k+1-parameter SBM. In this model, each node is assigned to one of k distinct communities. An edge between nodes i and j exists with probability p_s if i and j are both in community s and with probability p_0 otherwise. This is a generalization of the 2-parameter SBM used by Hofman and Wiggins in their recent paper on Bayesian community detection, and is suitable for a network with a single layer of community structure. However, the resulting degree distribution is still fundamentally Poisson (now actually the sum of several Poisson distributions).

In my upcoming senior thesis on network community detection, I propose a generalization of the k+1-parameter SBM that allows for an arbitrary degree sequence, effectively extending the configuration model to the realm of community structure. It can also be viewed as a slight generalization of the benchmark graph proposed by Lancichinetti et al that is suitable for maximum likelihood inference. In addition, this new model (which I am tentatively calling the 2-layer configuration model)can be naturally associated with the generative process behind the modularity function (more on this later).

Intuitively, the 2-layer configuration model works as follows. Each node is given a degree k_i and is assigned to one of k distinct communities, which means that each community has a total degree d_s.  Furthermore, each community is given an “affinity” \alpha_s in the range [0,1]. We then assign \alpha_s d_s / 2 edges to each community chosen by randomly picking two stubs within that community and connecting them with an edge (i.e., each community is treated as a separate configuration network with degree sequence \alpha_s k_i). The remaining edges are assigned by randomly choosing two of the unused stubs from anywhere in the network and connecting them with an edge (i.e., we then treat the entire network as a configuration network with degree sequence (1-\alpha_s) k_i). This yields a network with the desired degree sequence that also contains the desired community structure.

For reasons outlined in a previous post, it is often desirable to have a model in which each edge exists independently of all the others. This can be achieved (as in the case of the configuration model) by relaxing the degree requirements to merely specifying the expected degree w_i for each node. However, because of the caveats outlined in that previous post, this model turns out to be rather complicated to write down. With a little work, one can show that the edge probabilities p_{ij} should be given by

p_{ij} = \left\{\begin{array}{ll} \frac{1}{2} \left( \frac{\alpha_{s} w_i^2}{d_{s}} + \frac{(1-\alpha_{s})^2 w_i d_{s}}{\sum_u (1-\alpha_u) d_u} \right) & : \text{if} \, i=j \, \text{and} \, i \in s \\ \frac{\alpha_{s} w_i w_j}{d_{s}} & : \text{if} \, i \neq j \, \text{and} \, i,j \in s \\ \frac{(1-\alpha_{s})(1-\alpha_{t}) w_i w_j}{\sum_u (1-\alpha_u) d_u} & : \text{if} \, i \in s \, \text{and} \, j \in t\end{array}\right.

A detailed derivation will be given in the thesis.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: