Wednesday, October 20, 2004 - 3:00, WeH 4625
Title: Graph Mining
Speaker: Christos Faloutsos

Abstract:
Graphs appear everywhere: in document-term matrices (bi-partite graphs); in social networks; in computer networks; in the web; in gene regulatory networks, and many more. What do real graphs look like? What patterns do they obey? How can we generate realistic graphs? The talk presents some recent developments towards these questions. We show that real graphs obey power laws in their in- and out-degree distributions, short diameters, and surprising power laws in their eigenvalues. We also show R-MAT, a recursive matrix generator, which naturally leads to graphs with such patterns, and the cross-association method, that splits a graph into a 'natural' number of sub-graphs, using MDL.

Bio:
Christos Faloutsos is a Professor at Carnegie Mellon University. He has received the Presidential Young Investigator Award by the National Science Foundation (1989), five ``best paper'' awards, and several teaching awards. He is a member of the executive committee of SIGKDD; he has published over 120 refereed articles, one monograph, and holds five patents. His research interests include data mining for streams and networks, fractals, indexing methods for spatial and multimedia bases, and data base performance.