Python Recipes

1 Assortativity coefficient in Python

The code snippet below calculates the assortativity coefficient of a graph in a not too efficient but still usable way. Note that Python automatically converts integers to arbitrary precision long integers if necessary, so theoretically there's no need to worry about overflows.

def assortativity(graph, degrees=None):
    if degrees is None: degrees = graph.degree()
    degrees_sq = [deg**2 for deg in degrees]
 
    m = float(graph.ecount())
    num1, num2, den1 = 0, 0, 0
    for source, target in graph.get_edgelist():
        num1 += degrees[source] * degrees[target]
        num2 += degrees[source] + degrees[target]
        den1 += degrees_sq[source] + degrees_sq[target]
 
    num1 /= m
    den1 /= 2*m
    num2 = (num2 / (2*m)) ** 2
 
    return (num1 - num2) / (den1 - num2)

2 Generating Cayley trees

A Cayley tree of order k is a tree where every non-leaf vertex has degree k. There is no function in igraph to generate Cayley trees directly, but it can be implemented in a few lines of code:

def cayley_tree(order, depth):
    if depth == 0:
        return Graph(1)
    if depth == 1:
        return Graph.Tree(order+1, order)
    d = order - 1
    n1, n2 = d ** (depth+1) - 1, d ** depth - 1
    n1 /= d-1
    n2 /= d-1
    return Graph.Tree(n1, d) + Graph.Tree(n2, d) + (0, n1)

3 Betweenness centralization

Bernie Hogan sent this code snippet to the mailing list to calculate the betweenness centralization measure of a graph (a few modifications by Tamas Nepusz):

def betweenness_centralization(G):
    vnum = G.vcount()
    if vnum < 3:
        raise ValueError("graph must have at least three vertices")
    denom = (vnum-1)*(vnum-2)
 
    temparr = [2*i/denom for i in G.betweenness()]
    max_temparr = max(temparr)
    return sum(max_temparr-i for i in temparr)/(vnum-1)

4 Extracting the 'rich club' of a graph

The 'rich club' of a graph is the subgraph spanned by vertices of the highest degrees (say, the top 10%). The function below does something similar (although a bit more generic):

def richclub(graph, fraction=0.1, highest=True, scores=None, indices_only=False):
    """Extracts the "rich club" of the given graph, i.e. the subgraph spanned
    between vertices having the top X% of some score.
 
    Scores are given by the vertex degrees by default.
 
    @param graph:    the graph to work on
    @param fraction: the fraction of vertices to extract; must be between 0 and 1.
    @param highest:  whether to extract the subgraph spanned by the highest or
                     lowest scores.
    @param scores:   the scores themselves. C{None} uses the vertex degrees.
    @param indices_only: whether to return the vertex indices only (and not the
                         subgraph)
    """
 
    if scores is None:
        scores = graph.degree()
 
    indices = range(graph.vcount())
    indices.sort(key=scores.__getitem__)
 
    n = int(round(graph.vcount() * fraction))
    if highest:
        indices = indices[-n:]
    else:
        indices = indices[:n]
 
    if indices_only:
        return indices
 
    return graph.subgraph(indices)

5 Calculating Laplacian centrality

Laplacian centrality is a simple centrality measure that can be calculated in linear time. It is defined as the drop in the Laplacian energy (i.e. sum of squares of the eigenvalues in the Laplacian matrix) of the graph when the vertex is removed. See the following publication for more details:

http://www.scirp.org/journal/PaperInformation.aspx?PaperID=27402

The function below implements Laplacian centrality in Python:

def laplacian_centrality(graph, vs=None):
    if vs is None:
        vs = xrange(graph.vcount())
    degrees = graph.degree(mode="all")
    result = []
    for v in vs:
        neis = graph.neighbors(v, mode="all")
        result.append(degrees[v]**2 + degrees[v] + 2 * sum(degrees[i] for i in neis))
    return result

6 Converting SciPy sparse matrices into graphs

The function below converts a SciPy sparse matrix into an igraph graph directly (without constructing a dense matrix first):

from igraph import Graph
 
def scipy_to_igraph(matrix, directed=True):
    sources, targets = matrix.nonzero()
    weights = matrix[sources, targets]
    return Graph(zip(sources, targets), directed=directed, edge_attrs={'weight': weights})

Thanks to Alacast on the igraph mailing list.

7 Random walk generator

The function below returns a generator that can be used to generate random walks from a given or a randomly selected starting point:

from random import randint, choice
 
def random_walk_iter(g, start=None): 
    current = randint(0, g.vcount()-1) if start is None else start 
    while True: 
        yield current
        current = choice(g.successors(current))

Usage examples:

from itertools import islice, takewhile
 
g = Graph.GRG(100, 0.2)
 
desired_length = 20
walk = list(islice(random_walk_iter(g, start=5), desired_length))
 
finish = 15
walk = list(takewhile(random_walk_iter(lambda x: x != finish, start=5))) + [finish]

Note that you can also use the close() method of the returned generator to stop the random walk. E.g., the above code will stop the random walk at any time step with probability 0.1:

from random import random
 
vs = []
walker = random_walk_iter(g)
for node in walker:
    vs.append(node)
    if random() < 0.1:
        walker.close()