Identifying Infection Sources and Regions in Large Networks

Details Identifying Infection Sources and Regions in Large Networks Identifying Infection Sources and Regions in Large Networks

2012-04-02

arxiv.org/abs/1204.0354v1

Computer Science

Discrete Mathematics

Scientific paper

Identifying the infection sources in a network, including the individuals who started a rumor in a social network, the computers that introduce a virus into a computer network, or the index cases of a contagious disease, plays a critical role in limiting the damage caused by the infection through timely quarantine of the sources. We consider the problem of estimating the infection sources and the infection regions (subsets of nodes infected by each source) in a network, based only on knowledge of the underlying network connections, and when the number of sources is unknown a priori. We derive estimators for the infection sources and their infection regions based on approximations of the infection sequences counts. We prove that if there are at most two infection sources in a geometric tree, our estimator identifies the true source or sources with probability going to one as the number of infected nodes increases. When there are more than two infection sources, and when the maximum possible number of infection sources is known, we propose an algorithm with quadratic complexity to estimate the actual number and identities of the infection sources. Simulations are conducted on various kinds of networks, including tree networks, small-world networks and real world power grid networks, to verify the performance of our algorithms. Our simulation results show that with high probability, our proposed estimators are within a few hops from the true infection sources.

Affiliated with

Also associated with

No associations

Rating

Identifying Infection Sources and Regions in Large Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Identifying Infection Sources and Regions in Large Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying Infection Sources and Regions in Large Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509423