NetInf

NetInf is an algorithm proposed in Rodriguez et al. KDD 2010, which formulates the contagion spread in a social network as directed trees propagation. It manages to reduce the complexity of searching an exponential set of candidate trees to polynomial time. Instead of estimating the likelihood of a cascade using all possible propagation trees, which causes the likelihood computationally intractable, NetInf approximates it by considering only the most likely tree, and is found to work well empirically. Additionally, the external influence from outside the network is modeled via ε-edges, which basically says every node can get infected by some external source with small probability.