Learning Influence Structure in Sparse Social Networks

The 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 model. In this classical model, n agents discuss m ≪ n topics, which 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 opinions' profile only. The intrinsic sparsity of the graph is exploited via an ℓ0/ℓ1minimization. Different from the techniques previously proposed in the literature, no partial knowledge of the social graph is assumed, and there is no need to optimally place external stubborn agents injecting prescribed inputs, thus changing the terminal behavior of the opinion dynamics. Under suitable assumptions, we derive theoretical conditions that guarantee 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.