Leman Akoglu

Mining and Modeling Real-world Networks: Patterns, Anomalies, and Tools Degree Type: Ph.D. in Computer Science
Advisor(s): Christos Faloutsos
Graduated: December 2012

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 s/he 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.

Thesis Committee:
Christos Faloutsos (Chair)
Andrew Moore
Aarti Singh
Andrew Tomkins (Google Inc.)

Randy Bryant, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Data mining, knowledge discovery, graph mining, network analysis, information theory, graph structure and dynamics, pattern discovery, graph generators, clustering, anomaly and event detection, compression, sensemaking, summarization