[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] thoughts on mixing matrices?

From: Tamas Nepusz
Subject: Re: [igraph] thoughts on mixing matrices?
Date: Fri, 28 Aug 2009 11:39:52 +0100

Hi Bernie,

I'm interested in calculating a mixing matrix for a graph, and then
using this matrix as a sort of 'reduced graph' for visualization. I
think of how to do it programmatically, but I'm wondering if such a
facility is available natively.

We don't have such a facility natively, but it's not too hard to implement it in Python or R. Here's a quick Python implementation (_untested_, but it should work with minor modifications):

from igraph import *

def mixing_matrix(graph, membership):
    """Calculates the mixing matrix of a graph according to some
    categorisation of the vertices. Values in the membership vector
    must contain integers from zero to K-1 where K is the number of

    # Make sure we support VertexClustering objects directly
    if isinstance(membership, VertexClustering):
        membership = membership.membership

    if len(membership) < graph.vcount():
        raise ValueError, "membership vector too short"

    k = max(membership)
    result = [[0] * k for _ in xrange(k)]
    for edge in graph.es:
        ms, mt = membership[edge.source], membership[edge.target]
        result[ms][mt] += 1

    if not graph.is_directed():
        for edge in graph.es:
            ms, mt = membership[edge.source], membership[edge.target]
            if ms == mt: continue
            result[mt][ms] += 1

    return result

Not the fastest implementation, but I think it shows the general idea. If you want to construct a graph instead of a matrix, you can either pass the matrix to Graph.Adjacency using mode=ADJ_MAX, or make the result variable a defaultdict(int) and then use result[ms, mt] += 1 in the for loop. This way you get a dict associating type pairs to edge counts and you can use that to construct a graph:

g = Graph(result.keys(), edge_attrs = {"weight": result.values()})


reply via email to

[Prev in Thread] Current Thread [Next in Thread]