<p>Decentralized algorithms for variants of this problem have been published in <a href="http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/5888673/5934870/05935226.pdf?arnumber=5935226&amp;authDecision=-203" rel="nofollow">A distributed and privacy preserving algorithm for identifying information hubs in social networks</a> and  <a href="http://keg.cs.tsinghua.edu.cn/jietang/publications/KDD09-Tang-et-al-Social-Influence-Analysis.pdf" rel="nofollow">Social Influence Analysis in Large-scale Networks</a>.</p>

CC BY-SA 3.0
2012-01-22T09:22:57.163Z
2012-01-22T09:28:56.107Z
2012-01-22T09:28:56.107Z
Massimo Cafaro
<p>how about these? <a href="http://dl.acm.org/citation.cfm?id=1347498" rel="nofollow">Bringing Pagerank to the Citation Analysis</a> by Ma, Guan, Zhao</p>

<p><a href="http://arxiv.org/ftp/arxiv/papers/1012/1012.4872.pdf" rel="nofollow">
PageRank for ranking authors in co-citation network</a> Ding, Yan, Frazho, Caverlee</p>

CC BY-SA 3.0
2012-01-20T21:39:47.253Z
2012-01-20T21:39:47.253Z
vzn
<p>In this <a href="http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf" rel="noreferrer">paper</a> 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. </p>

<p>Basically the algorithm goes as follows:</p>

<ol>
<li>$S = {\rm empty~set}$</li>
<li>pick the node with highest individual influence, call it $v_1$; $S = S\cup v_1$</li>
<li>remove $v_1$ and all edges connecting $v_1$ to the rest of the network</li>
<li>repeat until $S$ has $k$ vertices</li>
</ol>

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

CC BY-SA 3.0
2011-09-08T22:57:02.937Z
How do you define an "influential" node?
Timothy Sun
CC BY-SA 3.0
2011-09-09T00:15:56.887Z
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
CC BY-SA 3.0
2011-10-12T23:29:27.937Z
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
CC BY-SA 3.0
2011-10-14T23:12:01.347Z
I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution.
zzzbbx
<ds.algorithms><graph-theory><dc.distributed-comp><social-sciences><heuristics>
Decentralized algorithm for determining influential nodes in social networks
zzzbbx
# Decentralized algorithm for determining influential nodes in social networks

(Asked by: username_0 on 2011-09-08)

In this [paper](http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf) 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?

**Tags:** ds.algorithms, graph-theory, dc.distributed-comp, social-sciences, heuristics
> **Comments:**
> **username_1**: How do you define an "influential" node?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: I understand that. My concern was if there is, at least, a suboptimal algorithm to approximate the optimal solution.  

---

## 2 answers

### Answer by username_3 on 2012-01-22. Score: 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](http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/5888673/5934870/05935226.pdf?arnumber=5935226&authDecision=-203) and [Social Influence Analysis in Large-scale Networks](http://keg.cs.tsinghua.edu.cn/jietang/publications/KDD09-Tang-et-al-Social-Influence-Analysis.pdf).


---

### Answer by username_4 on 2012-01-20. Score: 2

how about these? [Bringing Pagerank to the Citation Analysis](http://dl.acm.org/citation.cfm?id=1347498) by Ma, Guan, Zhao

[PageRank for ranking authors in co-citation network](http://arxiv.org/ftp/arxiv/papers/1012/1012.4872.pdf) Ding, Yan, Frazho, Caverlee


---

