Distribution of diameters for Erdős-Rényi random graphs

We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distributi...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E 2018-03, Vol.97 (3-1), p.032128-032128, Article 032128
Main Authors: Hartmann, A K, Mézard, M
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3
cites cdi_FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3
container_end_page 032128
container_issue 3-1
container_start_page 032128
container_title Physical review. E
container_volume 97
creator Hartmann, A K
Mézard, M
description We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10^{-100} which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.
doi_str_mv 10.1103/PhysRevE.97.032128
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_2041640603</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2041640603</sourcerecordid><originalsourceid>FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3</originalsourceid><addsrcrecordid>eNo9kEtKA0EYhBtRjMRcwIXM0s3Ev58zvZQYHxBQgq6bnn6YlsxM7J4RcgyP4TnEexnJY1W1qCqoD6ELDGOMgV4_L9Zp7j6nY1mMgRJMyiN0RlgBOQCnxwfP-ACNUnoHACxAFpicogGRRSGAwRmStyF1MVR9F9oma31mg65d52LKfBuzabS_Xymf_3w365BF3di2zt6iXi3SOTrxepncaKdD9Ho3fZk85LOn-8fJzSw3lJMu15jzQpaGUkmd0NyCx5UrqTDOC1eWlQfOWCWs3FxgmlQGDMNaCMa4xtbRIbra7q5i-9G71Kk6JOOWS924tk-KAMOCgQC6iZJt1MQ2pei8WsVQ67hWGNQ_NbWnpmShttQ2pcvdfl_Vzh4qe0b0D4FtahU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2041640603</pqid></control><display><type>article</type><title>Distribution of diameters for Erdős-Rényi random graphs</title><source>American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)</source><creator>Hartmann, A K ; Mézard, M</creator><creatorcontrib>Hartmann, A K ; Mézard, M</creatorcontrib><description>We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10^{-100} which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c&lt;1, our results are in good agreement with analytical results, proving the reliability of our numerical approach. For c&gt;1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.</description><identifier>ISSN: 2470-0045</identifier><identifier>EISSN: 2470-0053</identifier><identifier>DOI: 10.1103/PhysRevE.97.032128</identifier><identifier>PMID: 29776040</identifier><language>eng</language><publisher>United States</publisher><ispartof>Physical review. E, 2018-03, Vol.97 (3-1), p.032128-032128, Article 032128</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3</citedby><cites>FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/29776040$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Hartmann, A K</creatorcontrib><creatorcontrib>Mézard, M</creatorcontrib><title>Distribution of diameters for Erdős-Rényi random graphs</title><title>Physical review. E</title><addtitle>Phys Rev E</addtitle><description>We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10^{-100} which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c&lt;1, our results are in good agreement with analytical results, proving the reliability of our numerical approach. For c&gt;1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.</description><issn>2470-0045</issn><issn>2470-0053</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNo9kEtKA0EYhBtRjMRcwIXM0s3Ev58zvZQYHxBQgq6bnn6YlsxM7J4RcgyP4TnEexnJY1W1qCqoD6ELDGOMgV4_L9Zp7j6nY1mMgRJMyiN0RlgBOQCnxwfP-ACNUnoHACxAFpicogGRRSGAwRmStyF1MVR9F9oma31mg65d52LKfBuzabS_Xymf_3w365BF3di2zt6iXi3SOTrxepncaKdD9Ho3fZk85LOn-8fJzSw3lJMu15jzQpaGUkmd0NyCx5UrqTDOC1eWlQfOWCWs3FxgmlQGDMNaCMa4xtbRIbra7q5i-9G71Kk6JOOWS924tk-KAMOCgQC6iZJt1MQ2pei8WsVQ67hWGNQ_NbWnpmShttQ2pcvdfl_Vzh4qe0b0D4FtahU</recordid><startdate>201803</startdate><enddate>201803</enddate><creator>Hartmann, A K</creator><creator>Mézard, M</creator><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope></search><sort><creationdate>201803</creationdate><title>Distribution of diameters for Erdős-Rényi random graphs</title><author>Hartmann, A K ; Mézard, M</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hartmann, A K</creatorcontrib><creatorcontrib>Mézard, M</creatorcontrib><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><jtitle>Physical review. E</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hartmann, A K</au><au>Mézard, M</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Distribution of diameters for Erdős-Rényi random graphs</atitle><jtitle>Physical review. E</jtitle><addtitle>Phys Rev E</addtitle><date>2018-03</date><risdate>2018</risdate><volume>97</volume><issue>3-1</issue><spage>032128</spage><epage>032128</epage><pages>032128-032128</pages><artnum>032128</artnum><issn>2470-0045</issn><eissn>2470-0053</eissn><abstract>We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10^{-100} which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c&lt;1, our results are in good agreement with analytical results, proving the reliability of our numerical approach. For c&gt;1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.</abstract><cop>United States</cop><pmid>29776040</pmid><doi>10.1103/PhysRevE.97.032128</doi><tpages>1</tpages></addata></record>
fulltext fulltext
identifier ISSN: 2470-0045
ispartof Physical review. E, 2018-03, Vol.97 (3-1), p.032128-032128, Article 032128
issn 2470-0045
2470-0053
language eng
recordid cdi_proquest_miscellaneous_2041640603
source American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)
title Distribution of diameters for Erdős-Rényi random graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T21%3A05%3A08IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Distribution%20of%20diameters%20for%20Erd%C5%91s-R%C3%A9nyi%20random%20graphs&rft.jtitle=Physical%20review.%20E&rft.au=Hartmann,%20A%20K&rft.date=2018-03&rft.volume=97&rft.issue=3-1&rft.spage=032128&rft.epage=032128&rft.pages=032128-032128&rft.artnum=032128&rft.issn=2470-0045&rft.eissn=2470-0053&rft_id=info:doi/10.1103/PhysRevE.97.032128&rft_dat=%3Cproquest_cross%3E2041640603%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c352t-a155798c3393e6a5d0f1be836cef6e88bf0544b6d91284a2bc0c41a66445a1de3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2041640603&rft_id=info:pmid/29776040&rfr_iscdi=true