AF: Small: Geometric Methods for Network Science

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

Analyzing the spread of an epidemic, evaluating the vulnerability of Internet-based infrastructures, modeling dynamics of opinion in online social networks, understanding interconnections in the brain, and interactions between genes -- all these tasks are, in an abstract setting, struggling to understand large-scale, complex networks of interlinked nodes. These networks are complex not only because of their scale---social networks and the Internet-of-Things span billions of nodes and even coarse information maps of the brain involve many millions of voxels and pathways---but also because they entail complex, noisy, and time-varying behavior---the structure of links in social networks or connections in brain is poorly understood, and virtually all real networks are subject to non-linear dynamics. The abstraction of graph theory, in which any nodes can be linked, leads to algorithms that become computational bottlenecks on the graphs for these large and messy networks. This project advocates that embedding complex networks in a geometric space gives a framework to apply the use of geometric methods for fast, scalable and approximate analysis of complex networks. The project has three research thrusts: (1) theoretical investigation of geometric embeddings for 'scalable network analysis:' to better understand theoretically why certain graphs appear (empirically) to embed nicely in low-dimensional spaces, discover natural graph properties that cause large distortions, and design efficient and scalable algorithms for constructing low-distortion embeddings. (2) probabilistic embeddings for 'uncertain graphs:' to evaluate how the spatial richness of geometric embeddings capture the link uncertainties inherent in virtually all practical graph models, and (3) embedding of graphs in two-dimensional plane for 'information cartography:' to embed complex graphs in the two-dimensional plane to reveal important structural themes. These thrusts complement each other, since network analysis invariably requires both an initial quantitative part---estimating various network statistics by highly efficient algorithms that are enabled by the embedding of the entire network---followed by a qualitative presentation---displaying those network aggregates and substructrures in a visual context to create an informational cartogram. The results of this project will significantly broaden the applicability of geometric algorithms to network science, and to modern data sets in general. The project touches upon many topics in theoretical computer science and mathematics including discrete and computational geometry, non-Euclidean geometry, probability theory, graph drawing, and information cartography.