SIGCSE 2007 Workshop, March 10, 2007

It is also possible to change the value of attributes for nodes and edges. To do this we use both the '.' and the equals sign, '=' to "assign" the attribute a new value. For an example of this, lets first make Jack purple, and then make the edge between Jack and Kim orange. Here is the code:

Now it is easier to find Jack and the edge between Jack and Kim.

• name * - the name by which you access nodes
• label - text to recognize the node by
• x - x position in visualization
• y - y position in visualization
• width - width of node
• height - height of node
• style - style of node. rectangle = 1, ellipse = 2, rounded rectangle = 3, text inside a rectangle = 4, text inside an ellipse = 5, text inside a rounded rectangle = 6
• outdegree* - gives outdegree
• indegree* - gives indegree
totaldegree* - gives total degree
• betweenness* - gives betweenness centrality
• color - color of node
• visible - if visible = 0, then the node cannot be seen, if it is any other value it may be seen

Final Example

Here is a final example that will help you put together a couple of the things you have learned.
Let's say we want to investigate what impact the removal of Jack and all of his neighbors would have on the "24" graph. First, make sure you have the "twentyFour.gdf" file loaded and that you have opened the Node Functions Panel. Select Jack and highlight his neighbors. Now shift click Jack and all of his neighbors and click on "Save Group" to save these nodes to a group. Check the image below to make sure you got all of the nodes.

Now save this group under the name "friends". To make it appear like we have removed Jack and his friends, we need to type some commands into the interpreter.

You'll notice something strange about this line of code -- it doesn't contain any node names! In DukeGuess, if you have a group of nodes you can access and change the same attribute for all nodes in the group by using the '.' (dot) operator on the group name the same way you would use it on a node name.
You should end up with a graph that looks something like the one below. Clearly Jack and his friends are a key portion of this social network! Also notice that DukeGuess makes invisible edges attached to invisible nodes

Steven Johnson's popular book, Everything Bad Is Good for You: How Today's Popular Culture Is Actually Making Us Smarter, looks at how today's popular entertainment is actually far more complex than the culture of the past and requires more cognitive work of the pop culture consumer. As an example, he compares the social network of the characters in 24 (twentyFour.gdf) as compared to the popular 80s show Dallas (dallas.gdf).

In what ways, does the social network imply that 24 is indeed more complex?

Basic Graph Operations

This graph has six nodes (A-F) and eight edges. It can be represented by the following dictionary:

In Gython, the extension of Python used in GUESS, there is a -> operator that accesses a directed edge between two nodes. Therefore, you can create the graph above using with the following code.

GUESS automatically defines a variable g that represents the entire graph. g.nodes and g.edges are the list of of all nodes and edges in the graph, respectively.

There are actually five different operators that can be used to represent an edge between node1 and node2.

	node1->node2 # directed edge (node 1 to node 2)
	node1<-node2 # directed edge (node2 to node1)
	node1-node2  # undirected edge
	node1<->node2 # undirected edge (or bidirectional)
	node1?node2 # any type of edge between node1 and node2

Nodes are objects. To access node and edge attributes, use the dot operator (".").

node1.color = blue               # Make node1 blue
(node1?node2).color = cyan       # Make all types of edges between node1 and node2 cyan
(node1->node2).weight = 5        # Make the edge from node1 to node2 have a weight of 5
node1.visible = 0                # Make node1 invisible

For example, weight.min returns the minimum weight for all edges, and salary.max returns the max salary for all nodes. See our GUESS Quick Reference Sheet for more information on node and edge attributes.

Path Finding

    # returns list of nodes in path from start to end
    #  or None if no path exists
    def find_path(start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in g.nodes:
            return None
        adj = start.getNeighbors()
        for node in adj:
            if node not in path:
                newpath = find_path(node, end, path)
                if newpath: return newpath
        return None

One new feature here is the use of default arguments with path=[]. The function can now be called with only two arguments as in: findpath(node1, node2). A sample run (using the graph above):

    > find_path(A, D)
    [A, B, C, D]
    > 

Note that while the user calls find_graph() with two arguments, it calls itself with a third argument: the path that has already been traversed. The default value for this argument is the empty list, '[]', meaning no nodes have been traversed yet. This argument is used to avoid cycles (the first 'if' inside the 'for' loop). The 'path' argument is not modified: the assignment path = path + [start] creates a new list. If we had written path.append(start) instead, we would have modified the variable path in the caller, with disastrous results.

Exercises

1. It is simple to change this function to return a list of all paths (without cycles) instead of the first path it finds. Write find_all_paths
   A sample run:

       > find_all_paths(A, D)
       [[A, B, C, D], [A, B, D], [A, C, D]]
       > 
   

2. Another variant would finds the shortest path, write find_shortest_path based off of the function above to return the shortest path from start to end

   A sample run is below:

       > find_shortest_path(graph, A, D)
       [A, C, D]
       > 
   

3. The diameter of a graph is the longest shortest path between any two vertices. Write a function findDiameter that returns the longest path between any two vertices.

4. Consider the following depth-first search function dfs that takes a node as an argument and then visits every node reachable from

   # visit each connected node in the graph (g) start from u in a depth-first manner 
   def dfs(u):
     stack = [] 
     addNodeField("visited",Types.BOOLEAN,FALSE) # add visited field if necessary
     stack.append(u) # append to back works as push
     while len(stack) > 0: 
       v = stack.pop() 
       v.visited = true
       adj = v.getNeighbors()
       for w in adj:
         if not w.visited:
           stack.append(w)
   

   Now, write a function bfs that traverses the graph from a node in a breadth-first manner. Hint: use a queue. You should also be able to keep track of the unweighted distance from the source as you proceed. We have started it for you below.

   # visit each connected node in the graph (g) start from u in a breadth-first manner 
   def bfs(u):
     queue = []
     maxDist = len(g.nodes)   # no path can be longer than the number of vertices
     addNodeField("dist",Types.INTEGER,Integer(maxDist)) # add field to store distance
   
   

GUESS Centrality

In the 1970s, E.M. Rogers and D.L. Kincaid studies the diffusion of family planning methods in 24 villages in the Republic of Korea. In the DukeGUESS folder, there are two files, korea1.gdf and korea2.gdf, that represent the communication networks among women in the two villages. In both networks, each vertex represents a woman in the village and an edge between two vertices indicates that the two women discussed family planning. The vertices also have other attributes:

• adopter: true if and only if the woman adopted family-planning methods at least temporarily, false otherwise
• member: true if and only if the woman was a member of the local Mothers' Club, which played an important role in the diffusion of family-planning methods, false otherwise

(adopter == false).visible = false

The successful village which had a successful family planning program is on the left below (korea1.gdf) and, the unsuccessful group is on the right (korea2.gdf). When looking at the graphs of these two networks below, it is easy to see that the network structure does differ.

korea1	korea2

The centrality is the measure of how central a particular a vertex is in the social network. One would expect entities with high centrality to be hubs, having better access to information, and more opportunities to spread information. There are three relevant measures of centrality

• Degree: the degree of a node
• Closeness: a measure of the inverse average distance of a node to all other nodes

  Call the shortest path between two vertices a geodesic. The distance between two nodes is the number of edges be on that geodesic. The closeness centrality is the number of other vertices divided by the sum of all distances between the vertex and all others.

• Betweenness: a measure of how much a vertex is between other nodes

  The betweenness centrality is the proportion of all geodesics between pairs of other vertices that include this vertex.