The Analysis and Modeling of Large Linked Networks

NSF Award 0514429

PI:                      John Hopcroft, Cornell University

Co-PI:                Bart Selman, Cornell University

Grad Students:   Lukas Kroc, current PhD student
                                 Daniel Sheldon, current PhD student    Research Summary    Web Spam References
                                 Sucheta Soundarajan, current PhD student (associated)
                           
Undergrad
Students:           Anand Bhaskar    Research Summary
                                Aaron Sidford    Research Summary
                                Alex Tsiatas    Research Summary

Abstract:

This proposal focuses on extracting information from large network structures particularly on closing the gap between theory and empirical observations. The proposal focuses on three aspects of this problem. First, the graph structure of networks tends to be sparse and therefore the previous theory on spectral clustering does not apply.  We pursue an analysis of spectral methods for low density graphs. Second, we will extend our earlier work on tracking evolving structure in networks to identify structure previously under represented in results. Third, we will develop models of networks that more realistically capture aspects of networks that are vital to closing the gap between theory and empirical observations.

Statement concerning broader impacts resulting from proposed activities:  Our work will provide better models and tools for the rapidly growing scientific community studying large networks. Some of the key infrastructure in our modern society relies on large interconnected networks, such as the powergrid and the World Wide Web.  A better understanding both in theoretical and practical terms of large networks should enable us to improve the robustness, reliability, and efficiency of such networks.


Publications:

Andre Allavena, Anirban Dasgupta, John Hopcroft and Ravi Kumar., "Finding (short) paths in social networks.", Internet Mathematics, vol. , (), p. . Accepted

Anirban Dasgupta, John Hopcroft, Ravi Kannan, and Pradiptra Mitra, "Spectral Clustering with Limited Independence", SODA 2007, vol. , (2007), p. 474. Published