Inferring Network Structure via Cascades

The interaction between individuals are usually modeled as weighted edges in a social network. This information, however, is often unavailable in practice. On the other hand, information diffusion process upon the underlying network is observable. Hence sophisticated algorithm is needed to infer the edge set and edge weights from observed cascade set. To deal with this problem, we derive the likelihood of a given network generating a cascade set. With this likelihood, we design a distributed algorithm named Net Win that first calculates the optimal edge weights by maximizing likelihood and then sparsifies the result of optimization by a novel post-processing algorithm. In experimental results, Net Win infers various networks with high accuracy and outperforms other state-of-the-art algorithms in almost all cases.