Hopping in the Crowd to Unveil Network Topology

Malbor Asllani; Timoteo Carletti; Francesca  Di Patti; Duccio Fanelli; Francesco Piazza

doi:10.1103/PhysRevLett.120.158301

Hopping in the Crowd to Unveil Network Topology

Malbor Asllani, Timoteo Carletti, Francesca Di Patti, Duccio Fanelli, Francesco Piazza

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

50 Downloads (Pure)

Abstract

We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excluded-volume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.

Original language	English
Article number	158301
Number of pages	5
Journal	Physical review letters
Volume	120
Issue number	15
DOIs	https://doi.org/10.1103/PhysRevLett.120.158301
Publication status	Published - 9 Apr 2018

Funding

We thank Renaud Lambiotte for insightful comments. The work of M. A. is supported by a FRS-FNRS Postdoctoral Fellowship. The work of T. C. presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with its author(s). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No 642563.

Funders	Funder number
Horizon 2020 Framework Programme	642563
Belgian Federal Science Policy Office

Keywords

random walk
complex network
crowding
network reconstruction
non linear diffusion

Access to Document

10.1103/PhysRevLett.120.158301

PRL_120_2018pp158301Final published version, 349 KB

https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.120.158301

Cite this

@article{f405701cad5d468d9b3a1bf3c57f8b3a,

title = "Hopping in the Crowd to Unveil Network Topology",

abstract = "We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes{\textquoteright} degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excluded-volume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.",

keywords = "random walk, complex network, crowding, network reconstruction, non linear diffusion",

author = "Malbor Asllani and Timoteo Carletti and {Di Patti}, Francesca and Duccio Fanelli and Francesco Piazza",

note = "Funding Information: We thank Renaud Lambiotte for insightful comments. The work of M. A. is supported by a FRS-FNRS Postdoctoral Fellowship. The work of T. C. presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with its author(s). This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No 642563. Publisher Copyright: {\textcopyright} 2018 American Physical Society.",

year = "2018",

month = apr,

day = "9",

doi = "10.1103/PhysRevLett.120.158301",

language = "English",

volume = "120",

journal = "Physical review letters",

issn = "0031-9007",

publisher = "American Physical Society",

number = "15",

}

TY - JOUR

T1 - Hopping in the Crowd to Unveil Network Topology

AU - Asllani, Malbor

AU - Carletti, Timoteo

AU - Di Patti, Francesca

AU - Fanelli, Duccio

AU - Piazza, Francesco

N1 - Funding Information: We thank Renaud Lambiotte for insightful comments. The work of M. A. is supported by a FRS-FNRS Postdoctoral Fellowship. The work of T. C. presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with its author(s). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No 642563. Publisher Copyright: © 2018 American Physical Society.

PY - 2018/4/9

Y1 - 2018/4/9

N2 - We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excluded-volume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.

AB - We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excluded-volume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.

KW - random walk

KW - complex network

KW - crowding

KW - network reconstruction

KW - non linear diffusion

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

U2 - 10.1103/PhysRevLett.120.158301

DO - 10.1103/PhysRevLett.120.158301

M3 - Letter

SN - 0031-9007

VL - 120

JO - Physical review letters

JF - Physical review letters

IS - 15

M1 - 158301

ER -

Hopping in the Crowd to Unveil Network Topology

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Self-segregation in heterogeneous metapopulation landscapes

Competitive and diffusive processes in complex networks and time-delayed systems

PAI n°P7/19 - DYSCO: Dynamical systems, control and optimization (DYSCO)