Tore Opsahl

Degree Centrality and Variation in Tie Weights

August 8, 2011 at 11:28 pm Leave a comment

Node centrality, or the detection and identification of the central nodes in a network, has been a key issue in network studies. The basic node centrality measure is degree, which is defined as the number of connections or ties a focal node has (Freeman, 1978). Degree is a basic indicator and often used as a first step when studying networks (Wasserman and Faust, 1994). To formally describe this measure and ease the comparison among the different measures introduced in this post, this measure can be formalised for a focal node i as:

where j represents all other nodes, N is the total number of nodes, and x is the adjacency matrix, in which the cell is defined as 1 if node i is connected to node j, and 0 otherwise.

Degree has generally been extended to the sum of weights when analysing weighted networks, and labeled node strength (Barrat et al., 2004). This measure can be formalised as follows:

where w is the weighted adjacency matrix, in which is greater than 0 if the node i is connected to node j, and the value represents the weight of the tie. This is equal to the definition of degree if the network is binary, i.e. each tie has a weight of 1. Conversely, in weighted networks, the outcomes of these two measures are different. Since node strength takes into consideration the weights of ties, this has been the preferred measure for analyzing weighted networks (e.g., Barrat et al., 2004; Opsahl et al., 2008).

Nevertheless, node strength is a blunt measure as it only takes into consideration a node’s total level of involvement in the network, and not the number of other nodes to which it connected. To exemplify this, node A and node B have the same strength, but node A is connected to three times as many nodes as node A, and is therefore, involved in more parts of the network. As degree and strength can be both indicators of the level of involvement of a node in the surrounding network, a second generalisation was proposed by Opsahl et al. (2010) that incorporated both the number of ties and the sum of tie weights. Their measure can be formalised as:

where is a positive tuning parameter that controls the relative importance of the number of ties and the sum of ties. Specifically, there are two benchmark values (0 and 1), and if the parameter is set to either of these values, the existing measure is reproduced. If the parameter is set to the benchmark value of 0, the outcomes of the measure is solely based on the number of ties, and are equal to the ones found when applying Freeman’s (1978) measure to a binary version of a network where all the ties with a weight greater than 0 are set to present. Conversely, if the value of the parameter is 1, the outcomes of the measure is based on tie weights only, and are identical to the already proposed generalization of degree (Barrat et al., 2004). For other values of , alternative outcomes are attained, which are based on both the number of ties and tie weights. In particular, two ranges of values can be distinguished. First, a parameter set between 0 and 1 would positively value both the number of ties and tie weights. This implies that both increments in node degree and node strength will then increase the outcome. Second, if the value of the parameter is above 1, the measures would positively value tie strength and negatively value the number of ties. Nodes with on average stronger ties will get a higher score.

All of the above measures are insensitive to variation in tie weights. For example, the two nodes, A and B, in this diagram have the same number of connections, the same node strength, and attains the same score using the second generalisation as that it is a product of the degree and node strength. While the closeness and betweenness measures proposed in Opsahl et al. (2010) are sensitive to variation in tie weights, the degree measure was designed not to be. However, a measure closely related to the closeness and betweenness measures that is sensitive to tie weight differences can be defined as follows:

By exponenting the tie weight instead of the average tie weight, the measure becomes sensitive to variation in tie weights. For example, node A and node B would get the following score using the various measures:

Measure	Node
	A	B
Freeman’s	2	2
Barrat et al.’s	4	4
Opsahl et al.’s, alpha=0.5	2.83	2.83
Opsahl et al.’s, alpha=1.5	5.66	5.66
New measure, alpha=0.5	2.83	2.73
New measure, alpha=1.5	5.66	6.20

As it is possible to see from the above table, the new measure is closely linked to generalisation proposed by Opsahl et al. (2010); however, when the tie weights are different, the measure vary between the two nodes. Similarly as the other centrality measures using a tuning parameter, the tuning parameter in these measures control the relative importance of the number of ties and the sum of ties. In addition, it also controls whether variation in tie weights should be discounted or taken favourable. A parameter between 0 and 1 discounts, whereas a parameter above 1, increase the outcome of the measure when tie weights are different.

What to try it with your data?

Below is the code to calculate the proposed degree measure. You need to have the R-package tnet installed before to run the code.

# Load tnet
library(tnet)

# Load a function to calculate the new measures
degree2_w <- function (net, type="out", alpha = 1) {
    net <- as.tnet(net, type="weighted one-mode tnet")
    if (type == "in") {
        net <- data.frame(i = net[, 2], j = net[, 1], w = net[,3])
        net <- net[order(net[, "i"], net[, "j"]), ]
    }
    index <- cumsum(!duplicated(net[, 1]))
    k.list <- cbind(unique(net[, 1]), NaN, NaN, NaN)
    dimnames(k.list)[[2]] <- c("node", "degree", "output", "alpha")
    k.list[, "degree"] <- tapply(net[, "w"], index, length)
    k.list[, "output"] <- tapply(net[, "w"], index, sum)
    net[,"w"] <- net[,"w"]^alpha
    k.list[, "alpha"] <- tapply(net[, "w"], index, sum)
    if (max(net[, c("i", "j")]) != nrow(k.list)) {
        k.list <- rbind(k.list, cbind(1:max(net[, c("i", "j")]), 0, 0, 0))
        k.list <- k.list[order(k.list[, "node"]), ]
        k.list <- k.list[!duplicated(k.list[, "node"]), ]
    }
    return(k.list)
}

# Load a sample network
net <- cbind(
i=c(1,1,2,2),
j=c(2,3,1,3),
w=c(2,2,1,3))

# Calculate the measures
degree_w(net, measure=c("degree","output","alpha"), alpha=1.5)
degree_w(net, measure=c("degree","output","alpha"), alpha=0.5)
degree2_w(net, alpha=0.5)
degree2_w(net, alpha=1.5)

References

Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani, A., 2004. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences 101 (11), 3747-3752.

Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.

Opsahl, T., Agneessens, F., Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32, 245-251.

Opsahl, T., Colizza, V., Panzarasa, P., Ramasco, J. J., 2008. Prominence and control: The weighted rich-club effect. Physical Review Letters 101 (168702).

Wasserman, S., Faust, K., 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, New York, NY.

Entry filed under: Network thoughts. Tags: actors, centrality, complex networks, degree, edges, gregariousness, hubs, Links, local, network, nodes, popularity, social network analysis, strength of nodes, strength of ties, ties, valued networks, vertices, weighted networks.