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

三：小：动态图的建模、查询和挖掘

• 批准号: 1219254
• 负责人: Ambuj Singh
• 金额: $ 49.83万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219254&HistoricalAwards=false
• 关键词: III; Small; Modeling; Querying; Mining

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.

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