Groupies in multitype random graphs

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random b...

Descripción completa

Detalles Bibliográficos
Autor principal: Shang, Yilun
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer International Publishing 2016
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4937013/
https://www.ncbi.nlm.nih.gov/pubmed/27441125
http://dx.doi.org/10.1186/s40064-016-2705-4
_version_ 1782441632263569408
author Shang, Yilun
author_facet Shang, Yilun
author_sort Shang, Yilun
collection PubMed
description A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.
format Online
Article
Text
id pubmed-4937013
institution National Center for Biotechnology Information
language English
publishDate 2016
publisher Springer International Publishing
record_format MEDLINE/PubMed
spelling pubmed-49370132016-07-20 Groupies in multitype random graphs Shang, Yilun Springerplus Research A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results. Springer International Publishing 2016-07-07 /pmc/articles/PMC4937013/ /pubmed/27441125 http://dx.doi.org/10.1186/s40064-016-2705-4 Text en © The Author(s) 2016 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Research
Shang, Yilun
Groupies in multitype random graphs
title Groupies in multitype random graphs
title_full Groupies in multitype random graphs
title_fullStr Groupies in multitype random graphs
title_full_unstemmed Groupies in multitype random graphs
title_short Groupies in multitype random graphs
title_sort groupies in multitype random graphs
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4937013/
https://www.ncbi.nlm.nih.gov/pubmed/27441125
http://dx.doi.org/10.1186/s40064-016-2705-4
work_keys_str_mv AT shangyilun groupiesinmultityperandomgraphs

Ejemplares similares