The Sociograph

Talk on Facebook data, Privacy, and Scientific Research at Chaos Communication Congress

2012-01-11T16:54:00.000Z

Over the holidays I gave a presentation on how privacy issues surrounding Facebook data are affecting scientific research (the talk is about 30 minutes long, with 10 minutes of questions). I'm glad to see that it's been posted and the recording is high-quality, both in terms of editing and audio/video quality.

I try to flesh out the problems in the context of an example, the Taste, Ties, and Time dataset and it's "evil twin" the Facebook100 dataset.

Below you find the talk on Youtube, or you can download a high quality version here.

A gotcha with numpy's searchsorted

2011-12-05T16:09:00.001Z

Photo courtesy of Mike Fischer

I'm using numpy's searchsorted function find an item in a sorted numpy array with more than 1 billion entries. This should be quick, but each query was taking nearly a minute--why was this so slow?

My queries looked like this:

left_idx = numpy.searchsorted(mmap_fp, key, side="left")

The problem, as it turns out, is that my data array is of type numpy.uint64, while my key is simply a normal python integer. This causes things to slow way down. So the following code runs much more quickly than the code above:

left_idx = numpy.searchsorted(mmap_fp, numpy.uint64(key), side="left")

I find this annoying because there is no mention of this important point in searchsorted's documentation. It's not exactly a bug, but I think it falls under the category of "gotcha," which Wikipedia defines as follows:

In programming, a gotcha is a feature of a system, a program or a programming language that works in the way it is documented but is counter-intuitive and almost invites mistakes because it is both enticingly easy to invoke and completely unexpected and/or unreasonable in its outcome.

Scalable mean-shift clustering in a few lines of python

2011-11-18T13:49:00.001Z

In my last post, I gave a hand-wavy, intuitive explanation of the mean-shift algorithm. Here I show a concise implementation which, while simple, will scale to cluster several million points quickly.

Part of making this implementation scalable involves choosing seed positions for the kernels cleverly---I'll present a simple solution for this problem below, but first, let's look at the core of the algorithm. The code below is based on code I've submitted to the scikit-learn machine learning library---much of the credit for it goes to other scikit-learn developers. If you actually want to use this implementation, I suggest you use the version in the scikit-learn library.

The following code goes through a list of seeds serially, creates a kernel for each seed from that seed's position, and keeps shifting that kernel to the weighted mean of the points contained within it until either its position has converged, or a maximum number of iterations have occurred.

Notice that when we lookup the nearby points of a kernel, we use a data structure called a ball tree to efficiently query all points within a given radius. I've imported this structure (as well as other useful functions) from the scikit-learn library.

The function above will return one cluster center for each of the seeds. Many of these seeds will have converged to the same or nearly the same position, and thus you may want to weed out duplicate clusters from the output. Because it's not really pedagogically relevant, I've left this step out here---if you want to see how this is done, look at the source code of the scikit-learn implementation.

The mean_shift function takes a kernel update function as one of its arguments. We need to implement these as well---here are update functions for perhaps the two most commonly used kernels: the flat kernel and the Gaussian kernel:

In these two kernels, the bandwidth parameter (which is the most important parameter in mean shift clustering) has somewhat different meanings. In the Gaussian kernel it acts as the standard deviation of a normal distribution, so you want to set it such that nearly all of the points within a cluster will fall within 3X bandwidth from the center of the cluster. In the flat cluster, the bandwidth is the radius of the cluster, so all points should fall within 1X bandwidth.

As I mentioned above, to make this implementation scalable, you need to seed the initial positions of the kernels cleverly. The following code takes all of the data points, discretizes them by pushing them onto a grid (whose coarseness can be controlled with the bin_size argument), and then takes those points on the grid that have at least min_bin_freq points.

In my work on clustering geotags to find points of interest, I've found that if I set bin_size to about twice the bandwidth (using the Gaussian kernel) or the same size as the bandwidth (using the flat kernel), the results are good.

An accessible introduction to mean-shift

2011-11-17T13:40:00.001Z

Summary
This post provides a brief description of the mean-shift algorithm, as well as a discussion of two of its variants (the flat kernel and the Gaussian kernel). In my next post, I provide a concise implementation in python. Mean shift is a clustering algorithm; its strength is that one need not specify the number of clusters to be found in advance.

Mean shift clustering
Imagine that you have a bunch of points in two dimensional space, and you draw a circle somewhere in this space (let's assume at least one of the points is inside this circle). This circle is a called "kernel" in the mean-shift jargon. For now, you can just think of a kernel as defined by its center and its radius, where the jargon term for the radius is the "bandwidth." The bandwidth is essentially the only parameter of the mean-shift method (other than the choice of kernel, which I'll discuss below).

The task at hand is to shift this kernel (i.e., nudge its center) such that more points are contained within it. We keep shifting this kernel until there is no direction we can shift it such that more points will be contained within it. That's the basic idea: it's a hill climbing algorithm. Thus, in the figure below (taken from this paper), if our kernel starts off as the green circle in the bottom-right, after it's first iteration it might end up in the position of the orange circle, and it might keep moving until it converges to the location of the red circle.

But how do we calculate the sizes and directions these shifts (i.e., the mean-shift vector)? It's simple: we just move the kernel to the mean position of all the points within it (i.e., the centroid). I assume that's where the algorithm gets it's name: we iteratively "shift" the kernel to the mean of the points within it. Actually, that's what we do if we've chosen to run the algorithm using a "flat kernel." Other kernels just give us different ways of calculating a weighted mean. For example if we use a Gaussian kernel, then every point is first assigned a weight that decays exponentially as the distance from the center of the kernel increases.

To some of you familiar with other clustering methods, this mean-shift clustering might sound familiar, and with good reason: there are some interesting equivalences between mean-shift and other clustering techiniques. K-means clustering has been shown to be a limit case of mean-shift clustering, as described here. Also, mean-shift with a Gaussian kernel has been shown to be equivalent to expectation maximization.

Why might a Gaussian kernel be better than a flat kernel?
The flat kernel simply wants to have as many points as possible located in it, while the Gaussian kernel wants as many points possible near its center. This means that the flat kernel will be more likely to try to cover up two or more distinct clusters because it doesn't care if the dense cluster centers are located at its periphery. The following image (which contains two clusters, one above the other) demonstrates this behavior:

Whereas the flat kernel (below) simply tries to cover as many points as possible, the Gaussian kernel assigns a higher weight to points nearer to its center.

The Gaussian kernel gets it right because in its calculation of the weighted mean, it weights points nearer the center higher than points near the periphery.

How can we make mean-shift scalable?
While a naive implementation of mean-shift is not very scalable, a few straightforward measures allow it to run on datasets containing tens of millions of points.

Do efficient neighbor lookup: First, for each mean-shift iteration, we can look up only nearby points because with a flat kernel, points beyond the bandwidth are irrelevant to the mean shift calculation, and with the Gaussian kernel these will have little effect. There are a couple of data structures that allow one to efficiently query only the nearest neighbors of a given point, such as the k-d Tree or the ball tree (the ball tree should scale better in higher dimensions than the k-d tree).

Seed with binned points: Next, we can observe that kernels that are initiated next to each other tend to converge to the same clusters. So we can bin (i.e., discretize) the data points by pushing them onto a grid, and use only populated points on the grid as kernels. Furthermore, we can set some threshold and use only those bins with at least that many points as kernels.

I've noticed that if you filter out points on this grid that are populated with very few points, then this technique also solves another problem: kernels starting out and getting stuck in very sparse regions where no cluster exists. For example, in the image above, there is one lonely point in the top left. If we start a Gaussian kernel here, it will likely get stuck there, and end up as a cluster with only one or two points in it. However, if we filter out bins with just a couple of points in them (as I did to create the clustering visualized in that image), then no kernel will be initialized there.

For a more extended, technical discussion about how to speed up mean-shift, see this paper.

Clique percolation in a few lines of python

2011-11-05T20:04:00.001Z

Photo courtesy of noricum.

Update: Thanks to Aaron McDaid and Fergal Reid for catching a couple of bugs (I was percolating on cliques sharing k rather than k - 1 nodes, and forgot to leave out cliques with fewer than k nodes) also cliques that didn't percolate were being left out.

One well-known algorithm for detecting overlapping communities is called the Clique Percolation Method (CPM). While in my experience this algorithm is problematic, it is nonetheless well-known and widely used, probably because the method was published in Nature, was timely, and because the authors created an easy-to-use implementation called CFinder.

This algorithm is not yet in python's NetworkX library (Update: the code below made it into NetworkX 1.6). That's no problem though, because if you think of the algorithm in terms of finding connected components in the "clique graph," it is very easy to implement. Given some graph G, here's how you create G's clique graph:

Find all cliques in G. These are the "nodes" in G's clique graph, but to avoid confusion I'll call them cliques in what follows.
Compare every pair of cliques. If they share at least k - 1 nodes, then draw an edge between the pair of cliques in the clique graph.
Find the connected components in the clique graph--these are your percolated cliques! For each connected component return the set of nodes (from G) that are in that component.

That explanation is short but maybe a little unclear because I am describing a graph and it's clique graph, so words like node and clique are ambiguous. The code is less ambiguous:

That implementation is correct but expensive---it requires O(N^2) clique comparisons, where N is the number of cliques (which is often much larger than the number of nodes!). If we use a python dictionary to index which nodes belong to which cliques, then we can easily compare only those cliques that share at least one node in common. This implementation is a bit longer but should be much more efficient:

Fast I/O and compact data with python / numpy's memmap

2011-11-04T11:34:00.003Z

Image courtesy of fernando

Update: I discovered a bug in the way I was benchmarking these---the memmap parser ends up being 4X (not 30X) faster than the naive python parser (but the memmap method should still take up substantially less memory). Actually, it's 4X faster if the data is read in from the memmapped file using a for loop. But the bottleneck here is not I/O, it seems to be python's need to make a separate function call for each piece of data. If I were to benchmark using a vectorized numpy operation, then the memmap parser would, I suspect, be much faster, and disk I/O would be the bottleneck (this benchmark is on my to-do list, and I'll update this post once I've run it).

I've notice that I'm turning into a python evangelist lately, but I often need to face a hard fact: python, when used naievely, is slow and memory inefficient! However, there are all sorts of tricks you can use to speed it up and use less memory, such as use NumPy. Here I'll cover a little trick that allows one to quickly read in files that might not even fit in memory using NumPy's memory mapped files.

I'll explain how to use mmap in terms of an example: parsing in network data. Let's say I have my network data in the following edgelist format:

nodeID1 nodeID2 edgeweight

nodeID1 nodeID3 edgeweight

...

The straightforward python parser might look like this:

However, this parser won't be as fast as you'd like, mostly because python does not know how large the edgelist will be, so it needs to keep dynamically allocating memory over and over again. To read in 1,000,000 edges this parser takes 3.13 seconds, which isn't great. Even if we could allocate the memory in advance, python's split function and even its coversion of strings to integers isn't as quick as you might be used to if you use unix's command line tools like cut or sort. Additionally, the edgelist will take up more memory than is needed, because python int and float objects take up much more memory than in C/C++/Java.

Does this mean that python doesn't scale? No, it just means we should be using numpy.

Here's a solution that has four nice features

It stores data in a binary format. Once created, the data does not need to be parsed from text to binary each time.
It elegantly handles the case where the (binary) data does not fit into memory. You can still iterate over the edges as if they were all in memory---presumably the operating system's virtual memory is used to handle what won't fit.
Data is represented compactly and with a predictable size. The data is just as compact as if you were using C or Java, and you have full control over the types (e.g., signed or unsigned ints, 32-bit or 64-bit ints), which is not usually the case in python.
It's fast: To read in 1,000,000 edges takes only 0.788 seconds, which is 4X faster than the python parser above. If I had a slower disk (this is on my laptop's fast ssd), this difference might be smaller be smaller, because the "parsing time" would make up less of the overall runtime, and the I/O would make up more of it.

For more information on using numpy's memmap, check out the official documentation.

Converting huge edge list files to pajek format

2011-11-01T16:59:00.002Z

Some network analysis software requires the network to be in the pajek format. For example, I want to use Rosvall et. al's handy Infomap algorithm to perform community deteciton on a large network dataset, and his implementation expects a pajek-formatted file as input. However, I usually store my networks in the simpler edgelist format, which is just a text file with one edge per line.

I've just written a little python script that converts edge list files to pajek format. The script takes in a simple edgelist file and converts it to a pajek file. There are similar converters out there on the web, but my converter's special trick is to use the unix sort command so that it can convert files larger than will fit in memory. There are options for weighted/unweigted networks as well as directed/undirected networks.

The script creates a tempfile, and in order to create the tempfile safely (so that if the script is terminated or crashes , it still cleans up behind itself), I use python's handy with statement. This means you'll need python 2.6 or higher to run it.

To see how to use the script, just type

python edgelist2pajek.py -h

You can download, criticize, fork, or imporve the code here. Here's what the sourcecode looks like:

<p>&amp;lt;br /&amp;gt;</p>

Compiling ATLAS by hand speeds up NMF in python 3X

2011-09-26T17:27:00.000+01:00

I've been doing some Non-negative Matrix Factorization (NMF) to co-cluster users and the locations that they visit, as in the figure below

Basically there is one important parameter, k, which you have to set and which determines the number of clusters to be found. NMF then returns two matrices, W and H, whose product approximates the original data. W has one row per tourist that tells you how much each tourist belongs to each cluster. H has one column per Point of Interest (POI) which tells you how much each POI belongs to each cluster.

I have been using the well-documented scikit-learn python library to perform the NMF, which is nice because it provides clear examples. Scikit-learn relies on numpy and scipy for fast matrix operations, and these in turn rely on a slew of low-level linear algebra packages (e.g., BLAS and LAPACK). BLAS, a linear algebra library written in Fortran, seems to be key to these operations. It is possible to compile BLAS with settings so that it is optimized for your particular machine using a program called ATLAS. As far as I understand it, ATLAS performs a bunch of tests to empirically determine the optimal way to configure BLAS.

Using the guide provided here (which thankfully does not assume you have root access), I used ATLAS to optimize all this linear algebra and get my python setup to use these optimized libraries. This is a rather involved process of compiling packages that took me more than half an hour. Was it worth it? A few benchmarks on my data show a speed-up of 3X (on a 24 core Dell server with Intel chips running at 2.4 GHZ). Note that I was not able to disable the CPU-throttling as recommended by ATLAS, so perhaps others who can do so will benefit even more.

Metropolitan Sinks: A tunable definition of metropolitan areas

2011-08-25T17:08:00.001+01:00

Metropolitan sinks with r=0.5 degrees (55 km).

Metropolitan sinks with r=1.5 (165km)

I'm working on a project that studies how behavior varies regionally. One of the basic prerequisites to this problem is a good definition of the term region. In some contexts there might be some obvious definition: in the USA, one might choose states, counties, or zip codes as the unit of analysis.

However, I am interested in some international datasets, and in this context a couple of problems arise. First, it's hard to find a definition of region that is consistent in many countires. For example, the U.S. has states, Canada has provinces, and Switzerland has cantons. There are great services such as Yahoo!'s GeoPlanet APIs which will inform your program that a canton is a direct child of Switzerland, just as a state is a direct child of the USA. Because the service will list the child units of any country, it might seem that we have a solution. But are these units equivalent across countries? Or are Swiss cantons so small that they should be compared to US counties rather than states? After all, the entire country of Switzerland is about the size of a typical US state, both in terms of population and area. So in an international comparison of regions, do we compare each Swiss canton to each U.S. state, or do we compare the entire Swiss nation to the states?

By using cities and their metropolitan areas as the unit of analysis, we can ignore these problems more directly compare regions globally. The website geonames.org provides a great dataset that contains the geographic coordinates and population (as well as other information) of apparently all cities and towns in the world which have at least 1,000 inhabitants. However, the competing definitions of metropolitan area again make international comparison difficult.

The "correct" definition of metropolitan area will depend on how the definition is to be used. In my case, I have varied datasets which show how people from places around the world use social media sites. Each person can be resolved to a latitude and longitude using, for example, Yahoo!'s Placemaker API. Then the task is to assign a metropolitan area (if any) to each of these coordinates. In other words, we need to bin users geographically. While binning, we should keep in mind that although these datasets are in some sense large (based on millions of users), they are also sparse: there are suburbs, small towns, or villages in which nobody is a user of LastFM or Flickr. That means if we use each town as a bin, we will have many bins with very few users or no users, making it difficult or impossible to recognize trends. So the sparser the data, the larger we want the bins to be so that each one contains enough users for trends to be recognized. Rural regions will likely not have towns with enough users for trends to be recognized, so in practice we will be analyzing only densely populated areas, and we need to decide how many suburbs and surrounding areas do we associate with each city. Ideally we would have a single parameter that we could tune which control how many of the surrounding suburbs and town are bundled in with each metropolitan area.

Although one probably exists, I am not aware of any such parameterized definition of metropolitan area. It is, however, easy enough to come up with a hacky definition that is useful enough to work with. I propose the following procedure for detecting what I call "metropolitan sinks":

Insert city (i.e., city, town, or village) as a node into a graph.
For each city c, take all cities within a radius of length r and find the largest. Call this largest city n. Draw a directed edge from c to n. Self loops are allowed.
Find the weakly connected components in the graph constructed above. These are the metropolitan sinks. Each connected component will have one sink node---this is useful for naming each metropolitan area---for example, Chicago will be the sink of the Chicagoland area.

You might also want to filter out metropolitan sinks whose sum population is below some threshold---that will ensure that not every remote village is recognized as a metropolitan sink. The above procedure requires you to look up all points within some radius of a given point. To do so efficiently, you can use a k-d tree; it's easy to do so in python using the scipy.spatial -- see for example this solution to the problem.

What does this definition give us? To answer that question I have tried to visualize the results. To produce the visualization, I first calculated the alpha shape (a.k.a., the concave hull) of each metropolitan area, and then exported those alpha shapes into a KML file that can be viewed in Google Earth. At the top of this post, you see the the metro sinks of the eastern US with r set to 0.5 and 1.5 decimal degrees. Below you see the same for most of Europe. (Note that only cities of size 1000 or larger are included, and only those metropolitan areas with a total population of 10000 or larger are included. Also, if a metropolitan area is a single city or just two cities, then it is just a point or a line, and so will not be visible in the images.)

Metropolitan sinks with r=1.5 (165 km)

Metropolitan sinks with r=0.5 (55km)

Is this a perfect way to bin cities into metropolitan areas? No, but it's good enough for my purposes. I can make these coarser or finer depending on how sparse my data is. The are some clear imperfections, but none that will likely be very important. For example, you can see that with the larger radius (1.5 decimal degrees or 165 km), a few towns in northern France are in the metropolitan sinks of Southhampton and Bristol. But all in all, these metropolitan areas provide a reasonable way to bin geographic space into regions internationally, and it requires only an initial list of cities with their coordinates and their populations.

Metropolitan sinks with r=0.5 decimal degrees (55km).

A tutorial introduction to network analysis in python

2011-07-25T13:25:00.000+01:00

Derek Greene recently presented a tutorial at the Web Science Summer School in Galway, Ireland. I find that his slides and supporting material not only give a nice introduction to network analysis, but also to my favorite software library for network analysis, NetworkX.

For those of you who haven't used NetworkX, it's a truly pythonic environment for network analysis (in comparison to projects like iGraph or python boost graph, which just provide bindings to a C++ library.) This comes with many advantages like clean syntax and interactivity, and the distadvantage of being less scalable. Still I've used it for graphs with tens of thousands of nodes and over one million edges. One other nice thing about NetworkX is its active community and project leader, Aric Hagberg.

Communication networks part 3: The University of Kiel E-mail dataset

2011-05-09T11:57:00.001+01:00

Summary, download
I'll first briefly introduce the data and provide the cleaned files for download---if you're interested in the details of the data and the steps I took to clean it, read the following sections.

As I mentioned in the two previous posts in this series, I'm working on creating models of event-based networks, such as those formed by personal communication (the previous two posts are on the Enron e-mail dataset and the MIT Reality Mining dataset). Before using this data, I'm examining it to get a feel for its limitations and trying to clean it up. I'm also sharing up the data in its final cleaned form so others can replicate any experiments I perform with it.

In this post I describe a dataset that was introduced in a paper from Ebel et al. called Scale-free topology of e-mail networks. The original dataset can be downloaded here. In the above-menitoned paper, there is very little description of the where the data came from, basically only the following description:

The e-mail network studied here is constructed from log files of the e-mail server at Kiel University, recording the source and destination of every e-mail from or to a student account over a period of 112 days. The nodes of the e-mail network correspond to e-mail addresses which are connected by a link if an e-mail has been exchanged between them. The resulting network consists of N = 59 812 nodes (including 5165 student accounts) with a mean degree of k=2.88 and contains several separated clusters with less than 150 nodes and one giant component of 56 969 nodes (mean degree =2.96)...Let us briefly discuss how our result on e-mail networks may be influenced by the measurement process. The sampling of the network has been restricted to one distinct e-mail server. Therefore, only the degrees of accounts at this server are known exactly. Here, these internal accounts correspond to e-mail addresses of local students, whereas the external nodes are given by all other e-mail addresses.

The cleaned dataset contains 392,280 events sorted by time. The "edges" file, available here, contains information on each event, which is known to the nearest minute. You can get the edges file here. It is in the following format:

unix_timestamp;sender_id;receiver_id

The "attributes", available here, file labels each node as either in the core or in the periphery. It is in the following format

node_id;bool

where the value of "bool" is 1 if the node is in the core, and 0 if the node is in the periphery.

A problem: sparsity in the "core" of the dataset
Just as in the other two networks, one important aspect of the Kiel data is the notion of core and periphery. We have complete e-mail data for only those 5165 nodes in the core, and for the other approx 50,000 nodes in the periphery we know only how they communicated with nodes in the core. A closer look at the data reveals a serious limitation with the dataset: the vast majority of communication is between the core and the periphery. In the original, uncleaned data there are 447,533 events. Of these, only 6,256 (1.4%) take place between nodes in the core. After performing a couple of cleaning steps outlined below, only 0.6% of the communication events take place in the core. So although this dataset is in one sense large because it contains nearly half a million events, if you're interested in the subset of nodes among whom all communication is known, then it is quite a small, sparse dataset.

Cleaning the data: removing self-messages and spammers
Given that I'm interested in how information could spread in a communication network, I want to remove e-mails that people send to themselves. Surprisingly, more than half of all of the communication events in the core (3,301 of 6,256) were self-loops.

Additionally, I wanted to remove messages from spammers or large mailing lists so that in the end the data would contain only personal communication written by humans. Spam can be identified by a large number of e-mail being simultaneously sent by the same source. However, I also noticed that there were a couple of days in which a single sender would send out thousands of e-mail within the same hour. As one can see in the plot below, this behaviour was anomalous:

All Per Hour Hist

To remove such suspiciously spammy e-mails, I used the following procedure: if more than 20 e-mail came from the same sender in one hour, then I consider that all messages from that sender in that hour were spam, and I removed it from the dataset.

Periodicity, Stability
In contrast to the other event datasets, the Kiel dataset is quite stable. This is probably because, in contrast to the MIT Reality Mining dataset, people did not need to actively participate, and they had no option to "opt-out." Also, in contrast to the Enron dataset, there is a much bigger core (around five thousand accounts rather than around 150 accounts), and the period of observation is briefer (just 112 days), meaning that not as many people come and go. In the following plot we see the number of e-mail events per day---note that you can see the weekends, one holiday (in Germany October 3rd is the day of German Unity), and a strange gap in the middle---perhaps the e-mail server went down.
Kiel All Cleaned Contiguous Over Time

If we look at a finer resolution --- the number of e-mail sent per hour --- we also see stable periodicity
Kiel All Cleaned Contiguous Over Time Hourly

Note that in the original dataset, only the month, day, hour, and minute of each e-mail is given. Thus, it's not clear from which year this dataset comes. But given that the paper that introduces this dataset was submitted for publication in early 2002, it seemed likely to me that the data comes from 2001. This guess is further supported by the fact that in 2001 the holiday on October third landed on a Wednesday, a fact which is compatible with the data. One can also observe that there were somewhat more e-mails sent out on Sept. 11 than usual, indicating that the year would be 2001.

Distribution of messages / dyad
To get a feeling for the data, it's also useful to look at the distribution of messages per dyad. Note that below only those dyads are considered if there was at least one message between them. Also, the distributions below are for directed dyads (the plots for undirected dyads look similar). The first plot shows the distribution for all dyads, the second for only those dyads in the core.
Dyad Distro Directed All

Dyad Distro Directed Core

We note that there are a few dyads between which many more messages were sent than normal. For example, one e-mail address sent another one 7000 e-mails within the 112 day period (over 60/day on average).

Communication networks part 2: the MIT Reality Mining dataset

2011-04-13T20:02:00.003+01:00

One view of the network created by contact among participants in the MIT Reality Mining dataset

Like the last post in this series of three, this post is half intended to serve as self-documentation. It should also be anyone who wants to use the MIT Reality Mining dataset and wants to understand some nitty-gritty details, as it includes some information that's not in the official description of the data. Additionally, if you're just after a cleaned up dataset in a simple form, I provide that below.

The MIT Reality Mining Dataset is based on a quite high-profile collection of behavioral data. The data can be obtained from the official site (annoyingly, you have to e-mail someone to get the link to download the data, but the response time is good). The official read-me is a good place to begin to understand the data. Here's the abstract from that readme:

The Reality Mining project was conducted from 2004- 2005 at the MIT Media Laboratory. The Reality Mining study followed ninety-four subjects using mobile phones pre-installed with several pieces of software that recorded and sent the researcher data about call logs, Bluetooth devices in proximity of approximately five meters, cell tower IDs, application usage, and phone status. Subjects were observed using these measurements over the course of nine months and included students and faculty from two programs within a major research institution. We also collected self-report relational data from each individual, where subjects were asked about their proximity to, and friendship with, others.

One impressive feature of this dataset is that the phones that people carried around were nearly always on, as the following quote from the readme summarizes:

On average we have logs accounting for approximately 85.3% of the time that the phones have been deployed.

The data includes three types of social networks: phone calls, SMS messages, and proximity (via bluetooth). In what follows I will extract time-stamped communication events from only the voice communication.

A core of 94 people that collectively contact a periphery of 26,965 people
One important aspect is that there is a "core-periphery" structure to the data, i.e., it includes a "core" of 94 people for whom we know all communication data during their active people; additionally, there is data on all of the tens of thousands of people in the "periphery," i.e., those who had contact with the core. For a person in the periphery, we know only about his communication with the core. The vast majority of communication is between the core and the periphery. Crucially, we do not know about communication that takes place between members of the periphery.

Participation in the study varies over time
Unlike the Enron dataset, we don't have to worry about noise brought in to this data from broadcast-style communication, because mobile phone communication is inherently dyadic (between two people, except for three-way calls, which are rare enough that we can probably safely ignore them). However, in this dataset we have to worry about attrition; i.e., the tendency of people to drop out of the study. If we look at the following chart we can see that although the study was conducted over the course of a full academic year, there is a relatively short period during which the study is in full swing.

Because I'm interested in network data, I am interested in periods during which a large number of people are simultaneously involved in the study. The periods with few users contain much less information on the communication in the core of the network, i.e., the part for which we know about all pairwise communication events. For that reason, I am only going to include communication that occurs between midnight on Sept 24, 2004 and midnight on January 8th, 2005, in which the study was in full swing. This range is outlined in red in the image above.

Periodicity
It's interesting to look at the frequency of communication within these periods. If we aggregate by days and plot the number of communication events per day, we get the following chart (minor tick marks correspond to weekends):

It's hard to make much from the data aggregated at the daily level. We can see a spike on Nov. 2nd that is likely related to the presidential election, and we can see a lull at the end of December that might correspond to the winter break. If we look at events aggregated on a finer level, on an hourly basis, an more interesting periodicity emerges:

Above you can more clearly the periodicity and see things like that election day (November 2nd) was an anomaly (actually you have to zoom way in to see anything, and at that zoom level Scribd does something bad -- click on the download link and examine the original to see clearly). You can also see that there were many calls made late in the night on Halloween (which was on a Saturday night) --- we should expect this given that many of the participants were students. People also seemed to take it easy with phone communication on Thanksgiving morning. On the other hand, I don't see the spike in communication that I would have expected late in the evening on New Year's Eve.

Download
I used this python script to parse the data. The resulting list of communication events can be downloaded here and contains 52,050 calls between 27,059 people, 94 of whom are in the core. It output this file of communication events, and this file which indicates which nodes are in the core and which are in the periphery. The format of the communication events is a bunch of lines with the following form:

unix_timestamp;caller_id;receiver_id;duration_in_second;communication_type

This file indicates which nodes are in the core, and it has the following form:

node_id;bool

where bool==1 if the node is in the core and 0 otherwise.

A couple of notes
It occurred to me that in the above plots, I count each call as two communication events (an edge in each direction), so there are the number of calls is actually twice the number it should be.

There is some uncertainty about the exact time of communication events. The official readme did not specify which representation of time was used. The data was contained in a matlab object, in which time was usually represented in the following form:

731965.04835648148

I wasn't sure what this was, but it must be matlab's datenum format. I nearly fell into some dangerous traps as I converted this format into python's DateTime objects (I've documented this conversion process here), and the main remaining uncertainty has to do with the timezone. The data should be in UTC time because that's the timezone that matlab's datenum objects are assumed to use, but I don't think they are. I think they're in Eastern time, and so I've subtracted 5 hours from them. On top of this confusion, the data spans a time in which there was a transition from daylight savings time to standard time, and I don't know what to do about that. I contacted someone who is in charge of the dataset, and although he was generally very helpful about answering questions, to this one he just replied: "I'd assume Eastern or GMT" which was utterly unhelpful.

Converting MATLAB's datenum to Python's datetime

2011-04-12T18:45:00.003+01:00

Image courtesy of servus.

It's often convenient to represent a date and a time as a single number. This is commonly carried out by choosing some arbitrary point in time as the "epoch," and specifying time as the number of seconds or days from that epoch.

The most common way to represent time as a number a UNIX timestamp, which is the number of seconds since midnight on Jan 1st, 1970 in UTC, (not including leap seconds). If you're trying to decide which way to represent time as a number use UNIX timestamps and ignore the rest of this post.

I was recently confronted with the task of converting times stored in a matlab object into a python datetime object, and very nearly made a big mistake (366 days big, to be exact). The matlab representation of time looks like this:

731965.04835648148

If you parse this using python's

datetime.fromordinal(731965.04835648148)

then the result might look reasonable, but beware: you're off by 366 days! Matlab's datenum representation is the number of days since midnight on Jan 1st, 0 AD. Python's datetime.fromordinal function assumes time is the number of days since midnight on Jan 1st, 1 AD. So the duration of year 0 separates the time representation returned by python's fromordinal function and the time representation used by matlab. Apparently, the year 0 AD had 366 days, (can anyone confirm this?) so one can convert a matlab datenum to a python datetime as follows:

from datetime import datetime, timedelta
~~python_datetime = datetime.fromordinal(matlab_datenum) - timedelta(days=366)~~
python_datetime = datetime.fromordinal(matlab_datenum) + timedelta(days=matlab_datenum%1) - timedelta(days = 366)

Update: In order to achieve precision beyond days, you need to take care of the fractional part of the datenum with the + timedelta(days=matlab_datenum%1) term.

While representations of time are inherently arbitrary. The problem seems to have come up because there are different versions of the Gregorian calendar system.

For dates before the year 1, unlike the proleptic Gregorian calendar used in the international standard ISO 8601, the traditional proleptic Gregorian calendar (like the Julian calendar) does not have a year 0 and instead uses the ordinal numbers 1, 2, … both for years AD and BC. Thus the traditional time line is 2 BC, 1 BC, AD 1, and AD 2. ISO 8601 uses astronomical year numbering which includes a year 0 and negative numbers before it. Thus the ISO 8601 time line is -0001, 0000, 0001, and 0002.

So python's datetime.fromordinal method assumes that people are using the traditional propleptic Gregorian calendar, whereas matlab assumes people want to use the ISO Gregorian calendar. Why doesn't python stick to the ISO standard here?

Communication networks part 1: the Enron e-mail dataset

2011-04-04T22:18:00.003+01:00

This post is half intended to serve as self-documentation. I also just want to share a parsed version of an e-mail communication dataset in the hope that it will help others reproduce my experiments or save them time in their own experiments.

I'm interested in logs of direct communication (i.e., phone communication, e-mail communication, and not things like message boards or mailing lists). I'm not interested in the content of the communication---in fact, all I want is a file which contains data in the following form:

unix_timestamp;sender;receiver
...

In this post I outline how I processed the Enron dataset into this form, and the filtering steps that I took. In upcoming posts I'll describe how I processed two similar datasets: one on e-mail logs from students at the University of Kiel and one on the call logs of some participants in a study at MIT.

This is a rather long post with lots of detail, so I'll begin by cutting to the conclusion and summary:

In summary: The resulting dataset includes 240,947 communication events among 28,062 addresses. The 192 e-mail addresses that belong to the 156 members of the "core" have been disambiguated so that each person in the core is represented by a unique identifier. Events with clearly invalid timestamps were removed. The data was further filtered so that none of the communication events come from e-mail that had more than three recipients, and if a message comes from a address-hour combination such that more than 20 messages were sent by that address in that hour, then the message was excluded.

UPDATE: I noticed that I accidentally selected the date range starting from Jan. 1st, 2001 because I said that after this date the vast majority of events take place. Actually the date where the communication really takes off is a year earlier, around Jan. 1st, 2000. I've updated the files below to include all nodes since Jan. 1st, 2000.

Download: You can find the parsed list of events here (the format is as indicated above). Additionally, this file indicates which indicates which nodes belong to the core and which belong to the periphery. The format is as follows

node_id;boolean

where if boolean==1, then the node belongs to the core, and if boolean==0, then the node belongs to the periphery.

The Enron Dataset: a description and the pre-processing steps I took

A good starting point to describe this dataset is the abstract of the paper that introduces it:

A large set of email messages, the Enron corpus, was made public during the legal investigation concerning the Enron corporation. This dataset, along with a thorough explanation of its origin, is available at http://www-2.cs.cmu.edu/~enron/. This paper provides a brief introduction and analysis of the dataset. The raw Enron corpus contains 619,446 messages belonging to 158 users. We cleaned the corpus before this analysis by removing certain folders from each user, such as “discussion_threads”. These folders were present for most users, and did not appear to be used directly by the users, but rather were computer generated. Many, such as “all_documents”, also contained large numbers of duplicate emails, which were already present in the users’ other folders...

This dataset is unique in that privacy seems to be completely disregarded. The full text of e-mails is there for all to see, even though many of the e-mail are quite personal. As far as I know, real names and e-mail addresses are used.

After reading the literature on this dataset, I was initially overwhelmed by it. The dataset includes a lot of "noise" created by the fact that some e-mail are merely automated reports, some people have many e-mail addresses, many e-mail messages are duplicated in various ways, e.g. by people putting the same e-mail in many folders. A couple groups of researchers such as a group at C arnegie Mellon University and another at Berkeley have come up with cleaned, yet conflicting versions of the dataset. In the end I found the data in a nice format at infochimps -- this version is based on the Berkeley version because according to the infochimps dataset description, "after inspecting both [the CMU and Berkeley versions], it became clear that the UC Berkeley dataset contains more dimensions of the original data".

It's important to keep in mind that although this dataset contains information on the e-mail communication of over 87,000 e-mail addresses, the "core" of the network contains only 156 people (the abstract above says 158, but the version on infochimps is slightly different). In other words, we have complete information on the e-mail communication of only the 156 people in the core. For everyone else, we about only those e-mail that were also sent to one of the core members. So an important first step is to clearly fish out of the data which nodes belong to the core and which belong to the periphery. This is basic, but analysis in some papers, e.g., this one which I ran into yesterday, ignore this crucial distinction and report statistics on the aggregation of the core and the periphery, when clearly its more interesting to know these statistics about only those pairs of nodes in the core.

The second step I performed was straightforward: I removed events with invalid timestamps. A small proportion of e-mail all have one of a few different dates in the 1970s and 1980s. These times were easy to identify because a lot of messages were all reported as being sent within a single second at a few moments in these decades. The first timestamp after the mid eighties occurs at on Jan 1st, 1997. I filter out all events that take place before this date. Furthermore, the last few events take place in the year 2020---these are clearly mistakes and so I've filtered out all events after the end of 2005.

I carried out additional pre-processing with the intention of

removing automated e-mail notifications
removing messages that are sent out to too many people --- I want avoid including impersonal messages sent out to many people and focus on direct communication.
Keeping track of who is in the "core" of the dataset and who is in the periphery
Making sure that the nodes in the network represent people and not e-mail addresses (because some can have many e-mail addresses---we could carry out this step on only the 156 people in the "core.")

The third and fourth steps were straightforward to carry out. The first and second require answering two questions: (1) how many recipients can an e-mail have before we label it as an uninteresting "broadcast" type of communication that should be left out? (2) How can we detect automated e-mails? To answer the first question, it's helpful to look at the following plot

When interpreting the plot above, it's important to keep the following point in mind: each e-mail message turns into several e-mail events if it is sent to multiple recipients. So although only a minority of e-mails have more than 3 recipients, if we include them in the dataset these will have a disproportionate weight because exactly these messages create a large number of events. For example, if we include only those e-mails with 3 or fewer recipients, then then the dataset includes 242,000 email events, whereas if we include all e-mails, then the dataset contains 1,387,139 email events. In the end I choose to include only those messages with 3 or fewer recipients. I'll be the first to say that this is a bit arbitrary. But it seems like a good balance between filtering out impersonal e-mails and trying to include as much data as possible on communication. Also note that I decided to include all recipients when counting how many people have received an e-mail (i.e., direct recipients, cc'd recipients, and bcc'd recipients).

I assume that if an email address sends out more than max_sent_per_hour e-mails in one hour, then it's likely that some program is behind these messages and so I filter them out. It's not clear what value to use for max_sent_per_hour, but the following plot provides some feeling for this decision (note the log-scale in the y-axis):

Based on the chart, there seem to be very few mass-emails sent around (probably partly due to the pre-processing we did in the last step with multiple recipients). It seems reasonable to set max_sent_per_hour to 20, a value which filters out 0.28% of events. Of course this particular value is quite arbitrary---it could just as easily be 15 (which would filter out 0.73% of events) or 40 (0.04%), but at least the chart above indicates that the resulting dataset would not vary widely based on this choice. Again, the idea here is that if an address sends out more than 20 messages in one hour, then there's a relatively high probability that a program is behind those messages, and a relatively low probability that a person is behind them.

Here's a plot of the frequency of email over time:

There are some interesting features in the plot, such as the peak in December before the holidays, and the trough during the holidays (visible in December 2001 and 2002). There is a similar peak/trough in June 2001. The plot also suggests that although there are some emails starting at the beginning of 1997 and these continue until Jan 2006, the vast majority of the data is between Jan ~~2001~~ 2000 and April 2002. For this reason, anyone looking at the dynamics of this network may want to focus on only this range.

http://dl.dropbox.com/u/1800572/enron/enron-cleaned.edges

Facebook100 data and a parser for it

2011-03-05T17:49:00.003Z

Caltech's Facebook network, part of the Facebook100 dataset

A few weeks ago, Mason Porter posted a goldmine of data, the Facebook100 dataset. The dataset contains all of the Facebook friendships at 100 US universities at some time in 2005, as well as a number of node attributes such as dorm, gender, graduation year, and academic major. The data was apparently provided directly by Facebook.

As far as I know, the dataset is unprecedented and has the potential advance both network methods and insights into the structure of acquaintanceship. Unfortunately, the Facebook Data Team requested that Porter no longer distribute the dataset. It does not include the names of individual or even of any of the node attributes (they have been given integer ids), but Facebook seems to be concerned. Anonymized network data is after all vulnerable to de-anonymization (for some nice examples of why, see the last 20 minutes of this video lecture from Jon Kleinberg).

It's a shame that Porter can no longer distribute the data. On the other hand, once a dataset like that has been released, will the internet be able to forget it? After a bit of poking around I found the dataset as a torrent file. In fact, if anyone is seeding the torrent, you can download it by following this link ~~and it appears to be on rapidshare~~.

As Gephi's Sebastien Heymann noted, the dataset is a bit awkward to use if you don't have matlab. I've written a parser for it in python (which you can download here) that converts the 100 datasets into gml, graphml, and a simple edgelist-based format. To use it you will need to have scipy and networkx installed (both of these are python libraries). Then just put the script in the same folder as all those matlab files, and from that directory run the command

python parse_facebook100.py

That will create a subdirectory called output, which will be populated with one folder for each university dataset. In each university's subfolder you'll find the graphml, gml, and edgelist formats. The output takes up 4.4GB.

If you're interested to see some visualizations of these networks, check out my earlier post on the topic.

Problems with time-sliced network representations

2011-03-05T14:32:00.000Z

Lately I've been analyzing event-based network data. Whereas most network analysis looks at a static snapshot of a network, or a series of snapshots over time (panel data), in event-based data, each edge has a time-stamp which indicates when the interaction took place.

Communication is naturally represented by such a network, and if you're interested in how information could flow via communication, then network measures would ideally incorporate this rich temporal information.

In this post I'll briefly review some disadvantages related to static representations of this kind of data. Note that many of the so-called dynamic network analysis methods also suffer from these disadvantages, because they are based on, for example, splitting a network into non-overlapping snapshots. Such "time-slicing" flattens the temporal information of the network--I'll now explain why.

Why static representations of networks are lossy

For simplicity, let's consider a network with only three nodes. Let's assume that we know which nodes communicated over the course of a week, and that there were just two communication events. If we create the usual static network, it looks like this:

Static (flattened) representation of communication

Why is this representation lossy? Presented with the image above, it seems like node 1 could have indirectly received information about node 3, and vice versa. However, if we assume that the communication events did not take place at the same time, then it's impossible for both 1 to know about 3 and for 3 to know about 1. Instead, one of the following situations must be the case:

Either node 3 has indirect information on node 1, or (XOR, at that!)

node 1 has indirect information on node 3.

If one is interested in, say, viral spread or the flow of information, then one's representation of the graph would ideally pick up on even more temporal restrictions than the one just outlined. For example, consider the following situation

There are two propagation patterns that repeat in the above image: information either flows along the top or along the bottom. If the nodes propagate only recent information, then it could be the case that the green node never gets information from the red node. If we look at the static representation of this situation, that's not clear.

One might argue that I'm just picking out pathological situations that are not grounded in any particular setting, but I'm just trying to keep things simple. There are plenty of settings where retaining such dynamic patterns may be essential. For example, if one wanted to detect communities in a large mobile phone network, then it is likely the case that communities are not all active at the same time. Some will be active in evenings, others during the day, others on weekends, and others only on special holidays. By time-slicing the data you flatten out this temporal information, and it looks like all communities are active at the same time, making the task of community detection more difficult.

So how should event-based networks be represented?

I'm not sure. But given problems like those that I've outlined above, I have an aversion to the time-sliced approach (which happens to currently be the most popular approach).

Vector clocks are a potentially powerful representation of such event-based networks that does not suffer from the first problem that I outlined above. I became aware of vector clocks via an excellent 2008 KDD paper The Structure of Information Pathways in a Social Communication Network by G. Kossinets, J. Kleinberg, D. Watts (available for free on Jon Kleinberg's page, there's also a nice video lecture in which Kleinberg presents the paper). From the wikipedia article, it seems that vector clocks were developed to detect causality violations in distributed systems. They don't seem like a plausible way to represent social networks because they implicitly assume that when people communicate they have unlimited bandwidth. Nonetheless, the results of that KDD paper are fascinating and the whole framework could possible be modified to better reflect how communication takes place among humans.

The Irish Blogosphere

2011-02-10T14:57:00.004Z

As part of an interdisciplinary project, a few of us here in Clique have recently mapped out the Irish blogosphere. Our goal was to provide a group of cultural studies scholars with a representative sample of Irish blogs. Along the way we uncovered some results that might be interesting for active Irish bloggers. Before presenting the results, I should give credit where it's due: Karen Wade motivated this whole project, Derek Greene is responsible for scraping the data and the document clustering, and Daniel Archambault is responsible for much of the visualization work. Prof. Pádraig Cunnignham, my supervisor, oversaw and advised the project. Additionally, this work was supported by Science Foundation Ireland grant No. 08/SRC/I140 (Clique: Graph and Network Analysis Cluster). The full technical report is available here. The data we collected is available here.

The following results are based on a scrape of about 180,000 posts from 600 blogs which were prominent and clearly Irish. To collect data, we started with a "seed" set of blogs collected by looking at winners of the Irish Blog Awards. We then performed a "snowball crawl" by extracting all blogs on the blogrolls of the seed, adding them to the seed, and iterating this process twice. Finally, we filtered out all blogs with fewer than two incoming blogroll links. We manually filtered out blogs that are dead or not Irish. We argue that the resulting data includes nearly all active Irish blogs with moderate readership, but it will in some cases exclude some blogs that have little following. For each blog we scraped the most recent 1000 posts.

The lay of the land: an overview

As a starting point, we'll take a look at the overall blogroll-link structure of the blogosphere:

In the above image, links indicate whether one blog has listed the other on its blogroll. The larger nodes have more incoming links. While the image includes too many nodes to list their individual names without making a mess, we can see in this overview that there is a densely connected "core" and a number of outlying clusters. Further analysis (the text clustering, explained below) revealed that some of these clusters correspond to the topics, which we've sketched in.

Can you guess who the big dot in the middle might be? This will soon be clear.

The most prominent bloggers' blogs

All hail King Mulley!

The image above shows one version of the top Irish blogs, sized by PageRank in our Irish blogosphere dataset (rather than the PageRank in this subgraph). Only those blogs that were linked to more than 45 times in the posts of other Irish blogs make the cut for this image. The thickness of the edges indicate how often these blogs link to one another.

We can now scientifically verify that claim that Damien Mulley is the high king of the Irish blogosphere. Although PageRank is just one of many possible network centrality measures, we also tried others and the results were similar: mulley.net was on top. Other top-ranked blogs include twentymajor, nialler9, mamanpoulet, cedarlounge, and sluggerotoole and all the others in that image.

Territories in the Kingdom

Many of the top blogs come from the biggest cluster in the blogosphere, but there are more specialized topics, and each has its local celebrities. To discover these clusters and their topics, we applied a document clustering algorithm, which puts blogs with similar vocabularies into clusters. The algorithm returned 12 clusters (which we visualize using Wordle):

Music

Photography

Technology

Sports

Film (+ law and writing)

Wine

Food

Beauty

Fashion

Personal

Politics, general discussion

Gaelic

The blogs on the right side of these tag clouds are examples of members of the clusters. The size here does not indicate popularity, but rather membership strength. In other words, blogs which use a vocabulary that is very representative of the cluster are the largest. It's interesting that the method was able to distinguish a food from wine and beauty from the fashion, indicating that these topics are associated with distinct vocabularies.

The clustering method was nice in that it doesn't force all blogs to belong to exactly one cluster---some belong to no clusters, and others belong to more than one. In the following image we used the overlapping membership of the clusters to reveal the relations between them. You should be able to see overlap of clusters by areas where two types of cross-hatching interfere with each other.

The main overlapping clusters of the Irish blogosphere.

Some measures based on text similarity and del.icio.us tags revealed that the largest community, "Discussion," is not very cohesive. When we applied a community finding algorithm on the subgraph induced by this cluster, we detected sub-communities, with two political sub-communities (one of which had a greater emphasis on Northern Ireland than the other), one academic sub-community with a focus on law, one on movies, and one on humor/satire. There was also a small but clear cluster of three Sinn Féin (leargas.blogspot.com, daithimckay.blogspot.com, ograshinnfein.blogspot.com). Otherwise, I was surprised to find that the political sub-communities did not part along party lines, in sharp contrast to the state of the US political blogosphere:

The US political blogosphere is clearly divided on party lines, while the Irish political blogosphere (not pictured) is not. Image from a paper by Adamic and Glance.

Note that the methods we used are not in all cases sensitive to very small communities, or to communities that have no specialized vocabulary. So not all small groups of personal blogs were detected using the document clustering, for example.

Those are some of the more interesting aspects of the study. We also had one interesting negative finding, for those who are interested in network analysis, especially in the detection of network communities. While the document clustering (and network community detection within the largest document cluster) produced nice results, when we ran community detection algorithms on the two global versions of the blogosphere graph, the results were disappointing. We ran three community detection algorithms (InfoMap, GCE, and MOSES) on the two versions of the blogosphere that we came up with (one based on blogroll links, the other based on links between blog posts). The results varied widely, both when we used the same algorithm on the two different versions of the blogosphere, and when we used two different algorithms on the same data. Thus, we were left without a clear picture of the community structure based on network alone.

Visualizing Large Facebook Friendship Networks

2011-02-05T12:07:00.006Z

A few years ago, Traud, Kelsic, Mucha, and Porter posted a paper on arXiv, (the most recent version has been accepted to SIAM Review) in which they analyze five Facebook networks. In a bold (and in my opinion commendable) move, they also released the potentially sensitive data on which their work was based. The dataset consists of five collegiate Facebook friendship networks (it's rumored that the authors had access to 100). The dataset also includes information on gender, high-school, dorm, academic major, and some other attributes. Note that names of users have been stripped away, and attributes have been assigned numeric values to help protect identities, but it's a potentially risky move because anonymization of network data is an unsolved problem. The dataset has come to be known as the "Facebook5," and is available for download ~~here~~.

[Update: Mason Porter confirmed the rumor of the 100 collegiate networks, and he and his colleagues have ~~released the data~~.]

[Further update: At the request of the Facebook Data team, Mason Porter has taken down the data --- both the Facebook5 and the Facebook100. I hope you downloaded it before it disappeared.]

[Another update: The Facebook100 dataset is still kicking around the internet; for details, see this post.]

Facebook networks like these are notoriously hard to visualize, largely because people have so many friends, and these friends belong to distinct groups. As Sune Lehmann noted on his blog, part of the problem here is pervasive overlap:

If every node is a member of more than one community — and this is clearly the case in the LinkedIn example, as well as in real social networks — then the global structure of the network is not at all modular. Rather, the network will be a dense mess with no visually discernible structure. The network will look like ball of yarn … or a hairball (above, right). In fact, this is precisely the type of structure which has recently been discovered in empirical investigations of a comprehensive set of large networks (social and otherwise)

In their paper, the authors attempt a visualization of only the smallest dataset, which looks like the hairball described by Lehmann:

I should note that the authors did not focus on visualization, but rather used the above image as motivation for quantitative measures. Nonetheless, I can verify that it's hard to get much out of visualizing these networks. I have also tried to visualize this and similar data sets, and I've invariably ended up with even more tangled hairballs. I've wondered whether complicated visualization software, with scores of features hidden in long menus, could do a better job if only I understood all of those features.

So I was excited to be the official "data torturer" in a visualization workshop (VACN) on Jan. 19th 2011 by CASL. I had the opportunity to see whether the experts who develop some cutting edge visualization software could do a better job visualizing this data.

The workshop brought together the lead scientists behind five software packages used to visualize network data:

Visone (Germany, edu)
Pajek (Slovenia, edu)
Tulip (France, edu)
Gephi (France, edu)
I2's Analyst Notebook (U.K., commercial)

In the challenge section of the workshop, we asked participants to visualize three Facebook networks from the Facebook5:

Caltech (769 Nodes, 16656 Edges)
Princeton (6596 Nodes, 293,320 Edges)
UNC Chapel Hill (18163 Nodes, 766,800 Edges)

Here are the results of three of the teams:

Visone

Bobo Nick used Visone to produce the following visualization of the Caltech network.

To create the layout, Mr. Nick applied a spectral layout to the modified laplacian, and then used stress minimization to improve on the spectral layout. He colored nodes by dorm. The height of nodes indicates degree, and the width indicates betweenness centrality.

At first glance, the visualization looks rather like a hairball. But if you focus on the position and shape of the nodes, and ignore the edges, then this image reveals important aspects of the Caltech network. First and foremost, the layout reveals that nodes cluster according to their dorms. Furthermore, the orange dorm appears to be especially insular, while the light-green and dark blue dorms seem to mingle. By focusing on the width of the nodes, we can see that the nodes which appear between dorms also have a high betweenness centrality. As I recall, when Bobo colored the nodes by gender, he tentatively found that these bridge nodes tend to be female. The white nodes indicate that the dorm attribute is "unknown." Using this layout, one could make an educated guess that the white nodes in the orange cluster would be colored orange if we had data on them.

Tulip

David Auber, used Tulip to produce the following images. The first is of the large UNC dataset, which contains over 800,000 edges, and is particularly difficult to visualize.

Dr. Auber describes the process he used to create the image:

I've run a spring embedder layout, and a clustering algorithm that finds important clusters based on the connectivity of the element inside a cluster. I have colored the nodes according the student/faculty attribute. For the rendering, I used a bump mapping effect. You can see on the picture that there are many big clusters with almost the same composition of student/faculty. Only one cluster has a special structure mixing different student/fac (blue and yellow halo). You can also see in the the center of the image that there are hubs which connect these clusters, and that these hubs have got a high faculty ratio.

It's fascinating to see that instead of a mess, the graph clusters into five distinct clusters, one of which is closely related to some non-undergraduate part of the network (either professors or graduate students). I wish Auber would have colored the nodes by year instead of student/fac---I speculate that these five clusters correspond to freshmen, sophmore, junionr, senior, and grad students.

The second image is of the Princeton dataset. I've never seen this sort of representation of the relations between various attributes.

Auber descibes its creation and meaning:

I've used a paralllel coordinate plots that show each dimension of your dataset plus the degree of each element. One can see correlation between dimension and connectivy (degree centrality) [i.e., lines are colored by the number of friends each node has]. One can see that student_fac and years are really correlated---student fac 1 have only in year 06 07 08 09, while student_fac 2 are only in year 06 05 04 etc ... One can also see that high degree nodes come from student_fac 1 and year 2009-2004. One interesting thing is that it seems that gender 1 and gender 2 are not going in the same high school. We can also see all high connected nodes have a second major .... too many things to say here...

Auber's third image is also like nothing I've seen before:

Dr. Auber explains the process of its creation:

The image is a treemap representation, where the nodes have been clusterized according to dorm then gender then the year. On top of the treemap, the connection between nodes are drawn using an edge bundling technique. The color of nodes represent the degree of elements.
On this image one can detect several interesting properties. First, the connectivity between people from the same dorm seems to be the same in all dorms except for dorm zero.
If we extract the induced subgraphs for each dorm we can see that this phenomena is true. For intance, the density of the dorm 0 cluster is 13 times smaller than the dorm 171. It seems that dorm 0 represents people that do not specifytheir dorm (ie. a random cluster of people). Thus we can conclude that the dorm property is correlated with the connectivity (people from the same dorm seems to have more connections).

The image also enables to see intra cluster connections. We can see that some cluster are more linked together, for instance the 169-172 and 166-172.

For the node 622 (highest degree) [which is highlight and whose friendships are green] , we can see exactly all his/her connection with dorm/gender ... Visually, we see that he/she is more connected to the cluster 169, 166 and 172. It is interesting to see that these 3 clusters are the 3 more inter-connected clusters that we detected before.

Gephi

Sebastien Heymann and other members of the Gephi team won the visualization challenge. One of the most impressive images they came up with is the following visualization on the largest dataset, UNC. Note that it doesn't look like a hairball, but rather reveals clear structure.

Mr. Heymann comments on this visualization:

For the first step of the layout: I've run the OpenOrd layout, which is a force-directed layout particularly suitable for very large networks; I've then hidden the edges as we were only interested by the visual clusters. In the second step, I added visual information: I interpreted the year of graduation as a quantitative variable by mapping it to a color partitioning.

The Traud paper that introduced this dataset found that in the UNC Facebook network, graduation year appears to be the most important attribute. In order to arrive at this conclusion, they introduced complicated measures. While these measure certainly have their advantages, it would be great to be able to visualize that finding. Traud et al note:

Despite this demonstration of the utility of visualizing communities [in the Caltech data], it is typically necessary to perform quantitative analyses after detecting communities, as Caltech is unusual among universities in having a single characteristic that aligns so closely with its communities. For other institutions, we observe more heterogeneous communities, and it is typically difficult to visually assess which characteristics best correlate with the communities or even whether there is any strong correlation at all.

So we were very impressed that Gephi was able to find the correlation with year in the UNC data set, a finding that agrees with Traud et al's quantitative analysis.

Finally, above we see yet another visualization of the Caltech network. It's in line with the other visualizations we've seen of this set. Mr Heymann's comments:

I've run the ForceAtlas layout, which is suitable for dense small graphs. Then I mapped the dorms variable to a color partitioning. We could better see the different communities by hiding the edges between nodes with a low betweenness centrality score, of course.

Is Spinn3r still free for academic research?

2010-03-16T11:11:00.000Z

Update

The comments to this post seem to answer my question: Spinn3r is still supporting academic researchers, but rather than offering free data, they are offering heavily discounted data (charging $500/month instead of $6000/month). Why couldn't I find this this information on the Spinn3r site.

While it's too bad that the data is no longer free, it's really fair enough to charge something for it, considering that collecting, cleaning, hosting and, transferring hundreds of gigabytes of data is not free.

End update

---

Spinn3r is a service that aggregates the articles of thousands of newspapers and other media sources, as well as the posts of millions of blogs. They clean up this data, put it in a consistent format, and provide rich metadata.

For an academic researcher, especially a PhD student with limited resources, this dataset is very appealing. Spinn3r does all the dirty (and resource intensive) work, and provides unprecedented data on news media, which could be mined to make interesting conclusions about collective human behavior. For example, Jure Leskovec, Lars Backstrom and Jon Kleinberg wrote a fascinating article on the news cycle (see the companion MemeTracker website for details).

Spinn3r has generously offered give academic researchers free access to their API (as they mention here and as the head of Spinn3r, Kevin Burton, has mentioned here). However, I could not find any sign-up form for researchers. I assume that researchers are supposed to request access using the company's contact form. I have twice requested access, and I have waited months for a response. I have not heard back from them. Has anyone else had better luck?

For anyone interested in the data, the best I could do was find a dataset that Kevin Burton suppled for an academic conference called ICWSM 2009 - International AAAI Conference on Weblogs and Social Media. You can find details on this dataset in this video lecture.

Spinn3r's participation in this conference indicates that Spinn3r is serious about their support of the academic community, so why don't they seem to be answering requests for access to their API?

Recommended rate limit on crawling Google Profile pages: 100 per second

2010-03-16T10:14:00.000Z

It recently came to my attention that not only is it possible to crawl Google profile pages, but Google even supports this activity by providing a directory of user ids. There's some interesting data on many of these profiles, including current geographic location, past locations, education history, and organization affiliation. Also, many users have not opted-out of allowing their Buzz activity to be posted on these pages, which means there is a lot of data on media consumption and awareness of various memes.

Using a modified version of Pete Warden's open-sourced scraper, I set out to crawl all of the Google Profile pages that were listed in the files in their directory. It appears that this directory has not been updated since October 2009, and contains ~4.2 million user IDs. I guess a lot of people have created profiles since then due to the introduction of Buzz, so the directory might be quite out of date.

I wasn't sure of the correct crawling rate, so, because this crawling activity seems to be officially approved of by Google, I decided that it is better to ask for forgiveness than for permission and so I started off at an optimistic crawl rate. I used a Python module called forkmap to run 8 processes of Pete Warden's scraper in parallel (each of which contained 200 threads, for a total of 1,600 threads). I thought that bandwidth would keep the cralwer down to a reasonable rate, but I guess the University's connection is quite fast, because I received an e-mail a couple of hours later from a Google engineer informing me that I was crawling too quickly, in fact, I was scraping 1,800 profiles per second. The e-mail was friendly enough, and the general point was that although Google supports crawling the profile data, one should keep the crawl rate down to 100 requests per second.

This rate is still quite generous, and would allow one to crawl the 4.2 million listed profiles in 11.6 hours, which is really quick enough.

Is obesity contagious? A Review of the Debate over the "Network Effects" of Obesity

2009-11-06T15:11:00.000Z

Introduction

In July 2007, network science invaded medicine. Nicholas Christakis, a professor of public health at Harvard Medical School, and James Fowler, an associate professor of political science at UC San Diego, published a cover article in medicine's most prestigious journal, the New England Journal of Medicine, complete with a teaser written by complex-network-bigshot Albert-Laszlo Barabasi. The article served as the debut of social network analysis in medicine, complete with a glossary that explained terms such as "ego," "alter", "node," and "homophily" for uninitiated medical researchers.

In this article (freely accessible from the journal), entitled "The Spread of Obesity in a Large Social Network over 32 Years", Christakis and Fowler (CF) make a number of claims, each more bold than the last. In a later response to criticism, CF summarize their two major findings of the paper in the following two points:

(1) "obese persons formed clusters in the network at all time points and that these clusters extended to three degrees of separation (e.g., to a person's friend's friend's friend)"

(2) "statistical analysis suggested that the clusters were not soley attributable to the selective formation of social ties among obese persons. A person's chances of becoming obese increased if he or she had a friend who became obese in a given time period."

We should note that this brief summary of the main findings is slightly incomplete and actually leaves out the most contentious point. If one considers point (2), there are a number possible reasons why someone's body mass index (BMI) might be linked to the BMI of his or her friends. Let's begin by considering some possible causes for this clustering.

Various causes of clusters of obese people

Noting that friends often share similar environments, it could be the case that fast food chains (or fast food advertisements) have invaded our common environment, or some technological improvements such as elevators have decreased the need to be physically active. In this case, although a person's weight gain is correlated the weight gain of his friends, it's not really his friend that causes him to gain weight, but rather a shared environmental factor---a "confounding variable."

However, we can also imagine how, given some social dynamic, a person's weight gain is directly caused by his friends' weight gain. Let's reasonably assume that people have an incentive to eat lots of unhealthy food (e.g., it tastes good, is cheap, easy to find), which is held in check only by their desire to have a personally acceptable BMI. Let's imagine that my definition of an acceptable BMI is pegged to be slightly lower than the average BMI of my friends. If my friends gain a lot of weight, then my acceptable BMI will increase, allowing me to enjoy unhealthy foods without becoming, in my mind, unacceptably overweight. One can also imagine simpler processes whereby my friends' behavior directly affects my BMI; for example, if my friends start frequenting unhealthy restaurants and drag me along. Let's call these explanations of (2) cases of "social influence", and note that the "social influence" explanation of (2) differs from the "confounding variable" explanation" because we put the blame for our weight gain on the behavior of our friends rather than on some shared environmental change.

So far we have established two processes that could account for clusters of obese people: confounding variables (shared environmental factors such as fast food chains) and social influence. Point (2) also states that "the clusters were not soley attributable to the selective formation of social ties." To understand this statement, we must introduce a third process that can create clusters of similar people: selection (aka, "choice homophily","homophily"). Selection's mechanism is simple: "birds of a feather flock together," that is, people befriend those who resemble themselves. In this case clustering of obesity can emerge even though everyone's weight remains constant--overweight people tend to become friends with overweight people, and similarly, people who are not overweight tend to become friends with similarly slim people. This process, selection, also leads to obese clusters.

From a policy perspective it is important to know which of these three processes is responsible for the recent rise in the rate of obesity. In particular, if social influence plays a major role, then obesity is similar to a disease---it's contagious! When treating contagious diseases, there is a "multiplier effect." Imagine that at a certain stage in a flu epidemic, the average person spreads the disease to two other people. Then if I can prevent one person from getting infected, I also prevent that person from spreading the disease to two other people---thus the effect of my intervention becomes "multiplied." The other two processes I've mentioned, confounding variables and selection, do not have a multiplier effect. From a policy perspective it is therefore important to distinguish between these three processes.

Now that we have covered how confounding variables, social influence, and selection could all lead to clusters of obese people, we can return to the claims of CF. CF contend that (2) is not the result of just confounding variables or selection; they claim it is also due to the process of social influence. (In the course of this controversy, the process of social influence variously refered to as "endogenous effects", "induction", and the vague "social network effects".) From a policy perspective, this implies that intervention that prevents one person from becoming obese, or that cures a case of obesity, could have a multiplier effect---in a sense this multiplier effect lowers the cost, or increases the effect, of such intervention. Before we move on to criticisms of this claim, let's look at CF's argument in favor of social influence.

How to control for selection (a.k.a. choice homophily) as a cause of obese clusters of friends

Because confounding variables, selection, and social influence all create similarly clustered networks, it's very hard to say, given some clustered network, which of these three processes was responsible for the clustering.

However, if one has longitudinal data on friendships and obesity (also called dynamic network data), one can begin to untangle these three processes. Specifically, one can distinguish the effects of selection on the one hand, from confounding variables and influence, on the other. Separating the effects of selection from the other processes is achieved by using a "lagged variable."

The motivation for using a lagged variable becomes clear when considering the following scenario. Let's say that we observe a group of adolescents in 2005. We observe that they are all friends with each other and we measure the BMI of everyone in the group. In 2009, their BMIs are once again measured, and we confirm that they are all still friends. Let's assume that most of the members of this group became obese between 2005 and 2009. The end result is that we observe a cluster of obese people. If we did not have the longitudinal data from 2005, then we could not be sure whether this obese cluster was created by the process of selection or some other process. However, with our longitudinal data, we can say that these obese people actually chose to be friends with each other before they became obese---meaning we can rule out selection (with respect to obesity) as the cause of the obese cluster. In short, with longitudinal data one can isolate the effects of selection to a single moment, and assume that correlations in the change of BMI in the next moment are not due to selection.

[Note: CF do not use BMI in their independent and dependent variables, but rather the obesity status. Why did they make this decision? I find it suspicious: why throw away data by turning a real-valued variable into a categorical (true/false) variable?]

CF exploit this advantage of longitudinal data by using a logistic-regression model with the use of lagged dependent and independent variables. Let's call the dependent variable in their model, which is the obesity status of the subject at time t+1, obese?(subject, t+1). The independent variables include:

obese?(subject,t)
obese?(friend,t)
obese?(friend,t+1)

In this model, the effects of selection (homphily) should be absorbed in the coefficient for obese?(friend,t), and we assume that the coefficient for the variable obese?(friend,t+1) reflects either some confounding variable or the effects of social influence.

In fact, the core of the debate around CF's obesity study revolved around interpreting whether obese?(friend,t+1) should be attributed to confounding variables or to social influence.

How CF argue that social influence spreads obesity (i.e., that obesity is contagious)

The main empirical result that CF use to support their claim is summarized in the following graphic:

Pay particular attention to the first three rows in the graphic above. The first row suggests that if I call some person f my friend, who does not reciprocally name me as a friend, and that f becomes obese, then my risk of becoming obese increases by somewhere between approx 5% and 100%. The second row says that if I list f as a friend and f lists me as a friend (i.e., the friendship is observed to be reciprocal), then if f becomes obese, then the chances that I also become obese increase by anywhere between approx 75% and 300%. The third case says that if f names me as a friend, but I don't name him, then the fact that f becomes obese does not affect the probability that I also become obese with statistical significance.

The discussion above should make it clear that the cause of the my increased risk of obesity, given that my wife or friend becomes obese, is difficult to determine.

CF's argument that the cause is the social contagiousness of obesity (i.e., influence rather than selection or confounding variables) is mostly contained in the following few paragraphs from their paper:

"The use of a time-lagged dependent variable (lagged to the previous examination) eliminated serial correlation in the errors (evaluated with a Lagrange multiplier test) and also substantially controlled for the ego's genetic endowment and any intrinsic, stable predisposition to obesity. The use of a lagged independent variable for an alter's weight status controlled for homophily. The key variable of interest was an alter's [friend's] obesity at time t+1. A significant coefficient for this variable would suggest either that an alter's weight affected an ego's weight or that an ego and an alter experienced contemporaneous events affecting both their weights. We estimated these models in varied ego-alter pair types."

Before moving on to the next paragraph let's interpret this last one. Basically they are saying that their logistic regression model contains a variable for the past obesity status of the ego (subject) and the past and current obesity status of the alters (friends). They contend that the former variable (the past obesity status of the ego) controls for genetic predisposition (which is reasonable) and that, as explained in the last section, the variable that represents the previous obesity status of the alter (friend) controls for selection. The also state that a "significant coefficient for the variable obese?(friend, t+1) (i.e., a correlation between my weight gain and my friend's weight gain) would indicate something ambiguous: either that some confounding variable is responsible for our mutual weight gain, or that social influence is to blame. So far, so good. In the next paragraph, CF make the most contentious claim: that correlated weight gain is not due to some confounding variable, but rather social influence. Pay close attention to their line of argument:

"To evaluate the possibility that omitted variables or unobserved events might explain the associations, we examined how the type or direction of the social relationship between the ego and the alter affected the association between the ego's obesity and the alter's obesity. For example, if unobserved factors drove association between the ego's obesity and the alter's obesity, then the directionality of friendship should not matter." [Emphasis added]

The last sentence states that if the direction of friendship plays a role in the association of the weight gain of a subject with the weight gain of that subject's friend, then confounding factors can be ruled out and social influence must be the cause of correlated obesity status. If you accept this argument, then the graphic shown above quite convincingly indicates that obesity is contagious.

Now let's turn our attention to the criticism of this finding.

Criticism of CF's finding

In May 2008, Ethan Cohen-Cole, of the Federal Reserve Bank of Boston, and Jason Fletcher, of Yale University, published a paper whose main goal, they later describe, was "to illustrate that it takes relatively specific and potentially narrow specification choices to yield the contagion result." They also state, "our goal was to show that the methodology used by Christakis and Fowler (2007) was sensitive to specification choice, and once very small, yet reasonable modifications are made to the space of possible empirical models, the data yield coefficients that are statistically indistinguishable from zero."

To show that CF's results are not robust, Cohen-Cole and Fletcher (CCF):

Find data that is somewhat similar to CF's
Replicate CF's analysis and find similar results as CF found
Take into account an extra confounding variable (i.e., they extend CF's model to control for more)
Point out that after CF's model is extended to take this extra confounding variable into account, the main findings of CF no longer appear.

We should first note that it's a shame that CCF did not use the same data as CF. Their refutation is quite weakened by the fact that their so-called replication actually used different data (they use data from National Longitudinal Study of Adolescent Health [AddHealth]). While CCF acknowledge that there are important differences between their AddHealth data and the Framingham data that CF used, they do not state why they used different data. Presumably the Framingham data was not easy to obtain.

CCF reasonably justify their use of AddHealth by pointing out when they replicate CF's method on the AddHealth data, they find results that are remarkably similar to CF's Framingham results. While it is difficult to say whether this similarity means that the data really are similar or that the measure is biased to produce a narrow range for a particular coefficient, the similarity is nonetheless an indicator that the data sets are similar in an important way.

CCF's main finding is that if they add one additional independent variable, which, in the notation above, should be labeled obese?(community,t+1), then obesity no longer appears to be contagious. CCF explain the significance of including this variable in their model:

[The additional environmental variable] formalizes the notion of contextual effects...These represent a much richer set of controls to absorb average changes in social context experienced by all individuals in the sample. To explain further, these school-specific trends account for any environmental factors shared by individuals at the same school. CF control for year effects, but their specification does not capture any shared confounders that also vary across geographic space. For example, CF can control for the fact that the density of fast food restaurants has increased over time but not the fact that number of fast food restaurants has grown faster in some areas than in other areas. For example, suppose that the number of fast food rastaurants has grown faster in Boston, Massachusetts than in western Massachusetts. Controlling for year effects (which controls for the grown th the number of fast food restaurants across the states in a given year) is not as appealing as controlling for the number of fast food restaurant [sic] in an individual's local area.

"Without accounting for the trends, clustering of obesity in social networks that changed over time would incorrectly be absorbed in the estimation by the endogenous variable. Though one, in principle, would want many more controls to account for additional contextual effects, we will note shortly that the endogenous [social influence] effect vanishes even with this relatively simple characterization."

In short, CCF add an independent variable to their model that accounts for change in BMI of the entire school. This should help control for shared environmental (confounding) variables. In addition to this change to CF's specification, CCF make one other change:

We add to our evaluation by accounting for self-selection of friends (homophily). This is accomplished by looking only at the change in BMI fromthe time of declaration of friendship until the subsequentweight measurement. Note the distinction between this method and the lagged independent variable used in CF. Our method allows us to distinguish between the desire to become friends based on similarity in weight, which would appear based on the simultaneous measurement of friendship andweight, and the friendship effect ofweight gain.

After making these two modifications to CF's model, CCF find that the observed contagiousness of obesity disappears.

CCF also point out that CF's method of controlling for selection (homphily)---the use of a lagged variable---is susceptible to a particular problem. CCF provide a nice description of this weakness in a later critical article published in the British Medical Journal)

The claim [of CF] is that "the use of a lagged independent variable for an alter's weight status controlled for homophily."...Unfortunately, unless selection is conditioned only on this variable, this statement might be spurious. For example, if friendships are formed based on characteristics like self esteem, and if self esteem affects both current weight and future weight in differing ways, then adjustment for current peer weight status will not capture the self selection of friends based on self esteem that also affects future weight.

Why Cohen-Cole and Fletcher's refutation hits the target only halfway

CCF's findings indicate, using data that might be similar to CF's data, that CF's specification may be quite narrow---i.e., that their finding is not robust to variations in the specification of the logistic regression model. CCF suggest that if CF had controlled more shared environmental variables, their findings may have been statistically insignificant.

However, to be fair to CF, one must remember that CF recognize the need to take confounding environmental variables into account. Recall (in the bolded part of CF's excerpt above, also repeated below) that CF do in fact consider that correlated weight gain might be due to shared environmental variables. Thus both parties agree that confounding variables make it difficult to conclude that obesity is contagious. CF's strategy is to exploit the directionality of friendship to rule out confounding environmental variables. To repeat the key part of the excerpt above: "if unobserved factors drove association between the ego's obesity and the alter's obesity, then the directionality of friendship should not matter."

Why do I say that CCF only halfway succeed in criticizing CF? CCF do convincingly show that CF's result depends upon a quite narrow specification, and that if this specification is changed the the so-called contagiousness of obesity melts away into confounding variables. They do not, however, adequately address CF's main justification for disregarding confounding variables: confounders should not be related to direction of friendship---yet the data were very related to the direction of friendship! CCF briefly comment on the importance of edge direction in CF's findings:

CF appear to approach confounding by examining the type and direction of the friendship networks. For example, if individual A declared himself a friend of individual B but not vice-versa, then a social network effect should appear for A but not B.While network structures can be useful for identification of social network effects, their presence does not rule out the possibility that confounding environmental effects overlap and influence the decisions of network members.[15] Since CF never directly control for environmental factors, we view their results using directionality of friendship nominations as suggestive rather than conclusive.

The bracketed "[15]" refers to a footnote. Because it's relevant, let's have a look at it:

[15] The argument for identification of social network effects using network architecture has been formalized in Bramoull´e et al. (2007). The methodology is intriguing and may be sufficient to control for confounding in the CF case, however, CF do not employ it, and it is not clear whether the single-Alter structure of most of their data permit identification in this setup in any case.

Thus, CCF simply state that it's too bad that CF did not use Bramoull´e et al.'s methodology, without explaining why CF's use of friendship direction is flawed. In other words, they dance around CF's main justification for largely disregarding precisely the point that CCF criticize. In CCF's later additional critical article in the British Medical Journal, they again address this point without making it clear why direction should not matter. They state:

As schoolmates are often also frioends, these common environmental exposures might produce the appearance of "social network effects" if not controlled for in the empirical models, particularly if the type and direction of the friendship networks are used for adjustment. For example, if individual A declared himself a friend of individual B but not vice versa, then a social network effect should appear for A but not B. Unfortunately, while this "intransitivity" of the network can facilitate identification of network effects, it does not address confounding.

I wish CCF would provide an example here to explain why they believe that the direction of friendship cannot be exploited to adjust for confounding variables. In terms of CCF's example of A and B, the following seems to hold: A and B are likely in the same environment (because A claims B as a friend), and despite that fact, only B's weight affects A's weight, as one would expect if obesity were contagious.

So is obesity contagious?

The debate over the contagiousness of obesity is one of the rare instances where scientific findings are given the scrutiny that is essential for the health of science in general. The end result, however, is unsatisfying: although CCF provide evidence that CF's results are questionable, they do not directly undermine CF's

defense, which is based upon the importance of the direction of friendship.

Does this mean that CF's findings are solid? Maybe, maybe not. If one looks closely at the figure above, the error bars of all three directions overlap---meaning that one ought not reject the null hypothesis that directions does not matter.

However there are other reasons why a relation between weight gain and friendship direction need not imply that obesity is contagious.One can imagine how, even if obesity were not contagious, edge direction could still be related to correlated weight gain. Let's consider one possible scenario in which we would find that edge direction is related to mutual weight gain, and yet in which obesity is not actually contagious. I will simply snatch this example out of thin air---I do not mean to suggest that my example corresponds to reality, but rather demonstrate that CF's findings need not imply that obesity is contagious.

In this scenario, the following points are the most important:

First, let's assume some hypothetical world in which we know obesity is not contagious.
Obesity is socially stigmatized. Due to this stigma, non-obese people are more likely to drift away from their friends who become obese than they are to drift away from their friends who remain at a healthy weight. We don't have to assume that this effect is extremely pronounced, let's just call it a moderate tendency.
People who have recently become obese do not share this moderate tendency to prefer non-obese contacts---as obese people themselves, they are no longer sensitive to the social stigma associated with obesity.

The following points result as consequences of the three assumptions we've just made:

Due to this moderate tendency of non-obese to drift away from their newly-obese friends, when non-obese people are asked in some survey to quickly list their best friends, their newly-obese friends are less likely to be the first to come to mind. Keep in mind that in the Framingham study, most subjects listed either no friends or just one friend. This tendency leads to a relatively lower rate of friendship from non-obese people to obese people.
If you are newly obese, you still list your non-obese friends.
Furthermore, if both you and your friend become obese at the same time, you neither of you are more likely to forget about this friendship. This tendency leads to a higher rate of friendship among obese people (relative to the friendship from non-obese to obese people).

Thus, because the stigma related to obesity has a direction (from the non-obese to the obese), and because this stigma is related to reporting friendships, it creates the appearance of contagious obesity, where in fact obesity is not contagious. Although there are still some non-obese people who are friends with obese people, and perhaps the majority of obese people's friends are not obese, the relative rates are key here, not the absolute rates.

I provide this example simply to illustrate that the significance of friendship direction, does not necessarily mean that obesity is contagious. It's just one hypothetical, yet plausible, explanation---perhaps you can come up with one that is even more plausible.

The contagiousness of smoking (cessation), happiness, headaches, acne, and height

A year after their first big publication in the New England Journal of Medicine CF again publish a cover article in the same journal. The second article is nearly exactly the same as the first (the measure used are the same, the data is from the same Framingham dataset, the structure of the research design and the paper itself are the same---even some sentences are almost word for word the same), but this time the topic is the contagiousness of smoking and smoking cessation rather than obesity.

CF's main results in the smoking study largely mirror their results in their obesity study. Importantly, they use the same type of logistic regression model, with lagged dependent and independent variables, to conclude that smoking is contagious across friendship and family ties. (They include some results that smokers have moved to the periphery of social groups in the last thirty years---results which I find unconvincing.) Because the results in this study are based on the same methods as used in the obesity study, they are susceptible to the same criticism as the obesity study.

CF published a third article in a similar vein, this time exploring whether happiness is contagious. For their main statistical analysis they again use a regression model, with lagged variables to control for homophily, and contend that if friendship direction is important then one need not worry about confounding variables. Again, this study is susceptible to the same kind of criticism from CCF.