TY - JOUR
T1 - Clustering and Cliques in Preferential Attachment Random Graphs with Edge Insertion
AU - Alves, Caio
AU - Ribeiro, Rodrigo
AU - Sanchis, Rémy
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.
PY - 2024/6
Y1 - 2024/6
N2 - In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1-f(t). We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation -γ, where γ∈[0,1). We also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.
AB - In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1-f(t). We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation -γ, where γ∈[0,1). We also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.
KW - Cliques
KW - Complex networks
KW - Concentration bounds
KW - Diameter
KW - Preferential attachment
KW - Primary 05C82
KW - Scale-free
KW - Secondary 60K40, 68R10
KW - Small-world
UR - http://www.scopus.com/inward/record.url?scp=85196199335&partnerID=8YFLogxK
U2 - 10.1007/s10955-024-03279-8
DO - 10.1007/s10955-024-03279-8
M3 - Article
AN - SCOPUS:85196199335
SN - 0022-4715
VL - 191
JO - Journal of Statistical Physics
JF - Journal of Statistical Physics
IS - 6
M1 - 73
ER -