Connectionist Centrality


Definition

Connectionist Centrality measure the nodes’ centrality in terms of the influence of the nodes in the information diffusion scenario. The method employs a spreading activation mechanism which quantify how far the network is influenced by a given node through an iterative process. The resulting activation value of the network is then summed as the centrality of the given node.

Let $G =(V,E,W)$ be a weighted and directed network with the vertex set $V (G)= v_1,v_2,....v_n$, where each vertex $v_i$ is attached with an activation value $a_i$, edge set $E(G)$, where each edge $e_{i,j} =(v_i,v_j)$ is attached with a weight $w_{i,j}$. In the diffusion models, the weight $w_{i,j}$ usually represents the probability of success for node $v_i$’s attempt at activating $v_j$, which take value from $0$ to $1.0$. The activation value $a_i$ also varies from $0$ to $1.0$, where $0$ indicates the node is not activated while $1.0$ indicates that the node is fully activated. spreading activation is achieved by iteratively updating the activation value of every node in the network, until the whole network reach a stable solution that represent the final activation status of the network.

Since that all the activations and weights hold positive value, only the positive half of the original activation function will be used,which is:
$$a_i(t + 1) =sat(a_i(t)decay + input_i(t)(max−a_i(t)))$$

where $sat()$ is a saturation function:
$$\begin{equation}
sat(x)=\begin{cases}
1, & \text{if $x\geq0$}\\
x, & \text{if 0< x <1 }
\end{cases}
\end{equation}$$


were, $a_i(t)$ is the current activation of node $v_i$, which is decayed by a decay factor that is smaller than $1.0.inputi(t)$ represents the incoming activation from the neighbors of $v_i$ attime $t.max$ is the maximum value of activation,which is $1.0$ in this case.The equation shows that the activation of $v_i$ in the following time period $a_i(t + 1)$ is a combination of its current activation multiplied by a decay factor and the incoming activation multiplied by a scaling factor.

The incoming activation $inputi(t)$ is calculated as:

$$input_i(t)= {\underset{v_j\in N_i}{\sum}} w_{i,j}.a_j(t)$$

where $N_i$ is the set of neighbor nodes of $v_i$

According to these equations,the updating process for all the nodes will finally reach a stable activation after several iterations. The resulting activation value of a node reflects its degree of being influenced by the source node.

Once a network is input,assuming that the weights on the edges represent connection strength between nodes, the first step is to normalize the weights to the range $[0,1]$ in order to make the following calculation. In addition, as that information is easy to be diffused to all nodes in a network with high connectivity, a network with large average degree might be fully activated (all the nodes reach maximum activation) by a number of influential nodes respectively in few iterations. In this case, it is difficult to rank those nodes since that they all hold similar connectionist centralities generated by the full activation of the network. As a result, there is a need to uniformly weaken all the weights by a factor of the average degree of the network in order to avoid the full activation. After that, the spreading activation mechanism is then employed to compute the connectionist centrality for each node in the network. For a given node $v_i$, assume that it is the source node that activate the network and has a constant activation value of $1.0$, and all the other nodes $v_j(j\ne i)$ in the network start at an activation of $0$. The system then upgrades the activation for all the $v_j$ iteratively, until the whole network reach a stable status, namely:

$$a_j(t+1)-a_j(t) < error (\forall v_j\in V(G))$$


where $error$ is a predefined threshold.
$c_i$, which is the centrality of $v_i$, is then computed as:

$$c_i={\underset{v_j\in V(G)\cap j=1}{\sum}} a_j$$



Different from the conventional centrality measurements, this method generates the centrality index based on the local behaviors of the nodes and their interactions,employs a spreading activation mechanism which naturally fit the information diffusion process in social networks, The connectionist model adopts an efficient iterative distributed algorithm which consists of single-step information propagation within local neighborhoods only, regardless of the propagation path and the global network topology



Comments

There are no comment yet.

Add your comment

Name:
Email:
Sum of    and  

The rendering mode: