No description available.

Komplexe Netzwerke kodieren Strukturinformationen der zugrunde liegenden Systeme, die modelliert werden. Die Dekodierung der Strukturinformationen aus einem Netzwerk kann uns daher helfen, die Funktionsweise der zugrunde liegenden Systeme zu verstehen und sogar vorherzusagen. Vor diesem Hintergrund untersuchen wir drei Probleme: Multistabilität in vernetzten dynamischen Systemen, globale Muster extremer Niederschläge und Graphenverdünnung. Indem wir die drei Probleme angehen, wollen wir den Werkzeugkasten der Netzwerkwissenschaft erweitern und die Integration von Netzwerkwerkzeugen in andere Forschungsfelder fördern. Erstens ist das Verständnis der Entstehung von Multistabilität oder sogar extremer Multistabilität (EM) in vernetzten dynamischen Systemen immer noch ein herausforderndes Problem. Dazu zeigen wir mithilfe eines multistabilen Modells gekoppelter Pendeluhren (kurz: gekoppelte Uhren), dass eine symmetrische Kopplung die Komplexität der Multistabilität erhöhen und die durch Kopplung verursachte EM aufdecken kann. Als nächstes bilden in der Klimawissenschaft räumliche Muster die Grundlage für die Erforschung der geophysikalischen Mechanismen, die für die Muster verantwortlich sind. Wir betrachten die Identifizierung räumlicher Regionen mit ähnlichem Verhalten extremer Niederschläge als Clusterproblem und schlagen einen netzwerkbasierten Cluster-Workflow vor. Mithilfe dieses Workflows identifizieren wir zwei robuste Muster extremer Niederschläge auf globaler Ebene. Schließlich ist Graphensparsifizierung in der Informatik eine verlustbehaftete Komprimierungstechnik, die die Erhaltung repräsentativer Eigenschaften für Graphendaten erfordert. Zu diesem Zweck schlagen wir ein generisches Edge-Sampling-Framework vor, indem wir die Sparsifizierung als Optimierungsproblem formulieren. Experimentelle Auswertungen bestätigen die Wirksamkeit unserer Methode bei der Erhaltung repräsentativer Netzwerkeigenschaften (im Durchschnitt) besser als der Stand der Technik. / Complex networks encode structure information of the underlying systems being modeled. Decoding the structure information from a network can therefore help us to understand and even to predict the functioning of the underlying systems. With this in mind, we explore three problems: multistability in networked dynamical systems, global patterns of extreme rainfall, and graph sparsification. By addressing the three problems, we aim to extend the toolbox of network science and promote the integration of network tools with other research fields. First, understanding the emergence of multistability or even extreme multistability (EM) in networked dynamical systems is still a challenging problem. For this, using a multistable model of coupled pendulum clocks (coupled clocks for short), we reveal that a symmetric coupling can increase the complexity of multistability, and uncover the coupling-induced EM. Next, in climate science, spatial patterns provide the basis for the exploration of the geophysical mechanisms responsible for the patterns. We consider the identification of spatial regions of similar extreme rainfall behavior as a clustering problem, and propose a network-based clustering workflow. Using this workflow, we identify two robust patterns of extreme rainfall on a global scale. Finally, in computer science, graph sparsification is a lossy compression technique requiring preserving representative properties for graph data. For this, we propose a generic edge sampling framework by formulating sparsification as an optimization problem. Experimental evaluations verify the effectiveness of our method in preserving representative network properties (on average) better than the state of the art.

In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD. / Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)