During the last decade, the study of complex networks has diffused through many branches of science. How do we characterize the connectivity structure of the Internet, the power grid, or the human brain? Are there universal principles underlying the structure of these diverse systems? The availability of massive databases and reliable tools for data analysis provide a powerful framework to explore these structural questions. Furthermore, as the structure of most real-world networks is inherently evolving, an understanding of the dynamical complexity of networks is needed to provide a realistic description of such networks.
This project will develop efficient algorithms to analyze structural properties of large-scale networks. The PIs will also explore the connection between local structural properties and global spectral graph properties of relevance, such as the spectral radius of the adjacency matrix or the spectral gap of the Laplacian. The analysis will be extended to time-evolving networks and dynamic models of network evolution will be developed. Three scientific objectives of this proposal are: (1) designing algorithms to efficiently estimate local and global structural properties of large-scale networks, (2) relating local structural properties of a graph with its global spectral properties, using tools from spectral graph theory and convex optimization, and (3) developing predictive models of network evolution, as well as control strategies to drive the evolution of the network structure towards desirable spectral properties.
Networks are ubiquitous (the Internet, the web, biological, and social networks to name a few), and are continually evolving. Thus, developing efficient tools for understanding the evolution of structural and spectral properties of networks is of great relevance to many scientific disciplines. The project will support and train one PhD student, as well as involve undergraduate students in research at the University of Pennsylvania.
For further information see the project web site at:
