Local Views and Global Conclusions

Graph-structured data has become a universal phenomenon in the sciences, and novel mathematics is required to tackle the problems stemming from analyzing this data. The following challenge in bioinformatics exemplifies this general class of problems: the protein Interaction graph G of an organism has one vertex for each of its proteins and an edge for each pair of interacting proteins; several competing theories attempt to describe how such graphs emerge in evolution and we wish to tell which theory provides a better explanation.

A major difficulty in resolving such problems is that G is huge so it is unrealistic to calculate most of its nontrivial graph parameters. But even a huge graph G can be efficiently sampled. Given a small integer k (say k=10), the k-profile of G is a distribution on k-vertex graphs. It is derived by randomly sampling k vertices in G and observing the subgraph that they induce. A theory largely developed in MSR (“Theory of graph limits” – Lovasz, Szegedy, Chayes, Borgs, Cohn, Friedman…) offers a clue. It says essentially that to decide whether a series of large graphs is derived from a given statistical model it is enough to check that the graphs’ profiles behave as they should.

I will give you some sense of the theory of graph limits and then move to discuss profiles. The two main questions are: (i) Which profiles are possible? (ii) What global properties of G can you derive, based on its profiles?

Speaker Details

Nati Linial is a professor of computer science at the Hebrew University of Jerusalem. He obtained his undergraduate degree in mathematics at the Technion and his PhD at the Hebrew University, with a thesis on graph theory. Following a postdoctoral period at UCLA, Linial joined the faculty of the Hebrew University, where he has remained ever since. His main areas of interest are combinatorics, theoretical computer science and bioinformatics. Linial is a fellow of the American Mathematical Society, and an ISI Highly Cited Researcher.

Date:
Speakers:
Nati Linial
Affiliation:
Hebrew University of Jerusalem