Large communities in a scale-free network

DOI10.1007/S10955-016-1676-8zbMATH Open1364.05068arXiv1509.04650OpenAlexW3098065953MaRDI QIDQ2396572FDOQ2396572

Rémy Sanchis, Rodrigo Ribeiro, Caio Alves

Publication date: 8 June 2017

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

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.

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

zbMATH Keywords

cliquecomplex networkspreferential attachmentconcentration bounds

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Maximum Degree of the Barabási–Albert Random Tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient
• Diameters in preferential attachment models
• Title not available (Why is that?)
• Large Cliques in a Power-Law Random Graph
• Number of cliques in random scale-free network ensembles
• Global Clustering Coefficient in Scale-Free Networks
• Robustness and Vulnerability of Scale-Free Random Graphs
• The clustering coefficient of a scale-free random graph

Cited In (7)

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

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)