Maximal dispersion of adaptive random walks

Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real cas...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-01
Main Authors: Gabriele Di Bona, Leonardo Di Gaetano, Latora, Vito, Coghi, Francesco
Format: Article
Language:English
Subjects:
Dispersion
Maximum entropy
Random walk
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Gabriele Di Bona
Leonardo Di Gaetano
Latora, Vito
Coghi, Francesco
description Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real case scenarios. Here, we propose an adaptive random walk (ARW), which instead maximizes dispersion by updating its transition rule on the local information collected while exploring the network. We show how to derive ARW via a large-deviation representation of MERW and study its dynamics on synthetic and real world networks.
doi_str_mv 10.48550/arxiv.2202.13923
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2634671836</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2634671836</sourcerecordid><originalsourceid>FETCH-LOGICAL-a953-50fc8282ed648bc1cf1888b8bf4e455ed5ff5753176caec5375dc897ea747b4c3</originalsourceid><addsrcrecordid>eNotzctKw0AUgOFBECy1D-Au0KUkzpwzZ-ZkKcVLoeKm-zKZC6RNk5hpax9fQVf_7vuFeFCy0kwkn9x0bS8VgIRKYQ14I2aAqErWAHdikfNeSgnGAhHOxOOHu7ZH1xWhzWOccjv0xZAKF9x4ai-xmFwfhmPx7bpDvhe3yXU5Lv47F9vXl-3qvdx8vq1Xz5vS1YQlyeQZGGIwmhuvfFLM3HCTdNREMVBKZAmVNd5FT2gpeK5tdFbbRnuci-UfO07D1znm024_nKf-97gDg9pYxWjwB63bQ3s</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2634671836</pqid></control><display><type>article</type><title>Maximal dispersion of adaptive random walks</title><source>Publicly Available Content (ProQuest)</source><creator>Gabriele Di Bona ; Leonardo Di Gaetano ; Latora, Vito ; Coghi, Francesco</creator><creatorcontrib>Gabriele Di Bona ; Leonardo Di Gaetano ; Latora, Vito ; Coghi, Francesco</creatorcontrib><description>Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real case scenarios. Here, we propose an adaptive random walk (ARW), which instead maximizes dispersion by updating its transition rule on the local information collected while exploring the network. We show how to derive ARW via a large-deviation representation of MERW and study its dynamics on synthetic and real world networks.</description><identifier>EISSN: 2331-8422</identifier><identifier>DOI: 10.48550/arxiv.2202.13923</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Dispersion ; Maximum entropy ; Random walk</subject><ispartof>arXiv.org, 2023-01</ispartof><rights>2023. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2634671836?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,27925,37012,44590</link.rule.ids></links><search><creatorcontrib>Gabriele Di Bona</creatorcontrib><creatorcontrib>Leonardo Di Gaetano</creatorcontrib><creatorcontrib>Latora, Vito</creatorcontrib><creatorcontrib>Coghi, Francesco</creatorcontrib><title>Maximal dispersion of adaptive random walks</title><title>arXiv.org</title><description>Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real case scenarios. Here, we propose an adaptive random walk (ARW), which instead maximizes dispersion by updating its transition rule on the local information collected while exploring the network. We show how to derive ARW via a large-deviation representation of MERW and study its dynamics on synthetic and real world networks.</description><subject>Dispersion</subject><subject>Maximum entropy</subject><subject>Random walk</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNotzctKw0AUgOFBECy1D-Au0KUkzpwzZ-ZkKcVLoeKm-zKZC6RNk5hpax9fQVf_7vuFeFCy0kwkn9x0bS8VgIRKYQ14I2aAqErWAHdikfNeSgnGAhHOxOOHu7ZH1xWhzWOccjv0xZAKF9x4ai-xmFwfhmPx7bpDvhe3yXU5Lv47F9vXl-3qvdx8vq1Xz5vS1YQlyeQZGGIwmhuvfFLM3HCTdNREMVBKZAmVNd5FT2gpeK5tdFbbRnuci-UfO07D1znm024_nKf-97gDg9pYxWjwB63bQ3s</recordid><startdate>20230121</startdate><enddate>20230121</enddate><creator>Gabriele Di Bona</creator><creator>Leonardo Di Gaetano</creator><creator>Latora, Vito</creator><creator>Coghi, Francesco</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20230121</creationdate><title>Maximal dispersion of adaptive random walks</title><author>Gabriele Di Bona ; Leonardo Di Gaetano ; Latora, Vito ; Coghi, Francesco</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a953-50fc8282ed648bc1cf1888b8bf4e455ed5ff5753176caec5375dc897ea747b4c3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Dispersion</topic><topic>Maximum entropy</topic><topic>Random walk</topic><toplevel>online_resources</toplevel><creatorcontrib>Gabriele Di Bona</creatorcontrib><creatorcontrib>Leonardo Di Gaetano</creatorcontrib><creatorcontrib>Latora, Vito</creatorcontrib><creatorcontrib>Coghi, Francesco</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content (ProQuest)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><jtitle>arXiv.org</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gabriele Di Bona</au><au>Leonardo Di Gaetano</au><au>Latora, Vito</au><au>Coghi, Francesco</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Maximal dispersion of adaptive random walks</atitle><jtitle>arXiv.org</jtitle><date>2023-01-21</date><risdate>2023</risdate><eissn>2331-8422</eissn><abstract>Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real case scenarios. Here, we propose an adaptive random walk (ARW), which instead maximizes dispersion by updating its transition rule on the local information collected while exploring the network. We show how to derive ARW via a large-deviation representation of MERW and study its dynamics on synthetic and real world networks.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><doi>10.48550/arxiv.2202.13923</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2023-01
issn 2331-8422
language eng
recordid cdi_proquest_journals_2634671836
source Publicly Available Content (ProQuest)
subjects Dispersion
Maximum entropy
Random walk
title Maximal dispersion of adaptive random walks
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T00%3A39%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Maximal%20dispersion%20of%20adaptive%20random%20walks&rft.jtitle=arXiv.org&rft.au=Gabriele%20Di%20Bona&rft.date=2023-01-21&rft.eissn=2331-8422&rft_id=info:doi/10.48550/arxiv.2202.13923&rft_dat=%3Cproquest%3E2634671836%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a953-50fc8282ed648bc1cf1888b8bf4e455ed5ff5753176caec5375dc897ea747b4c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2634671836&rft_id=info:pmid/&rfr_iscdi=true