Aggregation of graph models and markov chains by deterministic annealing

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of simplifying large weighted directed graphs by aggregating nodes and edges. This problem is recast as a clustering/resource allocation problem, and a solution method that incorporates features of the deterministic annealing (DA) algorithm is proposed. The novelty in our method is a quantitive measure of dissimilarity that allows us to compare directed graphs of possibly different sizes (i.e., the original and the aggregated graphs). The approach we propose is insensitive to initial conditions and less likely to converge to poor local minima than Lloyd-type algorithms. We apply our graph-aggregation (clustering) method to Markov chains, where low-order Markov chains that approximate high-order chains are obtained through appropriate aggregation of state transition matrices. We further develop a decentralized computational scheme to improve tractability of the algorithm.

Original languageEnglish (US)
Article number6804680
Pages (from-to)2807-2812
Number of pages6
JournalIEEE Transactions on Automatic Control
Volume59
Issue number10
DOIs
StatePublished - Oct 1 2014

Keywords

  • Deterministic annealing (DA) algorithm

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Aggregation of graph models and markov chains by deterministic annealing'. Together they form a unique fingerprint.

Cite this