# How to calculate centrality measures in a 4 million edge network using R?

I have a CSV file with 4 million edges of a directed network representing people communicating with each other (e.g. John sends a message to Mary, Mary sends a message to Ann, John sends another message to Mary, etc.). I would like to do two things:

1. Find degree, betweeness and (maybe) eigenvector centrality measures for each person.

2. Get a visualization of the network.

I would like to do this on the command-line on a Linux server since my laptop does not have much power. I have R installed on that server and the statnet library. I found this 2009 post of someone more competent than me trying to do the same thing and having problems with it. So I was wondering if anyone else has any pointers on how to do this, preferably taking me step by step since I only know how to load the CSV file and nothing else.

Just to give you an idea, this is how my CSV file looks like:

$head comments.csv "src","dest" "6493","139" "406705","369798"$ wc -l comments.csv

• for some of these measures it whether R can handle it or note will depend on how many separate people (nodes) the network has. R may not necessarily be the best tool for the computational aspects. There's a guy with the last name of Leskovec who used to be at Carnegie Mellon---I think as a student---that did lots of stuff with descriptive statistics on large graphs. There are lots of utilities out there to "visualize" graphs, but mostly I've found they're pretty hard to interpret or make much sense out of. Graphing just the degree distributions might be a first start. – cardinal Feb 16 '11 at 3:03
• Even plotting 4 million points might take a while... – Wok Feb 16 '11 at 15:00
• @wok, nah. Piece of cake on today's computers. Anyway, you could always dump to a PNG first and that's likely to be good enough for the degree distribution. The OP's graph really isn't all that big. – cardinal Feb 16 '11 at 15:36

What you have is an edge list, which can be converted to a network object using the network library. Here is an example using fictitious data.

library(network)

src <- c("A", "B", "C", "D", "E", "B", "A", "F")
dst <- c("B", "E", "A", "B", "B", "A", "F", "A")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist")

summary(Net)
plot(Net)


However, a warning is in order: you have a very large network and I am not sure a plot will be all that informative. It will probably look like a big ball of yarn. I am also not sure how well these libraries deal with such large datasets. I suggest you take a look at the documentation for the network, statnet, and ergm libraries. The Journal of Statistical Software (v24/3) offers several articles covering these libraries. The issue can be found here:

http://www.jstatsoft.org/v24

• I dimly remember the world map of the facebook network, which was done in R. I think the author described his process in some detail in his blog. I suppose using that approach would generate a map that is informative even with 4 million nodes. – Owe Jessen Feb 16 '11 at 2:53
• Apologies for the naive question, but how do I convert a table into what you have as src and dst. This is what I typically do to load the file (now a tab-delimited file): el <- read.csv("comment-net/comments-ouids.tsv",header=T,sep="\t") – amh Feb 16 '11 at 20:45
• read.csv() should produce a data.frame. as.network() may read that directly or you may need to do as.matrix(el). – Jason Morgan Feb 16 '11 at 21:10
• I'm rather sceptical about these libraries being able to do much with a graph of millions of nodes. Have you actually used them with comparable datasets? – Szabolcs Oct 30 '13 at 15:35
• The poster was referring to a network with 4 million edges, not nodes. I have used the statnet family of libraries on an undirected network of more than 3500 nodes (~8 million possible edges). That was quite doable, especially when the goal was just to calculate network statistics. I have even estimated ERGMs on networks of this size. But your point is well taken; I doubt networks of millions of nodes could be easily analyzed. – Jason Morgan Oct 30 '13 at 21:29

I don't think that R is a first choice here (maybe I'm wrong). You will need huge arrays here to index and prepare your networks files in the appropriate data format. First of all, I will try to use Jure's (Rob mention him in the post above) SNAP library; it's written in C++ and works very well on large networks.

• Thanks for mentioning SNAP. I am looking into it. Have you used it? The centrality sample that comes with it seems close to what I want. I tried modifying it so it works with my multi directed graph data but it failed to compile. I am not sure if it is appropriate to ask a question about it here, so I might create a new Q. – amh Feb 16 '11 at 15:13
• @andresmh, you might try reducing your graph to have a single observation per directed pair first. For the eigenvalue stuff, your data is likely similar or equivalent to a weighted random walk on the graph. I'm not sure if SNAP supports that, but it's likely to. If all else fails, you might send a very specific email to Jure. He's a very nice guy, so I wouldn't be surprised if he provided some quick guidance. – cardinal Feb 16 '11 at 15:32
• @cardinal: I found a sample code in SNAP that does exactly what I want but for a undirected graph. I think my graph is what the SNAP docs calls "directed multi-graph". So I changed just one line in centrality.cpp from TUNGraph to TNEGraph (see pastebin.com/GHUquJvT line 24). It is not compiling anymore. I suspect it requires a different type of node? The error I get is: centrality.cpp:24: error: conversion from ‘TUNGraph::TNodeI’ to non-scalar type ‘TNEGraph::TNodeI’ requested (see full error at pastebin.com/86mCbByG) – amh Feb 16 '11 at 20:20

Gephi ( http://gephi.org/ ) might be an easy way to explore the data. You can almost certainly visualize it, and perform some calculations (though I have not used it for some time so I can't remember all the functions).

From past experience with a network of 7 million nodes, I think visualizing your complete network will give you an uninterpretable image. I might suggest different visualizations using subsets of your data such as just using the top 10 nodes with the most inbound or outbound links. I second celenius's suggestion on using gephi.

• @andresmh, Maslov and Sneppen (Science, 2002) have a visualization that might be useful in this context. Searching through recent stats/comp-sci--related citations of this work, I found this as well. Here may be another related work. – cardinal Feb 17 '11 at 19:06

If you're concerned with the size of the network, you could try the igraph package in R. And if that performs poorly inside R, it might do better as Python module. Or even the networkx package for Python

Do you suspect that the network has a small number of very large connected components? If not, you can decompose it into distinct components which will make it much easier to compute measures of centrality.

• +1 to this - if its an entirely connected component, that's one thing, but if you can decompose the network, you have both smaller data, and actually several independent networks that can be analyzed in parallel. – Fomite Oct 9 '11 at 20:46

There are several R software packages one could use, including "sna" and "network". One thing I wouldn't necessarily rely on if you're having performance issues with sna is NetworkX. I love NetworkX to death, and use it for most of my analysis, but NetworkX is quite proud of being a mostly purely Pythonic implementation. It doesn't particularly exploit speedy pre-compiled code well, and sna often outpaces NetworkX by a considerable margin.