Consider a k -regular undirected network (i.e., a network in which every vertex

Question

Consider a k-regular undirected network (i.e., a network in which every vertex has de- gree k).

1- Show that the vector 1 = (1, 1, 1, . . .) is an eigenvector of the adjacency matrix with eigenvalue k.

2- By making use of the fact that eigenvectors are orthogonal (or otherwise), show that there is no other eigenvector that has all elements positive. The Perron–Frobenius theorem says that the eigenvector with all elements positive has the largest eigen- value, and hence the eigenvector 1 gives, by definition, the eigenvector centrality of our k-regular network and the centralities are the same for every vertex.

3- Find the Katz centralities of all vertices in a k-regular network.

4- You should have found that , as with eigenvector centrality, the Katz centralities of all vertices in the network are the same. Name a centrality measure that could give different centralities for different vertices in a regular network.

Explanation / Answer

Let GG be a graph and let AA be its adjacency matrix. Let 11 denote the vector (1,…,1)(1,…,1) and let IIdenote the identity matrix. Then the Katz centrality of GG is given by the vector

v=(IA)11,(1)(1)v=(IA)11,

where >0>0 is a free parameter.

My question concerns the value of . It is clear that cannot take any value 11, where is an eigenvalue of AA: if took such a value, the right-hand side of (1)(1) would not exist.

So, letting 11 denote the largest eigenvalue of AA, Newman writes that in order to determine the Katz centrality of a graph, one should let be less than 1/11/1. In a footnote (p. 317, footnote 6), he writes, "Formally one uncovers finite values again when one moves past 1/11/1 to higher , but in practice these values are meaningless. The method returns good results only for <1/1<1/1."

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.