13
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ How do you define an "influential" node? $\endgroup$
    – Timothy Sun
    Commented Sep 8, 2011 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$
    – zzzbbx
    Commented Sep 9, 2011 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
    Commented Oct 12, 2011 at 23:29
  • $\begingroup$ I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution. $\endgroup$
    – zzzbbx
    Commented Oct 14, 2011 at 23:12

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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