Complex networks

Cécile Caretta Cartozo
EPFL, 2009
EPFL thesis

Abstract

The last decade has witnessed a fundamental change in the role of network theory. Side by side with the increasing relevance of interdisciplinarity, this ensemble of mathematical tools and methods has known such a success and such a wide range of different applications to transform it in the proper scientific field of complex networks that groups researchers from different communities. Two different approaches can be distinguished. The first one is descriptive, tightly related to the experimental world. Reality is permeated with complex systems that lend themselves naturally to a network representation. The amount of data on natural, social and artificial systems is constantly increasing, and network theory provides a powerful framework for the analysis of such large datasets. The second is theoretical, aimed at producing models and analytical solutions for the reproduction and understanding of real networks properties. The results presented in this Thesis reflect the interdisciplinarity of the field of complex networks as well as its twofold nature. The first part of the manuscript describes new methods for the study of gene expression and protein interactions. Biological systems are highly complex and sensitive to the environment. Experimental data are affected by errors and poor reproducibility. We propose a method for the comparative analysis of similar datasets. We present an application to three independent studies on gene expression in the cell cycle of the fission yeast that show very poor agreement. In an attempt to reconcile them, we define a periodic genes network in which each node represents a gene identified as periodically regulated in the cell cycle and an edge between two nodes is drawn according to the phase difference between the expression peaks of the corresponding genes. The analysis of the topological structure of the network reveals a universal picture that overcomes the discrepancies and that is strongly related to the biological structure of the cell cycle and to the regulation of its progression. The method is able to group genes that are co-expressed during the cell cycle and to identify putative regulators of the transition from one phase to the next. Proteins are the fundamental product of gene expression. They are characterized by a modular structure comprising independent domains that act as mediators of protein interactions and are common to evolutionary related proteins. We propose the study of domain-centered interaction networks as a complementary tool for the understanding of protein interactions. We explore their topological structure looking for stable similarity groups and we investigate domain-peptide correlations that could be used as patterns for the prediction of the properties and functions to unknown proteins. The second part of this Thesis presents an exact theoretical solution for the navigability of small world networks with an inverse power-law distribution of the length of the connections. Optimal navigability is crucial for real networks involving transportation or communication processes (Internet, electric power grid, neural networks). Most of these systems are small worlds, characterized by a surprisingly small distance between any two nodes that grows only logarithmically with the size. How they are able to exploit this property for optimized performances without a complete knowledge of the structure is still an open question. It has been shown that a small world can arise from a proper compromise between local and long-range connections. In the specific case in which the length of the connections is power-law distributed and a greedy algorithm is used to forward a message from a source to a target, we obtained an original exact solution for the behavior of the expected delivery time in any dimension. We discussed the resulting scenario for the navigability and the implication of different structural parameters.

Official source

https://infoscience.epfl.ch/record/138656?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Cécile Caretta Cartozo
EPFL, 2009
EPFL thesis

Abstract

Official source

https://infoscience.epfl.ch/record/138656?ln=en

About this result

Related concepts (27)

Related concepts

Related publications (22)

Related publications

Statistical Analysis of Protein Sequences: A Coevolutionary Study of Molecular Chaperones

Duccio Malinverni

Recent advances in DNA sequencing technologies led to the accumulation of enormous quantities of genetic information available in public databases. This rapid growth of available biological datasets calls for quantitative analysis tools and concomitantly opens the doors for new analysis paradigms. Particularly, the analysis of correlated mutations and their structural interpretation have witnessed a second youth in the last years. A natural formulation for such approaches is provided by the statistical physics of disordered systems. This thesis is articulated around different projects aimed at studying particular biological systems of interests, the Hsp70 molecular chaperones, through the lens provided by methods rooted in statistical physics. In a first project, we focus on correlated mutations within the Hsp70 family. Our analysis reveals the existence of a biologically important macro-molecular arrangement of these chaperones and we investigate its phylogenetic origin. A second project investigates the interactions between the Hsp70 chaperones and one of their main co-chaperones, J-proteins. Through the combined use of coevolutionary analysis and molecular simulations at both coarse-grained and atomistic levels, we construct a structural and dynamical model of this interaction which rationalizes previous experimental evidence. In a subsequent study, we specifically focus on the J-protein co-chaperones. Through phylogenetic and coevolutionary methods, we investigate the origin of recently discovered interactions which form the basis of the disaggregation machinery in higher eukaryotes. Finally, in a fourth project, we shift our attention to the analysis of proteins involved in the iron-sulfur cluster assembly pathway. Analysis of residue coevolution in the different proteins composing this pathway reveals multiple structural insights at several scales.

EPFL2018

Multilingual Training and Adaptation in Speech Recognition

Sibo Tong

State-of-the-art acoustic models for Automatic Speech Recognition (ASR) are based on Hidden Markov Models (HMM) and Deep Neural Networks (DNN) and often require thousands of hours of transcribed speech data during training. Therefore, building multilingual ASR systems or systems on a language with few resources is a challenging task. Multilingual training and cross-lingual adaptation are potential solutions. However, context-dependent states modeling creates difficulties for multilingual and cross-lingual ASR because of the large increase in context dependent labels arising from the phone set mismatch. The goal of this thesis is to improve current state-of-the-art acoustic modeling techniques in general for ASR, with a particular focus on multilingual ASR and cross-lingual adaptation. We systematically exploited new training frameworks, from Maximum Likelihood Estimation, Connectionist Temporal Classification to Maximum Mutual Information, in the context of phoneme-based multilingual training. In order to minimize the negative effects of data impurity arising from language mismatch, we investigated language adaptive training approaches which help further improve the multilingual ASR performance. Through comprehensive experimental comparison we demonstrated that phoneme-based multilingual models are easily extensible to unseen phonemes of new languages, from which the cross-lingual adaptation yields significant improvement over traditional approaches on limited data. Finally, we proposed a semi-supervised training approach based on dropout to boost the performance in low-resourced languages using untranscribed data. In the other part of the thesis, we conducted more theoretical analysis of techniques found to be useful in sequential multilingual training. More specifically, we revisited the recurrent architecture based on Bayesâs theorem. This leads to a Bayesian recurrent unit dictated by the probabilistic formulation and naturally support a backward recursion. Experiments show that the proposed architecture exceeds the performance of conventional recurrent network. Together, this thesis constitutes a thorough analysis of the current field. Through theoretical and experimental comparisons, the proposed approaches are shown to yield significant improvement over the conventional hybrid systems on multilingual speech recognition.

EPFL2020

The framework of complex networks has been shown to describe adequately a wide class of complex systems made up of a large number of interacting units. In this framework, a node is associated to each unit and two nodes are connected by an edge if the two units interact with each other. Examples of such systems can be found in living organisms—the map of interactions between proteins or the network of neurons in the brain. Moreover, artificial systems such as the WWW, electrical grids or airplane connections have been studied using the tools of complex networks. Finally networks have found many applications in social sciences to characterize for instance human interactions of different kinds underlying the spreading of an epidemic. For most of these systems, the complexity arises because of the large number of units and their intricate connection patterns. A natural approach is therefore to simplify the systems by decreasing their size. Different schemes can indeed be designed for each particular system, leading to effective but case-dependent methods. From a more global and statistical perspective, a promising alternative is to reduce the complexity of the corresponding networks. In order to simplify complex networks, two strategies are presented in this Thesis. The first approach refers to the well-known clustering paradigm. It aims at identifying groups of nodes densely connected between each other and much less to the rest of the network. Those groups are referred to as clusters or communities. For most real systems, nodes within a community share some similarity or common feature. For instance, in a synonymy network where nodes are words and edges connect synonymous words, we have shown that finding communities allowed us to identify words corresponding to a single concept. We have also studied a network describing the dynamics of a peptide by associating a node to a microscopic configuration and an edge to a transition. The community structure of the network was shown to provide a new methodology to explore the main characteristics of the peptide dynamics and to unravel the large-scale features of the underlying free-energy landscape. Finally we have designed a new technique to probe the robustness of the community structure against external perturbations of the network topology. This method allows us, among else, to assess whether communities correspond to a real structure of the network, or are simple artifacts of the clustering algorithms. Community detection techniques have found a large number of practical applications as a method to simplify networks since the number of clusters is often much smaller than the number of nodes. However, a crucial issue has often been disregarded: is the network of clusters truly representative of the initial one? In this Thesis, we show that this is indeed not verified for most networks. For example we have considered the evolution of random walks on the network of clusters and found that it behaves quite differently than in the initial network. This observation led us to develop a new strategy to simplify complex networks, ensuring that the reduced network is representative of the initial one. It is based on the idea of grouping nodes, akin to community detection. However, the aim is no longer to identify the "correct" clusters, but to find a smaller network which preserves the relevant features of the initial one, and especially the spectral properties. We therefore refer to our method as Spectral Coarse Graining, by analogy with the coarse graining framework used in Statistical Physics. Applying this method to various kinds of networks, we have shown that the coarse-grained network provides an excellent approximation of the initial one, while the size could be easily reduced by a factor of ten. Therefore, the Spectral Coarse Graining provides a well-defined way of studying large networks and their dynamics considering a much smaller coarse-grained version. Overall, we first discuss the use and the limits of the usual clustering approach to reduce the complexity of networks, and apply it to several real-world systems. In a second part, we develop a new coarse graining strategy to approximate large networks by smaller ones and provide several examples to illustrate the power and the novelty of the method.

EPFL2007