Many physical and logical networks, including the Internet, World Wide Web, and future ubiquitous wireless networks, have enormous size that can be regarded practically infinite. For example, the World Wide Web is estimated to have over 50 billion web pages. The huge networks are also extremely heterogeneous, both physically and in their technical/social usage. They are expected to eventually merge into a complex, global socio-technical infrastructure.
To understand and reason about the enormous socio-technical networks, including methods for designing/optimizing them, the traditional network analysis and modeling approaches are insufficient, due to their limited scalability. Simulation is only feasible up to a limited network size. Conventional analysis methods, such as teletraffic theory, queuing network analysis etc., also quickly lose scalability in huge networks. At the same time, modeling and analysis is still indispensable, since one may not be able to experiment with various new solutions via large scale practical deployment, due to prohibitive cost.
This situation, in which one deals with networks of practically infinite size, has naturally led to the emergence of novel analysis and modeling approaches. They can generally be characterized as having a more abstract, "bird's eye" view of the network and often relying on asymptotic analysis on the mathematical side. This project focuses on network models that describe and analyze the network using the mathematical methodology of random graph models. A large and diverse set of such models have been proposed and analyzed, but there is a lack of unified methodology. This methodological gap is what primarily motivates this work.
Intellectual Merit The project will fill the above described methodological gap and will develop general methods that can usefully apply to many different network models. Specifically, the project will pursue the following directions:
-Exploring connections and implications among model properties that are valid for large classes of network models, not just for a single model.
-Finding methods that provide useful model-independent bounds and approximations for various properties within large model classes.
Broader Impact The project will strengthen the cross-fertilizing effect between networking and graph theory, in particular, the theory of random graph models, potentially impacting both fields. The PI has experience in both areas, which provides an ideal position to generate meaningful interaction to overcome current limitations. The educational side of the project also has a non-conventional component: beyond integrating the subject into graduate courses, the project will include student competitions to motivate students for developing creative new modeling ideas.
