Random Walks on Complex Networks

Random walks are the simplest way to explore a graph. In [PRL08] , in collaboration with Y. Moreno (Bifi, Zaragoza) we have studied traffic in a complex network by modeling packets of information as non-interacting random walkers. The model is amenable to analytical solution and, notwithstanding its simplicity, is able to capture the essential ingredients determining the SCALING OF FLUCTUATIONS empirically observed for traffic flow in the Internet and in other real networks. In [PRE08] we have introduced the DYNAMICAL ENTROPY of a random trajectory on a graph, which can be used to characterize, within a single measure, various structural properties of a network. The dynamical entropy is quite a new concept in complex networks, where in fact the entropy has only been used in a statistical sense to characterize, for instance, ensemble of graphs. The idea is very simple: the dynamical entropy is essentially the amount of information contained, per step, in the sequence of steps that a random walk takes. A random walk that gets confined for long periods of time in subsections of a network contains less information and hence has a lower entropy, while high entropy can be used as an indicator of fast mixing. In particular, we have studied DEGREE-BIASED RANDOM WALKS in which the probability of moving to a node depends on some power of the degree of the target node. Depending on whether the exponent is positive or negative, this can give rise to walks that favor or disfavor high-degree vertices. In [PRE10], in collaboration R. Lambiotte (Imperial College, London) we have shown that, by opportunely tuning the value of the exponent, we can get diffusion process with local rules and maximal entropy rate. In [arXiv10], we have introduced and studied a model of interacting random walks competing for the nodes of a complex network.

Time-varying Graphs

Real-world networks are inherently dynamic, with the links fluctuating and changing over time. E.g., human contacts or relationships change over time because individuals lose old acquaintances, acquire new ones, or move over geographic space. Despite this fact, most of the classic studies on complex networks are based on the analysis of static graphs, as if the links were all concurrent in time. In order to capture the real dynamic behavior and time correlations of complex networks, we describe them as time-varying graphs, i.e. ensembles of time-ordered graphs. In this long-term project, in collaboration with the group of C. Mascolo (Univ. of Cambridge) and that of M. Musolesi (Univ. of St. Andrews), our plan is to extend to time-varying graphs all metrics and models developed so far for static graphs. In particular, in [PRE10] we have introduced the concepts of temporal shortest paths in time-varying graphs, and we have defined as TEMPORAL SMALL WORLD a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We have explored the small-world behavior in synthetic time-varying networks of mobile agents, and in real social and biological time-varying systems, and we have also shown how to exploit temporal centrality measures to containment mobile phone viruses that spread via Bluetooth contacts [arXiv10] (MIT Tech Review) .

Complex Networks and the Brain

Recent developments in neuroimaging, including structural and functional magnetic resonance imaging (MRI), magnetoencephalography (MEG), and electroencephalography (EEG) have provided the possibility to study human brain at a global scale as a complex network. In collaboration with the experimental group of F. Babiloni (Univ. Roma La Sapienza, and Fondazione Santa Lucia IRCCS) we have studied the topological properties of functional connectivity patterns among different cortical areas of the human brain. The networks were obtained from high-resolution EEG recordings in a set of SPINAL CORD INJURED PATIENTS during the preparation of a limb movement [IJBC09], [JPA08], and in couples of individuals playing an Iterated Prisoner's Dilemma game [PLoS10]. In particular, in the latter paper we showed how it is possible to predict human cooperative behaviors from the analysis of the so-called HYPERBRAIN NETWORKS, i.e. networks representing the connections among the areas of two distinct brains. In collaboration with M. Chavez (Lab. de Neurosciences Cognitives and Imagerie Cerebrale, CNRS, Paris) we have found that the modular structure of weighted brain networks extracted from MEG signals of EPILEPTIC PATIENTS recorded at rest, and far from the absence seizures, is intrinsically different from that of healthy subjects [PRL10] (On the cover page of PRL) .

The Physics of the City

Everyone knows that a place which is central has some special features to offer in many ways to those who live or work in cities: it is more visible, more accessible from the immediate surroundings as well as from far away, it is more popular in terms of people walking around and potential customers, it has a greater probability to develop as an urban landmark and a social catalyst, or offer first level functions like theatres or office headquarters as well as a larger diversity of opportunities and goods. In a long-term joint project with the Urban Design group of S. Porta (Univ. of Strathclyde and Politecnico di Milano), our aim is the development of new tools for the network analysis of urban spatial systems. One of such tools, named the MULTIPLE CENTRALITY ASSESSMENT (MCA), allows for mapping centrality in urban spaces [EPB06], [PhysA06], and establishing correlations with relevant dynamics such as land-use [EPB09], vehicular or pedestrian flows and crime rates. MCA has also been used for the statistical characterization of different types of urban fabrics taken from the history of cities, in order to infer relationships between them in an urban evolutionary perspective [PRE06], [PRE06]. Our latest research is mainly oriented to the definition of procedures, attitudes and tools for sustainable/human/adaptive urban analysis and design, ranging from GIS-based space analysis to sustainable community design [UDI08], transportation planning and traffic calming techniques [EPJB09], to strategies for safety and live-ability in the public domain. Much more on our work can be found at the website of the Human Space Lab, a space analysis and urban design unit based at the Politecnico of Milano.

Damage and Disease Spreading in Complex Networks

........................................ [PRE04] [EPJB05] [PNAS08] [EPL08] [JMV06]

Synchronization in Complex Networks

In collaboration with S. Boccaletti (CNR Firenze) we have studied the emergence of collective synchronized dynamics in complex networks, relating the propensity for synchronization of a network to the interplay between the network topology and the features of the coupled dynamical systems. In particular, we have addressed the problem of understanding the variable abundance of different MOTIFS by means of the Master Stability Function, an analytic method to measure the stability of the synchronous state the subgraph displays. We have found that, for undirected graphs, the stability of the synchronous state is positively correlated with the relative motif abundance, while in directed graphs the correlation exists only for some specific motifs [EPL07]. Furthermore, in [PRE07] we have introduced a method for the detection and identification of COMMUNITY STRUCTURES in complex networks, based on the formation of synchronized groups of dynamical units, and we have test the method on computer generated and real-world networks whose modular structure is already known or has been studied by means of other methods.

Structural Properties of Complex Networks

The connection topology of many biological, technological and social networks is neither completely regular nor completely random. These networks, named small worlds, are in fact highly clustered, like regular lattices, yet having small characteristics path lengths, like random graphs. In collaboration with M. Marchiori (W3C MIT and University of Padova) we have proposed a new theory of the small-world behavior based on the concept of information transport over the network and also valid for weighted networks [PRL01] (Press coverage). Our new theory is based on the definition of the EFFICIENCY of a network, which measures how well the network nodes exchange information. By using this measure both at a a global and at a local scale, small-world networks result as systems that are both globally and locally efficient. We have performed precise quantitative analysis of neural networks such as the C. elegans nervous system, and two databases of cortico-cortical connections in the macaque and in the cat, and transportation systems [PhysA02], also studying the small-world beahavior in connection to the cost of a network [EPJB03].