REU: Scale Free Random Graph Model, ALADDIN Center

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