Modified Betweenness Centrality


This method proposes the modified betweenness centrality based on two node disjoint paths to identify relay nodes in the data network. The measure is expected to give a ranking on the possibility that each node is to be a relay one of a network. Modified Betweenness Centrality represented by $C_M(v)$ and defines as fallows:

$$C_M(v)={\underset{|S=2|}{\underset{S\in P(V^{'}\backslash \{v\})}{\sum}}} {\sum_{\psi \in \Psi_S} \delta_\psi (v)\over |\Psi_s|}$$

were $v\in p$ if a vertex $v\in V$ is included in a path $p$, $\psi= (p,p^{′})$ as a pair of two paths $p$ and $p^{′}$ that are composed of the same endpoints. $V^{'}$ is the endpoints set. Depending on the way to find a path pair of a couple of endpoints and the topology of the graph $G$, no pair may be found. Therefore, $\Psi_S$ is a set of $\psi$ able to be discovered between two endpoints $s$ and $t$, where a set $S = \{s,t\} (s,t \in V^{'}, s\ne t)$.

Betweenness centrality assumes that every pair of nodes interchanges a message with equal probability in equal time intervals. This assumption can be unsuitable for several types of networks. Though a relay node is considered to be located closer to the middle of a route along which two nodes exchange data each other, suggested betweenness centrality may not be able to recognize such. In addition, the original betweenness centrality does not take consideration on survivability because of single path connecting two nodes


  • Masaaki Miyashita and Norihiko Shinomiya. 2015, Modified Betweenness Centrality to Identify Relay Nodes in Data Networks. ACHI 2015 : The Eighth International Conference on Advances in Computer-Human Interactions. DOI: Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: