Mining Billion Node Graphs
Christos Faloutsos, CMU
DLS, Georgia Tech, April 2011

FOILS

in PDF

ABSTRACT

What do graphs look like? How do they evolve over time? How to handle a graph with a billion nodes? We present a comprehensive list of static and temporal laws, and some recent observations on real graphs (like, e.g., ``eigenSpokes''). For generators, we describe some recent ones, which naturally match all of the known properties of real graphs. Finally, for tools, we present ``oddBall'' for discovering anomalies and patterns, as well as an overview of the PEGASUS system which is designed for handling Billion-node graphs, running on top of the ``hadoop'' system.