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

点击翻译按钮获取中文摘要

There has been an enormous amount of work in recent years directedtoward understanding the structural and dynamical properties of"informatics graphs" or "complex networks." Most of this work has beenon small to medium-sized networks, and it has led to an improvedunderstanding of the properties of networks arising in many graphmining applications. In spite of this, formulating appropriate modelsfor and answering even basic questions about larger informaticsgraphs remains challenging. For instance, recent work has shown thatdynamic properties as well as basic structural properties of largeinformatics graphs are not reproduced even qualitatively by popularnetwork generative models.The proposed work will use traditional and recently-developedapproximation algorithms for the graph partitioning problem as"experimental probes" of large informatics graphs in order tocharacterize in a more robust and scalable manner the structural anddynamic properties of very large informatics graphs. This willinclude extending and implementing recently-developed algorithms suchas "local" spectral methods and algorithms that intuitively"interpolate" between spectral and flow-based methods, as well asrevisiting in light of new applications traditional methods such asthe global spectral method and ideas underlying the popular packageMetis. A central goal will be to provide the analyst with tools thathave sufficient algorithmic and statistical flexibility tocharacterize the local and global structures of large networks in arich and robust way.The Intellectual Merit of the proposed work lies in extending recenttheoretical and algorithmic developments and applying them to veryreal-world problems. The Broader Impact of the project lies inenhancing interdisciplinary education at Berkeley and Stanford andmore generally. This will involve the organization of meetings andcourses that will include the opportunity for research projects,including by students from underrepresented groups, that focus onbridging theoretical methods and real-world applications. Forfurther information see the project web page:URL: http://cs.stanford.edu/people/mmahoney/graphmining/