NCVoteRank - Neighborhood Coreness VoteRank
Definition
The voting ability of each node should be different and should depend on its topological position in the network. This centrality propose a coreness based VoteRank method called NCVoteRank to find spreaders by taking the coreness value of neighbors into consideration for the voting.
Influential nodes have more neighbors residing in the core of the network and they proposed coreness centrality or Neighborhood Coreness $(NC)$ by taking the $K$-shell value of its neighbors into consideration, which is as follows:
$$NC(v)={\underset{u\in N(v)}{\sum}}Ks(u)$$
where $Ks(u)$ is $K$-shell value of the vertex $u$ and $NC(v)$ is the Neighborhood Coreness of a vertex $v$, which represents the sum of $K$-shell value of all its neighbors. By taking the $K$-shell centrality of all the neighbors simultaneously into account, Neighborhood Coreness $(NC)$ method is able to rank nodes based on its spreading abilities properly.
$NCVoteRank$ centrality finds spreaders by taking the coreness value of neighbors into consideration for the voting. Each node $v\in V$ is associated with a tuple $(S_v, Va_v)$, where $S_v$ and $Va_v$ denote voting score and voting ability of node $v$ respectively. Voting ability $(Va_v)$ means the vote that node $v$ will give to its neighbors. Voting score $S_v$, which is obtained from its adjacent neighbors and can be computed by adding their voting ability
Similar to basic VoteRank it also has four phases:
1) Initialization Phase: Each node $v$ is initialized with a tuple $(S_v, Va_v)$ as $(0, 1)$, i.e., the voting score of each node is $0$, and its voting ability is $1$.
2) Voting Phase: Based on the notion that a node in the core of the network can greatly affect information diffusion. We multiply the voting ability of each node with its Neighborhood Coreness $(NC)$ value. Each node $v$ gets a vote as the sum of voting abilities of its immediate neighbors by the following equation:
$$S_v={\underset{i\in N(v)}{\sum}}(Va_i * NC(i)*(1-\theta)Va_i*\theta)$$
where $\Theta$ is a controlling parameter and varies between $0$ and $1$, and $NC(i)$ is normalized neighborhood coreness of vertex $i$, where vertex $i$ is an immediate neighbor of node $v$. The normalization is required as the values of neighborhood coreness may have scaling issues due to greatly varying magnitudes. For normalization, it used the standard scores. An equation for the standard score of a variable $x$ in the list is:
$$\bar x= {x-x_{min}\over x_{max}-x_{min}}$$
where $x_{min}$ and $x_{max}$ are minimum and maximum value respectively in the list. If $\theta= 1$,
$$S_v={\underset{i\in N(v)}{\sum}}Va_i$$
Vote score of $v$ is equal to the sum of the voting ability of all its neighbors. In this case, $NCVoteRank$ is same as basic $VoteRank$.
if $\theta=0$
$$S_v={\underset{i\in N(v)}{\sum}}Va_i *NC(i)$$
Here, the vote score $(S_v)$ of node $v$ is equal to the sum of the products of voting ability and neighborhood coreness of its direct neighbors. In this manner value of vote score of a node can vary between the sum of the voting ability of all its neighbors and sum of the products of voting ability and neighborhood coreness of its direct neighbors. The node which has got maximum vote could be selected as a spreader in this round, if it was not selected earlier. Further, this node is not going to participate in the further voting round by setting its voting ability as zero.
3)Update Phase: To achieve maximum coverage of the information in the network, spreaders should be picked from diverse positions. It assumed that when a node is selected as a spreader, it can influence its neighbors up to two hops. A factor of $\delta$ will reduce the voting ability of all the neighbors up to distance two from the selected spreader. In the following equation, $Va_v$ denotes the updated voting ability of the neighbor nodes.
$$Va_v=\left\{\begin{array}{l}Va_v - \delta \enspace \enspace if \enspace \enspace Va_v - \delta > 0\\0 \enspace \enspace \enspace otherwise \end{array}\right.$$
where
$$\delta ={1\over kd}$$
and $k$ is the average degree of the nodes in the network, and $d$ is the distance between the selected node and all its updating neighbor up to two units of distance.
4) Iteration Phase: repeat steps (2) and (3) until $c$ nodes have been chosen as spreaders where $c$ is a constant.
Influential nodes have more neighbors residing in the core of the network and they proposed coreness centrality or Neighborhood Coreness $(NC)$ by taking the $K$-shell value of its neighbors into consideration, which is as follows:
$$NC(v)={\underset{u\in N(v)}{\sum}}Ks(u)$$
where $Ks(u)$ is $K$-shell value of the vertex $u$ and $NC(v)$ is the Neighborhood Coreness of a vertex $v$, which represents the sum of $K$-shell value of all its neighbors. By taking the $K$-shell centrality of all the neighbors simultaneously into account, Neighborhood Coreness $(NC)$ method is able to rank nodes based on its spreading abilities properly.
$NCVoteRank$ centrality finds spreaders by taking the coreness value of neighbors into consideration for the voting. Each node $v\in V$ is associated with a tuple $(S_v, Va_v)$, where $S_v$ and $Va_v$ denote voting score and voting ability of node $v$ respectively. Voting ability $(Va_v)$ means the vote that node $v$ will give to its neighbors. Voting score $S_v$, which is obtained from its adjacent neighbors and can be computed by adding their voting ability
Similar to basic VoteRank it also has four phases:
1) Initialization Phase: Each node $v$ is initialized with a tuple $(S_v, Va_v)$ as $(0, 1)$, i.e., the voting score of each node is $0$, and its voting ability is $1$.
2) Voting Phase: Based on the notion that a node in the core of the network can greatly affect information diffusion. We multiply the voting ability of each node with its Neighborhood Coreness $(NC)$ value. Each node $v$ gets a vote as the sum of voting abilities of its immediate neighbors by the following equation:
$$S_v={\underset{i\in N(v)}{\sum}}(Va_i * NC(i)*(1-\theta)Va_i*\theta)$$
where $\Theta$ is a controlling parameter and varies between $0$ and $1$, and $NC(i)$ is normalized neighborhood coreness of vertex $i$, where vertex $i$ is an immediate neighbor of node $v$. The normalization is required as the values of neighborhood coreness may have scaling issues due to greatly varying magnitudes. For normalization, it used the standard scores. An equation for the standard score of a variable $x$ in the list is:
$$\bar x= {x-x_{min}\over x_{max}-x_{min}}$$
where $x_{min}$ and $x_{max}$ are minimum and maximum value respectively in the list. If $\theta= 1$,
$$S_v={\underset{i\in N(v)}{\sum}}Va_i$$
Vote score of $v$ is equal to the sum of the voting ability of all its neighbors. In this case, $NCVoteRank$ is same as basic $VoteRank$.
if $\theta=0$
$$S_v={\underset{i\in N(v)}{\sum}}Va_i *NC(i)$$
Here, the vote score $(S_v)$ of node $v$ is equal to the sum of the products of voting ability and neighborhood coreness of its direct neighbors. In this manner value of vote score of a node can vary between the sum of the voting ability of all its neighbors and sum of the products of voting ability and neighborhood coreness of its direct neighbors. The node which has got maximum vote could be selected as a spreader in this round, if it was not selected earlier. Further, this node is not going to participate in the further voting round by setting its voting ability as zero.
3)Update Phase: To achieve maximum coverage of the information in the network, spreaders should be picked from diverse positions. It assumed that when a node is selected as a spreader, it can influence its neighbors up to two hops. A factor of $\delta$ will reduce the voting ability of all the neighbors up to distance two from the selected spreader. In the following equation, $Va_v$ denotes the updated voting ability of the neighbor nodes.
$$Va_v=\left\{\begin{array}{l}Va_v - \delta \enspace \enspace if \enspace \enspace Va_v - \delta > 0\\0 \enspace \enspace \enspace otherwise \end{array}\right.$$
where
$$\delta ={1\over kd}$$
and $k$ is the average degree of the nodes in the network, and $d$ is the distance between the selected node and all its updating neighbor up to two units of distance.
4) Iteration Phase: repeat steps (2) and (3) until $c$ nodes have been chosen as spreaders where $c$ is a constant.
References
- Kumar S., Panda B.S., 2020. Identifying influential nodes in Social Networks: Neighborhood Coreness based voting approach. Physica A: Statistical Mechanics and its Applications, 553.
DOI: 10.1016/j.physa.2020.124215
