# Decentralized algorithm for determining influential nodes in social networks

In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social networks.

Basically the algorithm goes as follows:

1. $S = {\rm empty~set}$
2. pick the node with highest individual influence, call it $v_1$; $S = S\cup v_1$
3. remove $v_1$ and all edges connecting $v_1$ to the rest of the network
4. repeat until $S$ has $k$ vertices

I have two questions about influential nodes in social networks.
a) Is there any algorithm to find the solution, or an approximation of it in a decentralized fashion?
b) Did anyone apply other algorithms, such as Page-Rank and similar, to solve the same problem?

• How do you define an "influential" node? Sep 8, 2011 at 22:57
• according to the paper, each link is defined with a probability to successfully transmit a message from one node to another. The objective is to find the subset of nodes that will deliver a message to the largest number of nodes, on expectation. Sep 9, 2011 at 0:15
• Regarding distributed algorithms: In general, any problem of the form "find $k$ best nodes" is inherently global; it cannot be solved much faster than in time $D$, where $D$ is the diameter of the graph. To see this, consider the case of $k = 1$ and connect two "good" nodes with a long path; to determine which of the good nodes is best, you need to propagate information for order of $D$ hops. Oct 12, 2011 at 23:29
• I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution. Oct 14, 2011 at 23:12