Keywords: line graph, irregularity, centrality, efficiency.

In this paper we give the relations between the centrality and the efficiency of a network and the respective measures on its associated line graph [1]. We do this with the help of the associated bipartite graph. Our motivation stems from the importance that edges sometimes have over nodes in the context of networks. A typical example of this comes from urbanism [2].

There are many different parameters that measure different properties related to the network performance, but in this paper we will only consider the Bonacich's centrality and the efficiency of a network.

The Bonacich centrality of a complex network is the non-negative normalized eigenvector associated to the spectral radius of the transposed adjacency matrix of the graph modelling the network [3,4], while the efficiency is a parameter measuring how easy (on average) it is to reach a node in the network starting from another one [5,6].

In [7] the Bonacich centrality of the line graph is recoverd from the corresponding one on the initial network, and reciprocally. If, in addition, the primal network is regular (all vertices have the same degree) then each of the three centralities can be recovered from any of the other. Also the efficiencies of the line graph and the primal graph are estimated by means of inequalities.

Based on a continuity argument, in [7], the authors consider the discrepancy between the Bonacich centrality of a given network and the network whose adyacency matrix is obtained by perturbing the matrix of the primal network with its vertice-degree diagonal matrix (that matrix reflects the irregularity of the primal network); in fact they conjecture that this discrepancy narrows as the regularity of the primal graph increases. Now the authors analytically support this conjecture by using a measure of irregularity on a network, the Collatz-Sinogowitz index [8].

1

C.J.L. Gross, J. Yellen, (Editors), "Handbook of graph theory", CRC Press, New Jersey, 2004.

2

P. Crucitti, V. Latora, S. Porta, "Centrality in networks of urban streets", Chaos, 16, 015113, 2006. doi:10.1063/1.2150162

3

P. Bonacich, "Factoring and weighing approaches to status scores and clique information", J. Math. Soc., 2, 113-117, 1972.

4

P. Bonacich, P. Lloyd, "Eigenvectors-like measures of centrality for asymetric relations", Soc.Netw., 23, 191-215, 2001. doi:10.1016/S0378-8733(01)00038-7

5

V. Latora, M. Marchiori, "Efficient Behavior of Small-World Networks", Phys.Rev.Lett., 87, 198701, 2001. doi:10.1103/PhysRevLett.87.198701

6

V. Latora, M. Marchiori, "A measure of centrality based on the network efficiency", New J.Phys., 9, 188, 2007. doi:10.1088/1367-2630/9/6/188

7

R. Criado, J. Flores, A. Garcia del Amo, M. Romance, "Analytical relationships between metric and centrality measures of a network and its dual", J. Comp. Appl. Math., to appear. doi:10.1016/j.cam.2010.04.011

8

L. Collatz, U. Sinogowitz, "Spektren endlicher Grafen", Abh. Math. Sem. University Hamburg, 21, 63-77, 1957. doi:10.1007/BF02941924

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £125 +P&P)