What are the conditions for a graph's adjacency matrix to not have a negative eigenvalue with magnitude>=1? Say I have a (directed) graph $G$ with an adjacency matrix $A$.  For the sake of the question, let's assume it's normalized column-wise (edge weights are normalized so the sum of out-edge weights per node is equal to 1).
I'd like to calculate the eigenvalue centrality of its nodes using the power method, but I know that it might not converge in some cases (which, if I understand correctly, occurs if and only if it has an eigenvalue of -1).
My question is: Generally, what are the conditions on the graph to avoid this case?
Specifically, if I use page-rank centrality (with damping factor < 1), can I be certain to avoid this case (For every choice of personalization vector?)
[Edited: It appears I can be even more specific: If there is an edge with non-zero weight from each node to each node, can I be sure not have an eigenvalue of -1?]
 A: Here's what I've got so far:
In a bi-partite graph, every eigenvalue $\lambda$ has a corresponding eigenvalue $-\lambda$ (see for example this answer in math.stackexchange, though it doesn't say if only a bi-partite graph has this attribute). 
So, for an adjacency matrix whose columns sum to $1$ (which has an eigenvalue of $1$, which corresponds to the eigenvector we're looking for in eigenvalue centrality), if the graph in discussion is bipartite, the adjacency matrix will have an eigenvalue of $-1$.
If the adjacency matrix has been modified to reflect a 'personalization vector' as in pagerank centrality, i.e. every column has been multiplied by the damping factor $d$ and added $1-d$ times the personalization vector, then as long as there's no zero elements in the personalization vector, we can be guaranteed the the modified graph is not bi-partite, and (if I followed correctly) - will not have a $-1$ eigenvalue.
So, if we can impose that there are no non-zero elements in the personalization vector, it is a sufficient condition so that the power method will converge when calculating the eigenvalue centrality.
