Tagged with

Zombie Escape

What would you do if there was a zombie apocalypse? Stay away from the zombies would be your priority number one, right? Many movies' plot these days revolve around zombies. In many of them, a person (or animal) becomes a zombie, if it's bitten or, sometimes, scratched by a zombie. Also, if a person becomes a zombie, generally speaking, it cannot go back. Thus, once a zombie, always a zombie! The likelihood of a person becoming a zombie is directly proportional to the degree of proximity of said person to the zombies, which makes sense since you are most likely to become a zombie with a horde of zombies on your back instead of only one zombie.

Strangely, the dissemination of opinion over a social network, like your family or facebook, behaves in almost the same manner. The likelihood of a person changing or maintaining a certain opinion is directly proportional to their exposition to it. Since social medias have an important hole in opinion dissemination these days, especially at election times, it's important to understand and create tools to analyze the main aspects of opinion dissemination and its behavior.

In order to model the zombie apocalypse the dissemination of opinions in a social network, we are going to use the infection model for graphs. In this model, an infection in a graph spreads over the vertices in a way that infected vertices remain infected forever and it spreads in rounds. Given a set of vertices initially infected, in each round, a vertex v is infected if there are at least ths(v) neighbors infected in previous rounds, where ths is the threshold function over the vertices of the graph. We say that a vertex infected at round i is infected at time i. The vertices initially infected are infected at time zero. The gif bellow depicts the spread of an infection in a graph at each time with ths(v) = 2 for each vertex v. A set S that infects all vertices of a graph G is an infectious set of G.

Infection

Infection in graphs is the subject of several scientific studies, like this, this, this, this and this, and has many different names in the scientific literature like k-neighbour bootstrap percolation, convexity on graphs, activation process and irreversible k-threshold process. Thus, there are many computational problems regarding infection in graphs like finding: the smallest set that infects the graph at time at most one, a set that infects the whole graph at maximum time and the largest set of vertices S that cannot be infected by the set V \ S, where V is the vertex set of the graph and S is a proper subset of V.

One of the most studied computational problems is to find a smallest infectious set of a graph. We are going to call it here the Minimum Infectious Set Problem.

Formally, the input of the Minimum Infectious Set Problem (MISP) is a graph G = (V,E) and a function ths : VN* of the vertices of G on the natural numbers greater than zero. The task is to find the size of a smallest infectious set (or a smallest infectious set itself) S of G. Unfortunately, this problem is hard, i.e., we probably can't find a fast (polynomial) algorithm to solve it. To put it on computer science terms, the problem is NP-complete. However, we can solve it for some special types of inputs.

Let the k-Minimum Infectious Set Problem (k-MISP) be the MISP such that ths(v) = k for all vertex v of the input graph. One of the cases where we have a fast algorithm is the 1-MISP. The 1-MISP can be reduced to the problem of finding one vertex for each connected component of the graph, that is, one vertex for each connected portion of the graph. For that, we can use the depth-first search (DFS) to find each connected component of the graph and take one vertex of each such component. The algorithm is the following.

DFS(G,v,component[],n)
    component[v] := n
    for each neighbor w of v do:
        if component[w] = -1 then
            DFS(G,w,component,n)

1-MISP(G)
    S := {}, n := 0
    for each vertex v of G do:
        component[v] := -1
    for all vertex v in V do:
        if component[v] = -1 then
            S := S U {v}
            n := n + 1
            DFS(G,v,component,n)
    return (S,n)

This algorithm returns a smallest set S that infects the input graph and its size n. Also, the algorithm is very fast, its time complexity is O(n+m) if we implement the set S as a boolean vector indexed by the vertices, where n = |V| and m = |E|.

Unfortunately, the k-MISP is hard for any k > 1. However, if the input graph is a tree, we can devise an algorithm that takes advantage of the tree's structure to solve the MISP problem quickly.

First, we root the tree at some node r. Then, we define S[v,3] as the size of a smallest infectious set of the subtree rooted at v that includes v, S[v,0] as the size of a smallest infectious set of the subtree rooted at v that doesn't include v and its father in the tree is infected after v, S[v,1] as the size of a smallest infectious set of the subtree rooted at v that doesn't include v and its father in the tree is infected before v and S[v,2] as the size of a smallest infectious set of the subtree rooted at v that doesn't include v and its father in the tree is infected at the same time as v. If there is no infectious set of the subtree rooted at v within the given restrictions, S[v,i] = ∞ and if v is the root, then S[v,0] is defined as the size of a smallest infectious set of the subtree rooted at v that doesn't include v and S[v,0] = S[v,1] = S[v,2].

Clearly, if l is a leaf, we have that S[l,2] = 1 and S[l,0] = S[l,1] = ∞. Also, we define S[r,1] = ∞, as the node r has no father. Thus, the size of the smallest infectious set of the tree is the value min(S[r,0],S[r,2]). Then, if our algorithm can calculate S[v,i] for any node v and 0 ≤ i ≤ 2, it can solve the problem. The algorithm is the following.

recursive_MISP(T,ths,root,v,S[][])
    k := ths(v)

    # base case: v is a leaf
    if v is a leaf then
        S[v,3] := 1, S[v,0] := infinity, S[v,2] := infinity
        if k = 1 then
            S[v,1] := 0
        else
            S[v,1] := infinity
        return

    for each child w of v do:
        recursive_MISP(T,ths,root,w,S)

    # Calculation of S[v,3]
    S[v,3] := 1
    for each child w of v do:
        S[v,3] := S[v,3] + min{S[w,i] | 1 <= i <= 3}

    # Calculation of S[v,0], S[v,1] and S[v,2]
    for mode := 0 to 2 do:
        S[v,mode] := infinity
        if mode = 0 or v != root then
            c := 0
            if mode = 1 then
                c := 1
            if v has at least k neighbors then
                for each combination of k-c children of v in the set W do:
                    curr_S := 0
                    for each node q in W do:
                        curr_S := curr_S + min(S[q,0],S[q,3])
                    for each children q of v not in W do:
                        curr_S := curr_S + min{S[q,i] | 1 <= i <= 3}
                    S[v,mode] := min(S[v,mode],curr_S)
        else
            S[v,2] := S[v,0], S[v,1] := S[v,0]

MISP_tree(T,ths)
    for each node v of T and integer 0 <= i <= 3 do:
        S[v,i] := -1
    Let r be the root of T;
    recursive_MISP(T,ths,r,r,S)
    return min(S[r,0],S[r,3])

For the sake of clarity, we invoke the DP_MISP function only with the two parameters that change throughout the algorithm, v and mode. The complexity of this algorithm is O(nk+1), where n = |V| and k is the maximum ths(v). Thus, we have that this algorithm is polynomial for each constant k and finds the smallest infectious set of a tree. Therefore, it solves the k-MISP in polynomial time for any constant k. It is known that, probably, this bound can't be significantly improved, that is, there is no algorithm that has a complexity of O(nc), for any constant c that is independent of k unless the likely true complexity theoretical conjecture FPT ≠ W[1] turns out to be not true.

There is plenty of scientific work regarding infection on graphs, including about other forms of infection spread that one can use to model the spread of the infection. With more and more people using social medias to express and form opinions, it's important to develop computational tools and techniques to understand how ideas and opinions spread throughout the social networks (or to survive a zombie apocalypse!).


3bbb29e186f7040f3db0463caf6d2b5d?s=184&d=mm

Thiago Marcilon I'm a Ph.D. in algorithms and complexity with experience in software development. Just recently, I realized just how much theoretical knowledge can aid the everyday developer and, since then, I'm keen to show people how computing theory can help them improve their skills.