Connectivity of random graphs with fixed degree sequence

Random Graphs are crucial for modelling large, complex networks such as: the hyperlinks between pages of the web, protein interactions at the cellular level, the brain’s neural pathways, social networks and many others. Graphs are ubiquitous because they focus only on connectivity structure. A graph consists of a set of vertices, some pairs of which are connected by an edge. The degree of a vertex is the number of edges leaving it. The classical Erdos-Renyi random graph does not reflect the structure of real-life networks because it treats all vertices identically and so the degrees are concentrated in a small range. In real world network, degrees tend to vary significantly, e.g. the web contains authoritative hubs each linked to thousands of times, while there are very few links into a typical page . We will study random graphs with a fixed degree sequence which are universally recognized as more appropriate for modelling real world networks. We will attempt to determine the conditions which ensure we can move from every vertex to every other vertex along a sequence of edges. This will be a novel result and is expected to innovate techniques related to working with such random graph models.

Faculty Supervisor:

Louigi Addario-Berry

Student:

Partner:

National Taiwan University

Discipline:

Mathematics

Sector:

Other

University:

McGill University

Program: