Understanding and Accelerating Information Spreading in Dynamic Networks. ARO Research Area 10: Network Science – 10.1 Communication and Human Networks
Project runs from 01/31/2017 to 01/30/2020
In many existing and emerging large-scale networks, an important application is to spread the information quickly and efficiently over the network. Over the past decade, this topic has received great research interest, and is relatively well studied for static networks. In contrast, our knowledge is far from complete when the network structures change over time, which is typical due to various reasons including environment changes, device and user mobility, variation of social relationship, and growth of the networks. There have been extensive studies on protocol and algorithm development in the area of mobile wireless networks, but many of them resort to simulation and
experimentation with synthetic and real-world mobility traces; a general analytical framework is lacking. In this project, built on our promising preliminary results, we intend to work towards a unified analytical framework for mobile networks that can address various types of mobility patterns and handle both connected and delay-tolerant networks. We also plan to extend our study to mobile social networks, which possess some unique features for information spreading that deserve separate and in-depth considerations. As emerging networks are complex and exhibiting unpredictable dynamics, random-walk based
algorithms become an appealing architectural solution for them. A pertinent question is whether we can further improve the efficiency of these algorithms while maintain their simplicity and robustness. Our preliminary results indicate that, by exploiting some additional information which may readily be available, a speedup by an order of magnitude is potentially achievable. Underlying our efficient algorithms is a design framework based on non-reversible Markov chains. In the second research thrust, we plan to deepen our study on this design framework, and further extend its underlying principle to the study in mobile social networks. The proposed research will be assessed through a comprehensive evaluation plan.