Random intersection graphs with tunable degree distribution and clustering

M. Deijfen, W. Kets

Research output: Contribution to journalArticleScientificpeer-review

Abstract

A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, and—in the power-law case—tail exponent.
Original languageEnglish
Pages (from-to)661-674
JournalProbability in the Engineering and Informational Sciences
Volume32
Issue number4
Publication statusPublished - 2009

Fingerprint

Intersection Graphs
Degree Distribution
Random Graphs
Clustering
Vertex of a graph
Subset
Power Law
Tuning
Weight Distribution
Graph in graph theory
Intersect
Likely
Exponent
If and only if
Graph
Arbitrary
Model
Power law

Cite this

@article{577861f867d5475fa68f27b893120df7,
title = "Random intersection graphs with tunable degree distribution and clustering",
abstract = "A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, and—in the power-law case—tail exponent.",
author = "M. Deijfen and W. Kets",
note = "Appeared earlier as CentER DP 2007-08",
year = "2009",
language = "English",
volume = "32",
pages = "661--674",
journal = "Probability in the Engineering and Informational Sciences",
issn = "0269-9648",
publisher = "Cambridge University Press",
number = "4",

}

Random intersection graphs with tunable degree distribution and clustering. / Deijfen, M.; Kets, W.

In: Probability in the Engineering and Informational Sciences, Vol. 32, No. 4, 2009, p. 661-674.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Random intersection graphs with tunable degree distribution and clustering

AU - Deijfen, M.

AU - Kets, W.

N1 - Appeared earlier as CentER DP 2007-08

PY - 2009

Y1 - 2009

N2 - A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, and—in the power-law case—tail exponent.

AB - A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, and—in the power-law case—tail exponent.

M3 - Article

VL - 32

SP - 661

EP - 674

JO - Probability in the Engineering and Informational Sciences

JF - Probability in the Engineering and Informational Sciences

SN - 0269-9648

IS - 4

ER -