Introduction to Networks

Background

This course contains multiple exercises that address different aspects of complex networks. These are:

Introduction to Networks

This is the first of several exercises on networks. A network (or graph, as it is often referred to in mathematics) is a data structure in which nodes are connected by edges, which provides a very general concept that plays a role in many scientific problems. This first exercise is focused on defining networks and on implementing algorithms to compute some of their properties. As such, it lays the groundwork for particular scientific applications in subsequent exercises, aimed at analyzing "small worlds" and percolation in networks.

In particular, in this exercise we will generate some random networks and calculate the distribution of distances (path lengths) between pairs of nodes. We will study small world networks, a theoretical model that suggests how a small number of shortcuts (e.g., unusual international and intercultural friendships in a social network) can dramatically shorten the tyical path lengths. Finally we will study how a simple, universal scaling behavior emerges for large networks with few shortcuts.

Learning Goals

Science: You will learn what a graph/network is. This exercise in largely about building infrastructure for use in more interesting scientific problems, such as the study of small worlds and percolation.

Computation: You will learn some basics of object-oriented programming: what a class is, how to use and manipulate them, and how they capture abstract relationships among data.

Procedure

This introductory exercise is focused on defining undirected graphs/networks.

The UndirectedGraph Class

  1. Create a new directory
  2. Download the following files:
  3. Test your routine by saving your "Networks.py", and typing in your ipython session %run Networks.py. Create an instance of your graph class by typing testgraph1=UndirectedGraph().
  4. Type testgraph1.connections to see if your initialization worked right. testgraph1 is now an instance of your class, although at this point it is a rather uninteresting instance, since it only contains an initializer that creates an empty dictionary.
  5. Go back to your text editor and complete your UndirectedGraph class by defining the following methods. Following each definition test the routine. This strategy of testing every routine immediately after writing it is the key to rapid software development. Ideally you should never have more than one routine which you are not certain works correctly. The hints file gives a good description of what each of the methods should do.
    1. HasNode
      • This is hard to test fully until you have defined AddNode. Without any nodes added, however, HasNode should return False for any node that is queried.
    2. AddNode
      • Test by typing testgraph1.AddNode(1), then look at the dictionary by typing testgraph1.connections (or, if you enjoy extra typing, print testgraph1.connections). The command testgraph1.HasNode(1) should now be True while testgraph1.HasNode(2) should be False. It should be clear how to test the rest of the methods.
    3. AddEdge
    4. GetNodes
    5. GetNeighbors
  6. Next it would be nice to visualize the graph. We have written some visualization software. To see a graphical representation of your test graph type: NetGraphics.DisplayCircleGraph(testgraph1). DisplayCircleGraph will work on any object which has the following methods: GetNodes, GetNeighbors. It doesn't care about the internal implementation.
  7. For further testing, your "Networks.py" file contains a predefined function called pentagraph. Type testgraph2=pentagraph() to run the function and assign the output to a new object called testgraph2. This should create a graph and display a figure shaped like a pentagram.
  8. You now have a working class, and we can start to use it for something. Proceed to either the Small Worlds Exercise or the Percolation Exercise.

Useful Constructions/Syntax

Science Concepts

Files

References

Links

Notes

Different types of networks

Networks and graphs come in many flavors. Undirected graphs involve edges that have no intrinsic directionality, i.e., the two nodes connected by the edge are symmetric. In directed graphs, edges have directionality: the edge points from one node to the other, introducing an asymmetry. We will be studying edges without weights (i.e., all edges are equivalent), but in many important problems, edges have weights. In this exercise, we're using the specific name UndirectedGraph to be clear and avoid confusion.

Objects and classes

Modules and namespaces

A module is a way of grouping together a set of classes and functions that are used for a particular purpose. For example, in this exercise you generate a networks module that has functions and classes used for manipulating networks. In python, you load a module with the command import, although the ipython interpreter provides the shortcut function %run that imports everything in the specified file into the __main__ namespace.

Namespaces are a mechanism for organizing the names of variables (objects, functions, classes, etc.), so as to avoid giving two variables/functions/classes/objects the same name. Suppose you are writing a program and you defined a function f. Suppose later you load the usefulstuff module (by typing import usefulstuff) and usefulstuff happens to also define a function f. There could be a conflict here. You don't want the f in usefulstuff to overwrite the f that you defined. The way python avoids this problem is that the two f's are in different namespaces. To access the usefulstuff function "f", you must type usefulstuff.f. You can think of the . in the same way you think of "/" when you are navigating directories. You can change the namespace that you import a module into by typing import usefulstuff as u -- which would put usefulstuff in the namespace u. This saves typing, but in the end can lead to more confusion. (You can also circumvent the protection that namespaces provide by typing from usefulstuff import *, in which case everything defined in usefulstuff will be imported into the space doing the importing, which could result in your previously defined functions being overwritten.)

Note that the syntax for calling the display function contained in the NetGraphics module is very similar to the syntax used to call methods of a class. This similarity is intentional: NetGraphics is a module, DisplayCircleGraph is a function inside that module, and the "dot" operator . is used to access the function within the module's namespace, just as the dot operator is used to access a method within an object's namespace.

Interplay of visualization tools and core data structures

As an aside, one could add to UndirectedGraph a method called Display, so that if you typed testgraph1.Display() it would call DisplayCircleGraph, creating a picture of the graph. One would say that the object knows how to display itself. In certain contexts this might be what you want. There are, however, several downsides:

Privacy in Python

Many object-oriented languages have a syntactic notion of privacy: data in a class that are declared private, for example, are incapable of being modified from outside the class. Python does not contain such constructs, generally relying instead on programmers' recognizing the value of encapsulating internal data and working instead through method interfaces. Although we have created the pentagraph using the externally defined methods like AddEdge, we could instead break the encapsulation of internal data and manipulate the connections dictionary directly. (If you're feeling adventurous, go ahead and try it: after creating the graph, now type testgraph2.connections[2].append(3). Any idea what this will do? Run NetGraphics.DisplayCircleGraph(testgraph2) to see. Looks can be deceiving, though. Even though node 3 is now a neighbor of node 2, is the converse true? Use GetNeighbors to check.) Breaking the data encapsulation makes for a fragile program. In scientific computing this may not be a bad thing. If you are only going to use a function once, then it might not be worth the time to figure out how to better design things. It is a good exercise to think of alternative ways to implement this function -- for example, you could add a SetNeighborDict method to write the entire neighbor dictionary by hand, or a SetNeighbors(node) to set the neighbors of a given node.

"Applying" a function to a tuple of arguments

Here is a useful construction that you might want to learn. Create a "tuple" of nodes: newnodes=(4,5). Suppose you wanted to add these nodes (and an edge between them) to testgraph1. The obvious way is to type testgraph1.AddEdge(newnodes[0],newnodes[1]). The shorter way is testgraph1.AddEdge(*newnodes). The asterix essentially "strips" the elements of the tuple so you can apply the function to them; that is, a function that accepts N arguments can be fed instead a tuple containing N elements. (This is equivalent to the Apply function in Mathematica.)
James P. Sethna, Christopher R. Myers, Erich J. Mueller.

Last modified: August 25, 2008