III: Small: Real-Time Detection of Structures from a Massive Graph Stream

迫切需要从日益增长的海量数据中快速获得可操作的情报。在许多领域，包括社交媒体分析和网络安全，数据包含实体之间的关系，可以使用图表进行建模，并且关于检测数据中的模式的问题可以转化为关于在适当的派生图表中检测新兴结构的问题。该项目的目标是开发用于从动态图形中实时发现重要结构的算法和软件。该项目将开发高效使用CPU和内存的算法，其性能可以用严格的数学方法量化。该项目还将开发预计将以高吞吐量处理数据的实施方案，并能够比目前的方法更快地识别新兴结构。这些方法和实施的可用性将影响网络安全和社交网络分析领域。开发的软件将作为操作员工具包发布，可用于当前的流处理系统。该项目将在现有课程和数据分析的新课程中引入新的教学材料，吸收来自代表性不足群体的个人，并与工业研究实验室建立研究合作。该项目将考虑包含不断演变的动态图的数据，并开发方法来检测和列举以下集合中的变化：(1)密集组合结构，如图中的最大团、准团、最大双团和准双团；(2)时间结构，如时间标记图中的时间路径和时间集团。虽然在检测海量静态图中的结构的方法方面已经有了重大进展，但对于动态图来说情况并非如此，并且通常，动态图的最先进技术是重复执行为静态图设计的方法。为了列举结构集合中的变化，该项目将采用一种新的方法来开发对变化敏感的算法，其处理成本与结构集合中的变化的大小成比例。它将使用近似算法领域的技术来设计(空间和时间)有效的方法，从图流中枚举时间结构。有关更多信息，请参阅项目网站：http://www.ece.iastate.edu/~snt/nsf-iis2015/

There is an urgent need to quickly derive actionable intelligence from increasingly large volumes of data. In many domains, including social media analytics and cybersecurity, data contains relationships between entities that can be modeled using a graph, and a question on detecting patterns in data can be transformed into questions on detecting emerging structures in appropriately derived graphs. The goal of this project is to develop algorithms and software for finding significant structures from dynamic graphs in real-time. The project will develop algorithms that are efficient in their use of CPU and memory, and whose performance can be quantified in a mathematically rigorous way. The project will also develop implementations that are expected to process data at a highthroughput and can identify emerging structures much faster than current methods. The availability of these methods and implementations will impact the domains of cybersecurity and social network analytics. Software developed will be released as a toolkit of operators that can be used with current stream processing systems. The project will lead to new instructional material in existing courses as well as new courses in data analytics, involve individuals from underrepresented groups, and forge research collaborations with industrial research labs.The project will consider data that contains an evolving dynamic graph, and develop methods for detecting and enumerating change in the set of (1) dense combinatorial structures such as maximal cliques, quasi-cliques, maximal bicliques and quasi-bicliques in a graph, and (2) temporal structures such as temporal paths and temporal cliques in a time-stamped graph. While there has been significant progress in methods for detecting structures in a massive static graph, the same is not true for a dynamic graph, and often, the state-of-the-art for a dynamic graph is to repeatedly execute a method designed for a static graph. For enumerating the change in the set of structures, the project will take a novel approach of developing change-sensitive algorithms whose processing cost is proportional to the magnitude of change in the set of structures. It will use techniques from the area of approximation algorithms in designing (space and time) efficient methods for enumerating temporal structures from a graph stream. For further information, see the project web site at: http://www.ece.iastate.edu/~snt/nsf-iis2015/