Learning Latent Structure in Complex Networks

Morten Mørup, Lars K. Hansen

AbstractLatent structure in complex networks, e.g., in the form of community structure,
can help understand network dynamics, identify heterogeneities in network properties,
and predict ‘missing’ links. While most community detection algorithms
are based on optimizing heuristic clustering objectives such as the Modularity, it
has recently been shown that latent structure in complex networks is learnable by
Bayesian generative link distribution models (Airoldi et al., 2008, Hofman and
Wiggins, 2008). In this paper we propose a new generative model that allows representation
of latent community structure as in the previous Bayesian approaches
and in addition allows learning of node specific link properties similar to that in
the modularity objective. We employ a new relaxation method for efficient inference
in these generative models that allows us to learn the behavior of very large
networks. We compare the link prediction performance of the learning based approaches
and other widely used link prediction approaches in 14 networks ranging
from medium size to large networks with more than a million nodes. While link
prediction is typically well above chance for all networks, we find that the learning
based mixed membership stochastic block model of Airoldi et al., performs
well and often best in our experiments. The added complexity of the LD model
improves link predictions for four of the 14 networks.
TypeConference paper [With referee]
ConferenceWorkshop on Analyzing Networks and Learning with Graphs NIPS 2009
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Intelligent Signal Processing

Back  ::  IMM Publications