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.

Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.