Connectivity of passive random intersection graphs and their intersection with Erdos-Renyi graphs
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2022-06-14
Department
Major/Subject
Applied Mathematics
Mcode
SCI3053
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
60+0
Series
Abstract
This thesis studies the connectivity of passive random intersection graphs. In addition to this, it studies the connectivity of an intersection between a passive random intersection graph and an Erdős–Rényi graph. Random intersection graphs can be used to model many real-life phenomena. For example, social networks and communication in sensor networks can be modelled by random intersection graphs. A random intersection graph is a random graph, where nodes are assigned attributes according to some random process. Two nodes are connected by an edge if they have at least one attribute in common. For a passive random intersection graph, each attribute is given a number according to some probability distribution. Each attribute then chooses that number of nodes, uniformly at random from the whole set of nodes. The chosen nodes are given the respective attribute. Two nodes are thus connected, if at least one attribute chooses them both. This thesis presents zero-one laws on passive random intersection graphs being connected and not having isolated nodes. This thesis also presents zero-one laws on the intersection between a passive random intersection graph and an Erdős–Rényi graph being connected and not having isolated nodes.Denna avhandling undersöker när en passiv slumpsnittgraf är sammanhängande. Avhandlingen undersöker dessutom, när snittet av en passiv slumpsnittgraf och en Erdős–Rényi graf är sammanhängande. Slumpsnittgrafer kan användas för att modellera flera riktiga fenomen. Till exempel kan sociala nätverk och kommunikation i ett sensornätverk modelleras med slumpsnittgrafer. En slumpsnittgraf är en slumpgraf, där noder blir givna egenskaper enligt någon slumpprocess. Två noder har en båge mellan sig om de har minst en gemensam egenskap. I en passiv slumpsnittgraf blir varje egenskap given ett eget nummer, detta nummer följer någon sannolikhetsfördelning. Efter detta väljer varje egenskap, numrets antal noder jämnt slumpmässigt från hela mängden noder. De valda noderna blir givna motsvarande egenskap. Två noder har alltså en båge mellan sig om åtminstone en egenskap väljer dem båda. I denna avhandling presenteras en lag för när stora passiva slumpsnittgrafer är sammanhängande och inte har isolerade noder. Dessutom presenteras en lag för när snittet mellan stora passiva slumpsnittgrafer och Erdős–Rényi grafer är sammanhängande och inte har isolerade noder.Description
Supervisor
Leskelä, LasseThesis advisor
Leskelä, LasseKeywords
random intersection graph, passive random intersection graph, connectivity, isolated nodes, random graph, Erdős–Rényi graph