Influence is a Matter of Degree: New Algorithms for Activation Problems

Details Influence is a Matter of Degree: New Algorithms for Activation Problems Influence is a Matter of Degree: New Algorithms for Activation Problems

2010-09-19

arxiv.org/abs/1009.3619v1

Computer Science

Discrete Mathematics

Scientific paper

We consider the target set selection problem. In this problem, a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $k$ active neighbors ($k$ is identical for all vertices of the graph). Our goal is to find a set of minimum size whose activation will result with the entire graph being activated. Call such a set \emph{contagious}. We prove that if $G=(V,E)$ is an undirected graph, the size of a contagious set is bounded by $\sum_{v\in V}{\min \{1,\frac{k}{d(v)+1}\}}$ (where $d(v)$ is the degree of $v$). We present a simple and efficient algorithm that finds a contagious set that is not larger than the aforementioned bound and discuss algorithmic applications of this algorithm to finding contagious sets in dense graphs.

Affiliated with

Also associated with

No associations

Rating

Influence is a Matter of Degree: New Algorithms for Activation Problems 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 Influence is a Matter of Degree: New Algorithms for Activation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Influence is a Matter of Degree: New Algorithms for Activation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408682