The clustering coefficient of a scale-free random graph

DOI10.1016/J.DAM.2011.02.003zbMATH Open1218.05175arXiv0804.3032OpenAlexW1990337750WikidataQ56828217 ScholiaQ56828217MaRDI QIDQ548267FDOQ548267

Authors: Nicole Eggemann, Steven D. Noble 

Publication date: 28 June 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider a random graph process in which, at each time step, a new vertex is added with m out-neighbours, chosen with probabilities proportional to their degree plus a strictly positive constant. We show that the expectation of the clustering coefficient of the graph process is asymptotically proportional to log n/n. Bollob'as and Riordan have previously shown that when the constant is zero, the same expectation is asymptotically proportional to ((log n)^2)/n.

Full work available at URL: https://arxiv.org/abs/0804.3032

Recommendations

• The degree sequence of a scale-free random graph process
• Global Clustering Coefficient in Scale-Free Networks
• Degree and clustering coefficient in sparse random intersection graphs
• A new class of scale free random graphs
• Clustering coefficient of a preferred attachment affiliation network

zbMATH Keywords

clustering coefficientscale-free graphBarabási-Albert graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Collective dynamics of ‘small-world’ networks
• The degree sequence of a scale-free random graph process
• The Maximum Degree of the Barabási–Albert Random Tree
• A general model of web graphs
• The diameter of a scale-free random graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Popularity based random graph models leading to a scale-free degree sequence
• On random trees

Cited In (17)

• Clustering in preferential attachment random graphs with edge-step
• Subgraphs in preferential attachment models
• Clustering and cliques in preferential attachment random graphs with edge insertion
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Towards a Systematic Evaluation of Generative Network Models
• Clustering Coefficients of Random Intersection Graphs
• DEGREE-BASED GINI INDEX FOR GRAPHS
• Clustering in random line graphs
• Clustering and the Hyperbolic Geometry of Complex Networks
• Global Clustering Coefficient in Scale-Free Networks
• Approximating Clustering Coefficient and Transitivity
• Statistical Clustering of a Random Network by Extremal Properties
• Computing the clustering coefficient of a random model of graphs
• New classes of clustering coefficient locally maximizing graphs
• General results on preferential attachment and clustering coefficient
• Small subgraphs in preferential attachment networks
• Large communities in a scale-free network

This page was built for publication: The clustering coefficient of a scale-free random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548267)