Various complex systems such as the Internet and the World WideWeb, neural networks, the human society, chemical and biological systems are composed of highly interconnected dynamical units. Such systems can all be described as complex networks where the nodes represent the dynamic units, and two nodes are connected by an edge if the two units interact with each other. For most networks, the complexity arises from the fact that the structure is highly irregular, complex and dynamically evolving in time and that the observed patterns of interactions highly influence the behaviour of the entire system. However, despite this complexity, a large number of networks from diverse fields such as biology, sociology, economics or technology has been found to exhibit similar topological and dynamical features. In this thesis we study different aspects of the structure and dynamics of complex networks by using approaches based on Markov and highorder Markov models. Regarding the structure of complex networks, we address the problem of the presence of threebody correlations between the node degrees in networks. Namely, we introduce measures to evaluate threebody correlations by using a thirdorder Markov model, and we study them in a wide range of real datasets. Then, we investigate how these correlations influence various dynamical processes. Specifically, we focus on Biased Random Walks (BRW), a class of Markovian stochastic processes which can be treated analytically and which extend the wellknown concept of Random Walk on a network. In a BRW, the motion of walkers is biased accordingly to a generic topogical or dynamical node property. In particular, we investigate the connection between nodecorrelations in a network and the entropy rate that can be associated to the BRWs on the network. We also show how it is possible to rephrase a BRW process on a network as a plain RW on another network having the same topology but different weights associated to the edges, and we propose a number of applications where this conversion proves to be useful. In the final part of the thesis we apply the theory of complex networks and highorder Markov models to analyze and model data sets in three different contexts. First, we introduce a method to convert ensembles of sequences into networks. We apply this method to the study of the human proteome database, to detect hot topics from online social dialogs, and to characterize trajectories of dynamical systems. Second, we study mobility data of human agents moving on a network of a virtual world. We show that their trajectories have longtime memory, and how this influences the diffusion properties of the agents on the network. Finally, we study the topological properties of networks derived by EEG recordings on humans that interact by playing the prisoner's dilemma game.
HIGHORDER MARKOV CHAINS IN COMPLEX NETWORKS: MODELS AND APPLICATIONS
SINATRA, ROBERTA
2011
Abstract
Various complex systems such as the Internet and the World WideWeb, neural networks, the human society, chemical and biological systems are composed of highly interconnected dynamical units. Such systems can all be described as complex networks where the nodes represent the dynamic units, and two nodes are connected by an edge if the two units interact with each other. For most networks, the complexity arises from the fact that the structure is highly irregular, complex and dynamically evolving in time and that the observed patterns of interactions highly influence the behaviour of the entire system. However, despite this complexity, a large number of networks from diverse fields such as biology, sociology, economics or technology has been found to exhibit similar topological and dynamical features. In this thesis we study different aspects of the structure and dynamics of complex networks by using approaches based on Markov and highorder Markov models. Regarding the structure of complex networks, we address the problem of the presence of threebody correlations between the node degrees in networks. Namely, we introduce measures to evaluate threebody correlations by using a thirdorder Markov model, and we study them in a wide range of real datasets. Then, we investigate how these correlations influence various dynamical processes. Specifically, we focus on Biased Random Walks (BRW), a class of Markovian stochastic processes which can be treated analytically and which extend the wellknown concept of Random Walk on a network. In a BRW, the motion of walkers is biased accordingly to a generic topogical or dynamical node property. In particular, we investigate the connection between nodecorrelations in a network and the entropy rate that can be associated to the BRWs on the network. We also show how it is possible to rephrase a BRW process on a network as a plain RW on another network having the same topology but different weights associated to the edges, and we propose a number of applications where this conversion proves to be useful. In the final part of the thesis we apply the theory of complex networks and highorder Markov models to analyze and model data sets in three different contexts. First, we introduce a method to convert ensembles of sequences into networks. We apply this method to the study of the human proteome database, to detect hot topics from online social dialogs, and to characterize trajectories of dynamical systems. Second, we study mobility data of human agents moving on a network of a virtual world. We show that their trajectories have longtime memory, and how this influences the diffusion properties of the agents on the network. Finally, we study the topological properties of networks derived by EEG recordings on humans that interact by playing the prisoner's dilemma game.File  Dimensione  Formato  

tesi_dottorato_sinatra.pdf
accesso aperto
Dimensione
10.48 MB
Formato
Adobe PDF

10.48 MB  Adobe PDF  Visualizza/Apri 
I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/20.500.14242/73809
URN:NBN:IT:UNICT73809