Extrema Analysis of Node Centrality
in Weighted Networks

Centrality assessment is a branch of study that emerged from complex network analysis and, in short, targets to indicate how important nodes of a network are to its structure. In practical terms, this can mean identifying influential people in online social applications [1], analyzing good routes in urban transportation networks [2], or even understanding which proteins can be considered essential for protein-protein interactions in a cell [3]. Three centrality measures are considered the most classic: degree, closeness, and betweenness. They were originally developed for networks in which relationships are binary, i.e., there is or not a connection between any pair of vertices [4]. But there are networks with numerical weights attached to the connections, quantifying some characteristic of these: e.g., distance, intensity, capacity, or cost. Likewise, several centrality measures also have been proposed with the latter type of network in mind.

Some of these [5] were proposed with the objective of incorporating concomitantly the number of connections – as originally intended in this regard – and the weights associated with them, allowing to regulate the relative importance given to each of these attributes. This dual description is relevant since in graphs that represent internet traffic, for example, for paths that have the same distance or cost, the quality of resources flowing through more intermediate nodes tends to be worse than with fewer of them. The measure, then, allows setting this kind of situation. Moreover, there can be several other situations in which such a tuning makes centrality assessment more assertive. Thus, the present work sought to extend such previous developed adjustable centrality generalizations to weighted networks, trying to obtain more polished and secure understanding of the information they provide.

This paper details multiple contributions to the literature in the field of the just mentioned subject. The first of which is the establishment of adjustable centrality measures based on the logarithm of the ratio between weighted and unweighted centralities, which possess quite interesting properties. This serves as the cornerstone to the evaluation of how wide is the range encompassing all possible node rankings defined for a perspective of centrality varying the importance of edge weights in this regard, which can be interpreted as proxy to the assessment of weights relevance to network structure. One last part of this whole is an algorithm to realize such a evaluation without relying on a brute-force approach, as well as a formal proof of its predicates.

The following sections, which complete this research report, are enumerated and summarized next. Section 2 establishes the theoretical foundations on which this work was built. Section 3 provides a brief systematization and analysis of previously proposed node centrality measures which allow edge weights influence on their computations to be calibrated. An alternative methodology to such indexes which overcomes some of their weakness is introduced in section 4. While section 5 shows how this methodology can be extended to allow analyzing weighted networks from so far unexplored point of view, section 6 formally describes how this can be efficiently realized. Section 7 details the application of the herein proposed ideas in a variety of practical scenarios. At last, section 8 brings some finishing remarks and points possible continuations.

A (simple, undirected) graph or network $G=(V,E)$ is a structure defined by the elements of set $V$, called vertices or nodes, which may have pairwise relationships, named edges, ties or links, that compose the set $E\subseteq\binom{V}{2}$. A node $u$ is adjacent to a node $v$ if there is the edge $e=\{u,v\}\in E$. A path between nodes $u$ and $v$ is a non-repeating sequence of nodes starting with $u$ and ending with $v$, or vice-versa, in which every two neighboring entries in the sequence are adjacent nodes in the network. The number of edges traversed in a path is its length. If there is a path between every pair of vertices, the graph is connected. There are also weighted or valued graphs, whose edges have a numerical value associated to each of them. These can be denoted as $G=(V,E,w)$, where $w:\binom{V}{2}\to\mathbb{R}$. In numerous situations such values are strictly positive, what is also assumed in the remainder of this text. As a consequence, it can be conveniently assumed that if $e\not\in E$, then $w(e)=0$.

The degree centrality refers to the number of edges incident upon a node:

This index covers only the influence of the nodes from a local perspective on the graph. On the other hand, the closeness centrality is the inverse of the total geodesic distance of one node to all the others (relying on the assumption that the graph is connected, which is not strictly necessary [6]). Between two nodes $u$ and $v$ the distance $dist(u,v)$ is the length of the shortest path between $u$ and $v$. The closeness, then, is formalized as:

The two Freeman’s measures [4] just presented were originally proposed for unweighted graphs. Based on them some generalizations were developed with valued networks in mind. In this regard, Barrat et al. [7] extended the notion of degree of a node to what was called strength, defined by the sum of the weights of all edges incident in it:

Newman [8] introduced the closeness to weighted networks based on Dijkstra’s shortest path algorithm [9]. In this method, the length of a path is the sum of the weights of each tie in it. The minimum length of a path between nodes $u$ and $v$ taking weights into account is denoted by $dist_{w}(u,v)$. With the notion of distance aligned with this approach, the weighted closeness centrality is:

It should be noted that Dijkstra’s algorithm was designed for graphs in which weights have a negative connotation, i.e., the shortest paths have the least accumulated weight. Thus, when the weights concern positive relations (e.g., affinity, capacity, similarity), their multiplicative inverses are commonly used for shortest path evaluation [5].

To evaluate or compare non-trivial properties of networks, random graphs [10] with specific characteristics can be used. A key model in this sense is the Erdős-Rényi (ER) [11], whose notation $G(n,p)$ represents a graph that has $n$ vertices and $p$ is the probability of each pair of vertices to be connected by an edge. Although edge weights are not incorporated by the original ER model, it has been taken as the basis of others which include this feature. Given an ER graph, the possibly simplest way to obtain its weighted version is to assign to each link a value randomly defined according to an uniform probability distribution [12], for example. Another ER-based weighted model, with quite interesting properties, is the WRG [13], implemented by having the edge weights assigned according to a Geometric distribution which uses the value of $1-p$ as its parameter.

The random models just referred to, especially the ER, are sometimes seen as lacking practical usefulness since their properties are not aligned with those observed in some remarkable real-world networks, considered as “more complex” [14]. Accordingly, alternatives that keep some features of a given network and randomize other aspects of it have been developed. A method that preserves node degrees while alters network topology is based on pairwise edge switching [15]. It consists of performing the following procedure a sufficient number of times: randomly choose two edges $\{a,b\}$ and $\{c,d\}$; then swap their ends to form the edges $\{a,d\}$ and $\{b,c\}$. A weighted version of this idea was previously used [16], which preserved edge weights distribution but not node strengths or network topology. Other models that only shuffle the edge weights, conserving topology [7, 16], or that randomize node degrees and edge weights while the node strengths remain unchanged [17] are also known.

The study of topological properties of complex networks has evolved over time and is ultimately important because these attributes are responsible for defining their functionality. For example, the structure of a social network affects the propagation of information or diseases in it, and the topology of a electrical grid changes supply robustness and stability [18]. Often, individual nodes assume a key function in this regard (e.g., people with great influence, large power stations) and, consequently, it is desirable to identify these nodes. That is the purpose of the centrality measures [19]. The versions of degree and closeness centralities presented in the section 2 take into account a single feature of the connections to determine node centrality: the number of links or, leaving aside the former, the sum of edge weights.

More recently, some centrality indices for weighted networks have approached this goal of incorporating both tie features simultaneously. Laplacian centrality [20] and the WKPN algorithm [21] have tried to merge local and global characteristics of the vertices to assess their importance. The former is based on 2-walks in which a node participates. The latter considers single-source shortest paths with $K$ edges, where the analyzed node is the spread source in a infectious disease model. The h-degree index [22] of a node displays only a local perspective and is defined as the greatest value $d_{h}$ so that a node has at least $d_{h}$ edges and the weight of each of them is greater than or equal to $d_{h}$.

Compared to the previous ones, the measures proposed by Opsahl et al. [5] are more adaptable, in terms of balancing the relative importance given to edge weights and counts. Such a statement is based on their use of a tuning parameter $\alpha$. Aiming at a local perspective, the degree (1) and strength (3) of a node are combined to define a new version of degree centrality as follows:

A similar approach was later applied to the weighted k-shell decomposition method [23]. In addition, some of the subsequent works include the analysis of node centrality in an online social network under the variation of $\alpha$ [24], and an attempt to find an optimal value for such a parameter [25]. An alternative closeness centrality, however, is based on weighted distances calculated on the graph obtained from the original by raising each edge weight to $\alpha$, represented by $dist_{\alpha}(u,v)$:

For both measures, when $\alpha=0$, the same results of Freeman’s original measures are produced, disregarding weights. Whereas when $\alpha=1$, the outcome corresponds to the generalizations for valued networks.

Besides the intrinsic differences regarding node reach in the network, Opsahl’s measures differ with respect to the type of summarization [26] each of them employ. In expression 5, both degree and strength are calculated in their original form, and the tuning parameter used to offset the product of these values, similarly a geometric mean. In expression 6, $\alpha$ is used to directly alter edge weights as a power to their exponentiation, which are then summed for shortest path computations, resembling the p-norm of a vector. Targeting to clarify such a discrepancy, these measures are herein identified with labels prod (product) and sum, instead of as originally denoted: $C_{D}^{w\alpha}(u)$ and $C_{C}^{w\alpha}(u)$, respectively.

Moreover, such an approach favors considering other combinations of the available parts. Therefore alternatives to Opsahl’s degree and closeness centralities could be defined as follows, respectively:

Both pairs of adjustable degree and closeness centralities produce the same results when $\alpha$ is 0 or 1. Table 1 provides a qualitative description of the behavior of the measures when the parameter is outside the range defined by the just mentioned benchmark values.

Now consider the graph presented in figure 1. In order to exemplify the distinguishable behavior of measures with distinct types of summarization, figure 2 shows how the node rankings derived from prod (5) and sum (7) degree centralities vary according to the value assigned to $\alpha$. It is interesting to remark that the majority of rank changes occur outside the unit interval, suggesting that analyses restricted to it may not take full benefit of these indexes. And as a demonstration of their unique aspects, it can be seen that node $C$ leaves the last place as $\alpha$ grows in the prod method – while in sum it occupies the same position in the entire interval – indicating its greater accumulated strength, concerning the number of ties, compared to the others. Node $A$ in the sum measure, however, occupies the second position at both extremes since its links have both the minimum and maximum edge weights. Despite their particularities, in specific conditions the measures may coincide, as indicated in proposition 1.

Opsahl’s measures have different methods of calculation from which it was presented a twofold description of adjustable degree and closeness centralities, which were subsequently compared. There is, however, a common thread in the four expressions: all of them are adjusted using exponentiation. For this reason they are notably susceptible to floating-point errors [27, 28] such as overflow or underflow, possibly combined with loss of significance, thereby limiting the range of the $\alpha$ parameter in order to enforce numerical computability. To quantify that, consider the widely used IEEE 754 [29] double precision format, in which 11 of 64 bits are reserved for an exponent field to hold a value whose magnitude is not greater than 1024. As a consequence, real numbers whose absolute value is outside the interval $[2^{-1024},2^{1024}]$ cannot be properly represented in this format.

Hence, safe intervals of $\alpha$ can be established for the measures: let $G=(V,E,w)$ be an hypothetical graph; let $B$ be the set of values which could be bases for exponentiation by $\alpha$ during the computation of one of the centrality indexes for vertices of G; let $b=\max\{(\min B)^{\ -1},\ \max B\}$; then such a interval is defined as $S=\left[\log_{b}2^{-1024},\ \log_{b}2^{1024}\right]$. The definition of $B$ goes as follows: for $C_{D}^{prod,\alpha}$, $B=\{k_{u}:u\in V\}\cup\{s_{u}:u\in V\}$; for $C_{D}^{sum,\alpha}$ and $C_{C}^{sum,\alpha}$, $B=\{w(e):e\in E\}$; and for $C_{C}^{prod,\alpha}$, $B=\{C_{C}(u):u\in V\}\cup\{C_{C}^{w}(u):u\in V\}$. At last, as a slight abuse of notation, hereinafter the following expression is used to denote the length of a real interval, like $S$: $|S|=\max S-\min S$.

The method presented depends on the floating-point model employed, but its utility remains as long as arithmetic precision is finite. Moreover, it is important to notice that setting $\alpha$ respecting its safe interval can be seen as a necessary but not sufficient condition for numerical computability: after all, the values exponentiated by $\alpha$ are then used in other arithmetic operations.

Although it is possible to determine safety parameters, such a range may be quite narrow, up to the point that its consideration disables $\alpha$ flexibility and, consequently, usefulness. A better approach in this sense can be obtained by taking the logarithm of the indices adjustable via product. This leads to a third pair of measures, defined as follows:

Such an approach preserves the benchmarks for $\alpha$, although the classical values of degree and closeness come to be in logarithmic fashion instead. Furthermore, comparability of the centralities remains unchanged, as the logarithm is a monotonic function. So the standings in figure 2 for the prod and log methods are the same. This also reverberates on figure 3: due to the linear variation, the centrality is equalized across the parameter interval, making the entire ranking and proximity of quantities easily discernible. Another relevant feature of the log-based measures is the enhanced flexibility for $\alpha$, since safe intervals become relatively unrestricted compared to those of exponential indices.

Section 4 introduced the idea of safe intervals for parameter $\alpha$, aiming at assuring numerical computability of the centrality indexes in question, and showed how the proposed measures $C_{D}^{log,\alpha}$ and $C_{C}^{log,\alpha}$ are superior to its counterparts in this regard. However in practice the entire safe intervals may not be functional: for example, there can be upper bound on $\alpha$ after which the node centrality ranking defined according to $C_{D}^{log,\alpha}$ remains unaltered; if the smallest value for such a bound is known, setting $\alpha$ beyond it can be considered senseless. This reasoning enables the definition of a useful interval, denoted as $U$, according to the first and last change points of the ranking. This section details how these intervals can be interpreted, and related to some well-known network global measures.

How these useful intervals can be understood is the first topic to be addressed because it also provides some motivation for their establishment. Varying parameter $\alpha$ allows to observe the same graph from different points of view, which can be materialized in the form of node centrality rankings, as already illustrated in figure 2. Therefore the most straightforward application of useful intervals is to avoid looking for such alternative perspectives where there is none. But a more interesting possibility comes from evaluating how narrow the interval is, as an estimate how condensed are these perspectives, and how smooth is the transition between them. Since these transitions are solely due structural distinctions between the nodes which are reflected by benchmark centralities (i.e., when $\alpha\in\{0,1\}$), the interval length can be seen as an indicator of node uniqueness in this sense.

For a better comprehension of the information provided by interval length, consider the following analyses of two degenerate cases:

• 1.

  Let $G=(V,E,w)$ be an hypothetical graph, such that $\forall e\in E,\ w(e)=1$ and $\exists\{u,v\}\subset V,\ k_{u}\not=k_{v}$. In this scenario, $\forall u\in V,\ C_{D}(u)=C_{D}^{w}(u)=k_{u}$ and, therefore, $\forall u\in V,\ \forall\alpha\in\mathbb{R},\ C_{D}^{log,\alpha}(u)=\log k_{u}$. In other words, the node ranking with respect to degree centrality would be the same regardless of $\alpha$. Consequently $U_{D}=(-\infty,+\infty)=\mathbb{R}$, as there is no upper or lower bound on the value of $\alpha$ for delimiting changes in such a ranking. This reflects how similar the nodes are considering the influence of edge weights on their centrality statuses.

• 2.

  Now let $G=(V,E,w)$ be another hypothetical graph, such that $\forall\{u,v\}\subset V,\ k_{u}=k_{v}$ and $\exists\{u,v\}\subset V,\ s_{u}\not=s_{v}$. In this case, the only change point in node ranking with respect to degree centrality is when $\alpha=0$, what leads to determining $U_{D}=[0,0]$. Since all nodes have the same degree but not the same strength, the range of $\alpha$ which allows multiple perspectives of the graph is minimum, as the importance of edge weights on switching between these perspectives is maximum.

How wide the useful intervals are depends on network global structure, and provides a feedback which is global as well. The relevance of edge weights to such a structure was previously ruled as of lesser importance relatively, considering a comparison between nodes degrees and strengths [30]. Despite the soundness of such a statement, having the means to concretely evaluate this is quite advantageous, since there is also the indication that such a difference in informativeness varies according to the network in question. As an example, Small-world-ness [31], another graph global measure, was developed with the same target of quantifying an until then imprecise concept. However, Small-world-ness as well as the majority of the most popular graph global measures [32, 33, 34] are unrelated to edge weights, leaving a blank this work targets to fill to some extent.

As previously stated, a useful interval of $\alpha$ for a certain centrality index is determined by the lowest and highest values of $\alpha$ which lead to changes in the node ranking defined according to that index. Such changes can be easily identified in a diagram like figure 3 since they happen whenever there is an intersection between any pair of non-coincident lines. Therefore determining useful intervals for the log-based measures comes down to determining the “leftmost” and “rightmost” single-point intersections of a collection of unbounded lines.

The most naive approach for such a goal is to exhaustively verify if the intersection of each pair of lines is one of the extrema, which has a time complexity of $O(n^{2})$. Fortunately improving this cost is possible avoiding to determine all intersections but directly finding those of interest. The relatable problem of deciding if there is at least one intersection between any pair of line segments given a set of these was previously addressed this way, so that an $O(n\log n)$ solution was provided [35]. Although this method cannot be directly adapted to the problem at hand, a solution with similar cost, principles, and applicability, which is not limited to the present context, could be found. It is based on the following statements:

As a preamble to the core procedure, for the input lines $L=\{(a_{i},b_{i})\}$, consider that an intersection between any pair of lines is determined on $x=r$: as remark 2 indicates, if this is not possible there is no intersection at all, and this can be decided in linear time. Next the lines are sorted in ascending order of $a_{i}(r+1)+b_{i}$, so that the leftmost intersection happens on some $s<r+1$, as affirmed in remark 3. These two steps have a time complexity of $O(n\log n)$.

At last, the algorithm itself has an inductive design [36], linearly incrementing on the lines. From now on the value of $x$ of the leftmost intersection between two of the first $n$ lines is represented by $x_{n}$. In the base case, only the first line is taken into account: in this trivial scenario, there are no intersections, what is denoted by $x_{1}=-\infty$. This part has constant computational cost.

Now, for the inductive step, first assume that $x_{n-1}$ is known. This can also be the solution for the first $n$ lines (i.e., $x_{n}=x_{n-1}$), but maybe an intersection between $l_{n}$ and any of the previous lines leads to a better solution. According to proposition 2, only lines whose slope is lower than that of $l_{n}$ could allow this improvement. And based on proposition 3, if there is more than one line matching this criterion, the one with the greatest slope, represented as $l_{n^{\prime}}$, should be responsible for the leftmost intersection with $l_{n}$, or no intersection with this line would be the leftmost of all. Thus, considering that an intersection between $l_{n}$ and a hypothetical $l_{n^{\prime}}$ happens when $x=t$, it follows that

With respect to the algorithmic complexity, each iteration of the inductive step is dominated by the identification of $l_{n^{\prime}}$. Any self-balancing binary search tree [37] could be used in this regard, whose queries and updates require $O(\log n)$ elementary operations. Consequently, the entire procedure has a time complexity of $O(n\log n)$ and a space complexity of $O(n)$.

As a closing remark, it is noticeable that the explanation just provided focused on finding the leftmost intersection of a pair of lines of $L$. However, since the goal is to determine the length of the intervel in which all intersections happen, only this is now enough. Fortunately the rightmost intersection can be determined by the same means, using the symmetry argument demonstrated next in proposition 4.

This section is focused on depicting meaningful examples of the application of the measures proposed in sections 5 and 4. For this purpose the null models described in section 2 were used, considering the variation of parameters such as the number of nodes and edges, and the weights distribution. The same evaluation was also performed for real-world networks and respective randomly generated surrogates which preserve some attributes of the original artifacts. The multiplicative inverse of the edge values was used to calculate the weighted distances in all cases.

It is worth pointing out that the experiments and respective analyses are far from exhausting the proposed methodology. Here it is shown how the measures behave in various scenarios, aiming at providing insights into how some graph attributes can influence them. Further studies may consider other characteristics, in addition to those assessed here, for the purpose of elucidating more properties and accomplishing other predictions.

The ubiquity of abstract and concrete systems which can be insightfully modeled as weighted networks is evident. This motivates the analysis of such structures from various points of view, such as node centrality. This work aimed at improving past ones on the consideration of edge weights for the establishment of the just mentioned perspective. Possibly the most repeated contribution in this sense is the proposal of measures to make the assessment in question. While this happens once again here, it is not an end in itself, but serves as the gateway to the entire methodology developed from there. Moreover, even this starting point is elaborately characterized and compared to its alternatives.

The conception and the interpretation of the useful intervals is the major accomplishment reported in this text. They lead to an entirely unexplored way to analyze weighted networks by allowing to objectively evaluate the significance of edge weights for node centrality. And targeting to assure the completeness of this contribution, an elegant procedure for the computation of these intervals is also provided, which is flexible enough to tackle problems in other contexts with similar geometric properties. At last, the performed experiments successfully illustrate the behavior of the presented methods in various situations, corroborating their usefulness and uniqueness.

About the next steps, we believe the application of the proposed methodology on a wider variety of real networks as well as probabilistically generated ones would enable the identification of other interesting patterns related to inherent characteristics of the former and parameter settings of the latter. Another future work could focus on the characterization of properties of well-known graph families based on the log-based centrality measures and their respective useful intervals. These are some promising potential continuations of this research.

We describe contributions to the paper as follows: R.S.P and D.O.C should be credited for conceptualization, methodology, software, validation, formal analysis, investigation, data curation, writing – original draft, review and editing –, and visualization; D.O.C also should be credited for resources, supervision, project administration, and funding acquisition.

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

This work was supported by the Carlos Chagas Filho Foundation for Research Support in Rio de Janeiro (FAPERJ) [grant number 248551 to R.S.P.].