Aggregation of graph models and markov chains by deterministic annealing

Research output: Contribution to journalArticlepeer-review


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
Issue number10
StatePublished - Oct 1 2014


  • Deterministic annealing (DA) algorithm

ASJC Scopus subject areas

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


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

Cite this