Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix $A$ changing a single $0$ into a $1$). Where should I put that one to have the highest increase in the biggest eigenvector as possible?

I suppose that the answer is "where you can connect the two largest strongly connected components".

  • $\begingroup$ looking at the undirected graph $A^T A$ or $A^T+A$ instead of $A$ would be easier ? $\endgroup$ – reuns Jan 22 '16 at 18:10

These two papers should be helpful for you.

[1] J. G. Restrepo, E. Ott, and B. R. Hunt, Phys. Rev. Lett. 97, 094102 (2006)

[2] A. Milanese, J. Sun, and T. Nishikawa, Phys. Rev. E 81, 046112, (2010)


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.