简介: |
Abstract
It is becoming more and more clear that many of the most exciting structures and phenomena of our world can be described as large networks (graphs). The internet is the foremost example, whose study motivates much of what is being done. The internet itself is modeled by different networks (the physical internet, the network of hyperlinks), and gives rise to various other networks like social networks, which are studied by sociologist, historians, epidemiologists, economists etc. Other huge networks arise in biology (from ecological networks to the brain), physics, engineering etc.
These networks pose exciting and challenging problems for the mathematician and the computer scientist; graph theory has been one of the fastest growing areas in mathematics. In "classical" graph theory we know (or assume to know) the full graph, with an exact list of nodes and edges connecting them (plus other information like capacities etc.). Graph theory established interesting and deep connections between their properties (connectivity, subgraphs, coloring, etc.), and developed sophisticated algorithms to determine these properties.
The huge networks that are at the center of interest lately represent a new kind of challenge: these networks are never completely known, and indeed often they are not completely defined. At any time, we can only have partial information about them through sampling locally, or observing the behavior of some global processes on them.
One approach to the study of such networks is to find compact approximate descriptions of them. This could be a procedure (usually randomized) that produces networks with similar behavior. The study of random graphs was initiated by Erdos and Renyi in the early 1960's, and took a new turn in 2002 when Barabasi and Albert invented a simple random growth procedure that reproduced some of the unusual features of the internet. These approaches lead to the important and mathematically interesting questions about how to define when two very large networks are similar, how to recognize this, how to do algorithms on these large networks, and many more.
Bio of the Speaker
Lovász, László is the Director of the Institute of Mathematics at the Eötvös Loránd University in Budapest, a member of the Hungarian Academy of Sciences, and President of the International Mathematical Union. He obtained his doctoral degree in mathematics from the Eötvös Loránd University, in Budapest, Hungary in 1971. He was Professor at Yale University and Principal Researcher at Microsoft Research. He wrote 4 research monographs and 4 textbooks, and over 250 research papers. His awards include the Wolf Prize and the John von Neumann Theory Prize. His field of research is discrete mathematics, in particular its applications to the theory of algorithms and the theory of computing. He is deeply interested in interactions between different parts of mathematics. Recently he has been working on the mathematical theory of large networks. |
