March 5, Tuesday
12:00 – 13:00
What to do with big graphs, or, local graph theory
Computer Science seminar
Lecturer : Nati Linial
Affiliation : School of Computer Science and Engineering, Hebrew University of Jerusalem
Location : 202/37
Host : Dr. Aryeh Kontorovich
In many fields of application we encounter very large graphs.
Because of their size and for many other practical reasons, it is
completely infeasible to calculate complicated graph parameters of
such graphs. Yet, and since we still want to extract some useful
information from the data, what should we do? Current practices in
this area are very unsatisfactory and often concentrate on
easy-to-compute but fairly uninformative parameters such as the degree
distribution of the vertices. Another approach which is also practiced in certain circles is take a ``local" view of the graph.
Namely, fix some small integer k; sample at random k-tuples of
veritces and look at the distribution of the induced k-vertex
subgraphs. This leads to many interesting questions, on some of which
we now have fairly satisfactory answers, while others are still very hard and challenging:
1. To what extent do local profiles characterize the big graph?
2. What local profiles are possible?
3. What global conclusions can be drawn from local information?