A Random Graph Model for Clustering Graphs

被引：1

作者：

Chung, Fan ^{[1
]}

Sieger, Nicholas ^{[1
]}

机构：

[1] Univ Calif San Diego, La Jolla, CA 92037 USA

来源：

ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2023 | 2023年 / 13894卷

关键词：

Random graphs; clustering coefficient; scale-free networks; Chung-Lu model; NETWORKS;

D O I：

10.1007/978-3-031-32296-9_8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce a random graph model for clustering graphs with a given degree sequence. Unlike previous random graph models, we incorporate clustering effects into the model without any geometric conditions. We show that random clustering graphs can yield graphs with a power-law expected degree sequence, small diameter, and any desired clustering coefficient. Our results follow from a general theorem on subgraph counts which may be of independent interest.

引用

页码：112 / 126

页数：15

共 17 条

[1] Aiello W, 2002, MASSIVE COMP, V4, P97
[2] A Spatial Web Graph Model with Local Influence Regions
Aiello, W.
Bonato, A.
Cooper, C.
Janssen, J.
Pralat, P.
[J]. INTERNET MATHEMATICS, 2008, 5 (1-2) : 175 - 196
[3] A random graph model for power law graphs
Aiello, W
Chung, F
Lu, LY
[J]. EXPERIMENTAL MATHEMATICS, 2001, 10 (01) : 53 - 66
[4] Alon N., 2016, PROBABILISTIC METHOD, V4th
[5] Scale-free characteristics of random networks:: the topology of the World-Wide Web
Barabási, AL
Albert, R
Jeong, H
[J]. PHYSICA A, 2000, 281 (1-4): : 69 - 77
[6] Emergence of scaling in random networks
Barabási, AL
Albert, R
[J]. SCIENCE, 1999, 286 (5439) : 509 - 512
[7] The Structure of Geographical Threshold Graphs
Bradonjic, Milan
Hagberg, Aric
Percus, Allon G.
[J]. INTERNET MATHEMATICS, 2008, 5 (1-2) : 113 - 139
[8] Geometric inhomogeneous random graphs
Bringmann, Karl
Keusch, Ralph
Lengler, Johannes
[J]. THEORETICAL COMPUTER SCIENCE, 2019, 760 : 35 - 54
[9] Spectra of random graphs with given expected degrees
Chung, F
Lu, LY
Vu, V
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2003, 100 (11) : 6313 - 6318
[10] Chung F., 2003, INTERNET MATH, V1, P91, DOI 10.1080/15427951.2004.10129081

← 1 2 →