Generation of random graphs with applications to complex networks MSc Thesis Defense by: Srivatsan Vasudevan

Wednesday, June 12, 2024 - 13:30

The School of Computer Science is pleased to present…

Generation of random graphs with applications to complex networks

MSc Thesis Defense by: Srivatsan Vasudevan

 

Date: Wednesday, June 12, 2024

Time:  1:30 PM

Location: Essex Hall, Room 122

 

Abstract: Given a sequence d of n positive integers, n−1 ≥ d1 ≥ d2 ≥ . . . ≥ dn ≥ 0, different sets of necessary and sufficient conditions have been proposed for the graphicality of such a sequence. When such a graph exists, we can use 2-switches of pairs of independent edges to transform one such graph G into another graph G′with the same degree sequence. This was proved by various authors. In this thesis we address the question whether a given graph G is at all switchable. Indeed, we show that unswitchable graphs are a proper subclass of split graphs, and exploit this fact to propose efficient algorithms for the recognition and generation of unswitchable graphs. This question of unswitchability is important as switching has been tried as a mechanism for generating a random graph with a given degree sequence or for generating new ones, preserving properties like simplicity or connectedness (this is known as constrained switching).

In the second part of this thesis, motivated by the application to the area of so−called complex networks (examples are: protein−protein interaction networks, social networks, metabolic networks etc.), the statistical properties of province-wise transportation networks of Canada are studied and compared with two random graphs, generated using the Erdos-Renyi model and the Configuration model. A method to extract transportation network and network resilience two key practical contributions are discussed in depth.

Finally, taking cue from the configuration model, in an appendix we discuss an implementation that generates a directed graph uniformly at random, using a Markov Chain Monte Carlo (MC−MC) method.

Keywords: Graph Theory, Complex Networks, Edge-Switching, Random Network

 

Thesis Committee:

Internal Reader: Dr. Jianguo Lu

External Reader: Dr. Mehdi S Monfared

Advisor: Dr. Asish Mukhopadhyay

Chair: Dr. Xiaobu Yuan

 

MAC STUDENTS ONLY - Register here