Repository: Freie Universität Berlin, Math Department

Optimal Fuzzy Aggregation of Networks

Sarich, M. and Schütte, Ch. and Vanden-Eijnden, E. (2010) Optimal Fuzzy Aggregation of Networks. Multiscale Modeling and Simulation, 8 (4). pp. 1535-1561.

[img] PDF - Submitted Version
Restricted to Registered users only
Available under License Creative Commons Attribution.


Official URL:


This paper is concerned with the problem of fuzzy aggregation of a network with non-negative weights on its edges into a small number of clusters. Specifically we want to optimally define a probability of affiliation of each of the n nodes of the network to each of m < n clusters or aggregates. We take a dynamical perspective on this problem by analyzing the discrete-time Markov chain associated with the network and mapping it onto a Markov chain describing transitions between the clusters. We show that every such aggregated Markov chain and affiliation function can be lifted again onto the full network to define the so-called lifted transition matrix between the nodes of the network. The optimal aggregated Markov chain and affiliation function can then be determined by minimizing some appropriately defined distance between the lifted transition matrix and the transition matrix of the original chain. In general, the resulting constrained nonlinear minimization problem comes out to have continuous level sets of minimizers. We exploit this fact to devise an algorithm for identification of the optimal cluster number by choosing specific minimizers from the level sets. Numerical minimization is performed by some appropriately adapted version of restricted line search using projected gradient descent. The resulting algorithmic scheme is shown to perform well on several test examples.

Item Type:Article
Subjects:Mathematical and Computer Sciences > Mathematics
Divisions:Department of Mathematics and Computer Science > Institute of Mathematics
Department of Mathematics and Computer Science > Institute of Mathematics > BioComputing Group
ID Code:768
Deposited By: Marco Sarich
Deposited On:01 Oct 2009 15:36
Last Modified:03 Mar 2017 14:40

Repository Staff Only: item control page