Representing Sparse Graphs with Graphons: Challenges and Approaches

The next statistics seminar will be presented by Dr Sevvandi Kandanaarachchi from Data 61.

Title: Representing Sparse Graphs with Graphons: Challenges and Approaches
Speaker: Dr Sevvandi Kandanaarachchi
Time and location : 3-4pm on Access Grid Room AGR 829 or Zoom
Abstract :

Social media networks and career networks generally grow over time. What tools are available to us to model growing networks/graphs? Do these growing graphs have a limit object? Specifically, how can we represent the limit of a graph sequence when the number of nodes increases to infinity?

To represent this infinite object, graphons are used. A graphon is a function defined on a unit square. Generally, the unit square represents a scaled adjacency matrix and the function value at each point in the square represents edge probabilities of nodes. The graphon can be used as a generating model or a blueprint for a sequence of graphs. For example, if we know the graphon and we want to see how a graph with 1000 nodes looks like in this instance, we can sample a 1000-node graph from the graphon.

The main challenge of graphons is that graphs generated from a graphon are dense. That is, the proportion of edges to the number of nodes squared is fixed as the graph grows. But in many real-world applications, graphs are sparse. So how do we represent sparse graphs using graphons? In this talk, we will discuss such methods and present some recent advances.