Learning network structures from contagion

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

Authors Adisak Supeesun, Jittat Fakcharoenphol 

Publication date 21 February 2017

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• Collective dynamics of `small-world' networks
• Random Graphs

Cited in

(7)

• Optimally learning social networks with activations and suppressions
• Contagion in graphons
• Learning from networked examples
• Inferring contagion patterns in social contact networks with limited infection data
• Recovering social networks from contagion information
• The inverse contagion problem (ICP) vs. predicting site contagion in real time, when network links are not observable
• Optimally Learning Social Networks with Activations and Suppressions

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)