Learning influence structure in sparse social networks

Aim of this paper is to propose a novel methodology for estimating the social influence among agents interacting in a sparse social network described by the Friedkin and Johnsen's model. In this classical model, n agents discuss m<<n topics, are influenced by the others' opinions, but are not completely open-minded, being persistently driven by their prejudices. We reconstruct the social network topology and the strength of the interconnections starting from observations of the initial and final opinionsn profile only. The intrinsic sparsity of the graph is exploited via an l0/l1 minimization. Different from the techniques previously proposed in literature, no partial knowledge of the social graph is assumed, and there is no need of optimally placing external stubborn agents injecting prescribed inputs, thus changing the terminal behavior of the opinion dynamics. Under suitable assumptions, we derive theoretical conditions that guarantee that the problem is well posed and sufficient requirements on the number of topics under discussion that ensure perfect recovery. Extensive simulations on synthetic and real networks corroborate theoretical results.