III: Medium: Collaborative Research: Geometric Network Analysis Tools: Algorithmic Methods for Identifying Structure in Large Informatics Graphs

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

There has been an enormous amount of work in recent years directed toward understanding the structural and dynamical properties of "informatics graphs" or "complex networks." Most of this work has been on small to medium-sized networks, and it has led to an improved understanding of the properties of networks arising in many graph mining applications. In spite of this, formulating appropriate models for and answering even basic questions about larger informatics graphs remains challenging. For instance, recent work has shown that dynamic properties as well as basic structural properties of large informatics graphs are not reproduced even qualitatively by popular network generative models. The proposed work will use traditional and recently-developed approximation algorithms for the graph partitioning problem as "experimental probes" of large informatics graphs in order to characterize in a more robust and scalable manner the structural and dynamic properties of very large informatics graphs. This will include extending and implementing recently-developed algorithms such as "local" spectral methods and algorithms that intuitively "interpolate" between spectral and flow-based methods, as well as revisiting in light of new applications traditional methods such as the global spectral method and ideas underlying the popular package Metis. A central goal will be to provide the analyst with tools that have sufficient algorithmic and statistical flexibility to characterize the local and global structures of large networks in a rich and robust way. The Intellectual Merit of the proposed work lies in extending recent theoretical and algorithmic developments and applying them to very real-world problems. The Broader Impact of the project lies in enhancing interdisciplinary education at Berkeley and Stanford and more generally. This will involve the organization of meetings and courses that will include the opportunity for research projects, including by students from underrepresented groups, that focus on bridging theoretical methods and real-world applications. For further information see the project web page: URL: http://cs.stanford.edu/people/mmahoney/graphmining/