13

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?

stamps
  • 33
  • 2
zzzbbx
  • 203
  • 1
  • 5
  • How do you define an "influential" node? – Timothy Sun Sep 08 '11 at 22:57
  • 2
    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. – zzzbbx Sep 09 '11 at 00: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. – Jukka Suomela Oct 12 '11 at 23:29
  • I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution. – zzzbbx Oct 14 '11 at 23:12

2 Answers2

3

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.

Massimo Cafaro
  • 2,216
  • 20
  • 19
2

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

vzn
  • 11,014
  • 2
  • 31
  • 64