III: Small: Characterizing and exploiting tree-like structure in large social and information networks

International Computer Science Institute, Berkeley CA

Investigators

Abstract

Recent technological advances have led to an explosive growth of social, biological, and information network data. This has led to a wide range of metrics, e.g., degree distributions, clustering coefficients, homophily measures, and so on, to describe and extract insight from real networks. The hope is that these metrics will help domain scientists to extract information and actionable insight from these networks. This enthusiasm, however, has not yet been fully realized; and an ongoing challenge is to develop finer actionable metrics to understand the properties of real networks. This project will facilitate the development of tools for the extraction of knowledge from large genetic, medical, internet, financial, astronomical, and other scientific network data sets, and it will enhance interdisciplinary education more generally. In more detail, this project will investigate methods to characterize and exploit tree-like structure in real information networks. It will focus on two related but complementary notions of tree-like-ness for graphs; it will use these notions to develop tools to characterize the manner in which real complex networks are tree-like; and it will use this characterization to develop tools for improved analytics on real networks. Particular attention will be paid to how this can shed light on intermediate-scale, i.e., not very small-scale or local and not very large-scale or global, structure in real networks; and the results of this project will provide implementations of algorithms to determine how and where this new understanding can be exploited for domain-specific insight more generally.