UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Identifying graph clusters using variational inference and links to covariance parametrization

Barber, D; (2009) Identifying graph clusters using variational inference and links to covariance parametrization. PHILOS T R SOC A , 367 (1906) 4407 - 4426. 10.1098/rsta.2009.0117.

Full text not available from this repository.

Abstract

Finding clusters of well-connected nodes in a graph is a problem common to many domains, including social networks, the Internet and bioinformatics. From a computational viewpoint, finding these clusters or graph communities is a difficult problem. We use a clique matrix decomposition based on a statistical description that encourages clusters to be well connected and few in number. The formal intractability of inferring the clusters is addressed using a variational approximation inspired by mean-field theories in statistical mechanics. Clique matrices also play a natural role in parametrizing positive definite matrices under zero constraints on elements of the matrix. We show that clique matrices can parametrize all positive definite matrices restricted according to a decomposable graph and form a structured factor analysis approximation in the non-decomposable case. Extensions to conjugate Bayesian covariance priors and more general non-Gaussian independence models are briefly discussed.

Type: Article
Title: Identifying graph clusters using variational inference and links to covariance parametrization
DOI: 10.1098/rsta.2009.0117
Keywords: graph clustering, community identification, network, variational inference, clique matrix, covariance, NETWORKS, MATRIX, MODELS
UCL classification: UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/19782
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item