It has been established that global connectivity metrics, such as expansion, conductance and the high-end spectrum relate to the scaling and performance of important network functions, such as routing, searching, navigating and sampling. From a theoretical point of view the work proposed here includes: (a) Characterization of clustering, conductance and spectral gap for a variety of network models related to routing, information retrieval and molecular interactions that arise in genomics. We are also explicitly interested in the algorithmic or semantic implications of these metrics in the corresponding application areas. (b)A spectral characterization of the small world phenomenon. (c )The design and analysis of several algorithms for efficient construction and maintenance of networks with good connectivity properties. From an applied point of view the proposed work includes: (a) Development of Markov chain network models with flexible parameters; we also wish to make our source code publicly available. (b )Applying spectral filtering information retrieval methods in existing data of gene and protein interaction networks. Besides theoretical computer science, the PI has also an established record of technology transfer in the field of networking and an interdisciplinary group of graduate students. Recent theory and networking publications related to the proposed work include [MP02, GMZ03b, GMZ03a, GMS03, DMV03, MPS03, GMS04, GMS05]. From an applied point of view the proposed work includes: (a) Development of Markov chain network models with flexible parameters; we also wish to make our source code publicly available. (b ) Applying spectral filtering information retrieval methods in existing data of gene and protein interaction networks. Intellectual Merit: The project will enhance our understanding in engineering and reverse engineering complex systems. The project cuts across deep mathematical notions and concrete application areas. This will contribute to our primary priority area Advances in Science and Engineering (ASE). By promoting well connected complex systems and by working with the critical BGP routing protocol the project relates directly to the National Homeland Security (NHS). By promoting efficient content distribution and information retrieval the project relates to Economic Prosperity and Vibrant Civil Society (ECS). The project has an interdisciplinary undergraduate and graduate educational component. Educational Impact: We are involved in graduate education and introduce a new application component to undergraduate courses by translating our interdisciplinary research experience to real data case studies. Integrating Diversity: The PI is a woman and several undergraduate and graduate students are involved from a diverse body of students at Georgia Tech. Broader Impact: The broader impact involves popularization of deep mathematical notions to vital application areas and education. We will continue the wide dissemination of our interdisciplinary work. The data that we propose to make available for undergraduate education will enhance the skills of undergraduate computer science majors.
