  The fast growth of social networks and their data access limitations in
recent years has led to increasing difficulty in obtaining the complete
topology of these networks. However, diffusion information over these networks
is available, and many algorithms have been proposed to infer the underlying
networks using this information. The previously proposed algorithms only focus
on inferring more links and ignore preserving the critical topological
characteristics of the underlying social networks. In this paper, we propose a
novel method called DANI to infer the underlying network while preserving its
structural properties. It is based on the Markov transition matrix derived from
time series cascades, as well as the node-node similarity that can be observed
in the cascade behavior from a structural point of view. In addition, the
presented method has linear time complexity (increases linearly with the number
of nodes, number of cascades, and square of the average length of cascades),
and its distributed version in the MapReduce framework is also scalable. We
applied the proposed approach to both real and synthetic networks. The
experimental results showed that DANI has higher accuracy and lower run time
while maintaining structural properties, including modular structure, degree
distribution, connected components, density, and clustering coefficients, than
well-known network inference methods.
