ATD: Collaborative Research: Spectral Interpretations of Essential Subgraphs for Threat Discoveries

ATD：协作研究：威胁发现的基本子图的光谱解释

• 批准号: 1737839
• 负责人: Van Vu
• 金额: $ 16.7万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1737839&HistoricalAwards=false
• 关键词: ATD; Collaborative; Research; Spectral; Interpretations

In the past decade, graph theory has undertaken a remarkable shift --- a profound transformation. Graph theory is no longer limited to a few vertices and edges (as in the famous riddle of "The Seven Bridges of Konigsberg"). Today, graph theory is often about understanding our ever-more connected world, which may contain millions and billions of nodes. Such a change is in large part due to the humongous amount of information present in today's society. For example, successful Web search algorithms are based on WWW graphs, which contain all web pages as vertices and hyperlinks as edges. In other cases, such as social networks, the sheer number of users contribute to the huge size of the graphs representing a particular social medium. In response to challenges set forth in the ATD announcement, this work seeks to develop a framework using advanced tools from random and spectral graph theory to carry out quantitative analyses of the structure and dynamics of large graphs or networks. Here, the focus is on finding patterns that may be hidden in them that could potentially be indicative of emerging threats of various kinds (internets, critical infrastructure networks, financial networks, social networks, etc.)This research plans to use tools from random graph theory, differential geometry, and information theory to carry out analytic computations of observable network structures and capture the most relevant and refined quantities of real-world networks. The approach is based on the Szemeredi regularity lemma, which provides regular partitions of a given graph. If these can be found efficiently, then rapid (and often parallel- and distributed- among partitions) methods to compute a myriad of graph properties of interest, including graph merging and subgraph detection, will be achieved. Unfortunately, the regularity Lemma is only an existence proof; however, it is here, using ideas from spectral graph theory, where computationally efficient and scalable methods to approximate these partitions will be developed. Moreover, to further achieve efficiency, a new model will be developed (based on a stochastic block model) representing information on graphs. The motivation behind this approach is two-fold. First, the most meaningful types of graph operations (graph merging, etc.) tend to preserve such partitions. Second, these blocks (or communities) can further reduce the complexity of finding a particular subgraph (often indicative of emerging threats) in a given graph.

在过去的十年中，图理论进行了非凡的转变 - 一种深刻的转变。图理论不再限于几个顶点和边缘（如“ Konigsberg的七座桥”的著名谜语）。如今，图理论通常是关于理解我们持续的联系世界，该世界可能包含数百万和数十亿个节点。这种变化在很大程度上是由于当今社会中存在的大量信息。例如，成功的Web搜索算法基于www图，其中包含所有网页作为顶点和超链接作为边缘。在其他情况下，例如社交网络，庞大的用户贡献了代表特定社交媒介的图表的巨大规模。为了应对ATD公告中规定的挑战，这项工作旨在使用随机和光谱图理论中的高级工具来开发一个框架，以对大图或网络的结构和动态进行定量分析。 在这里，重点是寻找可能隐藏在其中的模式，这些模式有可能表明各种形式的威胁（媒体，关键的基础架构网络，财务网络，社交网络等），该研究计划使用随机图理论，差异几何学，差异几何学和信息理论来实现可观察到的网络结构的分析和捕获最相关的数量和改进范围的工具。该方法基于Szemeredi规律性引理，该引理提供给定图的定期分区。 如果可以有效地找到它们，则将实现快速（通常是在分区之间平行和分布的）方法，以计算无数的图形属性，包括图合并和子图检测。不幸的是，规律性引理只是存在的证据。但是，在这里，使用光谱图理论的思想，将开发出计算高效且可扩展的方法来近似这些分区。 此外，为了进一步实现效率，将开发一个新模型（基于随机块模型），该模型代表图形上的信息。这种方法背后的动机是两个方面。首先，图形操作的最有意义的类型（图合并等）倾向于保留此类分区。其次，这些块（或社区）可以进一步降低给定图中找到特定子图（通常指示新兴威胁的）的复杂性。

项目成果

Spectrum of Complex Networks

• DOI: 10.24166/im.03.2019
• 发表时间: 2018-09
• 期刊: Internet Math.
• 作者: Daniel Montealegre;V. Vu