MSc Thesis Proposal Announcement of Srivatsan Vasudevan:"Generation of random graphs with application to complex networks"

 

Date: Wednesday April 26th, 2023

Time: 1:30 PM – 3:00 PM

Location: Essex Hall, Room 122

 

Reminders: 1. Two-part attendance mandatory (sign-in sheet, QR Code) 2. Arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED. Note that due to demand, if the room has reached capacity, even if you are "early" admission is not guaranteed. 3. Please be respectful of the presenter by NOT knocking on the door for admittance once the door has been closed whether the presentation has begun or not (If the room is at capacity, overflow is not permitted (ie. sitting on floors) as this is a violation of the Fire Safety code). 4. Be respectful of the decision of the advisor/host of the event if you are not given admittance. The School of Computer Science has numerous events occurring soon.

 

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. That is, these conditons tell us if there exists a graph whose vertex degrees are as given by the 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 proposal we adddress 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).

Motivated by the application to the area of so-called complex networks (examples are: protein-protein in- teraction networks, social networks, metabolic networks etc.), in this proposal we also address the problem of generating a graph uniformly at random. Switching unfortunately may not be able to produce a random graph. So, we focussed on a Markov-Chain Monte-Carlo method (MCMC method as it is popularly known) for generating random 0-1 matrices from given marginals (these are row and column sums of these matrices) by Rao, Jana and Rao. This method can provably generate random 0-1 matrices, though the authors have not explicitly proved the polynomial mixing time of their algorithm. To understand this method well, we implemented this algorithm in Python, using the FORTRAN-like pseudocode provided by the authors.

In the next phase of our work, we plan to study statistical properties of complex networks (social and/or transportation) by generating random samples using the MCMC method.

 

Key Words: Graph Generation, Unswitchable graphs, Split Graphs, Random Graphs, Markov-Chain Mote-Carlo (MCMC) method, Edge Switching

 

Internal Reader: Dr Jianguo Lu

External Reader: Dr. Mehdi Sangani Monfared

Advisor:  Dr Asish Mukhopadhyay