We are studying a random graph model of networks like the World-Wide Web where we keep the graph oriented and allow random deletions of vertices and edges. In so doing we are trying to generalise the following two papers: The first paper has orientation but does not allow for deletions and the second has deletions but does not allow for orientation. With guidance, the undergraduate student will set up (difference) equations for the expected number of vertices of degree k at time t and use various methods to try to solve them, including Laplace’s method and generating functions. The prerequisites are good mathematical skills, especially some knowledge of linear algebra and differential equations.

[1] Colin Cooper, Alan Frieze, and Juan Vera, Random
deletion in a scale free random graph process, to appear
in Internet Mathematics.

[2] Béla Bollobás, Christian Borgs,
Jennifer T. Chayes, and Oliver Riordan, Directed
scale-free graphs, ACM-SIAM Symposium on Discrete Algorithms
(SODA), January 2003, pp. 132-139.

Preliminary Presentation (pdf)

Progress as of June 1, 2004 (pdf)

Final Presentation (pdf)

Other REUs for Summer 2004

Algorithms for Dynamic Point Location with Good Practical Performance

A Bezier-Based Approach to Unstructured Moving Meshes

Evaluation of Algorithms for the List Update Problem

Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)

Fast and Compact Data Structures

The Game of NimG (Nim on Graphs)

Random Graph Models of Large Real-World Networks

Solving Partial Differential Equations Numerically

Traceable Anonymity

Back to the REU page