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].
Bloznelis, Mindaugas ;
Godehardt, Erhard ;
Jaworski, Jerzy ;
Kurauskas, Valentas ;
Rybarczyk, Katarzyna .
DATA SCIENCE, LEARNING BY LATENT STRUCTURES, AND KNOWLEDGE DISCOVERY, 2015, :79-88
[4]   EPIDEMICS ON RANDOM GRAPHS WITH TUNABLE CLUSTERING [J].
Britton, Tom ;
Deijfen, Maria ;
Lageras, Andreas N. ;
Lindholm, Mathias .
JOURNAL OF APPLIED PROBABILITY, 2008, 45 (03) :743-756
[5]   RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING [J].
Deijfen, Maria ;
Kets, Willemien .
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 2009, 23 (04) :661-674
[6]  
Eschenauer L, 2002, P 9 ACM C COMP COMM, DOI DOI 10.1145/586110.586117
[7]  
Frieze A., 2016, Introduction to Random Graphs, DOI DOI 10.1017/CBO9781316339831
[8]   UPPER-BOUNDS ON POISSON TAIL PROBABILITIES [J].
GLYNN, PW .
OPERATIONS RESEARCH LETTERS, 1987, 6 (01) :9-14
[9]  
Godehardt E, 2003, STUD CLASS DATA ANAL, P67