A Note on the Conductance of the Binomial Random Intersection Graph

被引：1

作者：

Rybarczyk, Katarzyna ^{[1
]}

Bloznelis, Mindaugas ^{[2
]}

Jaworski, Jerzy ^{[1
]}

机构：

[1] Adam Mickiewicz Univ, Poznan, Poland

[2] Vilnius Univ, Vilnius, Lithuania

来源：

ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2020 | 2020年 / 12091卷

关键词：

Random intersection graph; Mixing time; Conductance;

D O I：

10.1007/978-3-030-48478-1_9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We establish the rapid mixing property of a binomial random intersection graph G (n, m, p) introduced in [11,17]. For this purpose we show that the conductance is bounded away from zero by a positive constant. We consider the range of parameters n, m, p where the edge density is just above the connectivity threshold (our graph is connected with high probability as n, m -> + infinity). We assume in addition that np = Theta(1).

引用

页码：124 / 134

页数：11

共 19 条

[1]

[Anonymous], 2001, Random Graphs

[2]

Bloznelis M, 2020, Arxiv, DOI arXiv:1910.09639

[3] Recent Progress in Complex Network Analysis: Properties of Random Intersection Graphs [J].