Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries

Details Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries

2011-10-17

arxiv.org/abs/1110.3843v2

Computer Science

Social and Information Networks

Preprint of results to appear at 2012 American Control Conference

Scientific paper

We consider the problem of diffusing information in networks that contain malicious nodes. We assume that each normal node in the network has no knowledge of the network topology other than an upper bound on the number of malicious nodes in its neighborhood. We introduce a topological property known as r-robustness of a graph, and show that this property provides improved bounds on tolerating malicious behavior, in comparison to traditional concepts such as connectivity and minimum degree. We use this topological property to analyze the canonical problems of distributed consensus and broadcasting, and provide sufficient conditions for these operations to succeed. Finally, we provide a construction for r-robust graphs and show that the common preferential-attachment model for scale-free networks produces a robust graph.

Affiliated with

Also associated with

No associations

Rating

Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries 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 Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-289503