Optimal fuzzy aggregation of networks. (English) Zbl 1244.60006
This paper deals with stochastic clustering methods. Starting point is the paper by W. E, T. Li and E. Vanden-Eijnden [“Optimal partition and effective dynamics of complex networks”, Proc. Natl. Acad. Sci. USA 105, No. 23, 7907–7912 (2008; Zbl 1205.68031)]. In this paper, a network with positive weights on its edges (i.e., a weighted directed graph) is considered as a Markov chain \(M\) with finite state space \([1,\dots,n]\). A partition into \(m < n\) clusters is modelled by a Markov chain \(M\) with state space \([1,\dots,m]\). The clustering is optimal if the transition matrix of \(N\) and the (lifted) transition matrix of \(M\) have minimum distance with respect to the Frobenius norm. An algorithm to perform this minimization was proposed in [loc. cit.], but only for deterministic clustering. The authors of the present paper generalize this technique for stochastic clustering. This leads to nonconvex constrained minimization problems. The authors discuss in detail how to solve these problems. They present several test examples. It is a bit strange that the authors use fuzzy clustering and stochastic clustering synonymously.
Reviewer: Wolfgang Näther (Freiberg)
MSC:
60-08 | Computational methods for problems pertaining to probability theory |
65K10 | Numerical optimization and variational techniques |
05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
90C70 | Fuzzy and other nonstochastic uncertainty mathematical programming |