TY - GEN
A1 - Huisinga, Wilhelm
A1 - Best, Christoph
A1 - Cordes, Frank
A1 - Roitzsch, Rainer
A1 - Schütte, Christof
T1 - From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods
N2 - Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide.
T3 - ZIB-Report - SC-98-36
KW - conformational ensemble
KW - cluster method
KW - structural and dynamical similarity
KW - representative
KW - conformation
KW - essential degrees of freedom
KW - transi
Y1 - 1998
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3797
ER -
TY - GEN
A1 - Weber, Marcus
A1 - Meyer, Holger
T1 - ZIBgridfree - Adaptive Conformation Analysis with qualified Support of Transition States and Thermodynamic Weights
N2 - This paper introduces a new algorithm of conformational analysis based on mesh-free methods as described in [M. Weber. Mehless methods in Conformation Dynamics.(2005)]. The adaptive decomposition of the conformational space by softly limiting functions avoids trapping effects and allows adaptive refinement strategies. These properties of the algorithm makes ZIBgridfree particularly suitable for the complete exploration of high-dimensional conformational space. The adaptive control of the algorithm benefits from the tight integration of molecular simulation and conformational analysis. An emphasized part of the analysis is the Robust Perron Cluster Analysis (PCCA+) based on the work of Peter Deuflhard and Marcus Weber. PCCA+ supports an almost-characteristic cluster definition with an outstanding mapping of transition states. The outcome is expressed by the metastable sets of conformations, their thermodynamic weights and flexibility.
T3 - ZIB-Report - 05-17
KW - Molecular Dynamics
KW - Meshfree Methods
KW - Conformation Analysis
KW - Quality Functions
Y1 - 2005
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8514
ER -
TY - GEN
A1 - Cordes, Frank
A1 - Weber, Marcus
A1 - Schmidt-Ehrenberg, Johannes
T1 - Metastable Conformations via successive Perron-Cluster Cluster Analysis of dihedrals
N2 - Decomposition of the high dimensional conformational space of bio-molecules into metastable subsets is used for data reduction of long molecular trajectories in order to facilitate chemical analysis and to improve convergence of simulations within these subsets. The metastability is identified by the Perron-cluster cluster analysis of a Markov process that generates the thermodynamic distribution. A necessary prerequisite of this analysis is the discretization of the conformational space. A combinatorial approach via discretization of each degree of freedom will end in the so called ''curse of dimension''. In the following paper we analyze Hybrid Monte Carlo simulations of small, drug-like biomolecules and focus on the dihedral degrees of freedom as indicators of conformational changes. To avoid the ''curse of dimension'', the projection of the underlying Markov operator on each dihedral is analyzed according to its metastability. In each decomposition step of a recursive procedure, those significant dihedrals, which indicate high metastability, are used for further decomposition. The procedure is introduced as part of a hierarchical protocol of simulations at different temperatures. The convergence of simulations within metastable subsets is used as an ''a posteriori'' criterion for a successful identification of metastability. All results are presented with the visualization program AmiraMol.
T3 - ZIB-Report - 02-40
KW - metastability
KW - Perron-Cluster Cluster Analysis
KW - curse of dimension
KW - Hybrid Monte Carlo
KW - significant dihedrals
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7074
ER -
TY - GEN
A1 - Weber, Marcus
T1 - Improved Perron Cluster Analysis
N2 - The problem of clustering data can often be transformed into the problem of finding a hidden block diagonal structure in a stochastic matrix. Deuflhard et al. have proposed an algorithm that state s the number $k$ of clusters and uses the sign structure of $k$ eigenvectors of the stochastic matrix to solve the cluster problem. Recently Weber and Galliat discovered that this system of eigenvectors can easily be transformed into a system of $k$ membership functions or soft characteristic functions describing the clusters. In this article we explain the corresponding cluster algorithm and point out the underlying theory. By means of numerical examples we explain how the grade of membership can be interpreted.
T3 - ZIB-Report - 03-04
KW - cluster analysis
KW - stochastic matrices
KW - almost invariant sets
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7260
ER -
TY - GEN
A1 - Deuflhard, Peter
A1 - Weber, Marcus
T1 - Robust Perron Cluster Analysis in Conformation Dynamics
N2 - The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.
T3 - ZIB-Report - 03-19
KW - Markov chains
KW - cluster algorithms
KW - Perron cluster analysis
KW - conformation dynamics
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7415
ER -
TY - GEN
A1 - Weber, Marcus
T1 - Clustering by using a simplex structure
N2 - In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs.
T3 - ZIB-Report - 04-03
KW - cluster algorithms
KW - Perron cluster analysis
KW - stochastic matrices
KW - bipartite graphs
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7782
ER -
TY - GEN
A1 - Galliat, Tobias
A1 - Huisinga, Wilhelm
A1 - Deuflhard, Peter
T1 - Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification
N2 - One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included.
T3 - ZIB-Report - SC-99-38
KW - Self-Organizing Maps
KW - cluster analysis
Y1 - 1999
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4279
ER -
TY - GEN
A1 - Galliat, Tobias
T1 - Clustering Data of Different Information Levels
N2 - For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis.
T3 - ZIB-Report - SC-99-42
KW - cluster analysis
KW - Data Mining
KW - data preprocessing
KW - information theory
KW - missing values
KW - Self-Organizing Maps
KW - similarity measures
Y1 - 1999
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4319
ER -
TY - GEN
A1 - Kube, Susanna
A1 - Weber, Marcus
T1 - Conformation Kinetics as a Reduced Model for Transition Pathways
N2 - The complexity of molecular kinetics can be reduced significantly by a restriction to metastable conformations which are almost invariant sets of molecular dynamical systems. With the Robust Perron Cl uster Analysis PCCA+, developed by Weber and Deuflhard, we have a tool available which can be used to identify these conformations from a transition probability matrix. This method can also be applied to the corresponding transition rate matrix which provides important information concerning transition pathways of single molecules. In the present paper, we explain the relationship between these tw o concepts and the extraction of conformation kinetics from transition rates. Moreover, we show how transition rates can be approximated and conclude with numerical examples.
T3 - ZIB-Report - 05-43
KW - conformation kinetics
KW - transition rates
KW - Robust Perron Cluster Analysis
Y1 - 2005
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8763
ER -
TY - GEN
A1 - Galliat, Tobias
A1 - Deuflhard, Peter
T1 - Adaptive hierarchical cluster analysis by Self-Organizing Box Maps
N2 - The present paper aims at an extension of {\sc Kohonen's} Self-Organizing Map (SOM) algorithm to be called Self-Organizing Box Map (SOBM) algorithm; it generates box codebooks in lieu of point codebooks. Box codebooks just like point codebooks indirectly define a Voronoi tessellation of the input space, so that each codebook vector represents a unique set of points. Each box codebook vector comprises a multi-dimensional interval that approximates the related partition of the Voronoi tessellation. Upon using the automated cluster identification method that has recently been developed by the authors, the codebook vectors can be grouped in such a way that each group represents a point cluster in the input space. Since the clustering usually depends on the size of the SOM, one cannot be sure, whether the clustering comes out to be optimal. Refinement of part of the identified clusters would often improve the results. This paper presents the concept of an adaptive multilevel cluster algorithm that performs such refinements automatically. Moreover the paper introduces a concept of essential dimensions and suggests a method for their identification based on our herein suggested box codebooks. Applications of the algorithm to molecular dynamics will be described in a forthcoming paper.
T3 - ZIB-Report - 00-13
KW - Self-Organizing Maps
KW - cluster analysis
KW - Voronoi tessellation
KW - feature extraction
KW - essential dimensions
KW - multilevel methods
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5815
ER -
TY - GEN
A1 - Galliat, Tobias
A1 - Deuflhard, Peter
A1 - Roitzsch, Rainer
A1 - Cordes, Frank
T1 - Automatic Identification of Metastable Conformations via Self-Organized Neural Networks
N2 - As has been shown recently, the identification of metastable chemical conformations leads to a Perron cluster eigenvalue problem for a reversible Markov operator. Naive discretization of this operator would suffer from combinatorial explosion. As a first remedy, a pre-identification of essential degrees of freedom out of the set of torsion angles had been applied up to now. The present paper suggests a different approach based on neural networks: its idea is to discretize the Markov operator via self-organizing (box) maps. The thus obtained box discretization then serves as a prerequisite for the subsequent Perron cluster analysis. Moreover, this approach also permits exploitation of additional structure within embedded simulations. As it turns out, the new method is fully automatic and efficient also in the treatment of biomolecules. This is exemplified by numerical results.
T3 - ZIB-Report - 00-51
KW - biochemical conformations
KW - cluster analysis
KW - Molecular Dynamics
KW - Monte-Carlo methods
KW - operator discretization
KW - Perron cluster
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6197
ER -
TY - GEN
A1 - Weber, Marcus
A1 - Galliat, Tobias
T1 - Characterization of Transition States in Conformational Dynamics using Fuzzy Sets
N2 - Recently, a novel approach for the analysis of molecular dynamics on the basis of a transfer operator has been introduced. Therein conformations are considered to be disjoint metastable clusters within position space of a molecule. These clusters are defined by almost invariant characteristic functions that can be computed via {\em Perron Cluster} analysis. The present paper suggests to replace crisp clusters with {\em fuzzy} clusters, i.e. to replace characteristic functions with membership functions. This allows a more sufficient characterization of transiton states between different confor conformations and therefore leads to a better understanding of molecular dynamics. Fur thermore, an indicator for the uniqueness of metastable fuzzy clusters and a fast algorithm for the computation of these clusters are described. Numerical examples are included.
T3 - ZIB-Report - 02-12
KW - biochemical conformations
KW - conformational dynamics
KW - molecular dynamics
KW - cluster analysis
KW - transition states
KW - fuzzy sets
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6791
ER -
TY - GEN
A1 - Weber, Marcus
T1 - Conformation-based transition state theory
N2 - For the treatment of equilibrated molecular systems in a heat bath we propose a transition state theory that is based on conformation dynamics. In general, a set-based discretization of a Markov operator ${\cal P}^\tau$ does not preserve the Markov property. In this article, we propose a discretization method which is based on a Galerkin approach. This discretization method preserves the Markov property of the operator and can be interpreted as a decomposition of the state space into (fuzzy) sets. The conformation-based transition state theory presented here can be seen as a first step in conformation dynamics towards the computation of essential dynamical properties of molecular systems without time-consuming molecular dynamics simulations.
T3 - ZIB-Report - 07-18
KW - dynamical systems
KW - transition state theory
KW - rare events
Y1 - 2007
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9612
ER -
TY - THES
A1 - Weber, Marcus
T1 - A Subspace Approach to Molecular Markov State Models via a New Infinitesimal Generator
N2 - Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern.
KW - Conformation Dynamics
KW - Molecular Kinetics
KW - Transition Rates
KW - Markov State Models
Y1 - 2011
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14025
ER -
TY - GEN
A1 - Weber, Marcus
T1 - A Subspace Approach to Molecular Markov State Models via an Infinitesimal Generator
N2 - Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern.
T3 - ZIB-Report - 09-27
KW - Robuste Perron Cluster Analyse
KW - Molekülkinetik
KW - Übergangsraten
KW - Robust Perron cluster analysis
KW - molecular kinetics
KW - transition rates
Y1 - 2009
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11432
SN - 1438-0064
ER -
TY - THES
A1 - Galliat, Tobias
T1 - Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps
N2 - Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist, spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen Problemen lassen sich die Objekte als Punkte in einem von den Attributen aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte. Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B. in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen. In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen, das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist, wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.
KW - Biochemical conformations
KW - cluster analysis
KW - molecular dynamics
KW - Perron cluster analysis
KW - Self-Organizing Maps
KW - Biochemical conformations
KW - cluster analysis
KW - molecular dynamics
KW - Perron cluster analysis
KW - Self-Organizing Maps
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-2002001258
ER -
TY - GEN
A1 - Weber, Marcus
A1 - Walter, Lionel
A1 - Kube, Susanna
A1 - Deuflhard, Peter
T1 - Stable computation of probability densities for metastable dynamical systems
N2 - Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest to apply an aggregation/disaggregation method which only addresses wellconditioned sub-problems and thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples.
T3 - ZIB-Report - 06-39
KW - dynamical systems
KW - metastability
KW - molecular conformations
KW - cluster analysis
KW - sampling
KW - aggregation/disaggregation
KW - domain decomposition
Y1 - 2006
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9331
ER -
TY - GEN
A1 - Weber, Marcus
A1 - Rungsarityotin, Wasinee
A1 - Schliep, Alexander
T1 - Perron Cluster Analysis and Its Connection to Graph Partitioning for Noisy Data
N2 - The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.
T3 - ZIB-Report - 04-39
KW - Perron cluster analysis
KW - spectral graph theory
KW - clustering
KW - gene expression
Y1 - 2004
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8140
ER -
TY - GEN
A1 - Willenbockel, Christian Tobias
A1 - Schütte, Christof
T1 - A Variational Bayesian Algorithm for Clustering of Large and Complex Networks
N2 - We propose the Blockloading algorithm for the clustering of large and complex graphs with tens of thousands of vertices according to a Stochastic Block Model (SBM). Blockloading is based on generalized Variational Bayesian EM (VBEM) schemes and works for weighted and unweighted graphs. Existing Variational (Bayesian) EM methods have to consider each possible number of clusters sepa- rately to determine the optimal number of clusters and are prone to converge to local optima making multiple restarts necessary. These factors impose a severe restriction on the size and complexity of graphs these methods can handle. In con- trast, the Blockloading algorithm restricts restarts to subnetworks in a way that provides error correction of an existing cluster assignment. The number of clusters need not be specified in advance because Blockloading will return it as a result. We show that Blockloading outperforms all other variational methods regarding reliability of the results and computational efficiency.
T3 - ZIB-Report - 15-25
KW - Clustering
KW - Variational Bayes EM
KW - Model Selection,
KW - Stochastic Block Model
KW - Networks
KW - unsupervised classification
Y1 - 2015
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54588
SN - 1438-0064
ER -
TY - GEN
A1 - Willenbockel, Christian Tobias
A1 - Schütte, Christof
T1 - Variational Bayesian Inference and Model Selection for the Stochastic Block Model with Irrelevant Vertices
N2 - Real World networks often exhibit a significant number of vertices which are sparsely and irregularly connected to other vertices in the network. For clustering theses networks with a model based algorithm, we propose the Stochastic Block Model with Irrelevant Vertices (SBMIV) for weighted net- works. We propose an original Variational Bayesian Expectation Maximiza- tion inference algorithm for the SBMIV which is an advanced version of our Blockloading algorithm for the Stochastic Block Model. We introduce a model selection criterion for the number of clusters of the SBMIV which is based on the lower variational bound of the model likelihood. We propose a fully Bayesian inference process, based on plausible informative priors, which is independent of other algorithms for preprocessing start values for the cluster assignment of vertices. Our inference methods allow for a multi level identification of irrelevant vertices which are hard to cluster reliably ac- cording to the SBM. We demonstrate that our methods improve on the normal Stochastic Block model by applying it to to Earthquake Networks which are an example of networks with a large number of sparsely and irregularly con- nected vertices.
T3 - ZIB-Report - 16-01
KW - Clustering
KW - Variational Bayes EM
KW - Model Selection,
KW - Stochastic Block Model
KW - Networks
KW - unsupervised classification
KW - Noise
Y1 - 2016
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57003
SN - 1438-0064
ER -
TY - GEN
A1 - Fackeldey, Konstantin
A1 - Sikorski, Alexander
A1 - Weber, Marcus
T1 - Spectral Clustering for Non-reversible Markov Chains
N2 - 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.
T3 - ZIB-Report - 18-48
KW - spectral clustering
KW - Markov chain
KW - Schur decomposition
KW - non-reversible
Y1 - 2018
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70218
SN - 1438-0064
ER -
TY - GEN
A1 - Vega, Iliusi
A1 - Schütte, Christof
A1 - Conrad, Tim
T1 - SAIMeR: Self-adapted method for the identification of metastable states in real-world time series
N2 - In the framework of time series analysis with recurrence networks, we introduce SAIMeR, a heuristic self-adapted method that determines the elusive recurrence threshold and identifies metastable states in complex time series. To identify metastable states as well as the transitions between them, we use graph theory concepts and a fuzzy partitioning clustering algorithm. We illustrate SAIMeR by applying it to three real-world time series and show that it is able to identify metastable states in real-world data with noise and missing data points. Finally, we suggest a way to choose the embedding parameters used to construct the state space in which this method is performed, based on the analysis of how the values of these parameters affect two recurrence quantitative measurements: recurrence rate and entropy.
T3 - ZIB-Report - 14-16
KW - time series analysis
KW - application in statistical physics
KW - recurrence quantification analysis
KW - threshold
KW - metastability
KW - non-linear dynamics
Y1 - 2014
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50130
SN - 1438-0064
ER -