-
Research on Internet Mathematics
Discover the fundamental principles governing very large-scale 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 scale-invariance and the asymmetry of in-degrees and out-degrees.
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 look-ahead
-
Chip-firing 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 chip-firing 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 8-9, 2002.
This page is part of Fan Chung Graham's website.