@misc{DjurdjevacConradBanischSchuette, author = {Djurdjevac Conrad, Natasa and Banisch, Ralf and Sch{\"u}tte, Christof}, title = {Modularity of Directed Networks: Cycle Decomposition Approach}, issn = {1438-0064}, doi = {10.3934/jcd.2015.2.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51166}, abstract = {The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarsegrained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.}, language = {en} } @misc{SarichSchuette, author = {Sarich, Marco and Sch{\"u}tte, Christof}, title = {Utilizing hitting times for finding metastable sets in non-reversible Markov chains}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51209}, abstract = {Techniques for finding metastable or almost invariant sets have been investigated, e.g., for deterministic dynamical systems in set-oriented numerics, for stochastic processes in molecular dynamics, and for random walks on complex networks. Most prominent algorithms are based on spectral apporaches and identify metastable sets via the doimant eigenvalues of the transfer operator associated with the dynamical system under consideration. These algorithms require the dominant eigenvalues to be real-valued. However, for many types of dynamics, e.g. for non-reversible Markov chains, this condition is not met. In this paper we utilize the hitting time apporach to metastable sets and demonstrate how the wellknown statements about optimal metastable decompositions of reversible chains can be reformulated for non-reversible chains if one switches from a spectral approach to an exit time approach. The performance of the resulting algorithm is illustrated by numerical experiments on random walks on complex networks.}, language = {en} } @article{SchuetteNielsenWeber, author = {Sch{\"u}tte, Christof and Nielsen, Adam and Weber, Marcus}, title = {Markov State Models and Molecular Alchemy}, series = {Molecular Physics}, volume = {113}, journal = {Molecular Physics}, number = {1}, doi = {10.1080/00268976.2014.944597}, pages = {69 -- 78}, abstract = {In recent years Markov State Models (MSMs) have attracted a consid- erable amount of attention with regard to modelling conformation changes and associated function of biomolecular systems. They have been used successfully, e.g., for peptides including time-resolved spectroscopic experiments, protein function and protein folding , DNA and RNA, and ligand-receptor interaction in drug design and more complicated multivalent scenarios. In this article a novel reweighting scheme is introduced that allows to construct an MSM for certain molecular system out of an MSM for a similar system. This permits studying how molecular properties on long timescales differ between similar molecular systems without performing full molecular dynamics simulations for each system under con- sideration. The performance of the reweighting scheme is illustrated for simple test cases including one where the main wells of the respective energy landscapes are located differently and an alchemical transformation of butane to pentane where the dimension of the state space is changed.}, language = {en} } @article{DjurdjevacConradWeberSchuette, author = {Djurdjevac Conrad, Natasa and Weber, Marcus and Sch{\"u}tte, Christof}, title = {Finding dominant structures of nonreversible Markov processes}, series = {Multiscale Modeling and Simulation}, volume = {14}, journal = {Multiscale Modeling and Simulation}, number = {4}, doi = {10.1137/15M1032272}, pages = {1319 -- 1340}, language = {en} } @article{Nielsen, author = {Nielsen, Adam}, title = {The Monte Carlo Computation Error of Transition Probabilities}, series = {Statistics \& Probability Letters}, volume = {118}, journal = {Statistics \& Probability Letters}, publisher = {Elsevier}, doi = {10.1016/j.spl.2016.06.011}, pages = {163 -- 170}, abstract = {In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the \$L^2\$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains.}, language = {en} } @misc{DjurdjevacConradWeberSchuette, author = {Djurdjevac Conrad, Natasa and Weber, Marcus and Sch{\"u}tte, Christof}, title = {Finding dominant structures of nonreversible Markov processes}, issn = {1438-0064}, doi = {10.1137/15M1032272}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55739}, abstract = {Finding metastable sets as dominant structures of Markov processes has been shown to be especially useful in modeling interesting slow dynamics of various real world complex processes. Furthermore, coarse graining of such processes based on their dominant structures leads to better understanding and dimension reduction of observed systems. However, in many cases, e.g. for nonreversible Markov processes, dominant structures are often not formed by metastable sets but by important cycles or mixture of both. This paper aims at understanding and identifying these different types of dominant structures for reversible as well as nonreversible ergodic Markov processes. Our algorithmic approach generalizes spectral based methods for reversible process by using Schur decomposition techniques which can tackle also nonreversible cases. We illustrate the mathematical construction of our new approach by numerical experiments.}, language = {en} } @article{NielsenWeber, author = {Nielsen, Adam and Weber, Marcus}, title = {Computing the nearest reversible Markov chain}, series = {Numerical Linear Algebra with Applications}, volume = {22}, journal = {Numerical Linear Algebra with Applications}, number = {3}, doi = {10.1002/nla.1967}, pages = {483 -- 499}, abstract = {Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.}, language = {en} } @misc{SarichSchuette, author = {Sarich, Marco and Sch{\"u}tte, Christof}, title = {Markov Model Theory}, series = {An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation}, volume = {797}, journal = {An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation}, editor = {Bowman, Gregory R. and Pande, Vijay S. and No{\´e}, Frank}, publisher = {Springer}, doi = {10.1007/978-94-007-7606-7}, pages = {23 -- 44}, abstract = {This section reviews the relation between the continuous dynamics of a molecular system in thermal equilibrium and the kinetics given by a Markov State Model (MSM). We will introduce the dynamical propagator, an error-less, alternative description of the continuous dynamics, and show how MSMs result from its discretization. This allows for an precise understanding of the approximation quality of MSMs in comparison to the continuous dynamics. The results on the approximation quality are key for the design of good MSMs. While this section is important for understanding the theory of discretization and related systematic errors, practitioners wishing only to learn how to construct MSMs may skip directly to the discussion of Markov model estimation.}, language = {en} } @misc{Nielsen, author = {Nielsen, Adam}, title = {The Monte Carlo Computation Error of Transition Probabilities}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59933}, abstract = {In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the \$L^2\$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains.}, language = {en} } @misc{FackeldeySikorskiWeber, author = {Fackeldey, Konstantin and Sikorski, Alexander and Weber, Marcus}, title = {Spectral Clustering for Non-reversible Markov Chains}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70218}, abstract = {Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g. the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We also extend this spectral clustering method to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension non-reversible Markov chains can be analyzed. Furthermore, the chains do not need to have a positive stationary distribution. In addition to metastabilities, dominant cycles and sinks can also be identified. This novel method is called GenPCCA (i.e. Generalized PCCA), since it includes the case of non reversible processes. We also apply the method to real world eye tracking data.}, language = {en} } @article{FackeldeyRoehmNiknejadetal., author = {Fackeldey, Konstantin and R{\"o}hm, Jonas and Niknejad, Amir and Chewle, Surahit and Weber, Marcus}, title = {Analyzing Raman Spectral Data without Separabiliy Assumption}, series = {Journal of Mathematical Chemistry}, volume = {3}, journal = {Journal of Mathematical Chemistry}, number = {59}, publisher = {Springer}, doi = {10.1007/s10910-020-01201-7}, pages = {575 -- 596}, abstract = {Raman spectroscopy is a well established tool for the analysis of vibration spectra, which then allow for the determination of individual substances in a chemical sample, or for their phase transitions. In the Time-Resolved-Raman-Sprectroscopy the vibration spectra of a chemical sample are recorded sequentially over a time interval, such that conclusions for intermediate products (transients) can be drawn within a chemical process. The observed data-matrix M from a Raman spectroscopy can be regarded as a matrix product of two unknown matrices W and H, where the first is representing the contribution of the spectra and the latter represents the chemical spectra. One approach for obtaining W and H is the non-negative matrix factorization. We propose a novel approach, which does not need the commonly used separability assumption. The performance of this approach is shown on a real world chemical example.}, language = {en} } @article{DjurdjevacConradBrucknerConradetal.2012, author = {Djurdjevac Conrad, Natasa and Bruckner, Stefanie and Conrad, Tim and Sch{\"u}tte, Christof}, title = {Random Walks on Complex Modular Networks}, series = {Journal of Numerical Analysis, Industrial and Applied Mathematics}, volume = {6}, journal = {Journal of Numerical Analysis, Industrial and Applied Mathematics}, number = {1-2}, publisher = {European Society of Computational Methods in Sciences and Engineering}, pages = {29 -- 50}, year = {2012}, language = {en} } @article{ReuterWeberFackeldeyetal.2018, author = {Reuter, Bernhard and Weber, Marcus and Fackeldey, Konstantin and R{\"o}blitz, Susanna and Garcia, Martin E.}, title = {Generalized Markov State Modeling Method for Nonequilibrium Biomolecular Dynamics: Exemplified on Amyloid β Conformational Dynamics Driven by an Oscillating Electric Field}, series = {Journal of Chemical Theory and Computation}, volume = {14}, journal = {Journal of Chemical Theory and Computation}, number = {7}, doi = {10.1021/acs.jctc.8b00079}, pages = {3579 -- 3594}, year = {2018}, abstract = {Markov state models (MSMs) have received an unabated increase in popularity in recent years, as they are very well suited for the identification and analysis of metastable states and related kinetics. However, the state-of-the-art Markov state modeling methods and tools enforce the fulfillment of a detailed balance condition, restricting their applicability to equilibrium MSMs. To date, they are unsuitable to deal with general dominant data structures including cyclic processes, which are essentially associated with nonequilibrium systems. To overcome this limitation, we developed a generalization of the common robust Perron Cluster Cluster Analysis (PCCA+) method, termed generalized PCCA (G-PCCA). This method handles equilibrium and nonequilibrium simulation data, utilizing Schur vectors instead of eigenvectors. G-PCCA is not limited to the detection of metastable states but enables the identification of dominant structures in a general sense, unraveling cyclic processes. This is exemplified by application of G-PCCA on nonequilibrium molecular dynamics data of the Amyloid β (1-40) peptide, periodically driven by an oscillating electric field.}, language = {en} } @misc{ZhangWangHartmannetal., author = {Zhang, Wei and Wang, Han and Hartmann, Carsten and Weber, Marcus and Sch{\"u}tte, Christof}, title = {Applications of the cross-entropy method to importance sampling and optimal control of diffusions}, issn = {1438-0064}, doi = {10.1137/14096493X}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-49720}, abstract = {We study the cross-entropy method for diffusions. One of the results is a versatile cross-entropy algorithm that can be used to design efficient importance sampling strategies for rare events or to solve optimal control problems. The approach is based on the minimization of a suitable cross-entropy functional, with a parametric family of exponentially tilted probability distributions. We illustrate the new algorithm with several numerical examples and discuss algorithmic issues and possible extensions of the method.}, language = {en} } @article{HartmannSchuetteWeberetal., author = {Hartmann, Carsten and Sch{\"u}tte, Christof and Weber, Marcus and Zhang, Wei}, title = {Importance sampling in path space for diffusion processes with slow-fast variables}, series = {Probability Theory and Related Fields}, journal = {Probability Theory and Related Fields}, doi = {10.1007/s00440-017-0755-3}, pages = {1 -- 52}, abstract = {Importance sampling is a widely used technique to reduce the variance of a Monte Carlo estimator by an appropriate change of measure. In this work, we study importance sampling in the framework of diffusion process and consider the change of measure which is realized by adding a control force to the original dynamics. For certain exponential type expectation, the corresponding control force of the optimal change of measure leads to a zero-variance estimator and is related to the solution of a Hamilton-Jacobi-Bellmann equation. We focus on certain diffusions with both slow and fast variables, and the main result is that we obtain an upper bound of the relative error for the importance sampling estimators with control obtained from the limiting dynamics. We demonstrate our approximation strategy with an illustrative numerical example.}, language = {en} } @article{ZhangWangHartmannetal., author = {Zhang, Wei and Wang, Han and Hartmann, Carsten and Weber, Marcus and Sch{\"u}tte, Christof}, title = {Applications of the cross-entropy method to importance sampling and optimal control of diffusions}, series = {Siam Journal on Scientific Computing}, volume = {36}, journal = {Siam Journal on Scientific Computing}, number = {6}, doi = {10.1137/14096493X}, pages = {A2654 -- A2672}, language = {en} } @article{SarichBanischHartmannetal., author = {Sarich, Marco and Banisch, Ralf and Hartmann, Carsten and Sch{\"u}tte, Christof}, title = {Markov State Models for Rare Events in Molecular Dynamics}, series = {Entropy (Special Issue)}, volume = {16}, journal = {Entropy (Special Issue)}, number = {1}, doi = {10.3390/e16010258}, pages = {258 -- 286}, language = {en} } @article{DjurdjevacConradBanischSchuette, author = {Djurdjevac Conrad, Natasa and Banisch, Ralf and Sch{\"u}tte, Christof}, title = {Modularity of Directed Networks: Cycle Decomposition Approach}, series = {Journal of Computational Dynamics 2 (2015) pp. 1-24}, journal = {Journal of Computational Dynamics 2 (2015) pp. 1-24}, doi = {10.3934/jcd.2015.2.1}, abstract = {The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarsegrained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.}, language = {en} } @article{SarichDjurdjevacConradBruckneretal.2014, author = {Sarich, Marco and Djurdjevac Conrad, Natasa and Bruckner, Sharon and Conrad, Tim and Sch{\"u}tte, Christof}, title = {Modularity revisited: A novel dynamics-based concept for decomposing complex networks}, series = {Journal of Computational Dynamics}, volume = {1}, journal = {Journal of Computational Dynamics}, number = {1}, doi = {10.3934/jcd.2014.1.191}, pages = {191 -- 212}, year = {2014}, language = {en} }