VoteRank
Definition
The $VoteRank$ is an iterative method to identify a set of decentralized spreaders with the best spreading ability. In this approach, all nodes vote in a spreader in each turn, and the voting ability of neighbors of elected spreader will be decreased in subsequent turn.
In $VoteRank$, the main idea is to choose a set of spreaders one by one according to voting scores of nodes obtained from their neighbors. If we need to select top-$r$ influential spreaders, every node has to vote $r$ turns. The node getting the most votes in each turn is regarded as the most influential node in that turn and will be elected as one of top-$r$ influential spreaders. If a node has been elected as a spreader, it doesn’t participate in subsequent voting, and the voting ability of its neighbors also be decreased. Actually, when a node $u$ is elected as spreader, the propagation range has increased a little if the nodes near $u$ are elected as spreaders again since $u$ can transfer information to these nodes. So, it’s better to select far apart nodes because they can affect as many nodes as possible. That is to say, after a node is elected as spreader, the selection probability of its neighbors and neighbors’ neighbors will decrease. Under this mechanism, the selected nodes are far apart and are important in its local structure.
In $VoteRank$, each node $u$ is attached with a tuple $(s_u, va_u)$, where voting score $s_u$ denotes the number of votes obtained from $u^′$ s neighbors and voting ability $va_u$ represents the number of votes that $u$ can give its neighbors. The details of $VoteRank$ are described as following five steps:
step 1: Initialize. Tuples of all nodes are set to $(0, 1)$.
step 2: Vote. Nodes vote for their neighbors, at the same time are voted by their neighbors. After voting step, the voting score of each node will be calculated. It is noted that the voting score of node is set to zero if it has been elected in earlier turn so as to avoid electing it again.This voting process is different from political voting because some nodes just vote for less one vote in $VoteRank$.
step 3: Select. According to voting scores calculated in step 2, select the node $v_{max}$ that gets the most votes. This node will not participate in subsequent voting turns, that is, its voting ability $va_{v_{max}}$ will be zero from now on.
step 4: Update. Weaken the voting ability of nodes those voted for $v_{max}$ in step 2.
step 5: Repeat steps 2 to 4 until $r$ spreaders are elected.
The $VoteRank$ algorithm not only can be used to choose top-$r$ spreaders in undirected networks, but also can be used in directed networks.
VoteRank-LRed and VoteRank-XRed:
Freitas, J., Barbastefano, R. and Carvalho, D., 2018. Identifying influential patents in citation networks using enhanced VoteRank centrality. arXiv preprint arXiv:1811.01638.
In $VoteRank$, the main idea is to choose a set of spreaders one by one according to voting scores of nodes obtained from their neighbors. If we need to select top-$r$ influential spreaders, every node has to vote $r$ turns. The node getting the most votes in each turn is regarded as the most influential node in that turn and will be elected as one of top-$r$ influential spreaders. If a node has been elected as a spreader, it doesn’t participate in subsequent voting, and the voting ability of its neighbors also be decreased. Actually, when a node $u$ is elected as spreader, the propagation range has increased a little if the nodes near $u$ are elected as spreaders again since $u$ can transfer information to these nodes. So, it’s better to select far apart nodes because they can affect as many nodes as possible. That is to say, after a node is elected as spreader, the selection probability of its neighbors and neighbors’ neighbors will decrease. Under this mechanism, the selected nodes are far apart and are important in its local structure.
In $VoteRank$, each node $u$ is attached with a tuple $(s_u, va_u)$, where voting score $s_u$ denotes the number of votes obtained from $u^′$ s neighbors and voting ability $va_u$ represents the number of votes that $u$ can give its neighbors. The details of $VoteRank$ are described as following five steps:
step 1: Initialize. Tuples of all nodes are set to $(0, 1)$.
step 2: Vote. Nodes vote for their neighbors, at the same time are voted by their neighbors. After voting step, the voting score of each node will be calculated. It is noted that the voting score of node is set to zero if it has been elected in earlier turn so as to avoid electing it again.This voting process is different from political voting because some nodes just vote for less one vote in $VoteRank$.
step 3: Select. According to voting scores calculated in step 2, select the node $v_{max}$ that gets the most votes. This node will not participate in subsequent voting turns, that is, its voting ability $va_{v_{max}}$ will be zero from now on.
step 4: Update. Weaken the voting ability of nodes those voted for $v_{max}$ in step 2.
step 5: Repeat steps 2 to 4 until $r$ spreaders are elected.
The $VoteRank$ algorithm not only can be used to choose top-$r$ spreaders in undirected networks, but also can be used in directed networks.
VoteRank-LRed and VoteRank-XRed:
Freitas, J., Barbastefano, R. and Carvalho, D., 2018. Identifying influential patents in citation networks using enhanced VoteRank centrality. arXiv preprint arXiv:1811.01638.
References
- Zhang J., Chen D., Dong Q., Zhao Z., 2016. Identifying a set of influential spreaders in complex networks. Scientific Reports, 6.
DOI: 10.1038/srep27823
