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/) 提供了更多信息，并将用于结果传播。