CMU-CS-15-126Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-15-125
Danai Koutra August 2015 Ph.D. Thesis
Keywords:
Data mining, graph mining and exploration, understanding graphs, graph similarity, graph matching, network alignment, graph summarization, compression, pattern mining, outlier detection, anomaly detection, attribution, culprits, scalability, fast algorithms, models, visualization, social networks, brain graphs, connectomes, VoG, FaBP, DeltaCon, DeltaCon-Attr, TimeCrunch, BiG-Align, Uni-Align
Graphs naturally represent information ranging from links between webpages, to
friendships in social networks, to connections between neurons in our brains.
These graphs often span
To gain insights into these problems, this thesis focuses on developing
scalable, principled discovery algorithms that combine globality with locality
to make sense of one or more graphs. In addition to our fast
**Single-Graph Exploratio**n: We show how to interpretably*summarize*a single graph by identifying its important graph structures. We complement summarization with*inference*, which leverages information about few entities (obtained via summarization or other methods) and the network structure to efficiently and effectively learn information about the unknown entities.**Multiple-Graph Exploration**: We extend the idea of single-graph*summarization*to time-evolving graphs, and show how to scalably discover temporal patterns. Apart from summarization, we claim that*graph similarity*is often the underlying problem in a host of applications where multiple graphs occur (e.g., temporal anomaly detection, discovery of behavioral patterns), and we present principled, scalable algorithms for aligning networks and measuring their similarity.
billion
edges, a Twitter graph of 1.8 billion edges, brain graphs with up to
90 million edges,
collaboration, peer-to-peer networks, browser logs, all spanning millions of
users and interactions.
230 pages
Frank Pfenning, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |