Graphs as models of virtual networks have become quite popular lately. The best-known example is the World Wide Web, which can be seen as a directed graph where the nodes are the web pages, and the edges are the hyperlinks. Others are citation graphs, which model scholarly papers and their hyperlinks, or dictionary graphs, where nodes are words and links can represent various linguistic relationships between them.
The resulting graphs have certain common characteristics. They are extremely large---over one and a half billion nodes in the case of the web graph. They are sparse but still have a relatively small diameter, in other words, they are "small world" networks. They are also locally dense.
To study and analyze such graphs, non-traditional methods and models are needed. This seminar aims to initiate a search for such methods and models. The initial focus is twofold. One idea we will pursue is the use of wavelets to analyze these graphs. (This idea originated with Jason Brown, who also coined the term `graphlet'.) Another idea is that of modelling such graphs by a stochastic process of node creation based on the concept of copying with error. (Hence the term "evolution model")
FORMAT:
This seminar series is intended be a place for study and
discussion. We will start by studying background material (a book on
wavelets, background material on different random graph
models). Participants will take turns presenting this material. I
hope that this will lead to new ideas and new research, which can
then be presented in a later stage.