Learning network structures from contagion

DOI10.1016/J.IPL.2017.01.005zbMATH Open1404.68089arXiv1705.10051OpenAlexW2578994151MaRDI QIDQ509882FDOQ509882

Jittat Fakcharoenphol, Adisak Supeesun

Publication date: 21 February 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: In 2014, Amin, Heidari, and Kearns proved that tree networks can be learned by observing only the infected set of vertices of the contagion process under the independent cascade model, in both the active and passive query models. They also showed empirically that simple extensions of their algorithms work on sparse networks. In this work, we focus on the active model. We prove that a simple modification of Amin et al.'s algorithm works on more general classes of networks, namely (i) networks with large girth and low path growth rate, and (ii) networks with bounded degree. This also provides partial theoretical explanation for Amin et al.'s experiments on sparse networks.

Full work available at URL: https://arxiv.org/abs/1705.10051

zbMATH Keywords

learningcontagiongraph algorithmslarge girthnetwork structures

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Random Graphs
• Collective dynamics of ‘small-world’ networks
• Title not available (Why is that?)

Cited In (1)

• Inferring contagion patterns in social contact networks with limited infection data

Recommendations

• The implications of network structure for epidemic dynamics 👍 👎
• Inferring contagion patterns in social contact networks with limited infection data 👍 👎
• Recovering Social Networks from Contagion Information 👍 👎
• Inferring Social Networks from Outbreaks 👍 👎
• Network topology inference from infection statistics 👍 👎
• Contagion in networks: stability and efficiency 👍 👎
• Contagion dynamics in complex networks 👍 👎
• Mapping Out Emerging Network Structures in Dynamic Network Models Coupled with Epidemics 👍 👎
• Contagion dynamics in multilayer networks with community structure 👍 👎

This page was built for publication: Learning network structures from contagion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509882)