According to the law enforcement professionals we met, the idea of influence is critical to understanding the behavior of violent street gangs. Of particular concern is the influence of radicalizing gang members - charismatic individuals that not only participate in abnormally risky and violent behavior, but have the ability to encourage others to do the same. In order to identify sets of individuals who conduct such behavior, we consider the idea of influence spread through the “tipping model” [1]}. In such a model, we again consider a population structured as a social network (\(G=(V,E)\) ) where each vertex \(i \in V\)  is adjacent to \(d_i\)  edges. We model a social contagion that spreads through the network as follows: consider unaffected node \(i\) . If at least \(\lceil d_i/2 \rceil \)  of \(i\) 's neighbors have the contagion, then \(i\)  has the contagion – otherwise it does not. A key question regarding this model is to identify a seed set - a set of vertices in the network that, if initially infected, will lead to the entire population receiving the contagion. Identifying a seed set provides the analyst a set of individuals that, when taken together, are very influential to the overall network. Further, if the seed set is of minimal size, then the size of the set can be used as a proxy to measure how easily the network can be influenced. Unfortunately, a simple reduction from set cover shows that finding a seed set of minimal size is an NP-hard problem. [2]} However, we have designed a fast heuristic algorithm that finds seed sets of very small size in practice. [3]} This algorithm is based on the idea of shell decomposition often cited in physics literature [4]}, [5]}, [6]}, [7]} but modified to ensure that the resulting set will lead to all nodes being infected. The algorithm, TIP_DECOMP is presented in this section.
