Accession Number:

ADA568260

Title:

Mining and Modeling Real-world Networks: Patterns, Anomalies, and Tools

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2012-08-01

Pagination or Media Count:

244.0

Abstract:

Large real-world graph a.k.a network, relational data are omnipresent, in online media, businesses, science, and the government. Analysis of these massive graphs is crucial, in order to extract descriptive and predictive knowledge with many commercial medical, and environmental applications. In addition to its general structure knowing what stands out, i.e. anomalous or novel, in the data is often at least, or even more important and interesting. In this thesis, we build novel algorithms and tools for mining and modeling large-scale graphs, with a focus on 1 Graph pattern mining we discover surprising patterns that hold across diverse real-world graphs, such as the fortification effect e.g. the more donors a candidate has, the super-linearly more money she will raise, dynamics of connected components over time, and power-laws in human communications, 2 Graph modeling we build generative mathematical models such as the RTG model based on random typing that successfully mimics a long list of properties that real graphs exhibit, 3 Graph anomaly detection we develop a suite of algorithms to spot abnormalities in various conditions for a plain weighted graphs, b binary and categorical attributed graphs, c time-evolving graphs, and d sensemaking and visualization of anomalies.

Subject Categories:

  • Information Science

Distribution Statement:

APPROVED FOR PUBLIC RELEASE