Approximating Graphs by Graphs and Functions

摘要

In many areas of science huge networks (graphs) are central objects of study: the internet, the brain, various social networks, VLSI, statistical physics. To study these graphs, new paradigms are needed: What are meaningful questions to ask? When are two huge graphs “similar”? How to “scale down” these graphs without changing their fundamental structure and algorithmic properties? How to generate random examples with the desired properties? A reasonably complete answer can be given in the case when the huge graphs are dense (in the more difficult case of sparse graphs there are only partial results).