Computational Legal Studies™

Last summer, Dan, Jon and I wrote our conference paper for ASNA 2009 entitled On the Stability of Community Detection Algorithms on Longitudinal Citation Data.  The purpose of this paper was to experimentally explore a number of properties of community detection algorithms, especially as applied to citation networks (c.f. Supreme Court, Tax Court, United States Code).

The model is a fairly simple discrete-time directed growing graph.  At time 0, we create a completely disconnected graph with some initial number of vertices.  The number of new vertices after time 0 is then modeled by a homogeneous Poisson process.  For each of these new vertices, we also model the number of edges per vertex as IID Poisson distributions.  The probability distribution over these edges is specified by a modified preferential attachment mechanism.

Most of our questions consider what we’ve called the average pairwise stability.  This can be thought of as answering the following question: “what is the probability that Alice and Bob are friends tomorrow if they were friends today?” Here, friendship corresponds to sharing the same community.  By asking this question for all pairs of vertices (dyads) for all time steps in which both vertices existed, we get a probability that a community dyad is preserved from step to step.  It is important to note that we’re not claiming all algorithms applied to all systems should have high average pairwise stability. In fact, for systems that involve dynamics like random rewiring, the only way to get high pairwise stability is to put all vertices in the same community or their own community at all steps – obviously trivial and unhelpful solutions in practice.

Given this model and this conception of stability, we want to perform the following experiments:

1. How do the edge-betweenness, fast greedy, and leading eigenvector community detection algorithms compare in terms of their average pairwise stability…
   1. for varying levels of preferential attachment?
   2. for varying vertex and edge rates?
2. Is there a significant tradeoff between the number of communities and the average pairwise stability of these community detection algorithms?

The answers are yes, yes, and yes!  You should read the paper for more details.

I’ve also produced some code to help you assess the average pairwise stability for your dataset.  The code requires igraph and is only in Python at this point due to an issue with R’s vertex label handling (which I can hopefully work around).  You can get the average pairwise stability methods on github and check out the example below:

mjbommar Uncategorized computational social science, network analysis, physics

We have spent the past couple days at the University of Pennsylvania where we presented information about our efforts to compile a complete United States Supreme Court Corpus.  As noted in the slides below, we are interested in creating a corpus containing not only every SCOTUS opinion, but also every SCOTUS disposition from 1791-2010. Slight variants of the slides below were presented at the Penn Computational Linguistics Lunch (CLunch) and the Linguistic Data Consortium(LDC).  We really appreciated the feedback and are looking forward to continue our work with the LDC.  For those who might be interested, take a look at the slides embedded below or click on this link:

mjbommar Uncategorized computational linguistics, data mining, python, supreme court

Over the past few months, we’ve developed a library for simply generating dynamic network animations. We’ve used this library in visualizations like (1) Visualizing the Gawaher Interactions of Umar Farouk Abdulmutallab, the Christmas Day Bomber and (2) Dynamic Animation of the East Anglia Climate Research Unit Email Network.  Prior to these visualizations, we’ve used Sonia to produce animations like this one. While certainly a useful program for those without programming expertise, Sonia suffers from a number of issues that make it unusable for large graphs or graphs with many “slices.”  Furthermore, in our experience rendering various movies a number of platform issues with the Quicktime and Flash rendering engines have arisen.  Fixing these problems is possible, but Sonia’s large Java codebase makes for a steep learning curve.  As a result, we’ve decided to release this GraphMovie class so that others can use or possibly improve this library.

In order to use the GraphMovie, you’ll need the following:

• python (tested with 2.6)
• igraph for network manipulation and visualization
• Python Imaging Library for manipulating the image frames
• mencoder from the MPlayer package for encoding the image frames into a movie

Here are the files, hosted on github:

• GraphMovie.py
• GraphMovie_Example1.py

GraphMovie: Example 1 from Computational Legal Studies on Vimeo.

• GraphMovie_Example2.py

GraphMovie: Example 2 from Computational Legal Studies on Vimeo.

mjbommar Uncategorized dynamic visualization, network analysis, python

Drew Conway over at Zero Intelligence Agents brought to our attention the Farouk1986 data set provided by Evan Kohlman from the NEFA Foundation. For those not familiar, Umar Farouk Abdulmutallab, who is charged with willful attempt to destroy an aircraft in connection with the Christmas Day Flight 253 from Amsterdam to Detroit, made a  number of posts to the Islamic Forum Gawaher.com using the handle “Farouk1986.”

This data is useful and some good initial analysis has been offered at ZIA as well as other sites across the blogosphere. Moving beyond this initial analysis, we thought it would be helpful to analyze this set within the broader context of Umar Farouk Abdulmutallab’s posts. Thus, we downloaded the entire thread for each post in the NEFA data set — including content from many other authors.

Having this content allows us to understand the broader context of Abdulmutallab communications … including to what Abdulmutallab was responding and how others in the relevant community responded to his contributions.  We have parsed the data into threads and posts, and for each post, we have indicated the author, date, and content. For those interested in executing their own analysis, you can find an XML document with all this data here:  http://www-personal.umich.edu/~mjbommar/farouk.xml.

Feel free to use this data with proper attribution and keep your eyes posted for further analysis of the Abdulmutallab communications on this blog in the coming days.

And to all of our readers Happy New Year!

mjbommar Uncategorized data mining

As reported in a wide variety of news outlets, last week, a large amount of data was hacked from the Climate Research Unit at the University of East Anglia.  This data included both source code for the CRU climate models, as well as emails from the individuals involved with the group.  For those interested in background information, you can read the NY Times coverage here and here.  Read the Wall Street Journal  here.  Read the Telegraph here.  For those interested in searching the emails, the NY Times directs the end user to http://www.eastangliaemails.com/.

Given the data is widely available on the internet, we thought it would be interesting to analyze the network of contacts found within these leaked emails.  Similar analysis has been offered for large datasets such as the famous Enron email data set. While there may be some selection issues associated with observing this subset of existing emails, we believe this network still gives us a “proxy” into the structure of communication and power in an important group of researchers (both at the individual and organization level).

To build this network, we processed every email in the leaked data. Each email contains a sender and at least one recipient on the To:, Cc:, or Bcc: line.  The key assumption is that every email from a sender to a recipient represents a relationship between them.  Furthermore, we assume that more emails sent between two people, as a general proposition indicates a stronger relationship between individuals.

To visualize the network, we draw a blue circle for every email address in the data set.  The size of the blue circle represents how many emails they sent or received in the data set – bigger nodes thus sent or received a disproportionate number of emails.  Next, we draw grey lines between these circles to represent that emails were sent between the two contacts.  These lines are also sized by the number of emails sent between the two nodes.

Typically, we would also provide full labels for nodes in a network.  However, we decided to engage in partial “anonymization” for the  email addresses of those in the data set.  Thus, we have removed all information before the @ sign.  For instance, an email such as johndoe@umich.edu is shown  as umich.edu in the visual.  If you would like to view this network without this partial “anonymization,” it is of course possible to download the data and run the source code provided below.

Note: We have updated the image.  Specifically, we substituted a grey background for the full black background in an effort to make the visual easier to read/interpret. 

Click here for a zoomable version of the visual on Microsoft Seadragon.

Don’t forget to use SeaDragon’s fullscreen option:

Hubs and Authorities:

In addition to the visual, we provide hub and authority scores for the nodes in the network.  We provide names for these nodes but do not provide their email address.

Authority

1. Phil Jones: 1.0
2. Keith Briffa: 0.86
3. Tim Osborn: 0.80
4. Jonathan Overpeck: 0.57
5. Tom Wigley: 0.54
6. Gavin Schmidt: 0.54
7. Raymond Bradley: 0.52
8. Kevin Trenberth: 0.49
9. Benjamin Santer: 0.49
10.   Michael Mann: 0.46

Hubs returns nearly identical ranks with slightly perturbed orders with the notable exception that the UK Met Office IPCC Working Group has the highest hub score.

Thus, so far as these emails are a reasonable “proxy” for the true structure of this communication network, these are some of the most important individuals in the network.

Source Code:

Unlike some existing CRU code, the code below is documented, handles errors, and is freely available. 

• parseEmails.py: parses dates and email addresses out of the text
• plotEmails.py: produces the visual

mjbommar Uncategorized data mining, network analysis, structure of science, visualization

We have been working on a larger paper applying many concepts from structural analysis and complexity science to the study of bodies of statutory law such as the United States Code. To preview the broader paper, we’ve published to SSRN and arXiv a shorter, more technical analysis of the properties of the United States Code’s network of citations.

Click here to Download the Paper!

Abstract: The United States Code is a body of documents that collectively comprises the statutory law of the United States. In this short paper, we investigate the properties of the network of citations contained within the Code, most notably its degree distribution. Acknowledging the text contained within each of the Code’s section nodes, we adjust our interpretation of the nodes to control for section length. Though we find a number of interesting properties in these degree distributions, the power law distribution is not an appropriate model for this system.

mjbommar Uncategorized complex systems, computational legal studies, network analysis, united states code

In addition to the facts we have presented on HR 3962, we wanted to offer a visualization for the structure of the Bill. Like many other bills, HR 3962, is divided into Divisions, Titles, Subtitles, Parts, Subparts, Sections, Subsections, Clauses, and Subclauses. These hierarchical splits represent the drafters’ conception of its organization, and thus the relative size of these categories may provide an indication of both the importance of each section of the Bill as well as the overall size of the document. By clicking through the image below, you can navigate a zoomable representation of the structure of HR 3962 using Microsoft’s Seadragon zoom interface.  Many of the Divisions, Titles, Subtitles, Parts, and Subparts of the Bill are labeled. The balance are not labeled because they fell on an angle on the radial layout which rendered them impossible to read.

The graph is laid out in a radial manner with the center node labeled “H.R. 3962.” Legislation, the broader United States Code as well as many other classes of information are organized as hierarchical documents. H.R. 3962 is no different. For those less familiar with this type of documents, we thought it useful to provide a tutorial regarding (1) how to use this zoomable visualization (2) the correspondence between the visual and the Library of Congress version of H.R. 3962

How Do I Open/Navigate the Visualization?

(1) Open the Library of Congress version of H.R. 3962 in another browser window.

(2) Open the visualization by clicking on the large image above.

(3) Clicking on the image above will take you to the Seadragon platform. (Note: Load times will vary from machine to machine… so please be patient.)

(4) Seadragon allows for zoomable visualizations and for full screen viewing. Full screen is really the best way to go. If you run your mouse over the black box where the visual is located you will see four buttons in the southeast corner.  The “full screen” button is the last one on the right. Click the button and you will be taken to full screen viewing!

(5) Click to zoom in and out, hold the mouse down and drag the entire visual, etc. Now, you are ready to traverse the graph using this visualization as your very own “H.R. 3962 Magic Decoder Wheel.”

How Do I Understand the Visualization?

To introduce the substance of the visualization, we have color coded two separate examples right into the visualization.

Example 1: Bills such as HR 3962 often feature a “short title” provision at the very begining of the legislation.  For example, if you download the PDF copy of the bill, you can see the short title at the bottom of page 1 of the bill.  You can also see this in the Library of Congress version of H.R. 3962.

SECTION 1. SHORT TITLE; TABLE OF DIVISIONS, TITLES, AND SUBTITLES.
(a) Short Title- This Act may be cited as the `Affordable Health Care for America Act’.

Zoom in close to start in the center where the large node labeled “HR 3962.”  Notice the blue colorized path features the blue labels 1. and terminates with the label (a). The labels in the graph are the labels in the text above.  While this is a simple example, the precise logic defines the entire graph.

Example 2: This is a bit more difficult as it requires the traversal of several provisions in order to reach a terminal node.  In this case, the terminal node read as follows … “SEC. 401. INDIVIDUAL RESPONSIBILITY.For an individual’s responsibility to obtain acceptable coverage, see section 59B of the Internal Revenue Code of 1986 (as added by section 501 of this Act).”

DIVISION A–AFFORDABLE HEALTH CARE CHOICES
TITLE IV–SHARED RESPONSIBILITY
Subtitle A–Individual Responsibility
SEC. 401. INDIVIDUAL RESPONSIBILITY.

Again, zoom in close to start in the center--where the large node labeled “HR 3962.”  Notice the blue colorized path features the blue labels A and terminates with the label 401. In between the start and finish, there are stops at IV and A, respectfully.  Just as before, the labels in the graph are the labels in the text above.  The end user can follow the precise journey but without the visual by using the Library of Congress version of H.R. 3962.

mjbommar Uncategorized congress, Google for Government, united states code, visualization

In light of last night’s vote on H.R. 3962, the Affordable Health Care for America Act, we decided to calculate a few numbers on the current bill. Based on the Library of Congress’s XML representation of the bill (which can be obtained here), we have calculated a number of linguistic and citation properties of the Bill. The House of Representative approved HR 3962 by a 220-215 margin. The New York Times features a useful analysis of the vote including a breakout by party and region here.

On the Sunday morning talk shows as well as in other outlets, there has been significant discussion regarding the size of H.R. 3962. Specifically, many critics have decried the length of the bill citing its 1990 pages. The bill is indeed 1990 pages as you can see if you choose to download a PDF copy of the bill.

The purpose of this post is to provide a perspective regarding the length of H.R. 3962. Those versed in the typesetting practices of the United States Congress know that the printed version of a bill contains a significant amount of whitespace including non-trivial space between lines, large headers and margins, an embedded table of contents, and large font. For example, consider page 12 of the printed version of H.R. 3962.  This page contains fewer than 150 substantive words.

We believe a simple page count vastly overstates the actual length of bill. Rather than use page counts, we counted the number of words contained in the bill and compared these counts to the number of words in the existing United States Code. In addition, we consider the number of text blocks in the bill– where a text block is a unit of text under a section, subsection, clause, or sub-clause.

Basic Information about the Length of H.R. 3962

Number of words in H.R. 3962 impacting substantive law:

• 234,812 words (w/ generous calculation)

Number of total words in H.R. 3962: 363,086 words (w/ titles, tables of contents …)
Number of text blocks: 7,961
Average number of words per text block: 24.18
Average words per section: 267.03

Is this a Large or Small Number? Comparison to Harry Potter

Number of substantive words in H.R. 3962: 234,812 words
Harry Potter and the Order of the Phoenix - 257,000 words
Harry Potter and the Goblet of Fire - 190,000 words
Harry Potter and the Deathly Hallows – 198,000 words

Is this a Large or Small Number? Comparison to Other Legislation

Number of substantive words in Energy Bill of 2007: 157,835 words
Number of substantive words in Defense Authorization Act for 2010: 119,960 Words
H.R. 3962 is roughly 2x the Size of Medicare Rx Bill of 2003 (Given there is no public XML version of the bill, the Exact “Substantive Words” Number is not available)

Is this a Large or Small Number? Comparison to the Full U.S. Code

Size of the United States Code: 42+ Million Words
Relative Size of H.R. 3962: H.R. 3962 is roughly 1/2 of one percent of the size of the United States Code

Longest Sections in H.R. 3962

• Sec 341. Availability Through Health Insurance Exchange
• Sec 1222. Demonstration to promote access for Medicare beneficiaries with limited English proficiency by providing reimbursement for culturally and linguistically appropriate services.
• Sec 1160: Implementation, and Congressional review, of proposal to revise Medicare payments to promote high value health care
• Sec 305: Funding for the construction, expansion, and modernization of small ambulatory care facilities
• Sec 1417: Nationwide program for national and State background checks on direct patient access employees of long-term care facilities and providers

Modifications of the Existing U.S. Code By H.R. 3962

Number of Strikeouts: 332
Number of Inserts: 390
Number of Re-designations: 65

Acts Most Cited By H.R. 3962

Social Security Act: 622 times
Public Health Service Act: 134 times
Affordable Health Care for America Act: 60 times
Indian Health Care Improvement Act: 56 times
Indian Self-Determination and Education Assistance Act: 45 times
Employee Retirement Income Security Act: 39 times
Medicare Prescription Drug, Improvement, and Modernization Act: 11 times
American Recovery and Reinvestment Act: 7

Sections of the U.S. Code Cited (Properly) Most By H.R. 3962

25 U.S.C. §450. Congressional statement of findings: 38
25 U.S.C. §13. Expenditure of appropriations by Bureau: 13
42 U.S.C. §1396a(a). State plans for medical assistance: 10
42 U.S.C. §1396d(a). Definitions: 7
42 U.S.C. §2004a. Sanitation facilities: 7

mjbommar Uncategorized congress, Google for Government, united states code

igraph2sonia Example 1 from michael bommarito on Vimeo.

When it comes to quickly motivating a point or engaging students in a classroom, one of the most effective tools is visualization. Not only do movies provide fun and excitement, but they also allow viewers to leverage the abilities of the visual cortex to infer dynamics and patterns in the animated system.

For our recent research, dynamic graphs are the type of system of interest. As I’ve covered before, Python is my language of choice for most programming tasks. Furthermore, Python is a very accessible language, even for beginners. However, when it comes to visualizing dynamic networks, we need another tool.  Our tool of choice is SONIA, the Social Network Image Animator.

I thought I’d provide a helpful little function to generate SONIA input files from igraph objects, along with a few examples.

This function takes as input an igraph.Graph object and a file name to store the SONIA output in. Every vertex in the Graph object should have a time attributed specified, either simply as an integer indicating the start time, or as a tuple or list of the form (startTime,endTime). Check out the following two examples if you need more guidance. Both examples visualize the construction of a periodic lattice. However, in the second example, nodes decay after some random time. Make sure not to miss the second video at the bottom of the post!

igraph2sonia Example 2 from Michael J Bommarito II on Vimeo.

mjbommar Uncategorized dynamic networks, igraph, python, sonia, visualization