Network science has provided useful answers to research questions in many fields, from biology to social science, from ecology to urban science. The first analyses of networked systems focused on binary networks, where only the topology of the connections were considered. Soon network scientists started considering weighted networks, to represent interactions with different strength, cost, or distance in space and time. Also, connections are not fixed but change over time. This is why in more recent years, a lot of attention has been devoted to temporal or time-varying networks. We now entered the era of multi-layer networks, or multiplex networks, relational systems whose units are connected by different relationships, with links of distinct types embedded in different layers. Multiplexity has been observed in many contexts, from social network analysis to economics, medicine and ecology. The new challenge consists in applying the new tools of multiplex theory to unveil the richness associated to this novel level of complexity. How do agents organise their interactions across layers? How does this affect the dynamics of the system? In the first part of the thesis, we provide a mathematical framework to deal with multiplex networks. We suggest metrics to unveil multiplexity from basic node, layer and edge properties to more complicated structure at the micro- and meso-scale, such as motifs, communities and cores. Measures are validated through the analysis of real-world systems such as social and collaboration networks, transportation systems and the human brain. In the second part of the thesis we focus on dynamical processes taking place on top of multiplex networks, namely biased random walks, opinion dynamics, cultural dynamics and evolutionary game theory. All these examples show how multiplexity is crucial to determine the emergence of unexpected and instrinsically multiplex collective behavior, opening novel perspectives for the field of non-linear dynamics on networks.

Complex network theory has been well established as one of the main tools for understanding and analyzing the behavior of the natural systems that surround us. Social networks, genetic and protein interaction networks, airline and road traffic networks, brain connectivity networks and web graphs are only some of the examples. As network theory evolves it becomes more apparent that these complex systems are often composed of multiple types of interactions, each carrying a different piece of information, and therefore are commonly represented in the form of multiplex networks, where each layer represents a different type of interaction among nodes. In addition to the interactions among the nodes of the networks, these systems also present correlations among the various types of interactions, as represented by the intrinsic structure and the associations of the various layers of the graph. For example, in social sciences, a network with a large overlap between two layers that represent two distinct types of people interactions i.e. friendship and professional ties might indicate that there is an interconnection between the two in the given network. In another example, in transportation networks, where nodes represent airports connected by flights operated by specific airlines (each airline representing a layer of the graph), the structure of the layers can provide information about the airline: traditional airlines such as Lufthansa tend to have a large overlap in activity pattern with other airlines, whereas low-cost airlines such as easyJet tend to avoid such overlaps. Due to their ability to represent such complex entity interactions, multiplex networks have lately been the focus of a large part of the research community, studying a variety of aspects, such as structural measures, node communities detection, layer reducibility, network generative models, and information spreading. In this work we focus on techniques for the exploration of the intrinsic structure of multiplex networks, and contemplate ways of addressing common challenges of learning from multiplex networks. In particular, our work focuses on three main directions: structured regression, graph summarization and graph similarity. We analyze and discuss the main challenges of each of these research directions, and then we propose novel methods to address them. For each problem, we utilize artificial data to study their effectiveness, understand their intrinsic properties and evaluate their behavior under a controlled network structure. Then, we report applications on real-world data sets, from variety of domains, and compare our proposed methods with state-of-the-art and well established baseline methods. Through this work, we aim to offer proof that the networks' intrinsic structure, when utilized, can increase the informative power of network theory models and allow researchers to build more educated algorithms. / Computer and Information Science

Multiplex networks describe a set of entities, with multiple relationships among them, as a collection of networks over a common vertex set. Multiplex networks naturally describe complex systems where units connect across different modalities whereas single network data only permits a single relationship type. Joint spectral embedding methods facilitate analysis of multiplex network data by simultaneously mapping vertices in each network to points in Euclidean space, entitled node embeddings, where statistical inference is then performed. This mapping is performed by spectrally decomposing a matrix that summarizes the multiplex network. Different methods decompose different matrices and hence yield different node embeddings. This dissertation analyzes a class of joint spectral embedding methods which provides a foundation to compare these different approaches to multiple network inference. We compare joint spectral embedding methods in three ways. First, we extend the Random Dot Product Graph model to multiplex network data and establish the statistical properties of node embeddings produced by each method under this model. This analysis facilitates a full bias-variance analysis of each method and uncovers connections between these methods and methods for dimensionality reduction. Second, we compare the accuracy of algorithms which utilize these different node embeddings in a variety of multiple network inference tasks including community detection, vertex anomaly detection, and graph hypothesis testing. Finally, we perform a time and space complexity analysis of each method and present a case study in which we analyze interactions between New England sports fans on the social news aggregation and discussion website, Reddit. These findings provide a theoretical and practical guide to compare joint spectral embedding techniques and highlight the benefits and drawbacks of utilizing each method in practice.

<div>This dissertation focuses on developing a series of mathematical models to understand the role of urban transportation system, urban mobility and information dissemination in the spreading process of infectious diseases within metropolitan areas. Urban transportation system serves as the catalyst of disease contagion since it provides the mobility for bringing people to participate in intensive urban activities and has high passenger volume and long commuting time which facilitates the spread of contagious diseases. In light of significant needs in understanding the connection between disease contagion and the urban transportation systems, both macroscopic and microscopic models are developed and the dissertation consists of three main parts. </div><div></div><div>The first part of the dissertation aims to model the macroscopic level of disease spreading within urban transportation system based on compartment models. Nonlinear dynamic systems are developed to model the spread of infectious disease with various travel modes, compare models with and without contagion during travel, understand how urban transportation system may facilitate or impede epidemics, and devise control strategies for mitigating epidemics at the network level. The hybrid automata is also introduced to account for systems with different levels of control and with uncertain initial epidemic size, and reachability analysis is used to over-approximate the disease trajectories of the nonlinear systems. The 2003 Beijing SARS data are used to validate the effectiveness of the model. In addition, comprehensive numerical experiments are conducted to understand the importance of modeling travel contagion during urban disease outbreaks and develop control strategies for regulating the entry of urban transportation system to reduce the epidemic size. </div><div></div><div>The second part of the dissertation develops a data-driven framework to investigate the disease spreading dynamics at individual level. In particular, the contact network generation algorithm is developed to reproduce individuals' contact pattern based on smart card transaction data of metro systems from three major cities in China. Disease dynamics are connected with contact network structures based on individual based mean field and origin-destination pair based mean field approaches. The results suggest that the vulnerability of contact networks solely depends on the risk exposure of the most dangerous individual, however, the overall degree distribution of the contact network determines the difficulties in controlling the disease from spreading. Moreover, the generation model is proposed to depict how individuals get into contact and their contact duration, based on their travel characteristics. The metro data are used to validate the correctness of the generation model, provide insights on monitoring the risk level of transportation systems, and evaluate possible control strategies to mitigate the impacts due to infectious diseases. </div><div></div><div>Finally, the third part of the dissertation focuses on the role played by information in urban travel, and develops a multiplex network model to investigate the co-evolution of disease dynamics and information dissemination. The model considers that individuals may obtain information on the state of diseases by observing the disease symptoms from the people they met during travel and from centralized information sources such as news agencies and social medias. As a consequence, the multiplex networks model is developed with one layer capturing information percolation and the other layer modeling the disease dynamics, and the dynamics on one layer depends on the dynamics of the other layer. The multiplex network model is found to have three stable states and their corresponding threshold values are analytically derived. In the end, numerical experiments are conducted to investigate the effectiveness of local and global information in reducing the size of disease outbreaks and the synchronization between disease and information dynamics is discussed. </div><div></div>

Les gènes et les protéines n’agissent pas de manière isolée dans les cellules, mais interagissent plutôt pour faire leurs fonctions dans les processus biologiques. Ces interactions peuvent être représentées sous forme de grands réseaux dans lesquels les nœuds sont des gènes ou des protéines et les arêtes représentent leurs interactions. Diverses approches basées sur la théorie des graphes ont été développées pour extraire la connaissance fonctionnelle contenue dans ces réseaux. Néanmoins, ces méthodes ont été principalement appliquées à des réseaux individuels, en ignorant la diversité des interactions biologiques. Nous déclarons que ces différents types d’interactions peuvent être représentés sous la forme de réseaux multiplexes, c’est-à-dire des ensembles de réseaux partageant les mêmes nœuds, ce qui permet une description plus précise des systèmes biologiques. Cette thèse est focalisée sur le développement de nouveaux algorithmes étendant aux réseaux multiplexes certaines méthodes populaires de la théorie des graphes en biologie computationnelle, ainsi que sur leur application à l’étude des maladies humaines. Du côté des applications, nous nous concentrons sur les maladies liées au vieillissement prématuré, un groupe de maladies génétiques ressemblant à certains aspects du vieillissement physiologique à un âge précoce. Nous avons appliqué nos algorithmes pour détecter les modules associés à plus de 70 syndromes annotés avec un phénotype lié au vieillissement prématuré. Les résultats ont révélé le paysage des processus moléculaires perturbés dans ces maladies, qui peuvent être mis en parallèle avec les caractéristiques du vieillissement physiologique. / Genes and proteins do not act isolated in cells but rather interact to perform their functions in signaling pathways, molecular complexes, or, more generally, biological processes. These interactions can be represented as large networks in which nodes are genes or proteins and edges represent their interactions. Various graph-theory based approaches have been developed to extract the functional knowledge contained in biological networks. Nevertheless, these methods have been mainly applied to individual networks, ignoring the diversity of biological interactions. We state here that these different types of interactions can be represented as multiplex networks, i.e. collections of networks sharing the same nodes, leading to a more accurate description of biological systems. This thesis focuses on the extension from individual to multiplex networks of some of the state-of-the-art guilt-by-association methods in computational biology, and on their application to the study of human diseases. On the application side, we concentrate on premature aging diseases, a group of rare genetic disorders that resemble some aspects of physiological aging at an early age. In this framework, we applied our algorithms to detect the modules associated to more than 70 disorders annotated with at least one premature aging related phenotype. The results revealed the landscape of perturbed molecular processes in premature aging diseases, which can be paralleled with the hallmarks of physiological aging to help identifying common and specific features.

Aujourd'hui, dans de nombreux pays, les programmes de télévision de quelques entreprises américaines, les Majors, sont les plus populaires auprès des téléspectateurs. Cette thèse propose d'étudier le processus d'uniformisation culturelle qui a rendu ce phénomène possible en se concentrant sur les interactions commerciales sur le marché de la distribution de programmes de télévision. Nous avons choisi d'observer à la fois les acteurs qui portent cette uniformisation, les Majors, et les autres, qui essaient de résister. Pour ce faire, nous avons privilégié une entrée par les salons. En effet, ce secteur est structuré par un ensemble de salons et festivals, rythmant l'année. La stratégie de captation des Majors consiste à pratiquer des contrats exclusifs et à adopter un comportement de passager clandestin sur les salons. Durant ces derniers, ils sortent de la place de marché officielle, tout en restant à proximité, afin d'attirer les plus gros acheteurs. Ces comportements sont tolérés, car, pour un salon, la participation des Majors est une condition nécessaire à son succès du fait de leur popularité auprès des acheteurs. Au moyen d'une enquête ethnographique, d'une analyse des réseaux d'échanges d'informations et de rendez-vous entre individus, et d'une analyse des réseaux de contrats entre organisations reconstruits sur le principal salon en Europe Centrale et Orientale, nous montrons que les plus faibles peuvent résister en coopérant. Cette coopération correspond souvent à des mécanismes triadiques locaux, à la fois multiniveaux, multimilieux et multiplexes, que nous identifions avec leurs sous-structures et leurs conditions d'apparition, et dont nous testons la probabilité d'occurrence. / Today television programs produced by a few American companies, the Majors, are among the most popular with viewers. This dissertation examines the process of cultural uniformisation that has driven this phenomenon by focusing on commercial interactions in the global distribution market for television programs. We observe both the actors who promote this uniformisation, the Majors, and the others, who try to resist it. To do this we look at how trade fairs in this sector work. Indeed, this industry is structured by a set of recurrent and annual trade fairs and festivals. The captation strategy of the Majors consists in offering only exclusive contracts and free-riding on the trade fairs themselves. During these events, they leave the official marketplace while remaining in the close vicinity in order to organize private screenings and attract the buyers with the deepest pockets. This behavior is tolerated because the participation, at least formal, ofthe Majors is vital for the organizers of the trade fairs due to the popularity of their production with buyers and the public. Based on ethnographic observations, organizational analyses and a multilevel network study (i.e. inter-individual networks of information exchange and of scheduled meetings, and inter-organizational networks of contracts between companies) in the main tradefair of Eastern Europe, we show that the weakest parties in the system can cooperate to resist the domination of the Majors. This cooperation is often based on local, triadic mechanisms that are multilevel, multimilieux and multiplex that we identify with their substructures, determinants and probability of occurrence.