III: Small: Modeling, Querying and Mining of Dynamic Graphs

许多应用程序生成的数据可以建模为图表：生物网络、社会网络、生态网络和食物网等。传统的图论和目前在图建模、查询和挖掘方面的大多数研究都集中在图的结构本质上是静态的并且不随时间变化的问题。但现实世界中的网络本质上是动态的，具有广泛的时间变化。虽然社交网络和交通网络等网络的拓扑结构经历了逐渐的变化(或演变)，但内容(信息流、注释)变化更快。在此背景下，本课题致力于将数据库技术、数据挖掘技术和算法技术相结合，开发一套可扩展的动态图查询和挖掘工具。第一个研究重点考察了刻画动态图的固有性质，特别是节点的动态可达性结构。它还研究了基于这些性质生成动态图的高保真方法。第二个研究重点是开发动态图结构的摘要技术。这些技术可用于压缩大型图形数据集、对未来值进行预测，以及在部分观测下查询信息级联。第三个研究重点是开发在不同的连通性约束下挖掘有意义的动态子图的技术，如固定子图结构、连通子图和光滑子图。这里的目标是使用背景行为的统计特征来发现动态图形数据集中的异常模式。最后的研究主旨是从内容和主题模型的角度重新审视前三个研究推动力，以理解消息内容与其在网络中的流动之间的关系。开发的方法将使用一系列真实世界的数据集进行评估，包括安然等电子邮件数据集、Twitter上的转发活动数据集、Facebook墙上的帖子和交通网络。这项工作的一个重要结果是为动态图的建模、查询和挖掘提供了一个理论上有充分依据和经验可验证的框架。网络结构及其内容(信息流、注释等)的动态行为方面我们会考虑作出更改。研究这种动态网络以及信息如何在其中流动，对于发展动态网络及其演化理论是至关重要的。这项工作有助于回答诸如幂定律是否适用于动态行为，消息的内容是否可以预测其流量，反之亦然，是否可以通过建立经验总结或生成模型来有效地挖掘动态网络中的异常。基于开发的算法的强大的开源工具将发布用于研究、学术和非营利性努力。这项研究有望在图形算法、图形数据库和图形挖掘方面产生新的技术，并实现一系列可供科学家使用的工具，并最终产生动态图形理论。更广泛的影响：拟议的项目将把研究和教育结合起来，将项目成果介绍到研究生研讨会和信息管理研究生课程中。该项目将支持一名博士后研究人员，并培养研究生。该项目为研究生和本科生提供了更多以研究为基础的培训机会，包括代表人数不足的群体的成员，例如加州大学圣巴巴拉分校计算机科学专业的女性。对于高中生，UCSB的CNSI学徒研究计划每年夏天都会引入高中生。这项工作产生的算法的开源实现将免费传播给社区。

Many applications generate data that can be modeled as graphs: Biological networks, social networks, ecological networks and food-webs, among others. Traditional graph theory and most current research in graph modeling, querying, and mining concentrates on problems where the graph structure is inherently static and does not change with time. But networks in the real world are dynamic in nature with a wide range of temporal changes. While the topology of networks such as social networks and transportation networks undergoes gradual change (or evolution), the content (information flow, annotations) changes more rapidly. Against this background, this project aims to develop a set of scalable querying and mining tools for dynamic graphs by integrating techniques from databases, data mining, and algorithms. The first research thrust examines inherent properties for characterizing dynamic graphs, specifically the dynamic reachability structure of nodes. It also investigates high-fidelity methods for generating dynamic graphs based on these properties. The second research thrust aims to develop summarization techniques for dynamic graph structures. These techniques can be used to compress large graph datasets, to make predictions about future values, and to query information cascades under partial observation. The third research thrust aims to develop techniques for mining significant dynamic subgraphs under different constraints of connectivity such as fixed subgraph structure, connected subgraphs, and smooth subgraphs. The goal is here to find anomalous patterns in dynamic graph datasets using a statistical characterization of background behavior. The final research thrust reconsiders the first three research thrusts from the point of view of content and topic models in order to understand the relationship between content of a message and its flow in a network. The developed methods will be evaluated using a number of real-world data sets including email datasets such as Enron, re-tweeting activity data sets on Twitter, Facebook wall posts, and transportation networks. An important result of this work is a theoretically well-founded and empirically verifiable framework for modeling, querying and mining of dynamic graphs. Aspects of dynamic behavior in which both the structure of networks and their content (information flow, annotations, etc.) change will be considered. The study of such dynamic networks and how information flows through them is essential to developing a theory of dynamic networks and their evolution. This work helps answer questions such as power-law applies to dynamic behavior, whether content of a message can predict its flow and vice versa, whether anomalies in a dynamic network can be mined effectively by building either an empirical summary or a generative model. Robust open source tools based on the developed algorithms will be released for research, academic and non-profit endeavors. The research is expected to yield new techniques in graph algorithms, graph databases, and graph mining, and realize a collection of tools that can be used by scientists, and ultimately lead to a theory for dynamic graphs. Broader Impacts: The proposed project will integrate research and education by introducing the results of the project into a graduate seminar, and a graduate course on information management. The project will support a postdoctoral researcher and train graduate students. The project offers enhanced opportunities for research-based training of graduate and undergraduate students, including members of under-represented groups e.g., females in Computer Science at the University of California at Santa Barbara. For high school students, the CNSI Apprentice Research Program at UCSB brings in high school students every summer. The open source implementations of algorithms resulting from this work will be freely disseminated to the community.