Graph Mining: Laws, Generators and Tools

How do graphs look like? How do they evolve over time?
How can we generate realistic-looking graphs?
We review some static and temporal 'laws', and we describe the "Kronecker'
graph generator, which naturally matches all of the known properties of real
graphs. Moreover, we present tools for discovering anomalies and patterns in
two types of graphs, static and time-evolving. For the former, we present
the 'centerPiece' subgraphs (CePS), which expects $q$ query nodes (eg.,
suspicious people) and finds the node that is best connected to all $q$ of
them (eg., the master mind of a criminal group). We also show how to compute
CenterPiece subgraphs efficiently. For the time evolving graphs, we present
tensor-based methods, and apply them on real data, like the DBLP
author-paper dataset, where they are able to find natural research
communities, and track their evolution.

Finally, we also briefly mention some results on influence and virus
propagation on real graphs.