Learning network structures from contagion

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

Authors: Adisak Supeesun, Jittat Fakcharoenphol 

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

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

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

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

Cited In (7)

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

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)