Int. J.

Advanced Networking and Applications 3669

Volume: 09 Issue: 06 Pages: 3669-3673 (2018) ISSN: 0975-0290

Bridging Centrality: Identifying Bridging Nodes

in Transportation Network
Prof. A.K. Baruah
Department of Mathematics, Dibrugarh University, Dibrugarh-786004
Email:[email protected]
Tulsi Bora
Department of Mathematics, Dibrugarh University, Dibrugarh-786004
Email:[email protected]
-------------------------------------------------------------------ABSTRACT---------------------------------------------------------------
To identify the importance of node of a network, several centralities are used. Majority of these centrality
measures are dominated by components' degree due to their nature of looking at networks’ topology. We propose
a centrality to identification model, bridging centrality, based on information flow and topological aspects. We
apply bridging centrality on real world networks including the transportation network and show that the nodes
distinguished by bridging centrality are well located on the connecting positions between highly connected
regions. Bridging centrality can discriminate bridging nodes, the nodes with more information flowed through
them and locations between highly connected regions, while other centrality measures cannot.

Keywords : Betweenness centrality, Bridging centrality, Bridging coefficient, Degree, Transportation network.
----------------------------------------------------------------------------------------------------------------------------- ---------------------
Date of Submission: April 12, 2018 Date of Acceptance: April 25, 2018
----------------------------------------------------------------------------------------------------------------------------- ---------------------
1. INTRODUCTION In this paper, we focus the network analysis to identifying
the central nodes to another new and important direction.
N ow a days Transportation network is an important part We introduce a new centrality measure called bridging
of our daily life. Transportation network can be centrality that successfully identifies the bridging nodes
represented as G(V,E), where V denotes vertices, E locating among densely connected regions.
denotes edges. If G consists of public bus systems, V
means all stations, E means all available lines between 2. OVERVIEW OF NETWORK CENTRALITY
stations. However, if the air transport systems or highway
systems of a country are expressed as G, V signifies all Our model, a transportation network as an undirected
cities of the country, E signifies all airlines or highways graph which is represented by (V, E) with node set V and
between cities. edge set E. Here V represents the stations and E represents
To study the transportation network is to identify the the connection between stations. We now define some
centralities in the network which represent the more existing network centrality measures used in different
critical nodes whose degrees of reliability have major network analysis.
impact to the network efficiency. Freeman[1] discussed
many centrality measures, designed to capture different 2.1 Degree Centrality : It is the simplest and the first
aspects of the centrality concept in the study of social measure of centrality .Degree centrality of a node v is the
network. He also discussed the betweenness[2] centrality number of connections of that node is defined as
as the total fraction of shortest paths between each pair of
vertices that pass through a given vertex. Woochang CD(v) = d(v)
Hwang et al.[3] discussed the bridging centrality on scale- 2.2 Betweenness Centrality : The betweenness centrality,
free networks. Bridging centrality provides an entirely CB(v), for a node v of is defined by:
new way of scrutinizing network structure and measuring
components importance. g v
CB(v) = ∑ ≠v≠ ϵv
This understanding guides traffic and transport engineers g

and planners to resolve many burning issues related to In the above equation, g is the number of shortest paths
traffic flow [4]. Therefore, “quantitative analysis and from node s to t and g (v) the number of shortest paths
modeling of traffic flow has become a hot topid few years, from s to t that pass through the node v.
empirical and theoretical studies of networks are the most
popular subjects of recent researches in many areas 2.3 Closeness Centrality : If we denote the shortest path
including technological, social, and biological fields. distance between two nodes i and j by d(i ,j), then the
Network theories have been applied with good success to closeness centrality of a node i is defined as
these real world systems and many centrality indices, 1
measurements of the importance of the components in a Ccls(i) = where d(i) = ∑ ∈V, ≠ d ,
d 𝑖
network, have been introduced [8,9,10].
Int. J. Advanced Networking and Applications 3670
Volume: 09 Issue: 06 Pages: 3669-3673 (2018) ISSN: 0975-0290

2.4 Bridging Coefficient : The bridging coefficient of a CR(v) = BC(v) x CB(v)

node is defined as where CR(v) is the bridging centrality.
1
𝑑 𝑣 3 METHOD
BC(v) = 1
∑𝑖∈𝑁 𝑣
𝑑 𝑖
where d(v) is the degree of node v and N(v) is the set of 3.1 Terminology and Representation
neighbors of node v.
Real world systems can be represented using graph
2.5 Bridging Centrality : Identifying important nodes in a theoretic methods. In this paper we focus on undirected
network structure is crucial for the understanding of the graphs. An undirected graph G = (V, E) consists of a set V
associated real-world system. A bridging node is a node of nodes or vertices and a set E of edges. An edge e(i, j)
lying between modules, i.e., a node connecting densely connects two nodes i and j where e(i, j) 𝞊 E. The neighbors
connected components in a graph. The bridging nodes in a N(i) of node i are defined to be a set of directly connected
graph are identified on the basis of their high value of nodes to node i. The degree d(i) of a node i is the number
bridging centrality relative to other nodes on the same of the edges connected to node i. A path is defined as a
graph. The bridging centrality of a node is the product of sequence of nodes (n1,...,nk) such that from each of its
the betweenness centrality (CB) and the bridging nodes there is an edge to the successor node. The length of
coefficient (BC), which measures the global and local a path is the number of edges in its node sequence. A
features of a node, respectively. shortest path between two nodes, i and j, is a minimal
Mathematically, length path between them. The distance between two
nodes, i and j, is the length of its shortest path.

Figure 1: A small synthetic network example.

Node Degree CB BC CR
1 4 0.655556 0.1 0.065556
2 2 0.533333 0.85714 0.457141
3 3 0.477778 0.22222 0.106172
4 3 0.211111 0.16666 0.035184
5 2 0.155556 0.85714 0.133333
6 2 0.155556 0.85714 0.133333
7 2 0.088889 0.5 0.044445
8 2 0.088889 0.5 0.044445
9 2 0.011111 0.5 0.005556
10 1 0 3 0
11 1 0 3 0

Table 1: Centrality values of Figure 1, including Betweenness centrality(CB), Bridging coefficient (BC) and Bridging
centrality (CR) .

Figure 1 and Table 1 clearly illustrates the significant of located on the center of a module not on a bridge which
bridging centrality. Although node 1 has the highest results in the lowest bridging coefficient value. In other
degree and betweenness value, nodes 2 , 5, and 6 have words, more number of shortest paths goes through node 1
much higher bridging centrality values since node 1 is than other three nodes, but nodes 2, 5, and 6 position on
Int. J. Advanced Networking and Applications 3671
Volume: 09 Issue: 06 Pages: 3669-3673 (2018) ISSN: 0975-0290

bridges much better. So, nodes 2, 5, and 6 have higher node 2 is taking a better bridging position than nodes 5
bridging centrality values since they are on the bridges and 6 are in Figure 1.
between modules which leads much higher bridging
coefficient values than node 1. Betweenness centrality 3.2 Application on Transportation network
decides only the extent how much important the node of
interest is from information flow standpoint, and it does Dispur is the largest city in Assam and one of the fastest
not consider the topological locations of the node. On the developing cities in India. With the rapid growth of
other hand, nodes 5 and 6 have the same bridging population in the city, the road traffic problems are also
coefficient value with node 2, but nodes 5 and 6 have increasing at an alarming rate. The development of a city
much less betweenness centrality values since far more or town leads to the growth of the number of vehicles
number of shortest paths passes through node 2 than which is directly linked to increased traffic congestion and
through nodes 5 and 6. Even though nodes 2, 5, and 6 are a growing number of accidents and fatalities. Road traffic
located on similar local topological positions, i.e., similar problems like congestion, unpredictable travel-time delays
local topological surroundings, node 2 is taking a much and road accidents are taking a serious shape in the city.
more important location than nodes 5 and 6 in the The main objective of this study is to analyze the potential
information flow viewpoint. Bridging coefficient measures of bridging centrality on transportation network, viz.
only the extent how well the node is located between Dispur city map. It is a well planned city and capital of
highly connected regions .Therefore we can think that Assam. We take 35 major bus stoppages of this Dispur
area to analyze the bridging nodes.

Figure 2 : Major bus stoppages of Dispur city.

Degree
Id Label CB d(v)-1 BC CR
d(v)

1 khanapra 1 0 1 2 0.5 0
2 Research Gate 2 0.05882 0.5 1.5 0.33333 0.01961
3 Garm gate 2 0.11408 0.5 1 0.5 0.05704
4 Dairy gate 2 0.16578 0.5 1 0.5 0.08289
5 Training Center 2 0.2139 0.5 0.75 0.66667 0.1426
6 six mile 4 0.42335 0.25 2 0.125 0.05292
7 Rukmini gaon 2 0.04556 0.5 0.75 0.66667 0.03038
8 PIBCO 2 0.04635 0.5 1 0.5 0.02317
9 Down town hospital 2 0.05704 0.5 0.75 0.66667 0.03803
10 Super market 4 0.4492 0.25 1.41667 0.17647 0.07927
11 Ganeshguri 4 0.22727 0.25 2.25 0.11111 0.02525
Int. J. Advanced Networking and Applications 3672
Volume: 09 Issue: 06 Pages: 3669-3673 (2018) ISSN: 0975-0290

12 Statefed 2 0.05882 0.5 1.25 0.4 0.02353

13 International Hospital 1 0 1 0.5 2 0
14 Houshing colony 1 0 1 0.33333 3 0
15 Public Health 3 0.07576 0.33333 2 0.16667 0.01263
16 forest gate 2 0.08645 0.5 0.66667 0.75 0.06484
17 Hengerabari 3 0.35116 0.33333 1.25 0.26667 0.09364
18 Borbari 2 0.2959 0.5 0.58333 0.85714 0.25363
19 Gymkhana club 2 0.2139 0.5 0.83333 0.6 0.12834
20 Jatiya 2 0.16578 0.5 1 0.5 0.08289
21 DHE 2 0.11408 0.5 1 0.5 0.05704
22 SB 2 0.05882 0.5 1.5 0.33333 0.01961
23 Forensic 1 0 1 0.5 2 0
24 Last gate 3 0.35027 0.33333 1.25 0.26667 0.0934
25 Housefed 2 0.13102 0.5 0.83333 0.6 0.07861
26 Wireless 2 0.10873 0.5 1 0.5 0.05437
27 Houshing 2 0.09804 0.5 1 0.5 0.04902
28 Survey 2 0.09626 0.5 0.83333 0.6 0.05775
29 Beltola Tiniali 3 0.22371 0.33333 1.5 0.22222 0.04971
30 AG 2 0.11408 0.5 0.83333 0.6 0.06845
31 Basistha Chariali 2 0.05882 0.5 1.5 0.33333 0.01961
32 Brahmaputra board HQ 1 0 1 0.5 2 0
33 Jayanagar 2 0.19341 0.5 0.58333 0.85714 0.16578
34 Romo's restaurent 1 0 1 0.25 4 0
35 Anandaram LPS 2 0.03922 0.5 0.58333 0.85714 0.03361

Table 2 : Centrality values of Figure 2, including Betweenness centrality (CB), Bridging coefficient (BC) and Bridging
centrality (CR)

4 DISCUSSION AND CONCLUSION Throughout the experiments we performed in this paper,

bridging centrality did a good job to find out the important
Theoretically, we see that Borbari (Id number 18) has bridging nodes in a real world network. Bridging centrality
higher bridging centrality than Jayanagar (Id number 33), has many possible applications on many research areas.
Training center (Id number 5), Gymkhana Club (Id The identification of the bridging nodes and information
number 19) and other places. So we select Borbari is a about the bridging nodes should be very valuable
important node among the clusters, though it has less knowledge for further fruitful achievements in other
betweenness centrality than other some places. From this researches and in other fields too.
we can design some special construction at that point such
that the increased of traffic congestion and a growing Bridging centrality has many potential applications in
number of accidents and fatalities are decrease, which is several areas. First, it can be used to break up modules in a
link to other cluster from this Dispur city region. network for clustering purpose. Second, it also can be used
to identify the most critical points interrupting the
information flow in a network for network protection and
robustness improvement purposes for networks etc.
Int. J. Advanced Networking and Applications 3673
Volume: 09 Issue: 06 Pages: 3669-3673 (2018) ISSN: 0975-0290

REFERENCES
[1]Freeman, L., C., Soc. Networks 1, 215 (1979).
[2]L.C. Freeman. A set of measures of centrality based on
betweenness. Sociometry, 40(1) : 35-41, 1977.
[3]Woochang Hwang et al. “Bridging Centrality:
Identifying Bridging Nodes In Scale-free Networks.”
KDD’06 August 20-23, 2006, Philadelphia, PA,USA.
[4]Noulas, A.; Scellato, S.; Lambiotte, R.; Pontil, M.;
Mascolo, C. 2012. A tale of many cities: universal patterns
in human urban mobility. In PloS one, Public Library of
Science, 7.
[5]Gao, S.; Wang, Y.; Gao, Y.; Liu, Y. 2013.
Understanding urban traffic f low characteristics: a
rethinking of betweenness centrality, Environment and
Planning B: Planning and Design. DOI:
http://dx.doi.org/10.1068/ b38141, 40(1): 135-153.
[6]Jun, C.; Kwon, J.H.; Choi, Y.; Lee, I. 2007. An
Alternative Measure of Public Transport Accessibility
Based on Space Syntax, Advances in Hybrid
Information Technology Lecture Notes in Computer
Science. DOI: http://dx.doi.org/10.1007/978-3-540-
77368-9_28,4413:281-291.
[7]Scheurer, J.; Curtis, C.; Porta, S. 2007. Spatial Network
Analysis of Public Transport Systems: Developing a
Strategic Planning Tool to Assess the Congruence of
Movement and Urban Structure in Australian Cities.
Available from Internet:
<http://abp.unimelb.edu.au/files/miabp/3spatil-network-
analysis.pdf>.
[8]M. E. J. Newman. A measure of betweenness
centrlality on random walks. arXiv:cond-mat, 1:0309045,
Sep 2003.
[9]M. C. Palumbo, A. Colosimo, A. Giuliani, and L.
Farina. Functional essentiality from topology features in
metabolic networks: A case study in yeast. FEBS Letters,
579:4642-4646, 2005.
[10]G. Sabidussi. The centrality index of a graph.
Pyschometrika, 31:581-603, 1966.

BIOGRAPHIES AND PHOTOGRAPHS

Prof. A.K. Baruah is a senior Professor in
the Department of Mathematics at
Dibrugarh University, Assam, India. He
did his Ph. D degree in Mathematics from
Dibrugarh University in 1989. His area of interest are
Numerical analysis and Differential Equation, Graph
theory and data structure, Mathematical modeling in
Traffic control problems using Graph theory. He guided
many M.Phil and Ph. D research scholar. He also acted as
a resource person in various mathematical programmes
and social activities. He has many publications in different
refereed journals of National and International repute.

Tulsi Bora is a Ph D research scholar of

Dibrugarh University, Assam. Presently
he is working as a Assistant Professor of
Mathematics at CNB College, Bokakhat.
His area of interest is Graph theory.