DANI: Fast Diffusion Aware Network Inference with Preserving Topological Structure Property

Abstract

Numerous algorithms have been proposed to infer the underlying structure of social networks via observed information propagation. Previously proposed algorithms concentrate on inferring accurate links and neglect preserving the essential topological properties of the underlying social networks. We propose a novel method called DANI to infer the underlying network while preserving its structural properties. DANI is constructed using the Markov transition matrix derived from the analysis of time series cascades and the observation of node-node similarity in cascade behaviour from a structural perspective. The presented method has linear time complexity, and its distributed version in the MapReduce framework is scalable. Experiments on real and synthetic networks show that DANI has higher accuracy and lower run time than well-known network inference methods, while preserving modular structure, degree distribution, connected components, density and clustering coefficients.