Student research opportunities

Generation of random graphs

Project Code: CECS_1178

This project is available at the following levels:
Summer Scholar
Please note that this project is only for undergraduate students.

Keywords:

algorithms, graph theory, simulation

Supervisors:

Emeritus Professor Brendan McKay
Dr Mikhail Isaev

Outline:

There are many fields in which the structure of random networks is important, but there are only a few cases in which either an exact theoretical model or an exact simulation is available. This project will attempt to fill in the gap in the case of random graphs whose vertices have known degrees.

Goals of this project

Specific tasks will include the following. (0) Write a brief survey of existing literature. (1) Implement and test proposed algorithms for exact sampling. (2) Investigate Markov chains for refining inexact samplers. (3) Use the algorithms to estimate several parameters of practical importance.

Requirements/Prerequisites

Advanced programming ability. Some knowledge of graph theory and probability.

Student Gain

The student will gain an insight into the theoretic work on an important problem, and obtain valuable experience in the implementation of probabilistic combinatorial algorithms.

Background Literature

To be provided.

Contact: