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

近年来，为了理解“信息学图形”或“复杂网络”的结构和动力学特性，人们做了大量的工作。这些工作的大部分是在中小型网络上进行的，它使人们对许多图形挖掘应用中出现的网络的性质有了更好的理解。尽管如此，为更大的信息图制定适当的模型并回答甚至是基本的问题仍然具有挑战性。例如，最近的工作表明，流行的网络生成模型甚至不能定性地再现大型信息学图的动态属性和基本结构属性，所提出的工作将使用传统的和最近发展的图划分问题的近似算法作为大型信息学图的“实验探针”，以更健壮和可伸缩的方式表征超大型信息学图的结构和动态属性。这将包括扩展和实施最近开发的算法，如“局部”光谱方法和算法，在光谱方法和基于流动的方法之间直观地“内插”，以及根据新的应用重新审视传统方法，如全球光谱方法和流行的METIS包背后的思想。一个中心目标将是为分析员提供具有足够的算法和统计灵活性的工具，以ARICH和稳健的方式表征大型网络的局部和全局结构。拟议工作的智力价值在于扩展最近的理论和算法的发展并将它们应用于非常真实的世界的问题。该项目的更广泛影响在于加强伯克利和斯坦福的跨学科教育，以及更广泛的影响。这将包括组织会议和课程，其中将包括研究项目的机会，包括来自代表性不足群体的学生，这些研究项目侧重于将理论方法与现实世界的应用联系起来。有关更多信息，请参阅项目网页：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/