Large Communities in a Scale-Free Network

Caio Alves; Rodrigo Ribeiro; Rémy Sanchis

doi:10.1007/s10955-016-1676-8

Large Communities in a Scale-Free Network

Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

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 consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability p∈ (0 , 1) , whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph G_t produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by t^α, where α=(1-ε)1-p2-p, for any small ε> 0 asymptotically almost surely.

Original language	English
Pages (from-to)	137-149
Number of pages	13
Journal	Journal of Statistical Physics
Volume	166
Issue number	1
DOIs	https://doi.org/10.1007/s10955-016-1676-8
State	Published - Jan 1 2017
Externally published	Yes

Funding

C.A. was supported by Funda\u00E7\u00E3o de Amparo \u00E0 Pesquisa do Estado de S\u00E3o Paulo (FAPESP), Grant No. 2013/24928-2. R.S. has been partially supported by Conselho Nacional de Desenvolvimento Cient\u00EDfico e Tecnol\u00F3gico (CNPq) and by FAPEMIG (Programa Pesquisador Mineiro), Grant No. PPM 00600/16. R.R. has been partially supported by Coordena\u00E7\u00E3o de Aperfei\u00E7oamento de Pessoal de N\u00EDvel Superior (CAPES).

Funders	Funder number
Programa Pesquisador Mineiro	PPM 00600/16
Fundação de Amparo à Pesquisa do Estado de São Paulo	2013/24928-2
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Conselho Nacional de Desenvolvimento Científico e Tecnológico
Fundação de Amparo à Pesquisa do Estado de Minas Gerais

Keywords

Clique
Complex networks
Concentration bounds
Preferential attachment

Access to Document

10.1007/s10955-016-1676-8

Cite this

@article{84bf20c2e5ae4110912a9979f1972948,

title = "Large Communities in a Scale-Free Network",

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 consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability p∈ (0 , 1) , whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph Gt produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by tα, where α=(1-ε)1-p2-p, for any small ε> 0 asymptotically almost surely.",

keywords = "Clique, Complex networks, Concentration bounds, Preferential attachment",

author = "Caio Alves and Rodrigo Ribeiro and R{\'e}my Sanchis",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/s10955-016-1676-8",

language = "English",

volume = "166",

pages = "137--149",

journal = "Journal of Statistical Physics",

issn = "0022-4715",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Large Communities in a Scale-Free Network

AU - Alves, Caio

AU - Ribeiro, Rodrigo

AU - Sanchis, Rémy

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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 consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability p∈ (0 , 1) , whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph Gt produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by tα, where α=(1-ε)1-p2-p, for any small ε> 0 asymptotically almost surely.

AB - 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 consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability p∈ (0 , 1) , whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph Gt produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by tα, where α=(1-ε)1-p2-p, for any small ε> 0 asymptotically almost surely.

KW - Clique

KW - Complex networks

KW - Concentration bounds

KW - Preferential attachment

UR - http://www.scopus.com/inward/record.url?scp=84997079590&partnerID=8YFLogxK

U2 - 10.1007/s10955-016-1676-8

DO - 10.1007/s10955-016-1676-8

M3 - Article

AN - SCOPUS:84997079590

SN - 0022-4715

VL - 166

SP - 137

EP - 149

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

IS - 1

ER -

Large Communities in a Scale-Free Network

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this