Jeannette Janssen - Research

Large graphs

I am interested in understanding and explaining the structure of large networks (graphs). Given a random process that generates graphs, what particular properties will the graphs have? Also, given a particular graph structure, what type of generative process could have produced the graph? The ultimate aim of this research is to understand large networks, real and virtual, that arise in "real life": online social networks, brain networks, networks of interactions between proteins in a cell... Any data that is somehow linked through proximity or similarity can be modeled as a graph.

Spatial graph models

To understand how the connections made locally shape the network structure globally, we use a stochastic model. That is, probability is introduced as a proxy for the actions of many different individuals. I am interested in spatial graph models. In such models, nodes are embedded in some low-or high dimensional space, and the probability that there is a link between two nodes depends on their distance. The position of each node can represent the features of the entity modelled by the node. For example, a feature vector associated with a user in an on-line social network can represent the different interests and attributes of that user. If two users have similar feature vectors, they are more likely to be connected.

Spatial preferential attachment

With co-authors, including Anthony Bonato and Pawel Pralat, I proposed the Spatial Preferential Attachment (SPA) model. In this model, each node has a sphere of influence around it. Nodes are born one by one, and given a position. The position determines which nodes can be linked to: Each new node may link to an older node only if it falls within its sphere. As more nodes join the graph, all spheres shrink; this models the fact that as a network grows and there is more choice on who to link to, linking becomes more selective.. At the same time, individual spheres grow as their node accumulates more neighbours; this models the fact that existing links increase a node's visibility and tend to lead to new links. This leads to a structure where a few nodes have hundreds of neighbours while most nodes have only a few links. To the right of this text you see a graph generated by the SPA model.
I remain interested in the model. With Aaron Smith and post-doc Jordan Barrett, I am working on the following problem: given a graph generated by the SPA model, and noisy estimates of the position of each node, can we get better estimates of the node positions by looking at the graph structure?

Github repository of code to generate graphs according to the SPA model.

Graphons

I am also very interested in graphons. These are 2-dimensional functions that can be seen as limit objects of sequences of graphs with similar structure. Graphons can also be interpreted as very general random graph models: Each vertex is randomly assigned a value, and the graphon determines the probability that two vertices are linked, given their values. By interpreting the assigned value as a position in space, we can define spatial graphons, which lead to a very general spatial random graph model.

The general question I am interested in is: given a large graph generated according to a spatial graphon, what can we deduce about the positions of the vertices? My first paper on graphons addressing this problem was the result of a reading group formed by its authors, who were all student, postdoc or faculty member at Dalhousie at the time. We studied the simplest type of spatial graphon, where vertices are embedded in one dimension, in a line. In the paper, we develop a measure to determine whether a given graph is compatible with such a 1D spatial model, and study its continuity under the graph limit theory. I continue working on the limit theory of spatial graphs, with Mahya Ghandehari.
With Aaron Smith, I developed a randomized algorithm to determine the order of the vertices in a graph sampled from a 1-dimensional spatial graphon. In the future I hope to extend our methods to higher dimensions.

Complex networks

On the applied side, I am also interested in analyzing "real-life" networks, for example in order to find anomalous users or bot accounts in on-line social networks. I am pursuing this with Nur Zincir-Heywood and some students.