Aggregation of Graph Models and Markov Chains by Deterministic Annealing

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 met...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2014-10, Vol.59 (10), p.2807-2812
Main Authors: Yunwen Xu, Salapaka, Srinivasa M., Beck, Carolyn L.
Format: Article
Language:English
Subjects:
Agglomeration
Algorithms
Annealing
Approximation
Clustering
Clustering algorithms
Graph theory
Graphs
Markov chains
Markov processes
Optimization
Partitioning algorithms
Resource management
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2014.2319473