The harmonic influence in social networks and its distributed computation by message passing
For researchers studying influence in social networks, this work provides a theoretically grounded and practically useful distributed algorithm, though it is an incremental extension of prior work.
This paper extends a distributed message passing algorithm for computing node influence in social networks, proving its convergence on general graphs and showing through simulations that it provides a meaningful approximation.
In this paper we elaborate upon a measure of node influence in social networks, which was recently proposed by Vassio et al., IEEE Trans. Control Netw. Syst., 2014. This measure quantifies the ability of the node to sway the average opinion of the network. Following the approach by Vassio et al., we describe and study a distributed message passing algorithm that aims to compute the nodes' influence. The algorithm is inspired by an analogy between potentials in electrical networks and opinions in social networks. If the graph is a tree, then the algorithm computes the nodes' influence in a number of steps equal to the diameter of the graph. On general graphs, the algorithm converges asymptotically to a meaningful approximation of the nodes' influence. In this paper we detail the proof of convergence, which greatly extends previous results in the literature, and we provide simulations that illustrate the usefulness of the returned approximation.