Content preference estimation in online social networks: Message passing versus sparse reconstruction on graphs

We design two different strategies for computing the unknown content preferences in an online social network based on a small set of nodes in the corresponding social graph for which this information is available ahead of time. The techniques take advantage of the graph's structure and the additional affinity information between the social contacts, expressed through the graph's edge weights, to optimize the computation of the missing preference data. The first strategy is distributed and comprises a local computation step and a message passing step that are iteratively applied at each node in the graph, until convergence. We carry out a graph Laplacian based analysis of the performance of the algorithm and verify the analytical findings via numerical experiments involving sample social networks. The second strategy is centralized and involves a sparse transform of the content preference data represented as a function over the nodes of the social graph. We solve the related optimization problem of reconstructing the unknown preferences via an iterative algorithm based on variable splitting and alternating direction of multipliers. The algorithm takes into account the specifics of the data to be reconstructed by incorporating multiple regularization terms into the optimization. We investigate the underpinnings of the sparse reconstruction technique via numerical experiments that reveal its characteristics and how they affect its performance.