TY - GEN

T1 - Information source detection in networks

T2 - 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016

AU - Zhu, Kai

AU - Ying, Lei

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2016/7/27

Y1 - 2016/7/27

N2 - This paper studies information source detection in networks under the independent cascade (IC) model. Assume the spread of information starts from a single source in a network and a complete snapshot of the network is obtained at some time. The goal is to identify the source based on the observation. We derive the maximum a posterior (MAP) estimator of the source for tree networks and propose a Short-Fat Tree (SFT) algorithm for general networks based on the MAP estimator. The algorithm selects the Jordan infection center [1] and breaks ties according the degree of boundary infected nodes. Loosely speaking, the algorithm selects the node such that the breadth-first search (BFS) tree from it has the minimum depth but the maximum number of leaf nodes. On the Erdos-Renyi (ER) random graph, we establish the following possibility and impossibility results: (i) when the infection duration 0.5, SFT identifies the source with probability 1 (w.p.1) asymptotically (as network size increases to infinity), where n is the network size and μ is the average node degree; (ii) when the infection duration > [log n/ log μ ] + 2, the probability of identifying the source approaches zero asymptotically under any algorithm; and (iii) when infection duration < 0, asymptotically, at least 1-δ fraction of the nodes on the BFS tree starting from the source are leaf-nodes, where δ = 3√log n/μ, i.e., the BFS tree starting from the actual source is a fat tree. 1Numerical experiments on tree networks, the ER random graphs and real world networks with different evaluation metrics show that the SFT algorithm outperforms existing algorithms.

AB - This paper studies information source detection in networks under the independent cascade (IC) model. Assume the spread of information starts from a single source in a network and a complete snapshot of the network is obtained at some time. The goal is to identify the source based on the observation. We derive the maximum a posterior (MAP) estimator of the source for tree networks and propose a Short-Fat Tree (SFT) algorithm for general networks based on the MAP estimator. The algorithm selects the Jordan infection center [1] and breaks ties according the degree of boundary infected nodes. Loosely speaking, the algorithm selects the node such that the breadth-first search (BFS) tree from it has the minimum depth but the maximum number of leaf nodes. On the Erdos-Renyi (ER) random graph, we establish the following possibility and impossibility results: (i) when the infection duration 0.5, SFT identifies the source with probability 1 (w.p.1) asymptotically (as network size increases to infinity), where n is the network size and μ is the average node degree; (ii) when the infection duration > [log n/ log μ ] + 2, the probability of identifying the source approaches zero asymptotically under any algorithm; and (iii) when infection duration < 0, asymptotically, at least 1-δ fraction of the nodes on the BFS tree starting from the source are leaf-nodes, where δ = 3√log n/μ, i.e., the BFS tree starting from the actual source is a fat tree. 1Numerical experiments on tree networks, the ER random graphs and real world networks with different evaluation metrics show that the SFT algorithm outperforms existing algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84983315337&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983315337&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2016.7524363

DO - 10.1109/INFOCOM.2016.7524363

M3 - Conference contribution

AN - SCOPUS:84983315337

T3 - Proceedings - IEEE INFOCOM

BT - IEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 10 April 2016 through 14 April 2016

ER -