Random intersection graphs with tunable degree distribution and clustering

Maria Deijfen*, Willemien Kets

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

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, andin the power-law casetail exponent.

Original languageEnglish (US)
Pages (from-to)661-674
Number of pages14
JournalProbability in the Engineering and Informational Sciences
Volume23
Issue number4
DOIs
StatePublished - Oct 2009

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'Random intersection graphs with tunable degree distribution and clustering'. Together they form a unique fingerprint.

Cite this