Leman Akoglu Thesis Defense

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

August 22, 2012, 3:00 pm EDT
Gates Hall Center 4303

 

 

Committee

Christos Faloutsos, CMU
Andrew Moore, Google Inc., CMU
Aarti Singh, CMU
Andrew Tomkins, Google Inc.

Document

The thesis [.PDF] can be found here.

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.

 

List of references (Completed Work)

The following publications are referenced in the document (in reverse chronological order).

 

Contact information

Leman Akoglu
lakoglu@cs.cmu.edu
Carnegie Mellon University,
Computer Science Department
GHC 9223 Pittsburgh, PA 15213