A Note on the Vertex Degree Distribution of Random Intersection Graphs
- PDF / 142,392 Bytes
- 4 Pages / 594 x 792 pts Page_size
- 25 Downloads / 185 Views
Lithuanian Mathematical Journal
A note on the vertex degree distribution of random intersection graphs Mindaugas Bloznelis Institute of Computer Science, Faculty of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius 03225, Lithuania (e-mail: [email protected]) Received October 15, 2019; revised June 10, 2020
Abstract. We establish the asymptotic degree distribution of the typical vertex of inhomogeneous and passive random intersection graphs under minimal moment conditions. MSC: 05C80, 05C07, 05C82 Keywords: degree distribution, random graph, random intersection graph, power law
1 Introduction and results Random intersection graphs introduced by Karo´nski et al. [10] have attracted considerable attention in the recent literature. They provide mathematically tractable theoretical models of complex networks that capture important features of real networks: the power-law degree distribution, small typical distances between vertices, and a high statistical dependency of neighboring adjacency relations expressed in terms of nonvanishing clustering and assortativity coefficients; see [4, 6, 14] and references therein. Vertex degree distributions have been studied by several authors [1, 2, 3, 5, 8, 9, 12, 13, 15]. In this note, we give a simple proof of the asymptotic degree distribution in two random intersection graph (RIG) models, the inhomogenious RIG and passive RIG, under the optimal moment conditions.
1.1
Inhomogeneous random intersection graph, [13]
Let X1 , X2 , . . . and Y1 , Y2 , . . . be independent nonnegative random variables such that each Xi has the probability distribution P1 and each Yj has the probability distribution P2 . Given realized values X = {Xi }m i=1 and Y = {Yj }nj=1 , define the random bipartite graph HX,Y with bipartition V = {v1 , . . . , vn }, W = {w1 , . . . , wm }, where the edges {wi , vj } are inserted with probabilities pij = min{1, Xi Yj (nm)−1/2 } independently for each {i, j} ∈ [m] × [n]. The inhomogeneous random intersection graph G(P1 , P2 , n, m) defines c 2020 Springer Science+Business Media, LLC 0363-1672/20/6004-0001
1
2
M. Bloznelis
the adjacency relation on the vertex set V : vertices v , v ∈ V are declared adjacent whenever v and v have a common neighbor in HX,Y . Let d = d(v1 ) denote the degree of vertex v1 in G(P1 , P2 , n, m). The following result is shown in Theorem 1(ii) of [3]. Theorem A. Let β ∈ (0, +∞). Let m, n → ∞ so that m/n → β . Suppose that EX12 < ∞ and EY1 < ∞. Then d converges in distribution to the random variable d∗ =
Λ1
τj ,
(1.1)
j=1
where τ1 , τ2 , . . . are independent identically distributed random variables independent of the random variable Λ1 . They are distributed as follows. For r = 0, 1, 2, . . . , we have P(τ1 = r) =
r+1 P(Λ2 = r + 1) EΛ2
and P(Λi = r) = Ee−λi
λri , r!
i = 1, 2.
(1.2)
Here λ1 = Y1 β 1/2 EX1 and λ2 = X1 β −1/2 EY1 . It was conjectured in [3] that the second moment condition EX12 < ∞ can be relaxed to the first moment condition EX1 < ∞. We show that this is th
Data Loading...
