This paper proposes a new measure of node centrality in social networks, the Harmonic Influence Centrality, which emerges naturally in the study of social influence over networks. Using an intuitive analogy between social and electrical networks, we introduce a distributed message passing algorithm to compute the Harmonic Influence Centrality of each node. Although its design is based on theoretical results which assume the network to have no cycle, the algorithm can also be successfully applied on general graphs.
Knowing how important a node or an edge is, within a network, can be very valuable. In the area of complex networks, a variety of centrality measures, which assign to each node or edge a number representing its importance, have been proposed. In this paper, we consider two such measures, namely, node and edge betweenness that characterize how often a node or edge lies on the shortest paths between all pairs of nodes. For each measure, we use a dynamical systems approach to develop continuous- and discrete-time distributed algorithms, which enable every node in an undirected and unweighted tree graph to compute its own measure with only local interaction and without any centralized coordination. We show that the algorithms are simple and scalable, with the continuous-time version being unconditionally exponentially convergent, and the discrete-time version unconditionally exhibiting a deadbeat response. Moreover, we show that they require minimal node memories to execute, bypass entirely the need to construct shortest paths, and can handle time-varying topologies. In the search engine of Google, the PageRank algorithm plays a crucial role in ranking the search results. The algorithm quantifies the importance of each web page based on the link structure of the web. We first provide an overview of the original problem setup. Then, we propose several distributed randomized schemes for the computation of the PageRank, where the pages can locally update their values by communicating to those connected by links. The main objective of the paper is to show that these schemes asymptotically converge in the mean-square sense to the true PageRank values. A detailed discussion on the close relations to the multi-agent consensus problems is also given.