A Generalization of the Importance of Vertices for an Undirected Weighted Graph ^†

Abstract

Establishing a node importance ranking is a problem that has attracted the attention of many researchers in recent decades. For unweighted networks where the edges do not have any attached weight, many proposals have been presented, considering local or global information of the networks. On the contrary, it occurs in undirected edge-weighted networks, where the proposals to address this problem have been more scarce. In this paper, a ranking method of node importance for undirected and edge-weighted is provided, generalizing the measure of line importance (DIL) based on the centrality degree proposed by Opsahl. The experimentation was done on five real networks and the results illustrate the benefits of our proposal.

1. Introduction

Networks study, in the form of mathematical graph theory, is one of the most important objects from discrete mathematics [1]. The importance of its various applications in issues of traffic, economy, brain networks, spread of diseases, social networks, electrical power grid, etc. has made this field of research gain the attention of many researchers in the last 20 years (see for instance [2,3,4,5,6,7,8]).

In a complex network there are some more important vertices than others that influence or have a greater impact on their structure or function. This importance establishes some vertices rankings that can be based on different viewpoints, this is to say, we can have an importance based on the neighborhood, on the paths, on the link, connectivity or sensibility (more details in [9]). For example, the degree of a vertex allows ordering or making a vertices ranking according to the number of neighbors it has. In general, we have the well known centrality measures that give us a vertices importance ranking. However, identifying vital nodes is not an easy job because the criteria for vital nodes are diverse due to their context-dependent nature, and consequently it is not possible to find a universal index that better quantifies the importance of nodes in all situations. Even harder, if you want to find a set of important nodes, it is an NP-Hard problem (see [10]).

In this context, other criteria have emerged to determine the importance of a node. For instance, in [11] there are taken into account the characteristics of the scale, tightness and topology of the local area network where the node and its neighbors are located. Liu et al. [12] proposed an effective ranking method based on degree value and the importance of edges. Saxena et al. designed a method to identify the best ranked nodes in order to control an epidemic through immunizations [13]. On the other hand, the conscious centrality of the community is addressed by Magelinski et al., who propose the relevance of the bridge node in the network quantified in modular vitality [14]. Along the same lines, Ghalmane et al. analyze the nonoverlapping community structure network based on an immunization strategy, recognizing the relevance of the node given the characteristics of the communities [15], while the same author asserts that modular centrality must include the influences of the nodes both in their own communities and in others [16]. Gupta et al. also agree that community structure is important for understanding the spread of an epidemic [17].

In [18] the authors proposed a method based on degree and degree of their neighborhoods. Ren et al. in [19] proposed a measure based on degree and clustering coefficient. For its part, Ref. [20] is based on combining the existing centrality criteria, where the weight for each criterion is calculated by the entropy weighting method which overcomes the impact of the subjective factor, and the Vlsekriterijumska Optimizacija I Kompromisno Resenje (VIKOR) method is used for ranking nodes’ importance. Jia-Sheng et al. improved the method of node importance evaluation based on node contraction [21]. Recently, a new multievidence centrality is proposed based on evidence theory. The existing measures of degree centrality, betweenness centrality, efficiency centrality and correlation centrality are taken into consideration in [22].

Edge-weighted graphs are not exempt from this discussion. For example, there are the rankings which are natural extensions of unweighted graphs, that we could call more representative, they are the strength of the node [23], weighted H-index [24], weighted degree [25,26], the weighted closeness centrality [27], weighted betweenness centrality [28], weighted PageRank and leaderRank [29]. Furthermore, Opsahl in [30] proposed a generalization of degree for weighted graph that combines the strength and the number of neighbors.

In addition, on this type of networks new methods have been proposed to establish the importance or influence of the nodes. Among them, Yang et al. [31] proposed the Two-Way-PageRank method based on PageRank and analyzed the importance of two important factors that affect the importance of the nodes and gave a definition and expression of the importance of the nodes. A new centrality measure (Laplacian centrality) for undirected and edge-weighted graph is proposed in [32] as well. Tang [33] proposed the weighted K-order propagation number algorithm to extract the disease propagation based on the network topology to evaluate the node importance. In the field of maximization of influence, Ahmad proposes an approach that includes the weighted sum and a multicriteria decision method [34]. All this generates the recognition of influential nodes in the network. The authors, through experimentation, conclude that their model is competitive to other similar ones [34]. Even axiomatic approaches have been proposed (see [35,36]).

In the framework of modeling complex biological systems Almasi & Hu provide a measure from the importance of vertices in a weighted human disease network [2]. They propose a vertex importance measure by extending a centrality measure for unweighted networks proposed by Liu et al. They named their extension on weighted graphs, the DIL-W centrality.

In this paper, a ranking method for undirected and edge-weighted graph is provided. Particularly, the aim of this article is to generalize the vertex importance measure (DIL) of an undirected and unweighted network given by Liu et al., to an undirected and edge-weighted graph using the generalization of degree centrality proposed by Opsahl in [30]. Our proposal is slightly different from Almasi & Hu’s one, but when we compare both generalizations in real networks, with respect to the measure the network efficiency, we can see that we obtain a better or the same efficiency measure, as we will show in the following sections.

The paper is organized as follows. Section 2 contains generalities about graph theory and the definition of degree centrality proposed by Opsahl. In Section 3 the generalization of the importance vertex measure, denoted by DIL-W${}^{\alpha }$, is given. In Section 4, we compare our proposal DIL-W${}^{\alpha }$ with the one given by Almasi & Hu (denoted by DIL-W) considering $\alpha =1$ and $\alpha =0.5$ on some real networks (Zacharys karate club network, US air transport network, meta-analysis network of human whole-brain functional coactivations, colony of ants network and wild birds network). Moreover, we analyze the DIL-W${}^{\alpha }$ rank with different values of $\alpha$ and provide a discussion about the results. Finally, in Section 5, we give the final conclusions.

2. Basic Definitions

Graphs

The following definitions come from [37,38].

Definition 1.

A graph G is a finite nonempty set V of objects called vertices together with a possibly empty set E of 2-element subsets of V called edges.

To indicate that a graph G has vertex set V and edge set E, we write $G=(V,E)$. If the set of vertices is $V=\{v_1,v_2,\dots ,v_n\}$, then the edge between vertex $v_i$ and vertex $v_j$ is denoted by $e_{ij}$.

If $e_{ij}$ is an edge of G, then $v_i$ and $v_j$ are adjacent vertices. Two adjacent vertices are referred to as neighbors of each other. The set of neighbors of a vertex v is called the open neighborhood of v (or simply the neighborhood of v) and is denoted by $N\left(v\right)$. If $e_{ij}$ and $e_{jk}$ are distinct edges in G, then $e_{ij}$ and $e_{jk}$ are adjacent edges.

Definition 2.

The number of vertices in a graph G is the order of G and the number of edges is the size of G.

Definition 3.

The degree of a vertex v in a graph G, denoted by $deg\left(v\right)$, is the number of vertices in G that are adjacent to v. Thus, the degree of v is the number of vertices in its neighborhood $N\left(v\right)$.

On the other hand, an important generalization of the simple graph consists in the definition of weighted graph, more specifically edge-weighted graph. Informally, an edge-weighted graph is a graph whose edges have been assigned a weight.

Definition 4.

An edge-weighted graph is a pair $(G,w)$ where $G=(V,E)$ is a graph and $w:E\to ℝ$ is a weight function. If $e_{ij}\in E$ then $w\left(e_{ij}\right)=w_{ij}$.

The adjacency matrix of G is the $n\times n$ matrix $A\left(G\right)=\left[a_{ij}\right]$, or simply $A=\left[a_{ij}\right]$, where

$$a_{ij}=\left\{\begin{array}{cc}{w}_{ij}\hfill & \mathrm{if}{e}_{ij}\in E\left(G\right)\hfill \\ 0\hfill & \mathrm{if}{e}_{ij}\notin E\left(G\right).\hfill \end{array}\right.$$

Definition 5.

The strength of a vertex $v_i$, denoted by $S\left(v_i\right)$, is defined as the sum of the weights of all edges incident to it, this is to say

$$S\left(v_i\right)=\sum _{v_j\in N\left(v_i\right)}{w}_{ij}.$$

The following definition comes from [30] and it is very important in our work.

Definition 6

(Degree centrality). The degree centrality of $v_i\in V$ of an edge-weighted graph $(G,w)$, denoted by $C_D^{w\alpha }\left(v_i\right)$, is defined as

$$\begin{array}{cc}\hfill C_D^{w\alpha }\left(v_i\right)& =deg{\left(v_i\right)}^{(1-\alpha )}·S{\left(v_i\right)}^{\alpha },\hfill \end{array}$$

(1)

where $\alpha \in [0,1]$.

The parameter $\alpha$ is called tuning parameter. It is clear that when $\alpha =0$ then $C_D^{w\alpha }\left(v_i\right)=deg\left(v_i\right)$ and when $\alpha =1$ then $C_D^{w\alpha }\left(v_i\right)=S\left(v_i\right)$.

3. Measuring Vertex Importance on an Undirected Weighted Graph

In this section the generalization of the importance vertex measure is given, denoted by DIL-W${}^{\alpha }$.

Let us consider an undirected weighted graph $(G,w)$ with $G=(V,E)$ and $V=\{v_1,v_2,\dots ,v_n\}$. Let $\alpha \in [0,1]$ be the tuning parameter.

Definition 7

(Importance edge). The importance of an edge $e_{ij}\in E$, denoted by $I^{\alpha }\left(e_{ij}\right)$, is defined as

$$\begin{array}{cc}\hfill I^{\alpha }\left(e_{ij}\right)& =\frac{\left(C_D^{w\alpha }\left(v_i\right)-p_i^{\alpha }\right)·\left(C_D^{w\alpha }\left(v_j\right)-p_j^{\alpha }\right)}{{\lambda }^{\alpha }},\hfill \end{array}$$

where, for $k\in \{i,j\}$, ${\displaystyle p_k^{\alpha }={(p+1)}^{(1-\alpha )}·t_k^{\alpha }}$ with p is the number of triangles, one edge of the triangle is $e_{ij}$, $t_k^{\alpha }$ is the weight of the sum of the edges incident to $v_k$ that form a triangle with $e_{ij}$ and ${\displaystyle {\lambda }^{\alpha }=\frac{p^{(1-\alpha )}·{\left(t_i+t_j\right)}^{\alpha }}{2}+1}$.

Definition 8

(Contribution). The contribution that $v_i\in V$ makes to the importance of the edge $e_{ij}$, denoted by $W^{\alpha }\left(e_{ij}\right)$, is defined as

$$\begin{array}{cc}\hfill W^{\alpha }\left(e_{ij}\right)& =I^{\alpha }\left(e_{ij}\right)·\frac{C_D^{w\alpha }\left(v_i\right)-w_{ij}^{\alpha }}{C_D^{w\alpha }\left(v_i\right)+C_D^{w\alpha }\left(v_j\right)-2w_{ij}^{\alpha }},\hfill \end{array}$$

where $w_{ij}$ is the weight of $e_{ij}$.

Definition 9

(Importance of vertex DIL-W${}^{\alpha }$). The importance of a vertex $v_i\in V$, denoted by $L^{\alpha }\left(v_i\right)$, is defined as

$$\begin{array}{cc}\hfill L^{\alpha }\left(v_i\right)& =C_D^{w\alpha }\left(v_i\right)+\sum _{v_j\in N\left(v_i\right)}{W}^{\alpha }\left(e_{ij}\right).\hfill \end{array}$$

From the definition of degree centrality (Definition 6) proposed by Opsahl in [30], we can see that when the tuning parameter $\alpha$ is 0 the Definitions 7–9 of importance edge, contribution and importance of vertex respectively, are the same as that proposed by Liu et al. in [12] for an undirected and unweighted network. However, when $\alpha =1$, our proposal is slightly different from Almasi & Hu’s proposal in [2]. In the latter, the authors define the contribution as

$$\begin{array}{cc}\hfill W\left(e_{ij}\right)& =I^{\alpha }\left(e_{ij}\right)·\frac{S\left(v_i\right)}{S\left(v_i\right)+S\left(v_j\right)}.\hfill \end{array}$$

(2)

Notice that, if the strength of the vertex is the traditional degree centrality as in the case of the undirected and unweighted graph, it is not possible to get the proposal of Liu et al. from the Equation (2). This slight difference between the generalization of the vertex importance method of [2] and our generalization is relevant when we compare both generalizations in real networks with respect to the measure of the network efficiency as we will show in the next section.

On the other hand, a possibility to extend the vertex importance based on degree and the importance of lines from an unweighted network to the proposed by Almasi & Hu, is to consider the contribution as

$$\begin{array}{cc}\hfill W\left(e_{ij}\right)& =I^{\alpha }\left(e_{ij}\right)·\frac{C_D^{w\alpha }\left(v_i\right)-(1-\alpha )}{C_D^{w\alpha }\left(v_i\right)+C_D^{w\alpha }\left(v_j\right)-2(1-\alpha )}.\hfill \end{array}$$

(3)

Indeed, when $\alpha =0$ we obtain the original proposal and when $\alpha =1$ we get the generalization given in [2]. Despite the above, we do not consider Equation (3) because, in our opinion, it is not a good generalization proposal since it does not improve the one done by Almasi & Hu.

One of the good qualities of the DIL ranking is that it recognizes the importance of bridge nodes (see more in [39]). This quality is not lost in our extension to weighted graphs. For instance, we can see in Figure 1 that when applying the DIL-W${}^{\alpha }$ ranking with $\alpha =0.5$, vertex 10 has a better ranking than vertex 4; this is due to the vertex 10 being a bridge node. Indeed, from Definitions 9 we get

$$\begin{array}{cc}\hfill L^{0.5}\left(v_4\right)& =C_D^{w\alpha }\left(v_4\right)+\sum _{v_j\in N\left(v_4\right)}{W}^{0.5}\left(e_{4j}\right)=13.7834,\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill L^{0.5}\left(v_{10}\right)& =C_D^{w\alpha }\left(v_{10}\right)+\sum _{v_j\in N\left(v_{1}0\right)}{W}^{0.5}\left(e_{10j}\right)=17.4523.\hfill \end{array}$$

Therefore, $L^{0.5}\left(v_4\right)<L^{0.5}\left(v_{10}\right)$.

On the other hand, the consideration of the centrality measure that combines degree and strength, picks up the main idea of the original measure, which is the number of neighbors of a vertex, an idea that is lost when considering only the strength.

4. Comparison and Analysis Results

4.1. Data and Source Code

In our research, we compare our proposal DIL-W${}^{\alpha }$ for $\alpha =1$ and $\alpha =0.5$ with DIL-W on some real networks, these are: Zacharys karate club network [40] (with 34 vertices and 78 edges), US air transport network [41] (with 500 vertices and 2980 edges), meta-analysis network of human whole-brain functional coactivations [5] (with 638 vertices and 18,625 edges), colony of ants network [42] (with 113 vertices and 4550 edges) and wild bird network [43] (with 131 vertices and 1444 edges).

For the databases of colony of ants and wild birds networks, see [44]. For US air transport network see [45]. For brain functional coactivactions network database, see [46]. The source code of our analysis and network files can be found at https://github.com/RonaldManriquez/DIL-W-alpha.git from 8 March 2021.

4.2. Evaluation

According to [47], network efficiency is an index used to indicate the quality of network connectivity. A high connectivity indicates a higher efficiency of the graph. The efficiency of a graph, denoted by $\eta$, is defined as follows:

$$\begin{array}{cc}\hfill \eta & =\frac{1}{n(n-1)}\sum _{v_i\ne v_j}\frac{1}{d^w(v_i,v_j)},\hfill \end{array}$$

(4)

where $d^w(v_i,v_j)$ is the distance between the vertex $v_j$ and the vertex $v_j$, defined as,

$$\begin{array}{cc}\hfill d^w(v_i,v_j)& =min\left(\frac{1}{w_{ih}}+\dots +\frac{1}{w_{hj}}\right),\hfill \end{array}$$

(5)

where h are the indices of the intermediary vertices on paths between $v_i$ and $v_j$, and $w_{ih},\dots ,w_{hj}$ the weights of the edges $e_{ih},\dots ,e_{hj}$. (see more details in [27,28]). We consider $\alpha =1$ and $\alpha =0.5$ to compare DIL-W${}^{\alpha }$ with DIL-W, according to what was discussed at the end of Section 3.

The authors in [48] show that between 5% and 10% of important nodes may cause the entire network to falter. To compare the DIL-W${}^{\alpha }$ proposal with DIL-W, the 10% of the vertices are deleted one by one from the networks according to the importance ranking produced by DIL-W${}^{\alpha }$ and DIL-W, and we compute the decline rate of network efficiency, denoted by $\mu$, and defined by

$$\begin{array}{cc}\hfill \mu & =1-\frac{\eta }{{\eta }_0},\hfill \end{array}$$

where ${\eta }_0$ is the efficiency of the original graph, and $\eta$ is the graph efficiency after some vertices are removed [19]. We expect a greater decline rate of the network efficiency if we delete a more important vertex of the obtained DIL-W${}^{\alpha }$ ranking.

In Figure 2, we see the ranking done by DIL-W, DIL-W${}^1$ and DIL-W${}^{0.5}$ on the example networks versus the decline rate of the network efficiency. There exists a correlation between the rankings DIL-W, DIL-W${}^1$ and DIL-W${}^{0.5}$ and the decline rate of the network efficiency in Zacharys karate club, US air transport and colony of ants networks, whereas in the case of wild birds and brain functional coactivations networks, the correlation is not evident.

In each implementation only one node is removed according to the importance ranking list, then we compute the decline rate of the network efficiency.

In Figure 3, we can see the relation between the decline rate of network efficiency and the number of vertices deleted from five real networks.

In Zachary karate club, US air transport and wild birds networks, DIL-W${}^{0.5}$ performs the best between all three rankings. In brain functional coactivations and colony of ants networks, DIL-W${}^1$ and DIL-W perform the best. Notice that, only in the case of US air transport, DIL-W${}^1$ does not match completely with DIL-W.

Table 1. The ranking results of DIL-W and DIL-W${}^1$ on wild birds and US air transport networks.

	Wild Birds Network		US Air Transport Network
	DIL-W	DIL-W${}^1$	DIL-W	DIL-W${}^1$
Ranking Position	ID	ID	ID	ID
1	12	12	1	1
2	27	27	3	3
3	23	23	6	6
4	10	10	10	10
5	35	35	14	14
6	77	77	7	5
7	25	25	5	7
8	51	51	4	4
9	26	26	8	8
10	94	94	2	2
11	6	6	12	12
12	56	56	11	11
13	61	61	13	13
14	11	11	21	21

shows the nodes ranking on the wild bird and US air transport networks, making evident the same ranking of importance of nodes for DIL-W and DIL-W${}^1$ in wild birds network and the slight difference of ranking in US air transport network.

4.3. Ranking DIL-W${}^{\alpha }$ for Different Values of $\alpha$

In the previous section we could see that, with respect to efficiency, DIL-W${}^{\alpha }$ performs better rankings in brain functional coactivations and colony of ants networks, when $\alpha =1$, whereas in US air transport, Zachary karate club and wild birds’ networks the ranking is better with $\alpha =0.5$.

In this section we compare the different rankings that DIL-W${}^{\alpha }$ performs for different values of $\alpha$. We have considered the values $0.1$, $0.3$, $0.5$, $0.7$, $0.9$ and 1. Figure 4 shows the results.

For the US air transport, Zachary karate club and wild birds networks, it is observed that the smaller the $\alpha$, the better the efficiency ranking is performed. Conversely, in colony of ants and brain coactivations networks the best performance for efficiency is with $\alpha =1$ or $\alpha$ close to 1. In conclusion, we can see that DIL-W${}^{\alpha }$ is equal to or better in efficiency than the DIL-W proposal given in [2] in the five networks that we have considered. In particular, they coincide in efficiency in brain coactivations and colony of ants networks for $\alpha =1$ and cannot be improved with another value of $\alpha$ as we concluded from Figure 4. In contrast, DIL-W${}^{\alpha }$ performs better than DIL-W on the US air transport, Zachary karate club and wild birds networks, as soon as $\alpha <1$.

Moreover, we deepen into the possible relations between DIL and DIL-W${}^{\alpha }$ for the different values of $\alpha$ seen previously (i.e., $0.1,0.3,0.5,0.7,0.9,$ and 1) on all the networks that we have tested. Figure 5 shows the relations. In each network it is observed that the correlation coefficient between both rankings are very close to 1. In particular, for the Zachary karate club network we have all coefficients above 0.988. While for US air transport we have the largest range of correlation coefficients among all networks (between 0.7308 and 0.9998).

4.4. Computational Complexity

In general the real complex networks have many vertices, then the computational complexity plays an important role. DIL-W${}^{\alpha }$ has a computational complexity of $O(n·<k>)$, where n is the total numbers of vertices of the graph and $<k>$ is the average degree of vertices in a network. Moreover, DIL-W${}^{\alpha }$ uses local information of a vertex for its importance evaluation. By the above, we believe that DIL-W${}^{\alpha }$ can be efficient to compute in large networks.

5. Conclusions

In this paper, we propose a ranking of importance of nodes which is applicable to undirected and edge-weighted networks. We can see that DIL-W${}^{\alpha }$ is equal to or better in efficiency than the DIL-W proposal given in [2] in the five networks that we have considered.

We assess effectiveness by comparing the rate of decrease of network efficiency caused by node removal. The higher the rate of decrease of network efficiency caused by node removal, the more important will be the node. In Figure 4, the results show that DIL-W${}^{\alpha }$ can evaluate the importance of nodes better in the US air transport, Zachary karate club and wild birds networks, when $\alpha$ is less than one. Conversely, in colony of ants and brain coactivations networks, the best performance for efficiency is with $\alpha =1$ or $\alpha$ close to 1. In consequence, when modifying the parameter $\alpha$ it is possible to obtain better rankings for the network in the sense of effectiveness.

From the above, we are presented with an important task or challenge, which is to establish what value of $\alpha$ makes the ranking perform more optimally. It is difficult to determine the exact value of $\alpha$ to use. We think that there may be a dependency on the weights at the edges. For instance, is it better to have many edges with weights between 0 and 1 or few edges with weights greater than 1? Such answers would allow a better understanding of the optimal $\alpha$ in certain networks.

From Table 1 we can see that only in the US air transport network the rankings made by DIL-W and DIL-W${}^1$ do not match completely, since there is a small difference in positions 6 and 7 of the rankings.

With respect to the computational complexity, we believe that DIL-W${}^{\alpha }$ can be efficient to compute in large networks because it uses local information of a vertex for its importance evaluation.

In summary, our research provides a way to generalize the classification method for edge-weighted and undirected graphs. This turns out to be an element for the discussion around the usefulness of the concept of degree of centrality and its standard use has limitations in complex networks, as pointed out by Sciarra et al. [49].