Skip to content

Python Code for Network (Graph) Analysis

June 19, 2007

For the last week or so I have been revising some code I wrote a couple of years ago when I first read Barabasi’s excellent book, Linked. The refactored code is a better object-oriented design and my use of Python has improved. I will make the code available here soon.

To get to some results quickly, I started with a simple case: a network in which the nodes are randomly linked. For a network (graph) where the nodes are linked (edges) randomly, some basic results are fairly easy to get to and straight forward reproduce.

The node rank (or degree) is the number of links a given node has to other nodes.  If one starts with 100s of nodes, but only a few links, it is easy to see that the node rank of most of the nodes will be zero.  As the number of links in the network increases, the rank distribution evolves.  What is the distribution of node rank?  How does it depend on the ratio of links to nodes?

Below are three examples cases from the network simulations.  The first figure shows the distribution of rank for the case when there are half as many links as nodes (l = .5 n), the second figure shows the distributino when the number of links equals the number nodes (l = n), and the third figure shows the case when links are about 2.5 times the number of nodes (l = 2.5 n).  The distributions are said to be Poisson which the results here resemble–will have to test for that later.

 

node rank distribution 1

 

 Figure 1. What I labeled "Node Rank" is also called "Degree" in the literature and is the number of nodes one link away from a given node.

 

 

node rank distribution 2

 Figure 2

 

 

node rank distribution 3
 
Figure 3 

 

 

Advertisements
No comments yet

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: