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?

  • $\begingroup$ How do you define an "influential" node? $\endgroup$ – Timothy Sun Sep 8 '11 at 22:57
  • 2
    $\begingroup$ 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. $\endgroup$ – Bob Sep 9 '11 at 0:15
  • $\begingroup$ 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. $\endgroup$ – Jukka Suomela Oct 12 '11 at 23:29
  • $\begingroup$ I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution. $\endgroup$ – Bob Oct 14 '11 at 23:12

Decentralized algorithms for variants of this problem have been published in A distributed and privacy preserving algorithm for identifying information hubs in social networks and Social Influence Analysis in Large-scale Networks.

| cite | improve this answer | |

how about these? Bringing Pagerank to the Citation Analysis by Ma, Guan, Zhao

PageRank for ranking authors in co-citation network Ding, Yan, Frazho, Caverlee

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.