京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20893号 / 理博第4345号 / 新制||理||1624(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)准教授 篠本 滋, 教授 佐々 真一, 教授 川上 則雄 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

Dans cette thèse nous contribuons à répondre aux questions sur les processus dynamiques sur réseaux temporels. En particulier, nous etudions l'influence des représentations de données sur les simulations des processus épidémiques, le niveau de détail nécessaire pour la représentation des données et sa dépendance des paramètres de la propagation de l'épidémie. Avec l'introduction de la matrice de distributions du temps de contacts nous espérons pouvoir améliorer dans le futur la précision des prédictions des épidémies et des stratégies d'immunisation en intégrant cette représentation des données aux modèles d'épidémies multi-échelles. De plus nous montrons comment les processus épidémiques dynamiques sont influencés par les propriétés temporelles des données. / In this thesis we contribute to provide insights into questions concerning dynamic epidemic processes on data-driven, temporal networks. In particular, we investigate the influence of data representations on the outcome of epidemic processes, shedding some light on the question how much detail is necessary for the data representation and its dependence on the spreading parameters. By introducing an improvement to the contact matrix representation we provide a data representation that could in the future be integrated into multi-scale epidemic models in order to improve the accuracy of predictions and corresponding immunization strategies. We also point out some of the ways dynamic processes are influenced by temporal properties of the data.

Mathematical modeling of spreading processes have been largely studied in the literature, and its presented a boom in the past few years. This is a fundamental task on the understanding and prediction of real spreading processes on top of a population and are subject to many structural and dynamical constraints. Aiming at a better understanding of this processes, we focused in two task: the modeling and the analysis of both dynamical and structural aspects of these processes. Initially, we proposed a new and general model that unifies epidemic and rumor spreading. Besides, regarding the analysis of these processes, we extended the classical formalism to multilayer networks, in which the theory was lacking. Interestingly, this study opened up new challenges concerning the understanding of multilayer networks. More specifically, regarding their spectral properties. In this thesis, we analyzed such processes on top of single and multilayer networks. Thus, throughout our analysis, we followed three complementary approaches: (i) analytical, (ii) numerical and (iii) simulations, mainly Monte Carlo simulations. Our main results are: (i) a new unifying model, enabling us to model and understand spreading processes on large systems, (ii) characterization of new phenomena on multilayer networks, such as layer-wise localization and the barrier effect and (iii) an spectral analysis of multilayer systems, suggesting a universal parameter and proposing a new analytical tool for its analysis. Our contributions enable further research on modeling of spreading processes, also emphasizing the importance of considering the complete multilayer structure instead of any coarse-graining. Additionally, it can be directly applied on the prediction and modeling real processes. Thus, aside from the theoretical interest and its mathematical implications, it also presents important social impact. / A modelagem matemática dos processos de disseminação tem sido amplamente estudada na literatura, sendo que o seu estudo apresentou um boom nos últimos anos. Esta é uma tarefa fundamental na compreensão e previsão de epidemias reais e propagação de rumores numa população, ademais, estas estão sujeitas a muitas restrições estruturais e dinâmicas. Com o objetivo de entender melhor esses processos, nos concentramos em duas tarefas: a de modelagem e a de análise de aspectos dinâmicos e estruturais. No primeiro, propomos um modelo novo e geral que une a epidemia e propagação de rumores. Também, no que diz respeito à análise desses processos, estendemos o formalismo clássico às redes multicamadas, onde tal teoria era inexistente. Curiosamente, este estudo abriu novos desafios relacionados à compreensão de redes multicamadas, mais especificamente em relação às suas propriedades espectrais. Nessa tese, analisamos esses processos em redes de uma e múltiplas camadas. Ao longo de nossas análises seguimos três abordagens complementares: (i) análises analíticas, (ii) experimentos numéricos e (iii) simulações de Monte Carlo. Assim, nossos principais resultados são: (i) um novo modelo que unifica as dinâmicas de rumor e epidemias, nos permitindo modelar e entender tais processos em grandes sistemas, (ii) caracterização de novos fenômenos em redes multicamadas, como a localização em camadas e o efeito barreira e (iii) uma análise espectral de sistemas multicamadas, sugerindo um parâmetro de escala universal e propondo uma nova ferramenta analítica para sua análise. Nossas contribuições permitem que novas pesquisas sobre modelagem de processos de propagação, enfatizando também a importância de se considerar a estrutura multicamada. Dessa forma, as nossas contribuições podem ser diretamente aplicadas à predição e modelagem de processos reais. Além do interesse teórico e matemático, nosso trabalho também apresenta implicações sociais importantes.

Mathematical modeling of spreading processes have been largely studied in the literature, and its presented a boom in the past few years. This is a fundamental task on the understanding and prediction of real spreading processes on top of a population and are subject to many structural and dynamical constraints. Aiming at a better understanding of this processes, we focused in two task: the modeling and the analysis of both dynamical and structural aspects of these processes. Initially, we proposed a new and general model that unifies epidemic and rumor spreading. Besides, regarding the analysis of these processes, we extended the classical formalism to multilayer networks, in which the theory was lacking. Interestingly, this study opened up new challenges concerning the understanding of multilayer networks. More specifically, regarding their spectral properties. In this thesis, we analyzed such processes on top of single and multilayer networks. Thus, throughout our analysis, we followed three complementary approaches: (i) analytical, (ii) numerical and (iii) simulations, mainly Monte Carlo simulations. Our main results are: (i) a new unifying model, enabling us to model and understand spreading processes on large systems, (ii) characterization of new phenomena on multilayer networks, such as layer-wise localization and the barrier effect and (iii) an spectral analysis of multilayer systems, suggesting a universal parameter and proposing a new analytical tool for its analysis. Our contributions enable further research on modeling of spreading processes, also emphasizing the importance of considering the complete multilayer structure instead of any coarse-graining. Additionally, it can be directly applied on the prediction and modeling real processes. Thus, aside from the theoretical interest and its mathematical implications, it also presents important social impact. / A modelagem matemática dos processos de disseminação tem sido amplamente estudada na literatura, sendo que o seu estudo apresentou um boom nos últimos anos. Esta é uma tarefa fundamental na compreensão e previsão de epidemias reais e propagação de rumores numa população, ademais, estas estão sujeitas a muitas restrições estruturais e dinâmicas. Com o objetivo de entender melhor esses processos, nos concentramos em duas tarefas: a de modelagem e a de análise de aspectos dinâmicos e estruturais. No primeiro, propomos um modelo novo e geral que une a epidemia e propagação de rumores. Também, no que diz respeito à análise desses processos, estendemos o formalismo clássico às redes multicamadas, onde tal teoria era inexistente. Curiosamente, este estudo abriu novos desafios relacionados à compreensão de redes multicamadas, mais especificamente em relação às suas propriedades espectrais. Nessa tese, analisamos esses processos em redes de uma e múltiplas camadas. Ao longo de nossas análises seguimos três abordagens complementares: (i) análises analíticas, (ii) experimentos numéricos e (iii) simulações de Monte Carlo. Assim, nossos principais resultados são: (i) um novo modelo que unifica as dinâmicas de rumor e epidemias, nos permitindo modelar e entender tais processos em grandes sistemas, (ii) caracterização de novos fenômenos em redes multicamadas, como a localização em camadas e o efeito barreira e (iii) uma análise espectral de sistemas multicamadas, sugerindo um parâmetro de escala universal e propondo uma nova ferramenta analítica para sua análise. Nossas contribuições permitem que novas pesquisas sobre modelagem de processos de propagação, enfatizando também a importância de se considerar a estrutura multicamada. Dessa forma, as nossas contribuições podem ser diretamente aplicadas à predição e modelagem de processos reais. Além do interesse teórico e matemático, nosso trabalho também apresenta implicações sociais importantes.

Complex networks have been used to represent the fundamental structure of a multitude of complex systems from various fields. In the network representation, the system is reduced to a set of nodes and links that denote the elements of the system and the connections between them respectively. Complex networks are commonly adaptive such that the structure of the network and the states of nodes evolve dynamically in a coupled fashion. Adaptive networks lead to peculiar complex dynamics and network topologies, which can be investigated by moment-closure approximations, a coarse-graining approach that enables the use of the dynamical systems theory. In this thesis, I study several contact processes in adaptive networks that are defined by the transmission of node states. Employing moment-closure approximations, I establish analytical insights into complex phenomena emerging in these systems. I provide a detailed analysis of existing alternative moment-closure approximation schemes and extend them in several directions. Most importantly, I consider developing analytical approaches for models with complex update rules and networks with complex topologies. I discuss four different contact processes in adaptive networks. First, I explore the effect of cyclic dominance in opinion formation. For this, I propose an adaptive network model: the adaptive rock-paper-scissors game. The model displays four different dynamical phases (stationary, oscillatory, consensus, and fragmented) with distinct topological and dynamical properties. I use a simple moment-closure approximation to explain the transitions between these phases. Second, I use the adaptive voter model of opinion formation as a benchmark model to test and compare the performances of major moment-closure approximation schemes in the literature. I provide an in-depth analysis that leads to a heightened understanding of the capabilities of alternative approaches. I demonstrate that, even for the simple adaptive voter model, highly sophisticated approximations can fail due to special dynamic correlations. As a general strategy for targeting such problematic cases, I identify and illustrate the design of new approximation schemes specific to the complex phenomena under investigation. Third, I study the collective motion in mobile animal groups, using the conceptual framework of adaptive networks of opinion formation. I focus on the role of information in consensus decision-making in populations consisting of individuals that have conflicting interests. Employing a moment-closure approximation, I predict that uninformed individuals promote democratic consensus in the population, i.e. the collective decision is made according to plurality. This prediction is confirmed in a fish school experiment, constituting the first example of direct verification for the predictions of adaptive network models. Fourth, I consider a challenging problem for moment-closure approximations: growing adaptive networks with strongly heterogeneous degree distributions. In order to capture the dynamics of such networks, I develop a new approximation scheme, from which analytical results can be obtained by a special coarse-graining procedure. I apply this analytical approach to an epidemics problem, the spreading of a fatal disease on a growing population. I show that, although the degree distribution has a finite variance at any finite infectiousness, the model lacks an epidemic threshold, which is a genuine adaptive network effect. Diseases with very low infectiousness can thus persist and prevail in growing populations.

<div>Using sensor measurements to estimate the states and parameters of a system is a fundamental task in understanding the behavior of the system. Moreover, as modern systems grow rapidly in scale and complexity, it is not always possible to deploy sensors to measure all of the states and parameters of the system, due to cost and physical constraints. Therefore, selecting an optimal subset of all the candidate sensors to deploy and gather measurements of the system is an important and challenging problem. In addition, the systems may be targeted by external attackers who attempt to remove or destroy the deployed sensors. This further motivates the formulation of resilient sensor selection strategies. In this thesis, we address the sensor selection problem under different settings as follows. </div><div><br></div><div>First, we consider the optimal sensor selection problem for linear dynamical systems with stochastic inputs, where the Kalman filter is applied based on the sensor measurements to give an estimate of the system states. The goal is to select a subset of sensors under certain budget constraints such that the trace of the steady-state error covariance of the Kalman filter with the selected sensors is minimized. We characterize the complexity of this problem by showing that the Kalman filtering sensor selection problem is NP-hard and cannot be approximated within any constant factor in polynomial time for general systems. We then consider the optimal sensor attack problem for Kalman filtering. The Kalman filtering sensor attack problem is to attack a subset of selected sensors under certain budget constraints in order to maximize the trace of the steady-state error covariance of the Kalman filter with sensors after the attack. We show that the same results as the Kalman filtering sensor selection problem also hold for the Kalman filtering sensor attack problem. Having shown that the general sensor selection and sensor attack problems for Kalman filtering are hard to solve, our next step is to consider special classes of the general problems. Specifically, we consider the underlying directed network corresponding to a linear dynamical system and investigate the case when there is a single node of the network that is affected by a stochastic input. In this setting, we show that the corresponding sensor selection and sensor attack problems for Kalman filtering can be solved in polynomial time. We further study the resilient sensor selection problem for Kalman filtering, where the problem is to find a sensor selection strategy under sensor selection budget constraints such that the trace of the steady-state error covariance of the Kalman filter is minimized after an adversary removes some of the deployed sensors. We show that the resilient sensor selection problem for Kalman filtering is NP-hard, and provide a pseudo-polynomial-time algorithm to solve it optimally.</div><div> </div><div> Next, we consider the sensor selection problem for binary hypothesis testing. The problem is to select a subset of sensors under certain budget constraints such that a certain metric of the Neyman-Pearson (resp., Bayesian) detector corresponding to the selected sensors is optimized. We show that this problem is NP-hard if the objective is to minimize the miss probability (resp., error probability) of the Neyman-Pearson (resp., Bayesian) detector. We then consider three optimization objectives based on the Kullback-Leibler distance, J-Divergence and Bhattacharyya distance, respectively, in the hypothesis testing sensor selection problem, and provide performance bounds on greedy algorithms when applied to the sensor selection problem associated with these optimization objectives.</div><div> </div><div> Moving beyond the binary hypothesis setting, we also consider the setting where the true state of the world comes from a set that can have cardinality greater than two. A Bayesian approach is then used to learn the true state of the world based on the data streams provided by the data sources. We formulate the Bayesian learning data source selection problem under this setting, where the goal is to minimize the cost spent on the data sources such that the learning error is within a certain range. We show that the Bayesian learning data source selection is also NP-hard, and provide greedy algorithms with performance guarantees.</div><div> </div><div> Finally, in light of the COVID-19 pandemic, we study the parameter estimation measurement selection problem for epidemics spreading in networks. Here, the measurements (with certain costs) are collected by conducting virus and antibody tests on the individuals in the epidemic spread network. The goal of the problem is then to optimally estimate the parameters (i.e., the infection rate and the recovery rate of the virus) in the epidemic spread network, while satisfying the budget constraint on collecting the measurements. Again, we show that the measurement selection problem is NP-hard, and provide approximation algorithms with performance guarantees.</div>

Complex networks have been used to represent the fundamental structure of a multitude of complex systems from various fields. In the network representation, the system is reduced to a set of nodes and links that denote the elements of the system and the connections between them respectively. Complex networks are commonly adaptive such that the structure of the network and the states of nodes evolve dynamically in a coupled fashion. Adaptive networks lead to peculiar complex dynamics and network topologies, which can be investigated by moment-closure approximations, a coarse-graining approach that enables the use of the dynamical systems theory. In this thesis, I study several contact processes in adaptive networks that are defined by the transmission of node states. Employing moment-closure approximations, I establish analytical insights into complex phenomena emerging in these systems. I provide a detailed analysis of existing alternative moment-closure approximation schemes and extend them in several directions. Most importantly, I consider developing analytical approaches for models with complex update rules and networks with complex topologies. I discuss four different contact processes in adaptive networks. First, I explore the effect of cyclic dominance in opinion formation. For this, I propose an adaptive network model: the adaptive rock-paper-scissors game. The model displays four different dynamical phases (stationary, oscillatory, consensus, and fragmented) with distinct topological and dynamical properties. I use a simple moment-closure approximation to explain the transitions between these phases. Second, I use the adaptive voter model of opinion formation as a benchmark model to test and compare the performances of major moment-closure approximation schemes in the literature. I provide an in-depth analysis that leads to a heightened understanding of the capabilities of alternative approaches. I demonstrate that, even for the simple adaptive voter model, highly sophisticated approximations can fail due to special dynamic correlations. As a general strategy for targeting such problematic cases, I identify and illustrate the design of new approximation schemes specific to the complex phenomena under investigation. Third, I study the collective motion in mobile animal groups, using the conceptual framework of adaptive networks of opinion formation. I focus on the role of information in consensus decision-making in populations consisting of individuals that have conflicting interests. Employing a moment-closure approximation, I predict that uninformed individuals promote democratic consensus in the population, i.e. the collective decision is made according to plurality. This prediction is confirmed in a fish school experiment, constituting the first example of direct verification for the predictions of adaptive network models. Fourth, I consider a challenging problem for moment-closure approximations: growing adaptive networks with strongly heterogeneous degree distributions. In order to capture the dynamics of such networks, I develop a new approximation scheme, from which analytical results can be obtained by a special coarse-graining procedure. I apply this analytical approach to an epidemics problem, the spreading of a fatal disease on a growing population. I show that, although the degree distribution has a finite variance at any finite infectiousness, the model lacks an epidemic threshold, which is a genuine adaptive network effect. Diseases with very low infectiousness can thus persist and prevail in growing populations.:1. Introduction .................................................................................. 1 2. Moment-closure approximations of complex networks ................. 5 3. Cyclic dominance in adaptive network models of opinion formation .......... 25 4. Performance of moment-closure approximations of adaptive networks .... 35 5. Information and consensus in a fish school ................................. 65 6. Epidemic spreading on growing heterogeneous adaptive networks ......... 83 7. Conclusions ................................................................................. 101 Appendix A: Moment expansion for node update rules ................... 107

Menschliche Systeme werden seit einiger Zeit modelliert und analysiert auf der Basis der Theorie komplexer Netzwerke. Dies erlaubt es quantitativ zu untersuchen, welche strukturellen und zeitlichen Merkmale eines Systems Ausbreitungsprozesse beeinflussen, z.B. von Informationen oder von Infektionskrankheiten. Im ersten Teil der Arbeit wird untersucht, wie eine modular-hierarchische Struktur von statischen Netzwerken eine schnelle Verbreitung von Signalen ermöglicht. Es werden neue Heuristiken entwickelt um die Random-Walk-Observablen “First Passage Time” und “Cover Time” auf lokal geclusterten Netzwerken zu ermitteln. Vergleiche mit der Approximation eines gemittelten Mediums zeigen, dass das Auftreten der beobachteten Minima der Observablen ein reiner Netzwerkeffekt ist. Es wird weiterhin dargelegt, dass nicht alle modular-hierarchischen Netzwerkmodelle dieses Phänomen aufweisen. Im zweiten Teil werden zeitlich veränderliche face-to-face Kontaktnetzwerke auf ihre Anfälligkeit für Infektionskrankheiten untersucht. Mehrere Studien belegen, dass Menschen vornehmlich Zeit in Isolation oder kleinen, stark verbundenen Gruppen verbringen, und dass ihre Kontaktaktivität einem zirkadianen Rhythmus folgt. Inwieweit diese beiden Merkmale die Ausbreitung von Krankheiten beeinflussen, ist noch unklar. Basierend auf einem neuen Modell wird erstmals gezeigt, dass zirkadian variierende Netzwerke Trajektorien folgen in einem Zustandsraum mit einer strukturellen und einer zeitlichen Dimension. Weiterhin wird dargelegt, dass mit zunehmender Annäherung der zeitlichen Dimension von System und Krankheit die systemische Infektionsanfälligkeit sinkt. Dies steht in direktem Widerspruch zu Ergebnissen anderer Studien, die eine zunehmende Anfälligkeit vorhersagen, eine Diskrepanz, die auf die Ungültigkeit einer weit verbreiteten Approximation zurückzuführen ist. Die hier vorgestellten Ergebnisse implizieren, dass auf dem Gebiet die Entwicklung neuer theoretischer Methoden notwendig ist. / Human systems have been modeled and analyzed on the basis of complex networks theory in recent time. This abstraction allows for thorough quantitative analyses to investigate which structural and temporal features of a system influence the evolution of spreading processes, such as the passage of information or of infectious diseases. The first part of this work investigates how the ubiquitous modular hierarchical structure of static real-world networks allows for fast delivery of messages. New heuristics are developed to evaluate random walk mean first passage times and cover times on locally clustered networks. A comparison to average medium approximations shows that the emergence of these minima are pure network phenomena. It is further found that not all modular hierarchical network models provide optimal message delivery structure. In the second part, temporally varying face-to-face contact networks are investigated for their susceptibility to infection. Several studies have shown that people tend to spend time in small, densely-connected groups or in isolation, and that their connection behavior follows a circadian rhythm. To what extent both of these features influence the spread of diseases is as yet unclear. Therefore, a new temporal network model is devised here. Based on this model, circadially varying networks can for the first time be interpreted as following trajectories through a newly defined systemic state space. It is further revealed that in many temporally varying networks the system becomes less susceptible to infection when the time-scale of the disease approaches the time-scale of the network variation. This is in direct conflict with findings of other studies that predict increasing susceptibility of temporal networks, a discrepancy which is attributed to the invalidity of a widely applied approximation. The results presented here imply that new theoretical advances are necessary to study the spread of diseases in temporally varying networks.