The Analysis and Modeling of Large Linked Networks

Cornell University, Ithaca NY

Investigators

Abstract

The goal of this research project is to develop methods for uncovering information hidden in large linked real-world networks. The approach is based on spectral analysis techniques that were previously developed for sparse graphs, and are extended to work on complex networks in order to defuse the "majority rule" where the stronger areas of the network structure dominate the overall structure. The outcome is that the network analysis will not be dominated by the stronger nodes obscuring weaker nodes that are structurally significant in the network. The project also develops methods for tracking changes in such graphs in order to discover new clusters, e.g., novel research communities. Clusters that occur in most of these networks are the natural communities, and provide a basic unit of analysis for tracking over time. Finally, the network analysis and modeling methods are extended to heterogeneous graphs that include multiple link types. The work combines the development of formal models with the analysis of empirical data. The research project provides an excellent educational platform, introducing undergraduate and graduate students to statistical techniques and algorithmic methods. The theoretical results will find applications in a broad range of areas, including Web searching, citation analysis, data mining and information discovery, social networks analysis, or power grid management. The project's Web site (http://www.cs.cornell.edu/jeh/linked.htm) will provide access to the project's results and resulting software.