We consider three topics motivated by the Network Exploration Toolkit (NEExT) for building unsupervised graph embeddings. NEExT vectorizes the graphs in a graph collection using the Wasserstein (optimal transport) distance between the distributions of node features of each graph. We inspect the effect of sampling only a proportion of the nodes of each graph, and show that even if the sampling fraction tends to zero (sufficiently slowly), so does the Wasserstein distance. NEExT relies on the assumption that local node features are informative to global characteristics of graphs. With this in mind, we consider triangle count: triangles are a local feature that correlate with the strength of a graph's community structure. We give asymptotic results for the number of triangles in a 2-community stochastic block model setting and the ABCD random graph model in both a scale-free and finite variance degree regime. Lastly, we show by experiment that augmenting the node features of graphs with triangle count improves a Graph Neural Network (GNN) in its ability to pick up on community structure and local clustering. For this, we use a random graph dataset with varying community structure, a random graph dataset with varying clustering coefficient, and a real-life dataset. We position random graph models as an effective tool for benchmarking the expressiveness of GNNs.

During this research, we investigate if there exists a k(n)-core in the scale-free configuration model, this is a commonly used null model to simulate networks. The scale-free configuration model produces a random graph, where the degree of every vertex is determined using a random variable. In this thesis, the discrete Pareto variable is used with parameter τ ∈ (2, 3). The k-core of a graph is the biggest induced subgraph where every vertex is connected to at least k edges in the subgraph. In this thesis, we let k be dependent on the number of vertices in a graph, this makes it a k(n)-core. By investigating whether k(n)-cores exist in graphs produced by the scale-free configuration model, we hope to to get a better understanding of the structure of these graphs. In this thesis, the scale-free configuration model is modeled as a death process. This death process will produce the graph and its k(n)-core jointly. First, we remove all edges which cannot be part of the k(n)-core until the point where no such edges exist anymore. This is the moment where we reach the k(n)-core. Using this method, we prove that whenever the number of vertices is sufficiently high a (log(n))^α-core exists with high probability for all constant α >0. For α < (3−τ)/(8τ) , also a n^α-core exists with high probability when the number of vertices is sufficiently high. We also find a lower bound for the number of vertices and edges left in the cores.

We provide sufficient criteria for explosion in an age-dependent branching pro- cess. For this, we assume the offspring distribution is a variation of a Pareto distribution, as the chance to get at least k children is a slowly varying function over k. Given this form, we will construct a lower bound on the generation sizes. After we obtained this lower bound, we will start a process in which we will thin the tree. We will do this by pruning the children of an individual if that individual is born after its assigned time. Doing this for all generations gives rise to a thinned tree, with infinitely many non-empty generations in a finite time. Because of that, there are infinitely many individuals at a finite time, and thus the tree exploded. There is a constraint needed, dependent on the offspring distribution, for the thinned tree to survive. The goal of this thesis is to find that constraint.

The k-truncated metric dimension of a graph is the minimum number of sensors (a subset of the vertex set) needed to uniquely identify every vertex in the graph based on its distance to the sensors, where the sensors have a measuring range of k. We give an algorithm with the goal that given any tree and any value for the measuring range of the sensors k, the algorithm finds the k-truncated metric dimension of that tree. The algorithm presented in this thesis is a modification of the algorithm given by Gutkovich and Song Yeoh [6]. The algorithm in this thesis improves on their algorithm in both validity and time complexity. We show that given any tree and any value k, the algorithm returns a k-resolving set for that tree. Moreover, we conjecture the difference in the k-truncated metric dimension of any tree and the size of the k-resolving set found by the algorithm for that tree is never greater than one. The time complexity of the algorithm is proven to be O(k3n), where k is the measuring range of the sensors and n is the number of vertices in the tree. This implies that the time complexity is linear in n for fixed k.

A graph G=(V,E) is a mathematical model for a network with vertex set V and edge set E. A Random Graph model is a probabilistic graph. A Random Geometric Graph is a Random Graph were each vertex has a location in a space χ. We compare the Erdos-Rényi random graph, G(n,p), to the Random Geometric Graph model, RGG(n,r) where, in general we use r=c / (n^(-1/d)), with dimension d. It is known that for p = λ*/n the k-core has a first-order phase transition in G(n,p) where λ* is the critical value for the k-core. The k-core is a global property of a graph. The k-core is the largest induced subgraph where each vertex has at least degree k. We suggest by simulations and a supportive proof that for the RGG-model a first-order phase transition not plausible. A inhomogeneous extension of the RGG-model with a vertex weight distribution T is a Geometric Inhomogeneous Random Graph model (GIRG). We also prove why some heavy-tailed (i.e. power-law) distributions almost surely have a k-core, when the amount of vertices v, which have weights greater than the square root of n, is greater than k. Furthermore, we rephrase from known literature how using a fixed equation for a branching process is a useful tool for analysing the existence of a k-core. In particular, the critical value for the 3-core is recovered using the probability of a binary tree embedding in branching processes, with the root having at least 3 children.

A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.

In this thesis, we consider the threshold metric dimension problem of graphs, related to and motivated by source detection. We construct a graph G = (V,E) for a given set of sensors of size m: {s1, s2, ..., sm} and a range k > 0. We want that each node v ∈ V has a unique combination of distances (dk (s1, v),dk (s2, v), ...,dk (sm, v)), where dk is the distance function in a graph limited by the range k (the distance is denoted as being ∞ if the distance is larger than k). Our aim in this thesis is to construct such a graph that is extremal in size, that is: the vertex set V is as large as possible. We shall give such constructions with proof for optimality up to k = 3 and general m and a different construction with incomplete proof for optimality for general k and m. For any construction we will prove that each vertex is uniquely identified. Furthermore, we will compare our results to another paper with a similar conclusion about the extremal size of graphs with metric dimension m and a given diameter D.

All organisms are built out of cellular tissue. Being able to recognise abnormalities in these tissues could be useful in recognizing cancerous cells. In this thesis we construct a mathematical model for cellular tissue based on its spatial structure. We consider cells as elements of the network. Touching cells are considered connected. Cells grow at different growth speeds. We determine the point in time when this network is fully connected, meaning there is a path between every pair of cells through touching cells. This point indicates the start of the last phase of the cellular growth, where friction restricts cell movement. We first use a Poisson point process to generate the locations of the cells. To make the model more similar to cellular tissue, we introduce determinantal point processes which have short-ranged repulsion, meaning points repel each other and thus spread. We compare the repulsion of Poisson and Determinantal point processes with real cellular tissue. We conclude that determinantal point processes have significantly higher repulsion than Poisson point processes. We also conclude that the repulsion in cellular tissue is higher than both point processes. Using simulations, we show that the model with determinantal point processes reaches connectivity significantly earlier than the Poisson model. We conclude that the analytically derived connectivity time point from the Poisson model can be used as an upper bound for the determinantal model.

Preferential Attachment models offer an explanation for why power laws are so common in real-world data. In these models, we start out with an initial network and add nodes one at a time. For each new node, we make m connections to existing nodes and if we define the attachment probability of attaching to a vertex to be proportional to its degree, we have defined the Barabási–Albert (BA) model. The tail of the degree distribution of the vertices of this model decays like a power law, offering an explanation for why power law behavior is common in real world data. The BA model can be adjusted by letting the probability of attaching to a vertex depend on its degree and an additional parameter for each vertex called fitness, that we randomly assign from a fitness distribution. If we adjust the attachment probability by multiplying with fitness, this model, the Bianconi–Barabási (BB) model, shows three qualitative behaviors. For flat distributions, the model behaves as the BA model, the old get richer; if fitness values differ, the exponent of the sublinear growth of the expected degree is larger if fitness is larger; if the tail of the fitness distribution is light enough, we find that a larger than expected proportion of half-edges connects to vertices with very high fitness values—condensation. In this thesis we compare qualitative behaviors of various preferential attachment models. Chiefly, we concern ourselves with models with vertex fitness. For these models, we study how the fitness distribution affects qualitative behaviors, such as condensation. First we review known results about the degree distributions of the graph. Degree distributions are an accessible and understandable property that is related to the topology of the network. We do this for the model without vertex fitness, for multiplicative fitness and for models with additive fitness and define the regimes of their qualitative behavior. For these results, we give clarification of the behavior and highlight the principles employed to derive their proofs. In doing so, we gather the commonalities of these proofs and provide intuition about their underlying principles by accenting the recurring themes.

We consider the game cops and robbers, which is a pursuit-evasion game played on a graph G. The cops and the robber take turns moving across the vertices of G, where the goal for the cops is to eventually catch the robber. Specifically, we study the cop number of G, i.e. the minimum number of cops that is needed to catch the robber on G. We investigate the relation between the cop number of the Erdős-Rényi (ER) random graph G(n, p_n) and compare it to another graph parameter, the domination number. Our goal is to collect results from previous research and create an overview. Throughout this thesis, we provide some examples of graphs for which the cop number is equal to the domination number. Furthermore, we provide proofs for some results on the domination number of the ER random graph. The main takeaway is that the cop number is asymptotic to the domination number for particular values of p_n.

In this thesis, we examine the kernel-based spatial random graph (KSRG) model, which is a generalisation of many known models such as long-range percolation, scale-free percolation, the Poisson Boolean model and age-based spatial preferential attachment. We construct a KSRG from a vertex set V = Z^d, assigning each vertex v ∈ V a weight Wv according to a power-law with parameter τ − 1 and connecting each pair of vertices conditionally independently according to P(u ↔ v|Wu,Wv) = Θ(1 ∧(max {Wu,Wv}^(σ1) min {Wu,Wv}^(σ2)/|u − v|^d))^α. Our first contribution is to show that, under certain choices of the parameters σ1, σ2, τ and α, the graph distance is at most poly-logarithmic or at most doubly logarithmic when compared to the spatial distance. Furthermore, the parameters σ1 and σ2 allow for extra degrees of freedom when compared to the models mentioned earlier, which yields a new exponent for poly-logarithmic distances and a generalised constant for doubly logarithmic distances. Our second contribution lies in the techniques used to prove these results. In particular, we show that with probability tending to 1 there is a subset of vertices that behaves pseudo-randomly with regards to the expected amount of vertices with a given weight in any radius. The presence of this subset, which we call a net, allows for the avoidance of the use of FKG-like inequalities in proofs. Primarily, it allows us to reveal all relevant weights in advance, which allows us to disregard many correlations that we would otherwise need to take into account during construction of paths.