9
$\begingroup$

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 
4210369 comments.csv
Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – cardinal
    Commented Feb 16, 2011 at 3:03
  • $\begingroup$ Even plotting 4 million points might take a while... $\endgroup$
    – Wok
    Commented Feb 16, 2011 at 15:00
  • $\begingroup$ @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. $\endgroup$
    – cardinal
    Commented Feb 16, 2011 at 15:36

7 Answers 7

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Owe Jessen
    Commented Feb 16, 2011 at 2:53
  • $\begingroup$ 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") $\endgroup$
    – amh
    Commented Feb 16, 2011 at 20:45
  • $\begingroup$ read.csv() should produce a data.frame. as.network() may read that directly or you may need to do as.matrix(el). $\endgroup$
    – Jason Morgan
    Commented Feb 16, 2011 at 21:10
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Commented Oct 30, 2013 at 15:35
  • $\begingroup$ 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. $\endgroup$
    – Jason Morgan
    Commented Oct 30, 2013 at 21:29
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – amh
    Commented Feb 16, 2011 at 15:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – cardinal
    Commented Feb 16, 2011 at 15:32
  • $\begingroup$ @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) $\endgroup$
    – amh
    Commented Feb 16, 2011 at 20:20
3
$\begingroup$

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).

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – cardinal
    Commented Feb 17, 2011 at 19:06
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +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. $\endgroup$
    – Fomite
    Commented Oct 9, 2011 at 20:46
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.