Graph Mining: Laws, Generators and Tools

Speaker:	Professor Christos Faloutsos
		Electrical and Computer Engineering
		Carnegie Mellon University

Title:		"Graph Mining: Laws, Generators and Tools"

Date:		Monday, 7 February 2011

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F (near lifts 25/26), HKUST

Abstract:

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 query nodes
(e.g. suspicious people) and finds the node that is best connected to all
of them (e.g. 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.


********************
Biography:

Dr. Christos Faloutsos is a professor of Electrical and Computer
Engineering at Carnegie Mellon University (CMU). He has received the
Presidential Young Investigator Award by the National Science Foundation
(1989), the Research Contributions Award in ICDM 2006, the Innovation
Award in KDD 2010, fifteen ``best paper'' awards, and four teaching
awards. He has served as a member of the executive committee of SIGKDD,
received the ACM 2010 SIGKDD Innovation Award and he was also named a
Fellow of the ACM in 2010.

He has published over 200 refereed articles, 11 book chapters and one
monograph. He also holds five patents and has given over 30 tutorials and
over 10 invited distinguished lectures.  His research interests include
data mining for graphs and streams, fractals, self-similarity and power
laws, indexing for multimedia and bio-informatics data bases, and
performance.