2019/05/30 by Xuecheng Liu, Liu, Xuecheng, Luoyi Fu +7
Biochemistry, Genetics and Molecular Biology · Chemistry · Computer Science · Mathematics · #Advanced Graph Neural Networks #Algorithm #Bounded function #Combinatorics #Computer science #Discrete mathematics #Estimator #Mathematics #Metal-Organic Frameworks: Synthesis and Applications #Network topology #Node (physics) #Path (computing) #Peroxisome Proliferator-Activated Receptors #Real-time computing #Statistics #Theoretical computer science #Time complexity #Timestamp #Topology (electrical circuits) #Tree (set theory)
paper · pdf · doi:10.48550/arxiv.1905.12913
openalex publication_date 2019/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper investigates the problem of utilizing network topology and partial timestamps to detect the information source in a network. The problem incurs prohibitive cost under canonical maximum likelihood estimation (MLE) of the source due to the exponential number of possible infection paths. Our main idea of source detection, however, is to approximate the MLE by an alternative infection path based estimator, the essence of which is to identify the most likely infection path that is consistent with observed timestamps. The source node associated with that infection path is viewed as the estimated source v. We first study the case of tree topology, where by transforming the infection path based estimator into a linear integer programming, we find a reduced search region that remarkably improves the time efficiency. Within this reduced search region, the estimator v is provably always on a path which we term as candidate path. This notion enables us to analyze the distribution of d(v∗,v), the error distance between v and the true source v∗, on arbitrary tree, which allows us to obtain for the first time, in the literature provable performance guarantee of the estimator under limited timestamps. Specifically, on the infinite g-regular tree with uniform sampled timestamps, we get a refined performance guarantee in the sense of a constant bounded d(v∗,v). By virtue of time labeled BFS tree, the estimator still performs fairly well when extended to more general graphs. Experiments on both synthetic and real datasets further demonstrate the superior performance of our proposed algorithms.