dc.contributor.authorLuo, Wuqiong
dc.contributor.authorTay, Wee Peng
dc.contributor.authorLeng, Mei
dc.identifier.citationLuo, W., Tay, W. P., & Leng, M. (2017). On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks. IEEE Transactions on Information Theory, 63(7), 4634-4657.en_US
dc.description.abstractFinding the infection sources in a network when we only know the network topology and infected nodes, but not the rates of infection, is a challenging combinatorial problem, and it is even more difficult in practice where the underlying infection spreading model is usually unknown a priori. In this paper, we are interested in finding a source estimator that is applicable to various spreading models, including the susceptible-infected (SI), susceptible-infected-recovered (SIR), susceptible-infected-recovered-infected (SIRI), and susceptible- infected-susceptible (SIS) models. We show that under the SI, SIR, and SIRI spreading models and with mild technical assumptions, the Jordan center is the infection source associated with the most likely infection path in a tree network with a single infection source. This conclusion applies for a wide range of spreading parameters, while it holds for regular trees under the SIS model with homogeneous infection and recovery rates. Since the Jordan center does not depend on the infection, recovery, and reinfection rates, it can be regarded as a universal source estimator. We also consider the case where there are k 1 infection sources, generalize the Jordan center definition to a k-Jordan center set, and show that this is an optimal infection source set estimator in a tree network for the SI model. Simulation results on various general synthetic networks and real-world networks suggest that Jordan center-based estimators consistently outperform the betweenness, closeness, distance, degree, eigenvector, and pagerank centrality-based heuristics, even if the network is not a tree.en_US
dc.description.sponsorshipMOE (Min. of Education, S’pore)en_US
dc.format.extent24 p.en_US
dc.relation.ispartofseriesIEEE Transactions on Information Theoryen_US
dc.rights© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TIT.2017.2698504].en_US
dc.subjectInfection source estimationen_US
dc.subjectUniversal source estimatoren_US
dc.titleOn the Universality of Jordan Centers for Estimating Infection Sources in Tree Networksen_US
dc.typeJournal Article
dc.contributor.researchTemasek Laboratoriesen_US
dc.contributor.schoolSchool of Electrical and Electronic Engineeringen_US
dc.description.versionAccepted versionen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record