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 > Computer Science

Archive Staff Only: edit this record