CAREER: Modeling and Analysis of Data from Massive Graphs

Investigator(s):

Anna Gilbert (PI)

Sponsor:

University of Michigan Ann Arbor, MI 48109 7347641817

Start Date/Expiration Date

2006-05-15 to 2011-04-30 (amended 2006-05-02)

Awarded Amount to Date:

$400,000

Abstract: This project defines a new approach to massive graphs that identifies three fundamental challenges common to many applications: scale, dynamism, and uncertainty. The project advances graph compression schemes that are universal and independent of the application to summarize massive graphs at large scales. These algorithms should be highly efficient, using a small amount of space and time to produce a compressed representation. Furthermore, these algorithms should be provably correct. In addition, the tools should be adapted to dynamic graph data. They should learn a model of the graph from historical data. Finally, this project will design tools that can infer graph properties from samples of a massive graph, since such a graph cannot be observed in its entirety. In applications where sampling schemes can be devised, we strive to do so as effectively and as efficiently as possible.

We live in an information age. Behind many of our technological, scientific, and economic forces are large volumes of data. An increasingly important type of data is relational data or graph data. These data capture how entities are related to one another, how they interact with one another, or how objects are linked together. All forms of communication amongst entities give rise to graph data, including the communication of source and destination IP addresses via IP packets in the Internet, people sending email to one another, web pages referring to one another, or proteins interacting with one another in large biological systems. Many scientific, engineering, and medical applications depend on our abilities to model, to analyze, to process, and to synthesize this type of data quickly, in the face of changes to the data, and under imperfect information. Indeed, our security and the security of the Internet may hinge upon our understanding of how entities (be they people or IP addresses) interact with one another. Our current statistical and algorithmic tools for relational data are not adequate for massive graphs. They have not kept pace with our ability to collect enormous amounts of data and our need to accurately and efficiently analyze that data. We must be able to model, to compress, and to highlight the important features of graphs that are gigantic, that evolve over time (perhaps quickly), and that may capture a limited view of a larger graph. This project aims to develop robust, highly efficient, and provably correct methods for managing massive graphs.

NSF Org:

DMS - Division of Mathematical Sciences

Award Number:

0547744

Award Instrument:

Standard Grant

Program Manager:

Henry A. Warchall
DMS Division of Mathematical Sciences
MPS Directorate for Mathematical & Physical Sciences

NSF Program(s):

APPLIED MATHEMATICS, THEORETICAL FOUNDATIONS (TF)

Field Application(s):

Other nsf.applications NEC

Program Reference Code(s):

FACULTY EARLY CAREER DEVELOPMENT PROGRAM, 1045
PECASE- eligible, 1187
UNASSIGNED, 0000

Program Element Code(s):

1266
THEORETICAL FOUNDATIONS (TF), 7351