A lightweight method to investigate unknown social network structure

摘要

Information, rumors, infectious diseases, actions and influence propagate and diffuse through networks as probabilistic processes. Each piece of information appears in some nodes and spreads node by node over the underlying network. So, inferring network structures and analyzing information diffusion processes are required in various domains. In most cases the underlying network is hidden and we only observe the times in which nodes are infected by contagions. The vast majority of existing methods are parametric with the assumption that information diffusion patterns follow a particular distribution. In this paper, to tackle this problem, we propose a simple and non-parametric method that infers the networks topology given a set of cascades. We consider that there exists an unobserved network and we just observe the temporal diffusion events that occur over the edges of the network. First we extract all candidates edges in the network and after that we estimate weights and strength of these edges. In other words, we calculate the occurrence probability between each pair of nodes in all given cascades which is the pairwise transmission rate between that two nodes. The most dominant feature of our approach is having a very low time and computational complexity compared to the current approaches. In addition, as have not considered any assumptions on the information diffusion pattern, our proposed approach has the advantage of being more general and it can be used in various inferring network problems. In summary, experimental results show that not only our method can reach better or equal performance in comparison with baseline models but also it solves the problem in a simpler way with low time complexity.