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

III：媒介：协作研究：几何网络分析工具：识别大型信息学图中结构的算法方法

• 批准号: 0963904
• 负责人: Satish Rao
• 金额: $ 41.8万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2013-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0963904&HistoricalAwards=false
• 关键词: III; Medium; Collaborative; Research; Geometric

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/

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