Identifying graph clusters using variational inference and links to covariance parametrization.
PHILOS T R SOC A
4407 - 4426.
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.
|Title:||Identifying graph clusters using variational inference and links to covariance parametrization|
|Keywords:||graph clustering, community identification, network, variational inference, clique matrix, covariance, NETWORKS, MATRIX, MODELS|
|UCL classification:||UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Engineering Science
Archive Staff Only