Random Intersection Graphs with Tunable Degree Distribution and Clustering

M. Deijfen, W. Kets

Research output: Working paper › Discussion paper › Other research output

244 Downloads (Pure)

Abstract

A random intersection graph is constructed by independently assigning 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 paper 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 determined 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 so 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
Place of PublicationTilburg
PublisherMicroeconomics
Number of pages14
Volume2007-008
Publication statusPublished - 2007

Publication series

NameCentER Discussion Paper
Volume2007-008

Fingerprint

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

Keywords

  • Random intersection graphs
  • degree distribution
  • power law distri- bution
  • clustering
  • social networks

Cite this

Deijfen, M., & Kets, W. (2007). Random Intersection Graphs with Tunable Degree Distribution and Clustering. (CentER Discussion Paper; Vol. 2007-008). Tilburg: Microeconomics.
Deijfen, M. ; Kets, W. / Random Intersection Graphs with Tunable Degree Distribution and Clustering. Tilburg : Microeconomics, 2007. (CentER Discussion Paper).
@techreport{eddee3bd58454b188734b7a2dfc872ba,
title = "Random Intersection Graphs with Tunable Degree Distribution and Clustering",
abstract = "A random intersection graph is constructed by independently assigning 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 paper 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 determined 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 so 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.",
keywords = "Random intersection graphs, degree distribution, power law distri- bution, clustering, social networks",
author = "M. Deijfen and W. Kets",
note = "Subsequently published in Probability on the Engineering and Information Sciences, 2009 Pagination: 14",
year = "2007",
language = "English",
volume = "2007-008",
series = "CentER Discussion Paper",
publisher = "Microeconomics",
type = "WorkingPaper",
institution = "Microeconomics",

}

Deijfen, M & Kets, W 2007 'Random Intersection Graphs with Tunable Degree Distribution and Clustering' CentER Discussion Paper, vol. 2007-008, Microeconomics, Tilburg.

Random Intersection Graphs with Tunable Degree Distribution and Clustering. / Deijfen, M.; Kets, W.

Tilburg : Microeconomics, 2007. (CentER Discussion Paper; Vol. 2007-008).

Research output: Working paper › Discussion paper › Other research output

TY - UNPB

T1 - Random Intersection Graphs with Tunable Degree Distribution and Clustering

AU - Deijfen, M.

AU - Kets, W.

N1 - Subsequently published in Probability on the Engineering and Information Sciences, 2009 Pagination: 14

PY - 2007

Y1 - 2007

N2 - A random intersection graph is constructed by independently assigning 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 paper 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 determined 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 so 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 independently assigning 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 paper 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 determined 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 so 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.

KW - Random intersection graphs

KW - degree distribution

KW - power law distri- bution

KW - clustering

KW - social networks

M3 - Discussion paper

VL - 2007-008

T3 - CentER Discussion Paper

BT - Random Intersection Graphs with Tunable Degree Distribution and Clustering

PB - Microeconomics

CY - Tilburg

ER -

Deijfen M, Kets W. Random Intersection Graphs with Tunable Degree Distribution and Clustering. Tilburg: Microeconomics. 2007. (CentER Discussion Paper).

Access to Document