|
Friday, November 16, 2012 |
|
|
|
|
Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probability |
|
|
Many real-world graphs are large and growing. This naturally raises the question
of a suitable concept of graph convergence. For graphs with average degree
proportional to the number of vertices (dense graphs), this question is by now
quite well-studied. But real world graphs tend to be sparse, in the sense that
the average or even the maximal degree is bounded by some reasonably small
constant. In this talk, I study several notions of convergence for graphs of
bounded degree and show that, in contrast to dense graphs, where various a priori
different notions of convergence are equivalent, the corresponding notions are not
equivalent for sparse graphs. I then describe a notion of convergence formulated
in terms of a large deviation principle which implies all previous notions of
convergence. |