By the way, Jacob is looking for a data scientist position in the area between San Jose and Palo Alto. So if you are looking for PhD in math, with a lot of applied knowledge, I truly recommend Jacob!
(And tell him I sent you.. :-) Anyway he is his description of the method:
I'm posting to the list to announce that I've implemented Total
Subgraph Communicability, a new centrality measure due to
Benzi&Klymco[0]. For a directed graph with adjacenty matrix A,
TSC_i = sum_j exp(A)_{ij} = (exp(A)*1)_i.
This code calculates the TSC using an Arnoldi iteration on the Krylov
subspace {b, Ab,A*Ab, A*A*Ab, ...} due to Saad[1], and using the new
warp engine from Graphlab 2.2 (without which this would have been, at
best, very challenging).
I don't have access to a cluster right now, so I can't test that it performs
properly in the distributed environment, but it works fine on a single
macbook air (and can compute TSC for a graph with 130K nodes and 1.4M
edges in less than a minute under load).
Small components of large graphs will have bogus answers due to
floating point issues. To find the exact TSC for a particular node i,
run with "--column i" to find exp(A)*e_i; you will have to sum the
resulting output yourself, however.
SAMPLE INPUT:
0 1
1 2
1 3
2 4
3 4
1 0
2 1
3 1
4 2
4 3
OUTPUT:
0 5.17784
1 10.3319
2 8.49789
3 8.49789
4 7.96807
You can verify this in python as:
import scipy
import scipy.linalg
A = scipy.array([[0,1,0,0,0],[1,0, 1,1,0],[0,1,0,0,1],[0,1,0,0,1] ,[0,0,1,1,0]])
scipy.linalg.expm2(A).sum( axis=1)
The code is here: https://github.com/kesinger/ graphlab
And I've written more about it here: http://jacobkesinger.tumblr. com/post/64338572799/total- subgraph-centrality
[0]: Benzi, Michele, and Christine Klymko. Total Communicability as a Centrality Measure. ArXiv e-print, February 27, 2013.http://arxiv.org/abs/1302.6770 .
[1]: Saad, Yousef. “Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator.” SIAM Journal on Numerical Analysis 29, no. 1 (1992): 209–228.
No comments:
Post a Comment