Article: Node centrality in weighted networks: Generalizing degree and shortest paths
April 21, 2010
A paper called “Node centrality in weighted networks: Generalizing degree and shortest paths” that I have co-authored with Filip Agneessens
and John Skvoretz will be published in Social Networks. Unfortunately, the copyright agreement prevents me from uploading a pdf of the published paper to this blog. However, if you have access to Social Networks, you can download the paper directly. Otherwise, a preprint with the exact same text
is available.
Abstract
Ties often have a strength naturally associated with them that differentiate them from each other. Tie strength has been operationalized as weights. A few network measures have been proposed for weighted networks, including three common measures of node centrality: degree, closeness, and betweenness. However, these generalizations have solely focused on tie weights, and not on the number of ties, which was the central component of the original measures. This paper proposes generalizations that combine both these aspects. We illustrate the benefits of this approach by applying one of them to Freeman’s EIES dataset.
Motivation
Ego networks of Phipps Arabie (A), John Boyd (B), and Maureen Hallinan (C) from Freeman's third EIES network. The width of a tie corresponds to the number of messages sent from the focal node to their contacts. Adopted from the paper.
The three measures have already been generalised to weighted networks. Barrat et al. (2004) generalised degree to weighted networks by taking the sum of weights instead of the number ties, while Newman (2001) and Brandes (2001) utilised Dijkstra’s (1959) algorithm of shortest paths for generalising closeness and betweenness to weighted networks, respectiviely. Dijkstra’s algorithm defined the length of paths as the sum of cost (e.g., time in GPS calculations), which is generally only defined as the sum of the inversed tie weights. All these generalisations fail to take into account the main feature of the original measures formalised by Freeman (1978): the number of ties.
This limitation is highlighted for degree centrality by the three ego networks from Freeman’s third EIES network. The three nodes have roughly sent the same amount of messages; however, to a quite different number of others. If Freeman’s (1978) original measure was applied, the centrality score of the node in panel A is almost five times as high as the node in panel C attains. However, when using Barrat et al.’s generalisation, they get roughly the same score.
This articles proposes a new generation of node centrality measures for weighted networks. The second generation of measures takes into consideration both the weight of ties and the number of ties. The relative importance of these two aspects are controlled by a tuning parameter.
Want to test it with your data?
The degree_w, closeness_w, and betweenness_w-functions in tnet allows you to calculate the binary, weighted, and the measures that combine these two aspects on your own dataset.
For example, to calculate second generation node centrality measures (alpha = 0.5) on the sample network above, you can run the code below in R. The degree function easily calculates the binary and first generation measures as well; however, this is not the case for the closeness and betweenness-functions. If you would like the binary version, you can either use the dichotomise function or set alpha=0. If you would like the first generation weighted measures, you can set alpha=1 (default value).
# Load tnet
library(tnet)
# Load network
net <- cbind(
i=c(1,1,2,2,2,2,3,3,4,5,5,6),
j=c(2,3,1,3,4,5,1,2,2,2,6,5),
w=c(4,2,4,4,1,2,2,4,1,2,1,1))
# Calculate degree centrality
degree_w(net, measure=c("degree", "output", "alpha"), alpha=0.5)
# Calculate closeness centrality
closeness_w(net, alpha=0.5)
# Calculate betweenness centrality
betweenness_w(net, alpha=0.5)
To test it on Freeman’s third EIES network from the datasets page and recreate Table 3 of the paper, you can do the following:
# Load tnet
library(tnet)
# Load network
data(Freemans.EIES)
net <- Freemans.EIES.net.3.n32
# Calculate measures
tmp <- data.frame(
Freemans.EIES.node.Name.n32,
degree_w(net, measure=c("degree", "output", "alpha"), alpha=0.5),
degree_w(net, measure="alpha", alpha=1.5)[,"alpha"], stringsAsFactors=FALSE)
dimnames(tmp )[[2]] <- c("name", "node", "a00", "a10", "a05", "a15")
tmp <- tmp[,c("name","a00","a05","a10","a15")]
# Merge names and order table
out <- data.frame(
seq.int(nrow(tmp)),
tmp[order(-tmp[,"a00"], -tmp[,"a10"]),c("name", "a00")],
tmp[order(-tmp[,"a05"], -tmp[,"a10"]),c("name", "a05")],
tmp[order(-tmp[,"a10"], -tmp[,"a10"]),c("name", "a10")],
tmp[order(-tmp[,"a15"], -tmp[,"a10"]),c("name", "a15")])
dimnames(out)[[2]] <- c("Rank",
"a00.name","a00",
"a05.name","a05",
"a10.name","a10",
"a15.name","a15")
# Display table
out
References
Brandes, U., 2001. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25, 163-177.
Dijkstra, E. W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.
Freeman, L. C., 1978. Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239.
Newman, M. E. J., 2001. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E 64, 016132.
Opsahl, T., Agneessens, F., Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32, 245-251.
Entry Filed under: Network thoughts. Tags: network, social network analysis, weighted networks, valued networks, strength of ties, local, shortest distance, nodes, actors, vertices, ties, Links, edges, arcs, degree, strength of nodes, directed networks, undirected networks, betweenness, centrality, shortest path, closeness, reinforcement, gregariousness, popularity, hubs, complex networks, graphs.
23 Comments Add your own
Leave a Comment
Some HTML allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
Trackback this post | Subscribe to the comments via RSS Feed
1.
questavita | May 2, 2010 at 10:54 am
Thank you for your very good works.
–
Jacopo, from Rome, Italy.
2.
Marco | May 13, 2010 at 10:42 am
Hi Tore,
just one quick question (I’m pretty new in this stuff): with cbind what are you passing to the programme exactly? I dont understand why there are 3 parameters (i,j,w) with 12 elements..
Marco – Italy
3.
Tore Opsahl | May 13, 2010 at 12:53 pm
Hi Marco,
With cbind you combine columns. You can get the help file for each function in R by typing ?cbind
The command:
net <- cbind(
i=c(1,1,2,2,2,2,3,3,4,5,5,6),
j=c(2,3,1,3,4,5,1,2,2,2,6,5),
w=c(4,2,4,4,1,2,2,4,1,2,1,1))
I create an object called net that is composed of three columns (i, j, and w), which contain the values given in inside the vector-combination function, c.
Hope this helps,
Tore
4.
Marco | May 17, 2010 at 7:25 am
Hi Tore, thanks for your answer. Still, I got a doubt: the values in the columns, what do they correspond to? I mean, why is the vector i made of 1,1,2,2,2,2 etc? Because, looking to the net represented by the picture (the net made by 6 nodes, from A to F) I see other weigths, so I am pretty lost :)
Looking forward for your reply,
Marco
5.
Marco | May 17, 2010 at 9:35 am
Tore, I’ve just understood the values..but I’d have another quick question: what’s alpha?
Sorry for disturbing you:)
Marco
6.
Tore Opsahl | May 17, 2010 at 11:27 pm
Glad that you figured it out! Have a look at the paper for the alpha parameter!
7.
Thor Sigfusson | June 14, 2010 at 3:47 pm
Tore,
Thanks for your help. I am still figuring out out to work on weighted data.
What do the numbers in the columns represent ? (1,1,2,2,3,3 etc.
I have a data where names of individuals in the network (the nodes) are 1-300. I interviewed 20 entrepreneurs who have numbers from 1-20. Each mentioned around 15-20 connections.
Person 1 has strong ties with 5,12, 19,21 and weak ties with 12 others.
I am stryggling with setting this up in the correct manner.
Best regards and thanks again for a great initiative,
Thor
8.
Tore Opsahl | June 15, 2010 at 6:01 am
Hi Thor,
tnet cannot -so far- handle node labels, so they are simply the id numbers of the nodes.
The best way to enter larger networks is to load an edgelist file. You can do this by arranging your data in a txt file like this:
1 5 5
1 12 5
1 19 5
1 21 5
1 4 1
….
Then write in R: net <- read.table("filename.txt")
Hope this helps,
Tore
9.
Thor Sigfusson | June 24, 2010 at 11:30 am
Dear Tore,
It worked. Thanks a lot.
Thor
10.
Marco | June 30, 2010 at 10:18 am
Hi Tore,
got a quick question, maybe you can help me: I’m calculating the EigenValues of a Matrix, but R provides me only ordered values..is there a way to have unordered results?
Thnaks in advance
Marco
11.
Ben | July 24, 2010 at 10:19 am
Hi Tore,
What kind of software do you use for drawing your graph pictures?
For example, this one:
http://thetore.files.wordpress.com/2008/12/fig1.png?w=271&h=177
Thanks,
Ben
12.
Tore Opsahl | July 24, 2010 at 4:15 pm
Hi Ben,
I have actually made those in illustrator / photoshop. Not recommended, but that method enables you to make the graphs exactly as you want.
Best,
Tore
13.
Mauricio | August 10, 2010 at 2:19 pm
Hi Tore,
Thanks for your very good work.
I’m trying to calculate the degree_w for my data, but it seems that the output is always equivalent when alpha is set as 1. Even for the sample network in this post, I got the same results when varying the alpha parameter…
Please, could you tell me what is my mistake here?
With many thanks
Mauricio
> degree_w(net,measure=c(“degree”,”output”), type=”out”, alpha=1)
node degree output
[1,] 1 2 6
[2,] 2 4 11
[3,] 3 2 6
[4,] 4 1 1
[5,] 5 2 3
[6,] 6 1 1
> degree_w(net,measure=c(“degree”,”output”), type=”out”, alpha=0.5)
node degree output
[1,] 1 2 6
[2,] 2 4 11
[3,] 3 2 6
[4,] 4 1 1
[5,] 5 2 3
[6,] 6 1 1
14.
Tore Opsahl | August 11, 2010 at 12:37 am
Mauricio,
You need to include alpha in the measure-parameter.
Tore
#Load tnet and network library(tnet) net <- cbind( i=c(1,1,2,2,2,2,3,3,4,5,5,6), j=c(2,3,1,3,4,5,1,2,2,2,6,5), w=c(4,2,4,4,1,2,2,4,1,2,1,1)) # Run function degree_w(net, measure=c("degree", "output", "alpha"), alpha=0.5) # Output node degree output alpha [1,] 1 2 6 3.464102 [2,] 2 4 11 6.633250 [3,] 3 2 6 3.464102 [4,] 4 1 1 1.000000 [5,] 5 2 3 2.449490 [6,] 6 1 1 1.00000015.
Mauricio | August 11, 2010 at 1:23 pm
Hi Tore,
Thank you for your reply, it’s fixed my problem!!
I didn’t notice this detail in the post. I was following the help(degree_w) from the tnet package, and I got confused.
With many thanks,
M
16.
Nitesh | August 18, 2010 at 2:37 pm
Hi Tore,
Great work!!
Just having problem in installing tnet package in R 2.11.1.
The error I am getting is
Loading required package: igraph
Error : .onLoad failed in loadNamespace() for ‘igraph’, details:
call: inDL(x, as.logical(local), as.logical(now), …)
error: unable to load shared library ‘C:/PROGRA~1/R/R-211~1.1/library/igraph/libs/igraph.dll’:
LoadLibrary failure: The specified module could not be found.
Error: package ‘igraph’ could not be loaded
In the pop window, it is showing that iconv.dll file was not found..
Can you help me please??
17.
Tore Opsahl | August 18, 2010 at 2:52 pm
Nitesh,
Thanks for taking an interest in tnet. This is an issue with the igraph-package that tnet depends on. You can fix it by copying the iconv.dll from a previous version of igraph (or email me). I have sent them a bug report – hopefully they will have it sorted soon.
Best,
Tore
18.
Nitesh | August 18, 2010 at 3:56 pm
Many thanks Tore,
Nitesh
19.
Tore Opsahl | August 19, 2010 at 12:28 pm
Nitesh,
The igraph-guys (Gabor Csardi) have just submitted a new version of their R-package that should solve this issue. As soon as it has been approved by CRAN and disseminated across the servers, you should be able to get it by writing update.packages() in R.
Tore
20.
Nitesh | August 19, 2010 at 12:35 pm
Hi Tore,
Thanks for your response. As you mentioned before, by copying the iconv.dll file in igraph-libs, it worked.
Can you suggest me something about cliques in weighted graphs. I have seen your related to node centrality and clustering coefficient.
Just wondering, if you have any ideas on finding cliques in weighted graph.
Regard
Nitesh
21.
Tore Opsahl | August 19, 2010 at 1:42 pm
Nitesh,
You can look at my paper called Clustering in Weighted Networks for determining the level of clustering / cliqueness in a network. But if you would like to find the specific cliques or communities, I would suggest you contact some of the community detection guys. Also, you might want to have a look at the book Generalized Blockmodeling by Dorian, Batagelj, and Ferligoj.
Tore
22.
minjung | August 24, 2010 at 12:55 pm
Hi tore!
Thanks for sharing ur great works. It’s really helpful for me to understand
the concepts about centrality.
I just wondering u can give me some advice.
Im working on a project that analyzing the customers of mobile company and doing SNS. That is, i have to find the community among the customers and define the leader, who is influential to other customers.
So i detect the community(cluster) and i got the degree centrality, closeness centrality, between centrality of each nodes within a cluster.
And NOW, i have to assign roles to each node; leader, sub-leader,follower and outliers.
Do u think i can just assign roles based on three centrality? for example,
make the one with big centralites as a leader. Centrality can be the measure of influence within the community?
Thanks in advance,
MJ
23.
Tore Opsahl | August 24, 2010 at 7:03 pm
Hi MJ,
I am not aware of any general literature on this topic. You could have a look at the Fernandez and Gould-paper that does something similar with brokerage measures. They define – based on directionality, which your data should have – various roles based on ego networks.
Best,
Tore