Miguel Dianne S V Medeiros
email: dianne@gta.ufrj.br

Elias M Campista

Nathalie Mitton
email: nathalie.mitton@inria.fr

Marcelo Dias De Amorim

Guy Pujolle
email: guy.pujolle@lip6.fr

Miguel Elias
email: miguel@gta.ufrj.br

M Campista

Weighted Betweenness for Multipath Networks

Keywords: Centrality metrics, graph, static and dynamic networks. Reduction of #Disconnections Node label Dist. Scaled Weighted

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Metrics from graph theory provide means to quantify the importance of a node in a system and, thus, help to identify nodes playing central roles. The importance of a node is often computed through centrality metrics [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF]- [START_REF] Wehmuth | DACCER: Distributed assessment of the closeness centrality ranking in complex networks[END_REF], which classify nodes according to their topological position in the network. It is very common to employ the betweenness centrality, a metric that considers the proportion of shortest paths a node falls on. The idea is that the more shortest paths a node participates in, the more the node is central [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF].

Centrality is important to many networked applications, such as election mechanisms and routing protocols. These applications often rely on shortest paths between sourcedestination pairs. Assigning importance to nodes based only on their participation in shortest paths, however, may lead to biased classifications. This could happen, for instance, when a node that falls on a number of shortest paths is classified as more important than another that falls on slightly fewer shortest paths, but on a multitude of quasi-shortest paths.

Several authors have already questioned the use of only shortest paths to quantify nodes' importance [START_REF] Freeman | Centrality in valued graphs: A measure of betweenness based on network flow[END_REF]- [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF]. We also believe that such a definition limits the metric applicability and propose a novel weighted betweenness centrality. This proposal extends the definition of the traditional betweenness to also include nodes that fall on quasi-shortest paths. In a nutshell, the computation of the weighted betweenness of a node υ k is based on the ratio between the length of the shortest path connecting a given pair of nodes and the length of the quasi-shortest path passing through υ k between the same pair of nodes. The idea is to give more importance to shortest paths and paths slightly longer than the shortest one. In addition, we scale the contribution of each path according to the ratio between the number of shortest paths and quasishortest paths between the pair of nodes. In order to bound the computation complexity, each path is only accounted if the difference between its length and the length of the shortest path is less or equal than a given parameter γ.

The impact of our metric is investigated using four network datasets. To this end, we compare the weighted betweenness with both the traditional [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] and the distancescaled betweenness [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF] metrics. We examine the node ranking for each metric and we investigate its behavior over time to analyze the impact on network stability. Our main findings are that the proposed metric (i) identifies nodes misclassified by the other two metrics, (ii) solves ties between nodes classified in the same position but that do not present the same importance to the network and (iii) potentially keeps more nodes with the ability of intermediating flows.

This paper is organized as follows. Section II presents all the notations and definitions used herein. Section III discusses the related work and overviews betweenness centrality. In Section IV, the problem is stated, while in Section V the proposed betweenness is introduced. The selected datasets are described in Section VI and the obtained results are shown in Section VII. Finally, Section VIII concludes this work and presents our future plans.

II. NOTATION AND DEFINITIONS

We model a network as an weighted graph G = (V, E, ω), where V and E are the sets of vertices and edges, respectively, and ω : V → R + is a weight function defined on its vertices. Each vertex υ i ∈ V and each edge ε i,j ∈ E represent, respectively, a node in the network and a link between a pair of nodes [υ i , υ j ]. Each edge has a weight ω i,j ∈ R + , that is the cost of the link. The edges ε i,j and ε j,i exist simultaneously if the network is symmetric. Following, we present important definitions to understand this work. Definition 1 Path: A path p (.) from a source υ i to a destination υ j is an ordered sequence of distinct nodes in which any consecutive pair is connected by a link.

A path p 1,L between the source, υ 1 , and the destination, υ L , has a total length of ∆L = L -1 hops, with L ∈ N * , and is given by p 1,L = υ 1 , υ 2 , ..., υ L-1 , υ L , where {υ 1 , υ 2 , ..., υ L-1 , υ L } ⊆ V and {ε 1,2 , ..., ε L-1,L } ⊆ E. The shortest path, or geodesic, between these nodes is the one where ∆L is the smallest possible value, ∆L * . Definition 2 Quasi-shortest path: The path is quasishortest if ∆L -∆L * ≤ γ.

Parameter γ serves to limit the stretch of quasi-shortest paths and avoid the explosion of the number of possibilities. Furthermore, given p * 1,L , it is not reasonable to consider as useful those paths for which ∆L ≫ ∆L * .

More than one path may exist between a pair of nodes, either shortest or quasi-shortest. Therefore, the number of geodesics from υ 1 to υ L is denoted by n * 1,L and the number of quasi-shortest paths is n 1,L . Since we rely on the number of hops for path computation, a quasi-shortest path has always a greater number of intermediate nodes.

Definition 3 Path cost: The cost of a path p (.) between a pair of nodes is obtained from the number of hops connecting them.

We use the number of hops as the cost metric, such that the shortest path is the geodesic, represented by p * 1,L . The cost of p * 1,L is δ * 1,L , while the cost of the quasi-shortest path between the same pair of nodes is δ 1,L ≥ δ * 1,L . Note that if we consider an intermediary node υ k , the path cost can be always computed as the sum δ * 1,k + δ * k,L , independently of whether υ k falls on the geodesic.

III. REVISITING THE BETWEENNESS CENTRALITY

The betweenness centrality expresses the influence that a specific node could have on other nodes in the network. It is based on the computation of the number of geodesics a node is part of, considering all possible pairs of nodes in the network. Nevertheless, accounting only geodesics can limit the metric [START_REF] Opsahl | Node centrality in weighted networks: Generalizing degree and shortest paths[END_REF], [START_REF] Freeman | Centrality in valued graphs: A measure of betweenness based on network flow[END_REF]- [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF]. For instance, in a weighted graph, the shortest path is not always the path that costs less. Therefore, we cannot use the traditional betweenness to quantify node importance. Freeman et al. [START_REF] Freeman | Centrality in valued graphs: A measure of betweenness based on network flow[END_REF] and Opsahl et al. [START_REF] Opsahl | Node centrality in weighted networks: Generalizing degree and shortest paths[END_REF] tackles this issue by considering the link weight in the computation.

Newman [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF] uses another approach to handle the problem of accounting only shortest paths. The author advocates that information does not travel only through shortest paths, either because the shortest path is not known in advance or it does not exist, as a specific destination is not determined. Newman proposes then the random walk betweenness, in which both shortest paths and non-shortest paths are accounted for. Borgatti et al. [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF], in turn, argue that information tends to concentrate on shorter paths and propose the distance scaled betweenness, in which the contribution of each path is inversely proportional to its length.

This work also shares the same rationale of previous works -information does not necessarily travel through shortest paths. Nevertheless, our approach differs by proposing a closed expression for a weighted betweenness, which does not only consider shortest paths, but also paths longer than the shortest one up to a γ value. This would avoid the metric to take into account all possible existing paths in the network. The following subsections review the formal definition of traditional and distance-scaled betweenness, selected for comparison with our proposal.

A. Traditional betweenness centrality

Traditionally, the betweenness is defined for unweighted graphs, and it can be used in symmetric or asymmetric graphs. Its formal definition is given by:

b(υ k ) = |V| i=1 i =k |V| j=1 j =i j =k n * i,j (υ k ) n * i,j , (1)
where n * i,j (υ k ) is the number of geodesics between υ i and υ j which have υ k as intermediary node. Note that to be considered as geodesic, a path p 1,L must cost δ * 1,L . Therefore, any path with cost higher than δ * 1,L is ignored and n * i,j (υ k ) = 0, nullifying the term in the summation.

B. Distance-scaled betweenness centrality

The idea here is to make the contribution of each path inversely proportional to its length, assigning different importance to each path considered in Equation 1. Its formal definition is given by Equation 2.

b λi,j (υ k ) = |V| i=1 i =k |V| j=1 j =i j =k 1 ∆L × n * i,j (υ k ) n * i,j • (2)

IV. MOTIVATING EXAMPLE AND PROBLEM STATEMENT

The traditional betweenness frequently ignores nodes apparently important to the connectivity of the network. This happens because the metric traditionally uses only shortest paths to define the importance of nodes. This problem is illustrated in Figure 1, in which υ c is one of the main nodes responsible for maintaining the blue and green components connected. If it fails, υ p should replace the role of υ c , since it would be then the responsible for the connectivity of a greater component. In the traditional betweenness, however, the centrality of υ b is greater than the one of υ p because it connects υ f to all the other nodes in the network, despite υ b not being able to keep both components connected. Considering network connectivity, the presence of alternative paths not taken into account can represent, depending on the application, under-utilization of available resources.

In the Freeman's graph (Section VI), several paths exist in the network, but they can be underutilized when only geodesics are considered. We can have an idea of the number of paths neglected due to the traditional definition of betweenness if we compute the difference between the geodesic length, with cost δ * i,j , and the quasi-shortest path intermediated by υ k , p i,j (υ k ), with cost

δ i,j = δ * i,k + δ * k,j . If (δ * i,k + δ * k,j ) -δ * i,j = 0, then υ k belongs to a geodesic. This difference is referred to as ∆ = (δ * i,k + δ * k,j ) -δ * i,j
, which is upper bounded by γ.

Figure 2 shows the ∆ distribution for Freeman's graph. The X, Y -axes represent, respectively, the intermediary node and all possible values of ∆ for this node. The color scale indicates the relative frequency of occurrence for a given ∆, such that higher frequencies are darker. We observe in Figure 2 that ∆ > 0 frequently happens and, furthermore, less than 20% (0 ≤ ID ≤ 5) of nodes often fall on shortest paths. We can conclude that a significant number of nodes may never intermediate a communication due to the traditional definition of betweenness, assuming that only shortest paths are used.

Figure 3 shows how frequently we can find a given distance in Freeman's graph. In general, we note that ∆ = 1 and ∆ = 2 happen more often than ∆ = 0, while the maximum value ∆ = 4 is negligible. This indicates that nodes in quasi-shortest paths should be considered when computing betweenness, but only those falling in paths slightly longer than the geodesic.

V. WEIGHTED BETWEENNESS CENTRALITY

Our goal is to capture the potential of intermediate nodes, even when they do not belong to a geodesic, possibly revealing nodes that are ignored by the traditional vision of betweenness. To this end, we propose the weighted betweenness centrality, which considers both geodesics and longer paths upper bounded by a parameter γ. The contribution for the metric is proportional to the ratio between the number of shortest and quasi-shortest paths connecting [υ i , υ j ]. In addition, the metric considers the length of the paths, unlike the traditional betweenness.

While the traditional betweenness considers the ratio n * i,j (υ k )/n * i,j , which is based on the number of geodesics, the weighted betweenness considers the ratio between the lengths of the geodesic and the quasi-shortest path between [υ i , υ j ] when passing through υ k . As a consequence, the ratio between the aforementioned costs is defined as

δ * i,j /(δ * i,k +δ * k,j
) and if it is greater than γ, the quasi-shortest path is ignored. Note that using the number of hops does not limit the metric, which can be generalized to use other types of link weight.

Figure 4 shows the difference between all three approaches using the number of hops to compute the path cost. In Figure 4(a), node υ k belongs to one of two geodesics between [υ i , υ j ]. Thus, for the traditional and distance-scaled betweenness, we have n * i,j (υ k )/n * i,j = 1/2, and for the latter metric we still multiply this ratio by 1/∆L * = 1/4. In Figure 4(b), υ l falls in a quasi-shortest path between the same nodes. While both traditional and distance-scaled approaches ignore the potential of this node for the pair [υ i , υ j ], our metric considers the ratio δ * i,j /(δ * i,l + δ * l,j ) = 4/5. To account for multiple paths with equal lengths intermediated by υ l , the ratio between the costs is scaled by the number of such paths. The idea is to assign more importance to quasishortest paths if they are proportionally less numerous than shortest paths. In opposition, the importance is reduced if they are proportionally more numerous than the number of shortest paths. Table I compares the betweenness centralities computed for nodes υ c , υ b , and υ p in Figure 1, according to the traditional, distance scaled, and the proposed weighted betweenness, considering only 5 nodes totally connected in both green and blue networks. The weighted betweenness can capture better the centrality of the nodes, even if they do not belong to several geodesics. This result could also be used, e.g., to determine which node could be used for load balancing or to aggregate data from sensor networks.

We formally define the proposed metric for node υ k , w(υ k ), as:

w(υ k ) = |V| i=1 i =k |V| j=1 j =i j =k n * i,j n i,j (υ k ) × δ * i,j δ * i,k + δ * k,j , (3)
where n * i,j is the number of geodesics between [υ i , υ j ], and n i,j (υ k ) is the number of paths with the same length of the quasi-shortest path p i,j (υ k ). The weighted betweenness as defined by Equation 3 is computed for pairs of nodes in the same component. In case of distinct components, the contribution is null.

Both superior and inferior limits for the proposed metric depend on the relation between the number of paths, and between the cost of the paths. The inferior limit further depends on the parameter γ. In the worst case for the inferior limit,

if n i,j (υ k ) ≫ n * i,j or if δ * i,k + δ * k,j ≫ δ * i,j
, the corresponding term will tend to zero. The superior limit, in turn, can be equal to 1 when the quasi-shortest path is, in fact, a geodesic, or equal to

n * i,j × δ * i,j /(δ * i,k + δ * k,j
), if only one quasishortest path exists. As the weighted betweenness considers paths slightly longer than the geodesic, accounting all quasishortest paths between a pair of nodes intermediated or not by υ k can become unfeasible. Therefore, the parameter γ limits the Depth-First Search (DFS) algorithm used in this work, reducing its complexity.

Finally, the weighted betweenness requires the previous knowledge of the path costs, which can be infinite for disconnected components. As a consequence, the metric is computed only for nodes from the same component to avoid problems related to infinite costs. In this case, the contribution to the betweenness is considered null.

VI. DATASETS

In order to maintain the generality of the metric, we use four datasets with distinct characteristics to evaluate the weighted betweenness centrality proposed in this work.

• Freeman's EIES: presents the relationships in a group of 32 academics [START_REF] Freeman | The Networkers Network: A Study of the Impact of a New Communications Medium on Sociometric Structure[END_REF]. A directed edge between two nodes [υ i , υ j ] exists only if υ i has sent a message to υ j , totaling 460 links.

• Dolphins: provides the association relationship between 62 dolphins in Doubtful Sound, New Zeland [START_REF] Lusseau | The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[END_REF]. Each node corresponds to a dolphin and the interaction between them is represented by an undirected edge ε i,j , totaling 159 links. • PhD Students: it is a network of relationships between 1,025 PhD students and supervisors [START_REF] Johnson | The genealogy of theoretical computer science[END_REF]. A directed link exists from υ i to υ j if υ i is the supervisor of υ j , totaling 1,043 links. • TAPASCologne Dataset: it models the vehicular traffic in the city of Cologne, Germany [START_REF] Uppoor | Large-scale urban vehicular mobility for networking research[END_REF]. We use 10 samples of the original subset, containing 1,584 to 1,916 nodes and 1,573 to 2,044 undirected links. Each node is a vehicle and an edge exists between them if they are less than 50 meters away from each other.

VII. RESULTS

In this section, we present the impact of our metric on the selected datasets. We use γ = 3, since for the Freeman's graph a ∆ ≥ 4 is not frequent. Thus, we account quasishortest paths for which ∆L ≤ ∆L * + 3 or δ i,L ≤ ∆L * + 3.

Our first goal is to analyze the behavior of the ranking obtained for each metric. Following, we investigate the impact of the proposed metric on the stability of network. Note that in our results we consider that nodes with the same value of betweenness are tied in the same position.

A. Impact on the node ranking

We investigate the ranking variation for the distance scaled betweenness and our metric, through analysis of the node position gain for each metric in relation to the traditional betweenness. A positive gain implies centrality increase, whereas a negative gain indicates the opposite. Figure 5 shows that both metrics are able to modify the classification of nodes. In Figure 5(a), the X-axis is organized according to the traditional betweenness classification for the Freeman dataset, with "Lin Freeman" as the most central node. We observe that our metric modifies the classification of some nodes, specially those that are in lower positions, indicating that the traditional betweenness can underestimate the centrality of nodes that do not participate in many - (b) Dolphins. geodesics. For instance, "John Boyd" gains 10 positions according to the proposed metric. In addition, "Gary Coombs", "Brian Foster", and "Nick Poushinsky" which are tied with null traditional and distance-scaled betweenness are, in turn, reclassified in new positions according to the weighted betweenness. We emphasize these nodes with vertical arrows at the plot. The reclassification is also observed for the Dolphins dataset, as shown in Figure 5(b). Several nodes are demoted and promoted using both metrics. Once again, a significant number of nodes classified in lower positions are reclassified by our metric, while the distance scaled betweenness barely modifies the ranking. Further, nodes that were once tied with null betweenness (from node "Cross" downwards) are redistributed in the ranking.

Figure 6 shows the cumulative distribution functions for all three metrics. The betweenness value was normalized by the maximum value found for the dataset, allowing all metrics to be plotted using the same range in the X-axis. In Figure 6(a), the curves for the traditional and distancescaled betweenness are coincident, corroborating the results illustrated in Figure 5(a), where the position gain related to the distance-scaled betweenness is null. Further, we observe that approximately 40% of the nodes have low or no importance to the network, whereas our metric assigns low or no importance to only less than 5% of nodes. We observe the same behavior in Figures 6(b their respective students and only a few nodes represent both roles, originating many leaf nodes with null betweenness. In addition, as multipaths barely exist in this network, all three metrics equivalently capture the centrality for most nodes.

B. Impact on the number of network disconnections

From our results so far, we could note that the weighted betweenness is able to reclassify nodes that apparently should be given more importance. The main idea of our metric, however, is to reduce the number of disconnections in networks with dynamic topology. In this direction, we claim that the number of disconnections can potentially increase if the number of nodes with zero betweenness grows. Nodes with betweenness zero are not part of any path and, therefore, cannot intermediate communications. In this sense, we took 10 samples from the TAPASCologne dataset, each 10 seconds, to investigate the behavior of the disconnections for all three metrics. Figure 7(a) shows how often disconnections happen in our samples. The X-axis is the number of disconnections, whereas the Y -axis shows the frequency in which the number of disconnections happen during the interval provided by the 10 samples. If x = 0, no disconnection happened in the time interval and, if x = 10, nodes were never connected. The frequency in which nodes never disconnected is much higher for our metric compared to the other two. Disconnections become more frequent for x > 0, but the growth rate for our metric is lower than for the others. When x = 8, the frequency for the other metrics becomes greater than for the weighted betweenness.

To verify if the reduction of the disconnections also benefits the most important nodes, we analyze the variation of the number of disconnections for the initial top 20 nodes. In Figure 7(b), the X-axis represents the node label, also organized according to its importance. The Y -axis indicates the difference between the number of disconnections for the distance-scaled and weighted betweenness compared to the traditional betweenness. We observe that for the top-20 nodes, the distance-scaled betweenness does not avoid any disconnection. The weighted betweenness, however, is able to avoid up to 3 disconnections for half of these nodes.

VIII. CONCLUSIONS

We propose a novel weighted betweenness centrality metric, a variation of the traditional betweenness. Our goal is to also assign importance to nodes that not necessarily fall on shortest paths, but can still be considered critical to keep the network connectivity. To assess the impact of the metric, we analyzed four datasets with distinct characteristics, for which we also computed the traditional and the distance-scaled betweenness. We observed that, whereas the traditional and the distance-scaled metrics lead us to think that nodes tied in the ranking have the same centrality in the network, the weighted betweenness shows that this is usually not true, since they can participate in several quasi-shortest paths. Our metric can potentially avoid network disconnections by more frequently assigning weights to participating nodes. As future work, we plan to verify the influence of the parameter γ and extend the metric to weighted networks.

Figure 1 .

 1 Figure 1.Example of network in which the traditional betweenness centrality elects υ b as more important than υp, even considering the connectivity of the greater component.

Figure 2 .

 2 Figure 2. Distribution of the difference between the lengths of the geodesic and the paths that traverse any intermediary node in Freeman's graph.

Figure 3 .

 3 Figure 3. Distribution of parameter ∆ for Freeman's graph.

Figure 4 .

 4 Figure 4. The traditional and distance-scaled betweenness are based on the number of paths, whereas the weighted betweenness uses the cost of such paths. The difference between both approaches is highlighted when an intermediate node is part of a quasi-shortest path.

Figure 5 .

 5 Figure 5. Position gain in relation to the ranking provided by the traditional betweenness compared with the distance-scaled betweenness.

  Figure6shows the cumulative distribution functions for all three metrics. The betweenness value was normalized by the maximum value found for the dataset, allowing all metrics to be plotted using the same range in the X-axis. In Figure6(a), the curves for the traditional and distancescaled betweenness are coincident, corroborating the results illustrated in Figure5(a), where the position gain related to the distance-scaled betweenness is null. Further, we observe that approximately 40% of the nodes have low or no importance to the network, whereas our metric assigns low or no importance to only less than 5% of nodes. We observe the same behavior in Figures6(b) and 6(c).

Figure 6 (

 6 Figure 6(d) shows a singular behavior for the cumulative distribution of betweenness for the PhD Students dataset. All three curves are practically coincident. This happens because the PhD Students network is a directed graphs with many vertices that never, or almost never, would intermediate communications, since most edges connect supervisors to

Figure 6 .

 6 Figure 6. Cumulative distribution of normalized betweenness computed for the four datasets using all three metrics.

  Frequency of disconnections. (b) Number of disconnections for the top-20 nodes.

Figure 7 .

 7 Figure 7. The proposed weighted metric is able to reduce the number of disconnections in the network compared with the other metrics.

Table I COMPARISON

 I BETWEEN THE THREE METRICS FOR NODES IN FIGURE 1.

	Node Traditional	Distance Scaled Weighted
	υc	48	9.4	53.1
	υp	8	2.2	67.8
	υ b	15	3.5	15.0

ACKNOWLEDGMENT

The authors thank CNPq, CAPES, and FAPERJ for their financial support.