Title of the page: Abstract of: A stochastic uncoupling process for graphs
Content of the page
Abstract of: A stochastic uncoupling process for graphs
INS-R0011
S. van Dongen ;
2000, INS-R0011, ISSN 1386-3681
PDF-file
compressed PostScript
( 145 KB )
( 19 pages )
Abstract
A discrete stochastic uncoupling process for finite spaces is introduced, called the Markov Cluster Process. The process takes a stochastic matrix as input, and then alternates flow expansion and flow inflation, each step defining a stochastic matrix in terms of the previous one. Flow expansion corresponds with taking the kth power of a stochastic matrix, where k ∈ N. Flow inflation corresponds with a parametrized operator Γr, ≥ 0, which maps the set of (column) stochastic matrices onto itself. The image Γr M is obtained by raising each entry in M to the rth power and rescaling each column to have sum 1 again.
In practice the process converges very fast towards a limit which is idempotent under both matrix multiplication and inflation, with quadratic convergence around the limit points. The limit is in general extremely sparse and the number of components of its associated graph may be larger than the number associated with the input matrix. This uncoupling is a desired effect as it reveals structure in the input matrix.
The inflation operator Γr is shown to map the class of matrices which are diagonally similar to a symmetric matrix onto itself. The term diagonally positive semi-definite (dpsd) is used for matrices which are diagonally similar to a positive semi-definite matrix. It is shown that for r∈ N and for M a stochastic dpsd matrix, the image Γr M is again dpsd. Determinantal inequalities satisfied by a dpsd matrix M imply a natural ordering among the diagonal elements of M, generalizing a mapping of nonnegative column allowable idempotent matrices onto overlapping clusterings. The spectrum of Γ∞ M, for dpsd M, is of the form {0n-k, 1k}, where k is the number of endclasses of the ordering associated with M, and n is the dimension of M.
Reductions of dpsd matrices are given, a connection with Hilbert's distance and the contraction ratio defined for nonnegative matrices is discussed, and several conjectures are made.
CWI Group(s):
INS3 (Visualization and 3D Interfaces)
Keywords:
Markov matrix
flow simulation
stochastic uncoupling
diagonal similarity
positive semi-definite matrices
circulant matrices
reinforced random walk
S. van Dongen ;
2000, INS-R0011, ISSN 1386-3681
PDF-file
compressed PostScript
( 145 KB )
( 19 pages )
Abstract
A discrete stochastic uncoupling process for finite spaces is introduced, called the Markov Cluster Process. The process takes a stochastic matrix as input, and then alternates flow expansion and flow inflation, each step defining a stochastic matrix in terms of the previous one. Flow expansion corresponds with taking the kth power of a stochastic matrix, where k ∈ N. Flow inflation corresponds with a parametrized operator Γr, ≥ 0, which maps the set of (column) stochastic matrices onto itself. The image Γr M is obtained by raising each entry in M to the rth power and rescaling each column to have sum 1 again.
In practice the process converges very fast towards a limit which is idempotent under both matrix multiplication and inflation, with quadratic convergence around the limit points. The limit is in general extremely sparse and the number of components of its associated graph may be larger than the number associated with the input matrix. This uncoupling is a desired effect as it reveals structure in the input matrix.
The inflation operator Γr is shown to map the class of matrices which are diagonally similar to a symmetric matrix onto itself. The term diagonally positive semi-definite (dpsd) is used for matrices which are diagonally similar to a positive semi-definite matrix. It is shown that for r∈ N and for M a stochastic dpsd matrix, the image Γr M is again dpsd. Determinantal inequalities satisfied by a dpsd matrix M imply a natural ordering among the diagonal elements of M, generalizing a mapping of nonnegative column allowable idempotent matrices onto overlapping clusterings. The spectrum of Γ∞ M, for dpsd M, is of the form {0n-k, 1k}, where k is the number of endclasses of the ordering associated with M, and n is the dimension of M.
Reductions of dpsd matrices are given, a connection with Hilbert's distance and the contraction ratio defined for nonnegative matrices is discussed, and several conjectures are made.
CWI Group(s):
INS3 (Visualization and 3D Interfaces)Keywords:
Markov matrix
flow simulation
stochastic uncoupling
diagonal similarity
positive semi-definite matrices
circulant matrices
reinforced random walk