
Research on Internet Mathematics
Discover the fundamental principles governing very largescale distributed
networks and analyze key mathematical and algorithmic problems
arising in various areas of information technology.
 Massive graphs
We are still far from taming the beast
but we have
developed
quantitative rigorous methods for modeling and analyzing massive graphs
by using random graph theory.
In turn,
the study of power law model for massive graphs has deepened
our understanding for
sparse random graphs with general degree distributions.

The first paper includes the basic model for power law graphs, the expected
distribution of the giant component and the second largest components.
Abstract
some descriptions

paper

STOC paper
other related papers
Coauthors  Bill Aiello, Fan Chung, Lincoln Lu.
The STOC talk in ppt (Math type notation required).

A second paper is on the evolution of massive graphs with special emphasis on
the the scaleinvariance and the asymmetry of indegrees and outdegrees.
Abstract
paper
FOCS paper
Coauthors  Bill Aiello, Fan Chung, Lincoln Lu.

A paper on (classical) random sparse concerns
expected
values for
diameters
in very sparse graphs.
Abstract
paper
Coauthors  Fan Chung, Lincoln Lu.

For random graphs with given degree sequence,
the distribution of the sizes of connected components
depends primarily on the average degree.
Abstract
paper
Coauthors  Fan Chung, Lincoln Lu.

For random graphs with given degree sequence,
the average distances are examined. The structure of a powerlaw random graph with
exponent between 2 and 3 is
particularly interesting.
It has average distance of order log log n but has diameter of order log n.
Abstract
paper
Coauthors  Fan Chung, Lincoln Lu.

A SODA paper by
Lincoln Lu on the diameters
of power law graphs.

A
simulation project for massive graphs.

Guessing secrets
,
A problem that
arose in connection with
Internet traffic routing
has led
to many interesting new directions in
solving equations with uncertainty.

The first paper contains the formulation, variations,
upper and lower bounds, algorithms and relations to hypergraph theory.
Abstract
paper

SODA paper
.
Authors: Fan Chung, Tom Leighton, Ronald Graham

In a second paper, efficient inverse strategies are presented
with special emphasis on inner product methods.
Abstract
paper
Authors: Fan Chung, Ronald Graham and Lincoln Lu

A third paper, in preparation.

An
article
in Science News.
 Internet tomography

Dynamic location problems with finite lookahead

Chipfiring and load balancing in distributed networks.
Various methods are based on an interesting question:
Can you
hear the shape of a graph?
An implementation can be found
in a neat
webpage designed by
Robert Ellis.
A simulation of several chipfiring games is under construction.
Abstract
papers on this topic.

Selected research topics in
spectral graph theory
:

Selected topics in
extremal graph theory and random graph theory
An
article in Business Week on the special session on Internet Math at AMS meeting, Jan 89, 2002.
This page is part of Fan Chung Graham's website.