Large communities in a scale-free network

DOI10.1007/S10955-016-1676-8MaRDI QIDQ2396572zbMATH OpenOpenAlexFDO

Authors Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Publication date 8 June 2017

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

cliquecomplex networksconcentration boundspreferential attachment

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Other physical applications of random processes (60K40) Stochastic network models in operations research (90B15)

Abstract: We prove the existence of a large complete subgraph w.h.p. in a preferential attachment random graph process with an edge-step. That is, we prove that the random graph $G_t$ produced by the so-called GLP model at time $t$ contains a complete subgraph of order $t^{a}lpha$, where $alpha=(1-varepsilon)frac1-p2-p$, $varepsilon$ is any number such that $0<varepsilon<1$, and $0<p<1$ is a parameter of the model.

Recommendations

• Preferential attachment without vertex growth: emergence of the giant component
• Scale-free property for degrees and weights in a preferential attachment random graph model
• Clustering in preferential attachment random graphs with edge-step
• A Geometric Preferential Attachment Model of Networks
• Random networks with sublinear preferential attachment: the giant component

Cites work

• Community structure in social and biological networks
• Complex graphs and networks
• Diameters in preferential attachment models
• Emergence of Scaling in Random Networks
• Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient
• Global Clustering Coefficient in Scale-Free Networks
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• scientific article; zbMATH DE number 1875439 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Large cliques in a power-law random graph
• Number of cliques in random scale-free network ensembles
• Random graphs and complex networks. Volume 1
• Robustness and Vulnerability of Scale-Free Random Graphs
• The clustering coefficient of a scale-free random graph
• The Maximum Degree of the Barabási–Albert Random Tree
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Structure and Function of Complex Networks

Cited in

(8)

• Based on agent model and \(K\)-core decomposition to analyze the diffusion of mass incident in microblog
• On the independence number and the chromatic number of generalized preferential attachment models
• Preferential attachment random graphs with edge-step functions
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Clustering in preferential attachment random graphs with edge-step
• Spread of infection over P.A. random graphs with edge insertion
• On the growth of large independent sets in scale-free networks
• Clustering and cliques in preferential attachment random graphs with edge insertion

This page was built for publication: Large communities in a scale-free network

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