Source-linked AI summary
Random intersection graphs with tunable degree distribution and clustering
Maria Deijfen, Willemien Kets
TL;DR
Real networks can combine heavy-tailed degree distributions with substantial clustering, while standard models may not capture both. This paper introduces a weighted random intersection graph and characterizes its degree and clustering. In the α = 1 regime, power-law weights yield power-law degrees, and model parameters allow the clustering and expected degree to be tuned.
Problem
The paper seeks a model that captures heavy-tailed degrees and substantial clustering, since existing degree-distribution models typically have zero limiting clustering.
Source: §1 · p. 2Method
The model assigns random weights to vertices, makes group membership depend on those weights, and connects vertices that share a group.
Source: §1 · p. 2, §1.1 · p. 4Results
For α = 1, clustering is E[(1 + βγW_k)^−1], and power-law weights yield power-law degrees with tunable expected degree and clustering.
Source: §1.2 · p. 6Takeaways & Limitations
Choosing α = 1 and a power-law weight distribution lets the model produce a power-law degree distribution with prescribed exponent and mean while tuning clustering.
Source: §1.2 · p. 6Extending epidemic-process analysis on random intersection graphs to include vertex weights and their tunable degree distributions remains future work.
Source: §5 · p. 12
Abstract
from arXiv · showhide
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 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 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 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.
1 Introduction
The paper develops a weighted random intersection graph to model networks with both heavy-tailed degrees and substantial clustering. It characterizes the degree and clustering behavior, finding that the α = 1 regime permits these features to be tuned together.
1 Introduction
- The model targets real-network features that standard graph models miss: heavy-tailed degrees and substantial clustering.The paper notes that Erdős–Rényi degrees are asymptotically Poisson, while models designed for a given degree distribution typically have zero limiting clustering.Source: §1 · p. 2
1.1 Description of the model
- Vertices receive random weights that influence their likelihood of joining groups, and two vertices are connected when they share a group.The paper motivates weights as a way to represent differences in individual social activity and to characterize degree and clustering explicitly.Source: §1.1 · pp. 3–4
1.2 Results
- For α = 1, the degree is asymptotically compound Poisson with the vertex weight as a parameter, and the clustering is c(G) = E[(1 + βγW_k)^−1].For α < 1, the degree converges to zero; for α > 1, it converges to a Poisson distribution.Source: §1.2 · pp. 5–6
- With power-law weights, α = 1 permits a power-law degree distribution with prescribed exponent and mean while tuning clustering through β and γ.For finite-mean weights, the asymptotic mean degree conditional on W_i is βγ²W_i.Source: §1.2 · pp. 4, 6
2 The degree distribution
The degree distribution is analyzed across three regimes of α. For α < 1, a vertex’s degree converges to zero; the proof identifies compound Poisson and Poisson limits for the other regimes.
2 The degree distribution
- For α < 1, the degree converges to zero because the probability that a vertex belongs to no group tends to 1.The proof notes that a vertex outside every group has degree zero.Source: §2 · p. 7
- For cases (b) and (c), the proof reduces the degree limit to that of a truncated degree, since the contribution from larger-weight neighbors vanishes in probability.The argument uses a truncation at n^(1/4).Source: §2 · p. 7
- The proof identifies compound Poisson and Poisson limits for the degree distribution in cases (b) and (c), respectively.For case (c), the generating function converges to e^(βγ²W1(t−1)).Source: §2 · p. 8
3 Clustering
The clustering analysis treats α < 1, α = 1, and α > 1 separately. At α = 1, the conditional clustering limit is (1 + βγWk)^−1; the proof also establishes the stated limiting behavior in the other regimes.
3 Clustering
- The proof estimates configurations where pairs share distinct groups and treats multiple shared groups as negligible in comparison.It also bounds cases involving a group shared by all three vertices together with another shared group.Source: §3 · pp. 9–10
- For α < 1, Markov’s inequality and independence of Wi, Wj, and Wk, each with finite mean, imply the quotient in (5) converges to 1 in probability.Source: §3 · p. 10
- For α = 1, applying Lemma 3.1 gives an upper bound, while the quantity indexed by i,j,k converges in probability to (1 + βγWk)^−1.Source: §3 · p. 10
- For α > 1, the bound used for the clustering quantity converges in probability to 0.The proof uses that WiWjWk n^−1 converges to zero in probability.Source: §3 · p. 10
4 Clustering for a power law weight distribution
For Pareto weights, the section develops expressions for asymptotic clustering and shows how model parameters can tune clustering while preserving a fixed mean degree. It also gives further forms for the clustering calculation under specified parameter conditions.
4 Clustering for a power law weight distribution
- When α = 1, clustering is E[(1+βγWk)−1]; this section evaluates it for Pareto weights.For λ > 2, the Pareto distribution has mean 1, and the asymptotic clustering is given by an integral.Source: §4 · p. 11
- For βγ ≥ (λ−1)/(λ−2), the integrand admits a series expansion, and the section also gives a separate expression for integer λ.The surrounding text identifies the hypergeometric function and Lerch transcendent in these expressions, but does not state their full forms.Source: §4 · p. 11
- For any c in (0, 1) and fixed tail exponent λ, βγ can be chosen to attain clustering c; fixing mean degree adds a condition on βγ² to specify β and γ.Figure 1(a) and (b) show clustering’s dependence on λ and βγ.Source: §4 · p. 11
5 Future work
The paper identifies degree correlations, vertex distances, and weighted epidemic dynamics as questions for further study. It connects these questions to shared-group structure and to prior epidemic work on unweighted random intersection graphs.
5 Future work
- Shared groups should induce positive degree correlation, consistent with observations from social networks; quantifying degree correlations is a next step.The paper also notes the broader possibility of positive or negative correlations between neighboring degrees.Source: §5 · pp. 11–12
- The relation between vertex distances, degree distribution, and clustering remains an open question for this model.The paper frames this alongside the small-world property, where distances remain small in very large networks.Source: §5 · p. 12
- Extending prior epidemic analysis on unweighted random intersection graphs to include vertex weights could test their impact on epidemic spread and degree-tail tuning.The cited prior work studies how clustering affects epidemic spread.Source: §5 · p. 12