Making friends

Social networking sites often have an eerie ability to make good suggestions about who you should add to your list of “connections” or “friends.” One way they do this is by examining the connections of your connections (or “friends-of-friends”). For example, consider the expanded social network graph in Figure 12.5. Dave currently has only three friends. But his friends have an additional seven friends that an algorithm could suggest to Dave.

In graph terminology, the connections of a node are called the node’s neighborhood, and the size of a node’s neighborhood is called its degree. In the graph in Figure 12.5, Dave’s neighborhood contains Beth, Cathy and Christina, and therefore his degree is three.

Once we have a network in an adjacency list, writing an algorithm to collect new friend suggestions is relatively easy. The function below iterates over the neighbors of the node for which we would like suggestions and then, for each of these neighbors, iterates over the neighbors’ neighbors.

 1 def friendsOfFriends(network, node):
 2     """Find new neighbors-of-neighbors of a node in a network.
 3
 4     Parameters:
 5         network: a graph represented by a dictionary
 6         node: a node in the network
 7
 8     Return value: a list of new neighbors-of-neighbors of node
 9     """
10
11     suggestions = [ ]
12     neighbors = network[node]
13     for neighbor in neighbors:                # neighbors of node
14         for neighbor2 in network[neighbor]:   # neighbors of neighbors
15             if neighbor2 != node and 
16                neighbor2 not in neighbors and 
17                neighbor2 not in suggestions:
18                 suggestions.append(neighbor2)
19     return suggestions

On line 12, network[node] is the list of nodes to which node is connected in the adjacency list named network. We assign this list to neighbors, and then iterate over it on line 13. On line 14, in the inner for loop, we then iterate over the list of each neighbors’ neighbors. In the if statement, we choose suggestions to be a list of unique neighbors-of-neighbors that are not the node itself or neighbors of the node.

In the next section, we will design an algorithm to find paths to nodes that are farther away. The ability to compute the distance between nodes will also allow us to better characterize and understand large networks.

Exercises

12.1.1. Besides those presented in this section, describe three other examples of networks.

12.1.2. Draw the network represented by the following adjacency matrix.

12.1.3. Draw the network represented by the following adjacency list.

graph = {'A': ['C', 'D', 'F'],
          'B': ['C', 'E'],
          'C': ['A', 'B', 'D'],
          'D': ['A', 'C'],
          'E': ['B', 'F'],
          'F': ['A', 'E']}

12.1.4. Show how the following network would be represented in Python as

1. an adjacency matrix

2. an adjacency list

12.1.5. What is the neighborhood of each of the nodes in the network from Exercise 12.1.4?

12.1.6. What is the degree of each node in the network from Exercise 12.1.4? Which node(s) have the maximum degree?

12.1.7. Are the networks in each of the following pairs the same or different? Why?

(a)

(b)

12.1.8. A graph can be represented in a file by listing one link per line, with each link represented by a pair of nodes. For example, the graph below is represented by the file on the right. Write a function that reads such a file and returns an adjacency list (as a dictionary) for the graph. Notice that, for each line A B in the file, your function will need to insert node B into the list of neighbors of A and insert node A into the list of neighbors of B.

12.1.9. In this chapter, we are generally assuming that all graphs are undirected, meaning that each link represents a mutual relationship between two nodes. For example, if there is a link between nodes A and B, then this means that A is friends with B and B is friends with A, or that one can travel from city A to city B and from city B to city A. However, the relationships between nodes in some networks are not mutual or do not exist in both directions. Such a network is more accurately represented by a directed graph (or digraph), in which links are directed from one node to another. In a picture, the directions are indicated arrows. For example, in the directed graph below, one can go directly from node A to node B, but not vice versa. However, one can go in both directions between nodes B and E.

1. (a) Give three examples of networks that are better represented by a directed graph.
2. (b) How would an adjacency list representation of a directed graph differ from that of an undirected graph?
3. (c) Write a function that reads a file representing a directed graph (see the example above), and returns an adjacency list (as a dictionary) representing that directed graph.

12.1.10. Write a function that returns the maximum degree in a network represented by an adjacency list (dictionary).

12.1.11. Write a function that returns the average degree in a network represented by an adjacency list (dictionary).

Finding the actual paths

In some applications, just finding the distance between two nodes is not enough; we actually need a path between the nodes. For example, just knowing that you are only three hops away from that potential employer in your social network is not very helpful. You want to know who to ask to introduce you! And in a road network, we want to know the actual directions, not just the distance.

Fortunately, the breadth-first search algorithm is already finding the shortest paths; we just need to remember them. Consider how the distance from Beth to Tyler was computed in the previous example. As depicted below, from Beth, we visited Dave; from Dave, we visited Christina; and from Christina, we visited Tyler.

Since we incremented the distance to Tyler by one each time we crossed one of these links, this path must be a shortest path! Therefore, all we have to do is remember this order of nodes, as we visit them. This is accomplished by adding another dictionary, named predecessor, to the bfs function:

 1 def bfs(network, source):
 2     """ (docstring omitted) """
 3
 4     visited = { }
 5     distance = { }
 6     predecessor = { }
 7     for node in network:
 8         visited[node] = False
 9         distance[node] = float('inf')
10         predecessor[node] = None
11     visited[source] = True
12     distance[source] = 0
13     queue = [source]
14     while queue != [ ]:
15         front = queue.pop(0)             # dequeue front node
16         for neighbor in network[front]:
17             if not visited[neighbor]:
18                 visited[neighbor] = True
19                 distance[neighbor] = distance[front] + 1
20                 predecessor[neighbor] = front
21                 queue.append(neighbor)   # enqueue visited node
22     return distance, predecessor

The predecessor dictionary remembers the predecessor (the node that comes before) of each node on the shortest path to it from the source. This value is assigned on line 20: the predecessor of each newly visited node is assigned to be the node from which it is visited.

To construct the path to any particular node, we need to follow the predecessors backward from the destination. As we follow them, we will insert each one into the front of a list so they are in the correct order when we are done. For example, in the previous example, to find the shortest path from Beth to Tyler, we start at Tyler.

path = ['Tyler']

Tyler’s predecessor was Christina (i.e., predecessor['Tyler'] was assigned to be 'Christina' by the bfs algorithm), so we insert Christina into the front of the list:

path = ['Christina', 'Tyler']

Christina’s predecessor was Dave, so we next insert Dave into the front of the list:

path = ['Dave', 'Christina', 'Tyler']

Finally, Dave’s predecessor was Beth:

path = ['Beth', 'Dave', 'Christina', 'Tyler']

Since Beth was the source, we stop. The following function implements this idea.

def path(network, source, dest):
    """Find a shortest path in network from source to dest.

    Parameters:
        network: a graph represented by a dictionary
        source: the source node in network
        dest: the destination node in network

    Return value: a list containing a path from source to dest
    """

    allDistances, allPredecessors = bfs(network, source)

    path = [ ]
    current = dest
    while current != source:
        path.insert(0, current)
        current = allPredecessors[current]
    path.insert(0, source)

    return path

With the destination node initially assigned to current, the while loop inserts each value assigned to current into the front of the list named path and then moves current one step closer to the source by reassigning it the predecessor of current. When current reaches the source, the loop ends and we insert the source as the first node in the path.

In the next section, we will use information about shortest paths to investigate a special kind of network called a small-world network.

Exercises

12.2.1. List the order in which nodes are visited by the bfs function when it is called to find the distance between Ted and every other node in the graph in Figure 12.5. (There is more than one correct answer.)

12.2.2. List the order in which nodes are visited by the bfs function when it is called to find the distance between Caroline and every other node in the graph in Figure 12.5. (There is more than one correct answer.)

12.2.3. By modifying one line of code, the visited dictionary can be completely removed from the bfs function. Show how.

12.2.4. Write a function that uses the bfs function to return the distance in a graph between two particular nodes. The function should take three parameters: the graph, the source node, and the destination node.

12.2.5. We say that a graph is connected if there is a path between any pair of nodes. The breadth-first search algorithm can be used to determine whether a graph is connected. Show how to modify the bfs algorithm so that it returns a Boolean value indicating whether the graph is connected.

12.2.6. A depth-first search algorithm (see Section 10.5) can also be used to determine whether a graph is connected. Recall that a depth-first search recursively searches as far from the source as it can, and then backtracks when it reaches a dead end. Writing a depth-first search algorithm for a graph is actually much easier than writing the one in Section 10.5 because there are fewer base cases to deal with.

1. Write a function

   dfs(network, source, visited)

   that performs a depth-first search on the given network, starting from the given source node. The third parameter, visited, is a list of nodes that have been visited by the depth-first search. The initial list argument passed in for visited should be empty, but when the function returns, visited should contain all of the visited nodes. In other words, you should call the function initially like this:

   visited = []
   dfs(network, source, visited)

2. Write another function

   connected(network)

   that calls your dfs function to determine whether network is connected. (The source node can be any node in the network.)

Clustering coefficients

The extent to which the neighborhood of a node is clustered is measured by its local clustering coefficient. The local clustering coefficient of a node is the number of links between its neighbors, divided by the total number of possible links between neighbors. For example, consider the cluster on the left below surrounding the blue node in the center.

The blue node has five neighbors, with six links between them (in red). Notice that each of these links, together with two black links, forms a closed cycle, called a triangle. So we can also think about the local clustering coefficient as counting these triangles. As shown on the right, there are four dashed links between neighbors of the blue node (i.e., four additional triangles) that are not present on the left, for a total of ten possible links altogether. So the local clustering coefficient of the blue node is 6/10 = 0.6. (The clustering coefficient will always be between 0 and 1.)

Each of the k neighbors could be connected to k – 1 other neighbors, for a total of k(k – 1) links. However, this counts each link twice, so the total number of possible links is actually k(k – 1)/2. Therefore, the local clustering coefficient of a node with k neighbors is the number of neighbors that are connected, divided by k(k – 1)/2. The clustering coefficient for an entire network is the average local clustering coefficient over all nodes in the network. The highly structured grid or mesh graph in Figure 12.7 does not have any triangles at all, so its clustering coefficient is 0. On the other hand, the graph in Figure 12.6 has a clustering coefficient of about 0.59.

It has been suggested that situations like this breed instability. Imagine that, instead of a social network, we are talking about a network of nations and links represent the existence of diplomatic relations. A nation with diplomatic relations with many other nations that are enemies of each other is likely in a stressful situation. It might be helpful to detect such situations in advance to curtail potential conflicts.

To compute the local clustering coefficient for a node, we need to iterate over all of the node’s neighbors and count for each one the number of links between it and the other neighbors of the node. Then we divide this number by the maximum possible number of links between the node’s neighbors. This is accomplished by the following function.

def clusteringCoefficient(network, node):
    """Compute the local clustering coefficient for a node.

    Parameters:
        network: a graph represented by a dictionary
        node: a node in the network

    Return value: the local clustering coefficient of node
    """

    neighbors = network[node]
    numNeighbors = len(neighbors)
    if numNeighbors <= 1:
        return 0
    numLinks = 0
    for neighbor1 in neighbors:
        for neighbor2 in neighbors:
            if neighbor1 != neighbor2 and neighbor1 in network[neighbor2]:
                numLinks = numLinks + 1
    return numLinks / (numNeighbors * (numNeighbors - 1))

This function is relatively straightforward. The two for loops iterate over every possible pair of neighbors, and the if statement checks for a link between unique neighbors. However, this process effectively counts every link twice, so at the end we divide by numNeighbors * (numNeighbors - 1) (i.e., k(k – 1)), which is twice what we discussed previously.

The function effectively counts every link twice because it checks whether each neighbor is in every other neighbor’s list of adjacent nodes. Therefore, for any two connected neighbors, call them A and B, we are counting the link once when we see A in the list of adjacent nodes of B and again when we see B in the list of adjacent nodes of A.

To count each link just once, we can use the following trick. In the list of neighbors, we first check whether the node at index 0 is connected to nodes at indices 1, 2, ..., k – 1. Then, to prevent counting a link twice, we never want to check whether any node is connected to node 0 again. So we next check whether node 1 is connected to nodes 2, 3, ..., k – 1. Now, to prevent double counting, we never want to check whether any node is connected to nodes 0 or 1. So we next check whether node 2 is connected to nodes 3, 4, ..., k – 1. Do you see the pattern? In general, we only want to check whether node i is connected to nodes i + 1, i + 2, ..., k – 1. (This is the same trick you may have seen in Exercise 8.5.4.) This is implemented in the following improved version of the function.

def clusteringCoefficient(network, node):
    """ (docstring omitted) """

     neighbors = network[node]
     numNeighbors = len(neighbors)
     if numNeighbors <= 1:
         return 0
     numLinks = 0
     for index1 in range(len(neighbors) - 1):
         for index2 in range(index1 + 1, len(neighbors)):
             neighbor1 = neighbors[index1]
             neighbor2 = neighbors[index2]
             if neighbor1 != neighbor2 and neighbor1 in network[neighbor2]:
                 numLinks = numLinks + 1
     return numLinks / (numNeighbors * (numNeighbors - 1) / 2)

Once we have this function, to compute the clustering coefficient for the network, we just have to call it for every node, and compute the average. We leave this, and writing a function to compute the average distance, as exercises.

Scale-free networks

In addition to having short paths and high clustering, researchers soon discovered that most small-world networks also contain a few highly connected (i.e., high degree) nodes called hubs that facilitate even shorter paths. In the network in Figure 12.6, nodes 5, 12, and 18 are hubs because their degrees are large relative to the other nodes in the network.

The existence of hubs in a large network can be seen by plotting for each node degree in the network the fraction of the nodes that have that degree. This is called the degree distribution of the network. The degree distribution for a network with a few hubs will show the vast majority of nodes having relatively small degree and just a few nodes having very large degrees. For example, Figure 12.8 shows such a plot for a small portion of the web. Each node represents a web page and a directed link from one node to another represents a hyperlink from the first page to the second page.¹ In this network, 99% of the nodes have degree at most 25, while just a few have degrees that are much higher. (In fact, 98% of the nodes have degrees at most 20 and 90% have degrees at most 15.) These few hubs with high degree enable a small average distance and a clustering coefficient of about 0.37.

Networks with this characteristic shape to their degree distributions are called scale-free networks. The name comes from the observation that the fraction of nodes with degree d is roughly (1/d)^a, for some small value of a. Such functions are called “scale-free” because their plots have the same shape regardless of the scale at which you view them. A scale-free degree distribution is very different from the normal distribution that seems to describe most natural phenomena, which is why this discovery was so interesting.

The presence of hubs in a network is a double-edged sword. On the one hand, hubs enable efficient communication and transportation. For this reason, the Internet is structured in this way, as are airline networks (see Figure 12.9). Also, because so many of the nodes in a scale-free network are relatively unimportant, scale-free networks tend to be very robust when subjected to random attacks or damage. Some have speculated that, because some natural networks are scale-free, they may represent an evolutionary advantage. On the other hand, because the few hubs are so important, a directed attack on a hub can cause the network to fail. (Have you ever noticed the havoc that ensues when an airline hub is closed due to weather?) A directed attack on a hub can also be advantageous if we want the network to fail. For example, if we suspect that the network through which an epidemic is traveling is scale-free, we may have a better chance of stopping it if we vaccinate the hubs.

Exercises

12.3.1. Write a function that returns the average local clustering coefficient for a network. Test your function by calling it on some of the networks on the book web site. You will need the function assigned in Exercise 12.1.8 to read these files.

12.3.2. Write a function that returns the average distance between every pair of nodes in a network. If two nodes are not connected by a path, assign their distance to be equal to the number of nodes in the network (since this is longer than any possible path). Test your function by calling it on some of the networks on the book web site. You will need the function assigned in Exercise 12.1.8 to read these files.

12.3.3. The closeness centrality of a node is the total distance between it and all other nodes in the network. By this measure, the node with the smallest value is the most central (and perhaps most influential) node in the network. Write a function that computes the closeness centrality of a node. Your function should take two parameters: the network and a node. Test your function by calling it on some of the networks on the book web site. You will need the function assigned in Exercise 12.1.8 to read these files.

12.3.4. Using the function you wrote in the previous exercise, write another function that returns the most central node in a network (with the smallest closeness centrality).

12.3.5. Write a function that plots the degree distribution of a network, producing a plot like that in Figure 12.8. Test your function on a small network first. Then call your function on the large Facebook network (with 4,039 nodes and 88,234 links) that is available on the book web site. (You will need the function assigned in Exercise 12.1.8 to read these files.) Is the network scale-free?

Exercises

12.4.1. Show how to create a uniform random graph with 30 nodes and 50 links, on average.

12.4.2. Exercise 12.3.1 asked you to write a function that returns the clustering coefficient for a graph. Use this function to write another function

avgCCRandom(n, p, trials)

that returns the average clustering coefficient, over the given number of trials, of random graphs with the given values of n and p.

12.4.3. Exercise 12.3.2 asked you to write a function that returns the average distance between any two nodes in a graph. Use this function to write another function

avgDistanceRandom(n, p, trials)

that returns the average of this value, over the given number of trials, for random graphs with the given values of n and p.

12.4.4. Exercise 12.3.5 asked you to write a function to plot the degree distribution of a graph and then call the function on the large Facebook network on the book web site. This network has 4,039 nodes and 88,234 links. To compare the degree distribution of this network to a random graph of the same size, write a function

degreeDistributionRandom(n, p, trials)

that plots the average degree distribution, over the given number of trials, of random graphs with the given values of n and p. Then use this function to plot the degree distribution of random graphs with 4,039 nodes and an average of 88,234 links. What do you notice?

12.4.5. We say that a graph is connected if there is a path between any pair of nodes. Random graphs that are generated with a low probability p are unlikely to be connected, while random graphs generated with a high probability p are very likely to be connected. But for what value of p does this transition between disconnected and connected graphs occur?

To determine whether a graph is connected, we can use either a breadth-first search (as in Exercise 12.2.5) or a depth-first search (as in Exercise 12.2.6). In either case, we start from any node in the network, and try to visit all of the other nodes. If the search is successful, then the graph must be connected. Otherwise, it must not be connected.

1. Write a function

   connectedRandom(n, minp, maxp, stepp, trials)

   that plots the fraction of random graphs with n nodes that are connected for values of p ranging from minp to maxp, in increments of stepp. To compute the fraction that are connected for each value of p, generate trials random graphs and count how many of those are connected using your connected function from either Exercise 12.2.5 or Exercise 12.2.6.

2. For n = 24, what do you find? For what value of p is there a 50% chance that the graph will be connected? Does the transition from disconnected graphs to connected graphs happen gradually or is change abrupt?

Project 12.1 Diffusion of ideas and influence

In this project, you will investigate how memes, ideas, beliefs, and information propagate through social networks, and who in a network has the greatest influence. We will simulate diffusion through a network with the independent cascade model. In this simplified model, an idea originates at one node (called the seed) and each of the neighbors of this node adopts it with some fixed probability (called the propagation probability). This probability measures how influential each node is. In reality, of course, people have different degrees of influence, but we will assume here that everyone is equally influential. Once the idea has propagated to one or more new nodes, each of these nodes gets an opportunity to propagate it to each of their neighbors in the next round. This process continues through successive rounds until all of the nodes that have adopted the idea have had a chance to propagate it to their neighbors.

For example, suppose node 1 in the network below is the seed of an idea.

In round 1, node 1 is successful in spreading the idea to node 2, but not to node 4. In round 2, the idea spreads from node 2 to both node 3 and node 5. In round 3, the idea spreads from node 3 to node 7, but node 3 does not successfully influence node 8. Node 5 also attempts to influence node 4, but is unsuccessful. In round 4 (not shown), node 7 attempts to spread the idea to nodes 6 and 8, but is unsuccessful, and the process completes.

readNetwork(fileName)

diffusion(network, seed, p)

rateSeed(network, seed, p, trials)

maxInfluence(network, p, trials)

Project 12.2 Slowing an epidemic

In Section 4.4, we simulated the spread of a flu-like virus through a population using the SIR model. In that simulation, we lumped all individuals into three groups: those who are susceptible to the infection, those who are currently infected, and those who recovered. In reality, of course, not every individual in the susceptible group is equally susceptible and not every infected person is equally likely to infect others. Some of the differences have to do with who comes into contact with whom, which can be modeled by a network. For example, consider the network in Figure 12.6 on Page 602. In that network, if node 3 becomes infected and there is a 10% chance of any individual infecting a contact, then the virus is very unlikely to spread at all. On the other hand, if node 12 becomes infected, there is a 9 · 10% = 90% chance that the virus will spread to at least one of the node’s nine neighbors.

If a vaccine is available for the virus, then knowledge about the network of potential contacts can be extremely useful. In this project, you will simulate and compare two different vaccination strategies: vaccinating randomly and vaccinating targeted nodes based on a criterion of your choosing.

readNetwork(fileName)

infection(network, p, vaccinated)

vaccinationSim(network, p, trials, numVaccs, randomSim)

Project 12.3 The Oracle of Bacon

In the 1990’s, a group of college students invented a pop culture game based on the six degrees of separation idea called the “Six Degrees of Kevin Bacon.” In the game, players take turns challenging each other to identify a connected chain of actors between Kevin Bacon and another actor, where two actors are considered to be connected if they appeared in the same movie. An actor’s Bacon number is the distance of the actor from Kevin Bacon.

This game later spawned the “Oracle of Bacon” website, at http://oracleofbacon.org, which gives the shortest chain between Mr. Bacon and any other actor you enter. This works by constructing a network of actors from the Internet Movie Database (IMDb)², and then using breadth-first search to find the desired path. This network of movie actors provides fertile ground for investigating all of the concepts discussed in this chapter. Is the network really a small-world network, as suggested by the “Six Degrees of Kevin Bacon?” Is there really anything special about Kevin Bacon in this network? Or is there a short path between any two pair of actors? Is the network scale-free?

In this project, you will create an actor network, based on data from the IMDb, and then answer questions like these. You will also create your own “Oracle of Bacon.”

League of Their Own, A (1992)Tom HanksMadonnaPenny Marshall …
Animal House (1978)Kevin BaconJohn BelushiDonald Sutherland …
Apollo 13 (1995)Kevin BaconTom HanksBill PaxtonGary Sinise …

createNetwork(filename)

degreeDistribution(network)

oracle(network)

Zooey Deschanel and Kevin Bacon have distance 2.

1. Kevin Bacon was in "The Air I Breathe (2007)" with Clark Gregg.
2. Clark Gregg was in "(500) Days of Summer (2009)" with Zooey Deschanel.

baconNumbers(network)

Bacon Number     Frequency
------------     ---------
     0                   1
     1                 152
     2                2816
     3               12243
     4                4230
     5                 253
     6                  47
     7                   0
     8                   0
  infinity             819