Open Lecture — How (and Why) to "Read" Big Graphs

A graph consists of a set of vertices and edges, where each edge connects a pair of vertices. This mathematical construct is an extremely important theoretical object as well as a wonderful tool for modeling and analyzing real-life systems. For example, each vertex can represent a person, and an edge between two vertices x and y represents the fact that person x and person y are friends. In another important example, vertices represent proteins in an organism and an edge between x and y conveys the information that the corresponding proteins are in physical interaction. It is not hard to think of many other types of graphs. In summary, graphs can represent numerous complicated systems in science, engineering, economics, human relations and more.

Clearly a large graph encodes a lot of valuable information on various systems of great interest. The trouble is that the human eye/brain is not very good at observing large graphs. The question is how to glean the relevant information by observing a large graph. With the advance of data-collecting technologies in various areas of science and technology, this is becoming a pressing problem.

We are still unable to provide a fully satisfactory answer to this question. However, recent advances in graph theory are suggesting some promising approaches. By and large the underlying idea is to observe the "local" structure of  big graphs. In this talk I will try to explain the basic aspects of this newly emerging field of "local graph theory."

Light refreshments will be served before the lecture at 3:30 p.m.