Date of Award

7-8-2024

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Complex Networks;Edge-Switching;Graph Theory;Random Network;Unswitchable Graphs

Supervisor

Asish Mukhopadhyay

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.

Download

Share

COinS