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

近年来，有大量的工作是为了理解“信息学图”或“复杂网络”的结构和动态特性。大部分工作都是在中小型网络上进行的，并且它已经导致了对许多石墨挖掘应用中出现的网络特性的更好理解。尽管如此，为更大的信息图表制定合适的模型并回答基本问题仍然具有挑战性。例如，最近的研究表明，流行的网络生成模型甚至不能定性地再现大型信息学图的动态特性和基本结构特性。提出的工作将使用传统的和最近开发的图划分问题的近似算法作为大型信息学图的“实验探针”，以便以更健壮和可扩展的方式表征超大型信息学图的结构和动态特性。这将包括扩展和实现最近开发的算法，如“局部”光谱方法和在光谱和基于流的方法之间直观地“插值”的算法，以及根据新的应用重新审视传统方法，如全局光谱方法和流行的软件包背后的思想。中心目标将是为分析人员提供具有足够算法和统计灵活性的工具，以丰富和稳健的方式表征大型网络的局部和全局结构。所提出的工作的智力价值在于扩展了最近的理论和算法发展，并将它们应用于非常现实的问题。该项目更广泛的影响在于加强伯克利和斯坦福乃至更广泛的跨学科教育。这将涉及组织会议和课程，其中包括研究项目的机会，包括来自代表性不足群体的学生，这些项目侧重于连接理论方法和现实世界的应用。欲了解更多信息，请参阅项目网页：URL: http://cs.stanford.edu/people/mmahoney/graphmining/

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/