Speaker: Edmund Yeh Yale University
Time: 2009-12-28 14:00-2009-12-28 16:00
Venue: Room 4-603, FIT Building, Tsinghua University
Download: Click!

Abstract:

Over the past decade, there has been a concerted effort to develop a network science for studying physical, biological, social, and information networks within a common framework. In this talk, we discuss a number of recent results in network science concerning connectivity, information and epidemic spread, and robustness in large-scale networks with spatial location and mobility.

We first study connectivity and information/epidemic spread in large-scale networks modelled by random geometric graphs with dynamic on-off links. Using a percolation-based perspective, we characterize the scaling behavior of the delay for spreading broadcast information or a virus in these networks. We show that the dissemination delay exhibits two behavioral regimes, corresponding to a phase transition of the underlying network connectivity. When the dynamic network is in the subcritical phase, ignoring propagation delays, the dissemination delay scales linearly with the Euclidean distance between the sender and the receiver. When the dynamic network is in the supercritical phase, the delay scales sublinearly with the distance. More interestingly, by using a new analysis which maps a network of mobile nodes to a network of stationary nodes with dynamic links, we show that the above results can be used to characterize information/epidemic spread in mobile networks.

Next, we study the resilience of networks to node failures. In many networks, the failure of a node depends on its degree, which may reflect the amount of traffic load on the node, or the relative importance of the node. Furthermore, in networks carrying load, the failure of one node can result in redistribution of the load onto other nearby nodes. If these nodes fail due to excessive load, then this process can result in a cascading failure. From the percolation perspective, the resilience of the network can be characterized in terms of whether correlated node failures lead to a large connected component of failed nodes or not. Using this approach, we obtain analytic conditions on the existence or non-existence of correlated and cascading failures.

The above results have important implications for problems such as cascading failures in power grids, the spread of epidemics among humans, and the dissemination of broadcast information in wireless communication networks.

Joint work with Zhenning Kong.
 

Short Bio: