Finding Patterns and Anomalies in Large Time-Evolving Graphs

在大型时间演化图中查找模式和异常

• 批准号: 0534205
• 负责人: Christos Faloutsos
• 金额: $ 33.76万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-04-15 至 2009-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0534205&HistoricalAwards=false
• 关键词: Finding; Patterns; Anomalies; Large; Time

Social networks can be represented as time-evolving graphs where the nodes are the members/entities of the social network and the edges represent connections/relationships between the nodes. This project tries to answer questions such as: How does a "normal" social network look like? How will it evolve over time? How can we spot "abnormal" interactions (e.g., spam), in a time-evolving e-mail graph? The approach developed in this project is to look for time-evolution "laws", and to design fast, scalable data mining tools for real graphs with millions and billions of nodes. The approach consist of two efforts: (1) discovery of patterns that hold when graphs evolve over time and (2) tools to analyze, visualize and mine such graphs to discover anomalies. The resulting tools will have a broad applicability. They will be vital for mining and outlier detection in numerous settings, such as money-laundering rings, mis-configured routers on the Internet, suspicious user accesses to database records, surprising protein-protein interactions in a gene regulatory network, and many applications involving large-scale evolving social networks. The project Web site (http://www.cs.cmu.edu/~christos/PROJECTS/GRAPH-MINING/) provides additional information and will be used for results dissemination.

社交网络可以表示为时间进化的图，其中节点是社交网络的成员/实体，边表示节点之间的连接/关系。这个项目试图回答这样的问题：一个“正常”的社交网络是什么样的？随着时间的推移，它将如何演变？我们如何在一个随时间变化的电子邮件图中发现“异常”的交互（例如，垃圾邮件）？该项目开发的方法是寻找时间进化的“规律”，并为具有数百万和数十亿节点的真实图形设计快速，可扩展的数据挖掘工具。该方法包括两个方面的努力：(1)发现图形随时间演变的模式；(2)分析、可视化和挖掘这些图形以发现异常的工具。由此产生的工具将具有广泛的适用性。它们在许多情况下对挖掘和异常值检测至关重要，例如洗钱圈，互联网上配置错误的路由器，可疑用户访问数据库记录，基因调节网络中令人惊讶的蛋白质-蛋白质相互作用，以及涉及大规模进化的社会网络的许多应用。项目网站（http://www.cs.cmu.edu/~christos/PROJECTS/GRAPH-MINING/）提供了更多信息，并将用于传播结果。