Clustering in Graphs with Dynamics

October 21, 2015
  • graph simplification, deterministic annealing algorithm, dynamic clustering
  • 91C20
We consider the problem of simplifying representations for networks, or large weighted directed graphs, by aggregating nodes and edges. Our approach is to view this problem as a clustering problem and incorporate features of the deterministic annealing algorithm in our computational solution. The novelty in our method includes a quantitative measure of dissimilarity that allows us to compare directed graphs of possibly different sizes. We also introduce an approach that allows for clustering in the case of dynamics in the nodes or the edges. In this talk, an overview of our clustering algorithm will be given, along with some metrics and an analysis of the algorithm performance. Applications will be discussed as time allows.