Print Email Facebook Twitter K-core in random graphs Title K-core in random graphs Author Wassenaar, Vincent (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Komjáthy, J. (mentor) Spandaw, J.G. (graduation committee) Degree granting institution Delft University of Technology Programme Applied Mathematics Date 2022-07-12 Abstract 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. Subject Random Graphsk-coreRandom Geometric GraphGeometric Inhomogeneous Random Graph To reference this document use: http://resolver.tudelft.nl/uuid:b195b6fa-7521-4c12-9fc6-a930b798bf8f Part of collection Student theses Document type bachelor thesis Rights © 2022 Vincent Wassenaar Files PDF K_cores_in_random_graphs_final.pdf 5.53 MB Close viewer /islandora/object/uuid:b195b6fa-7521-4c12-9fc6-a930b798bf8f/datastream/OBJ/view