Getting Sage Running

• Online: either with SageMath Cloud or the Sage Notebook. For these you need to login, but you can save your worksheets. There is also the Sage Cell Server, where you don't need to login in.
• Download it and install it on your machine. The current version on my Mac is about 3GB, though the download is only about half a gig or so. The easiest thing seems to be to install a pre-built binary, though on Windows this involves installing VirtualBox, which I have no experience with.
• Run Sage using VirtualBox on the machines in the lab. See instructions.

A little graph theory in Sage

First, Sage uses Python, so your familiarity with Python will give you a good start. You can do things in Sage the same was as in Python, but it has a whole bunch more built in so we can do lots of things more easily. If you like, you can go through a bit of the tutorial. For graph theory in Sage, the pages Sage in Graph Theory and Algebraic Graph Theory with Sage contain some instructions, and when all else fails, you can check the Sage Graph Theory Reference Manual.

We'll just go through a sample of some simple things you can do.

Constructing Graphs:

• Use built-in graph constructors, such as graphs.CycleGraph(8) or graphs.CompleteGraph(5).
• Create a matrix A in Sage, e.g., A = matrix([[0,1], [1,0]]). The associated graph is G = Graph(A).
• Graph modifiers G.add_edge, G.add_vertex, G.delete_edge, G.delete_vertex, G.union(H), etc.

Graph Details: Given a graph G, you can get the

• adjacency matrix with G.am()
• drawing with G.plot() or G.plot3d()
• vertices with G.vertices()
• edges with G.edges()
• distances with G.distance(u,v)
• a shortest path with G.shortest_path(u,v)
• connected components with G.connected_components()

Graph Invariants: Given a graph G, you can get the

• order with G.order()
• size with G.size()
• average degree with G.average_degree()
• degree sequence with G.degree_sequence()
• diameter with G.diameter()
• average distance with G.average_distance()
• size with G.size()

Here is a comprehensive list of generic (directed or undirected) graph functions.

Here are two examples of social networks you can play with.

Task 1: Using the graphs.RandomGNP(n,p) generate and plot several random graphs for n=20, p = 0.1. Here n is the number of vertices, and p is the probability of an edge between any pair of distinct vertices (i,j). (The probability p are identical and independent for all pairs of vertices.) What do you notice about the structure of such graphs? Do the same thing for various some different values of p, e.g., p=.05, .15, .2, .3, .5. Now what do you notice? How large should p be for this to usually be connected? Does this change if you take n=100? (You can use the function G.is_connected().)

Task 2: Write a function ddplot(G) that will graph the degree distribution of G. We can do this with a line plot or a bar chart, but let's use a bar chart. Use the bar_chart function on G.degree_histogram(). Now graph the degree distribution for our two social networks, as well as some random graphs. What do the degree distributions look like? Can you get similar degree distributions to the social network ones by using random graphs? (Use the same n, and figure out what p should be based on the number of edges to try to model these social networks.)