There has been a rapid increase in the number and types of digital networks over the last 2 decades beginning, of course with the Internet, its constituent networks, and the World Wide Web. We now have a wide range of on-line social networks (OSNs) such as Facebook, Twitter, mobile ad hoc networks (MANETs) and delay tolerant networks (DTNs). These networks pervade all aspects of our lives and provide a growing range of services in commerce, business, communications, and connectivity. Many of these networks are continually in a dynamic state of flux and/or extremely large. For example, the topology of a MANET or a DTN is constantly changing, and that of an OSN such as Facebook is rapidly growing and evolving. The modeling, analysis, and measurement of such networks are challenging, due to their dynamism and sizes. As a consequence, traditional mathematical techniques are not suitable and fundamentally new techniques are needed.
This research will focus on three interrelated problems. The first is to develop useful and accurate models that capture the dynamics of today?s social and technological networks. The second is to develop and study a class of techniques for characterizing and searching such networks. These techniques are based on a very simple mechanism, namely to let an agent explore the network by randomly choosing where to go. This is known as a random walk in the mathematics literature and has been shown to exhibit desirable search and characterization properties in static networks that shows promise in dynamic networks. Last, many static networks exhibit what is known as a power law, namely that the distribution for the number of neighbors of a node roughly decays as k−a where k is the number of neighbors and a is a positive constant greater than one. The third problem is to understand what constitutes a power law in a dynamic network, how this power law comes to be, and what implications there might be regarding the health of the network.
Broader Impact. The work will positively impact society by providing a deeper understanding of and a set of tools for managing and monitoring digital networks such as MANETs and OSNs. The project includes a comprehensive dissemination plan including public release of tools for network characterization. The education plan includes cross-specialty seminars, undergraduate involvement in research through a REU site, and international outreach to South America.
