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.