Geometric Networks Analysis
Abstract
The main goal of the project was to develop and use algorithmic tools with a geometric underpinning to analyze large networks. For example, the Internet, social networks, connectivity properties between genes or proteins in a biological cell, and other types of data that may be viewed as finite metric spaces can all be fruitfully modeled as a network or a graph G = (V,E) consisting of nodes and edges. A general property of many of these networks is that there is some sort of very local structure (e.g., clustering coefficients in so-called "small world" models, or degree distribution in so-called "power law" models) that is meaningfully geometric (in the sense of having a low-dimensional Euclidean geometry or other "nice" geometry associated with it), and the graph is relatively-unstructured otherwise. When working with networks with millions (or more) of nodes, algorithmic considerations are central; but those networks are typically extremely sparse and noisy, and so understanding the statistical properties underlying those algorithmic tools is also central. Developing and using principled algorithmic tools to extract and exploit this structure, as well as using the statistical and geometric properties underlying those tools to certify in a reliable manner when such structure is not present, were primary goals of the research.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 12, 2012
- Accession Number
- ADA567132
Entities
People
- Gunnar E Carlsson
- Mike Mahoney
Organizations
- Stanford University