Algorithms

graph.algorithms.page_rank(g, reset_prob[, ...]) Computes the PageRank of each node in g and stores it in node[‘page_rank’].
graph.algorithms.out_degree(g) Computes the out degree of each node.
graph.algorithms.connected_comp(g) Computes the connected components of the graph.

Convenience Classes

graph.algorithms.GraphLabel(name, \*\*attrs) A dict-like convenience wrapper object for graph nodes and edge labels.

Graph Algorithms

Note

For each of the following algorithms, the node and edge objects must be able to store attributes in dict-like fashion. If necessary you can wrap the existing node and edge objects with graph.algorithms.GraphLabel use the method

g.new_projection(GraphLabel.edge_wrapper,GraphLabel.node_wrapper)

and then apply the algorithm to the returned graph. See graph.algorithms.GraphLabel for more details.

Out Degree

graph.algorithms.out_degree(g)

Computes the out degree of each node.

Parameters:g (graph.Graph) – Each node in the graph should be a graph.algorithms.GraphLabel, or else behave like a dict. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def out_degree(g):
    # Each edge emits a non-empty message to the source node (and an empty message to the destination node)
    def emitter(src,dst,e):
        return [1],[]
    
    # Each node collects all the messages it receives and counts them, the result is the number of outgoing edges.
    def collector(node,msgs):
        node['out_degree'] = len(list(msgs))
    
    g.send_collect(emitter,collector)

PageRank

graph.algorithms.page_rank(g, reset_prob, threshold=0.001)

Computes the PageRank of each node in g and stores it in node[‘page_rank’].

Note

The node and edge objects must be able to store attributes in dict-like fashion. If necessary you can use the method g.new_projection(edge_map,node_map) where

Parameters:
  • g (graph.Graph) – The graph we use to compute the PageRank. Each node in the graph should be a graph.algorithms.GraphLabel, or else behave like a dict.
  • reset_prob (float) – The probability (between 0 and 1) that one jumps to a random node (as opposed to following one of the outgoing edges).
  • threshold (float,optional) – The algorithm terminates when the PageRank of each node has converged up to this threshold. This must be a postive number.
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def page_rank(g,reset_prob,threshold=0.001):
    if not (reset_prob >= 0  and reset_prob <=1):
        raise ValueError('We require 0 <= reset_prob <= 1')
        
    if not threshold > 0:
        raise ValueError('We require 0 < threshold')
        
    #Initialize the nodes and edges:
    out_degree(g) # make sure each node knows it's out_degree
    
    #Each node starts the algorithm with a PageRank of 1.
    def init_node(node):
        node['page_rank'] = 1.
        node['halt'] = False
    g.update_nodes(init_node)
    
    #Each edge remember the proportion of the traffic if carries out of it's source:
    def init_edge(src,dst,e):
        e['traffic_prop'] = 1./src['out_degree']
    g.update_edges(init_edge)
    
    #The emitter sends the relevant proportion of the 
    #source node's page_rank along each edge:
    def emitter(src,dst,e):
        return [],[src['page_rank']*e['traffic_prop']]
        
    

    #Dangling nodes (nodes with out_degree==0) cannot transmit it's current page_rank
    #along any outgoing edges, so we need to collect their current page_ranks centrally
    #and redistibute them equally amongst all nodes.
    num_nodes = sum(1 for node in g.nodes())
    
    node_pred = lambda node : node['out_degree']==0
    dangling_nodes = g.new_subgraph(node_pred=node_pred).nodes()
    
    def page_rank_collector(node,incoming_ranks,avg_dangle_rank):
        old_rank = node['page_rank']
        node['page_rank'] = (1-reset_prob)*(sum(incoming_ranks)+avg_dangle_rank)+reset_prob  
        if abs(old_rank - node['page_rank']) < threshold:
            node['halt']=True
        else:
            node['halt']=False
    
    while sum( 1 for node in g.nodes() if not node['halt']) > 0:
        avg_dangle_rank = sum(node['page_rank'] for node in dangling_nodes)/num_nodes
        collector = lambda node,msgs: page_rank_collector(node,msgs,avg_dangle_rank)
        g.send_collect(emitter,collector)

Connected Components

graph.algorithms.connected_comp(g)

Computes the connected components of the graph.

Each node node, in the graph should be a graph.GraphLabel. Each connected component receives a distinct label, and the labels are stored in node['cc'].

Parameters:g (graph.Graph) – Each node in the graph should be a graph.algorithms.GraphLabel, or else behave like a dict. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def connected_comp(g):
    # We initialize each node by setting node['cc'] to it's own id.
    def init_node(node):
        node['cc'] = node.name+" id:"+str(id(node))
        node['halt'] = True
    g.update_nodes(init_node) #Initialize vertices 
    
    # Each edge sends messages to both nodes informing them of the value of each other's node['cc']
    def emitter(src,dst,e):
        return [dst['cc']],[src['cc']]

    # The node sets node['cc'] to the smallest value received from it's neighbors.
    def collector(node,msg_iter):
        node['halt'] = True
        for near_cc in msg_iter:
            if near_cc < node['cc']:
                node['cc'] = near_cc
                node['halt'] = False
    
    g.send_collect(emitter,collector)
    while sum( 1 for node in g.nodes() if not node['halt'])>0:
        g.send_collect(emitter,collector)

Convenience Classes for Algorithms

class graph.algorithms.GraphLabel(name, **attrs)

A dict-like convenience wrapper object for graph nodes and edge labels. Graph algorithms are able to store their results as attributes on the labels. Attributes can be accessed and set as with a dict.

Operations Description
n[key] = val set the value of n[key] to val.
n[key] Return the item of n with key key.
Parameters:
  • name (string) – The label name
  • attrs – Arbitrary attributes stored by the graph label.
static edge_wrapper(src, dst, edge_obj)

Wrap an edge in a GraphLabel. Useful as the edge_map for Graph.new_projection.

Parameters:
  • src – The source node of the edge (this is ignored).
  • dst – The destination node of the edge (this is ignored).
  • edge_obj – The edge_obj to be wrapped.
Returns:

A GraphLabel object with name=str(edge_obj) and edge_obj stored as the attribute data.
Return type:

GraphLabel
name

The name of the graph label

static node_wrapper(node)

Wrap a node in a GraphLabel. Useful as the node_map for Graph.new_projection.

Parameters:node – The node to be wrapped.
Returns:A GraphLabel object with name=str(node) and node stored as the attribute data.
Return type:GraphLabel