mixer (version 1.7)

mixer: MIXtures of Erdos-Renyi random graphs

Description

Estimate the parameters, the hidden class variables, as well as the number of classes q of a MIXture of Erdos Renyi random graphs. The estimation is performed for binary graphs (edges are assumed to be drawn from Bernoulli distributions).

Usage

mixer( x, qmin=2, qmax=NULL, method="variational", directed = NULL,
nbiter=10, fpnbiter=5, improve=FALSE, verbose=TRUE)

Arguments

x

an adjacency matrix or a matrix of edges (each column gives the two node indexes defining an edge) or a spm file name (a .spm file describes the network as a sparse matrix).

qmin

minimum number of classes.

qmax

maximum number of classes (if NULL, only q=qmin is considered).

method

strategy used for the estimation: "variational", "classification", or "bayesian"

directed

TRUE/FALSE for directed/undirected graph. Default is NULL, i.e. according to the input array x, mixer identifies whether the graph is directed or undirected.

nbiter

maximum number of EM iterations (default: 10).

fpnbiter

maximum number of internal iterations for the E step (default: 5).

improve

selects between improved or basic strategies (default: FALSE).

verbose

display warning messages (default: TRUE).

Value

• mixer returns an object of class mixer. Below the main attributes of this class:
• nnodes
  number of connected nodes.
• map
  mapping from connected nodes to the whole set of nodes.
• edges
  edge list.
• qmin, qmax
  number of classes.
• output
  output list of qmax-qmin+1 items. Each item contains the result of the estimation for a given number of class q. Details of output field:
• output[[i]]$criterion
  ICL criterion or ILvb criterion used for model selection (see details section for more).
• output[[i]]$alphas
  vector of proportion, whose length is the number of component.
• output[[i]]$Pis
  class connectivity matrix.
• output[[i]]$Taus
  matrix of posterior probabilities (of the hidden color knowing the graph structure).

Details

mixer implements the Erdos-Renyi mixture model for graphs (called MixNet) which has been proposed by Daudin et. al (2008) with an associated EM estimation algorithm. The MixNet model is well suited to capture the structure of a network and in particular to detect communities.

MixNet must not to be confused with Exponential Random Graph Models for Network Data (ERGM) which considers distributions ensuing from the exponential family to model the edge distribution. There exists a strong connection between Mixnet and block clustering. Block clustering searches for homogeneous blocks in a data matrix by simultaneous clustering of rows and columns. The mixer package implements three different estimation strategies which were developed to deal with directed and undirected graphs: [object Object],[object Object],[object Object]

The implementation of the two first methods consists of an R wrapper of the c++ software package mixnet developed by Vincent Miele (2006). The mixer routine uses the estimation strategy described in method and computes a model selection criterion for each value of q (the number of classes) between qmin and qmax. The ICL criterion is used for the variational and classification methods. It corresponds to an asymptotic approximation of the Integrated Classification Likelihood. The other criterion, so called ILvb (Integrated Likelihood variational Bayes), is used for the bayesian method. It is based on a variational (non-asymptotic) approximation of the Integrated observed Likelihood. mixer is an user-friendly package with a reduced number of functions. For R-developers in statistical networks a more complete set, called mixer-dev, is provided (see below).

References

Jean-Jacques Daudin, Franck Picard and Stephane Robin June (2008), A mixture model for random graphs. Statistics and Computing, 18, 2, 151--171.

Hugo Zanghi, Christophe Ambroise and Vincent Miele (2008), Fast online graph clustering via Erdos-Renyi mixture. Pattern Recognition, 41, 3592-3599.

Hugo Zanghi, Franck Picard, Vincent Miele, and Christophe Ambroise (2008), Strategies for Online Inference of Network Mixture, http://arxiv.org/abs/0910.2034v1

Pierre Latouche, Etienne Birmele, and Christophe Ambroise (2008), Bayesian methods for graph clustering, http://genome.jouy.inra.fr/ssb/preprint/SSB-RR-17.bayesianMixNet.pdf

Vincent Miele, MixNet C++ package, http://stat.genopole.cnrs.fr/sg/software/mixer/.

mixer-dev tool: see http://ssbgroup.fr/mixnet/mixer.html

Examples

graph.affiliation(n=100,c(1/3,1/3,1/3),0.8,0.2)->g
mixer(g$x,qmin=2,qmax=6)->xout
plot(xout)

graph.affiliation(n=50,c(1/3,1/3,1/3),0.8,0.2)->g
mixer(g$x,qmin=2,qmax=5, method="bayesian")->xout
plot(xout)

data(blog)
mixer(x=blog$links,qmin=2,qmax=12)->xout
plot(xout)