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.
|
|
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.
|