3
$\begingroup$

I'm implementing some calculations on networks, and one of the properties I'm using is the Subgraph Centrality (developed on this paper). The equation I'm using is the equation (4) on the paper.

I wrote the following code for the equation:

eigenvalues = Chop[Eigenvalues[N[Normal[AdjacencyMatrix[graph]]]]];
eigenvectors= Eigenvectors[N[Normal[AdjacencyMatrix[graph]]]];
subCentrality=Table[N[Sum[(Power[eigenvectors[[i,j]],2])*Exp[eigenvalues[[i]]], {i,VertexCount[graph]}]],{j,Length[eigenvectors]}];

Where 'graph' is any graph. The data I'm using is on this link, which corresponds to the 'AdjacencyMatrix' of my network. Using this formula, it took me about 9h to complete the calculation. That could be a suitable time if I had to calculate it only once, but I'm trying to implement it in some algorithms, where I'll have to calculate this about 2000-3000 times. Is there a way of optimizing this code?

$\endgroup$
  • $\begingroup$ You might use EigenSystem to get both the values and vectors at once -- with luck this might cut the time in half. $\endgroup$ – bill s Nov 23 '17 at 15:59
6
$\begingroup$

This should save you several hours...

{λ, U} = Eigensystem[N[Normal[AdjacencyMatrix[graph]]]];
subCentrality2 = Exp[λ].(U^2);

Note that the exponential might be problematic as it easily kicks you out of the machine numbers. (When that happens, the matrix-vector product slows down considerably.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.