Edge Centrality via the Holevo Quantity
In the study of complex networks, vertex centrality measures are used to identify the most important vertices within a graph. A related problem is that of measuring the centrality of an edge. In this paper, we propose a novel edge centrality index rooted
- PDF / 534,391 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 155 Views
3
Department of Computer Science, University College London, London, UK 2 DAIS, Universit` a Ca’ Foscari Venezia, Venice, Italy School of Engineering and Applied Science, Aston University, Birmingham, UK [email protected]
Abstract. In the study of complex networks, vertex centrality measures are used to identify the most important vertices within a graph. A related problem is that of measuring the centrality of an edge. In this paper, we propose a novel edge centrality index rooted in quantum information. More specifically, we measure the importance of an edge in terms of the contribution that it gives to the Von Neumann entropy of the graph. We show that this can be computed in terms of the Holevo quantity, a well known quantum information theoretical measure. While computing the Von Neumann entropy and hence the Holevo quantity requires computing the spectrum of the graph Laplacian, we show how to obtain a simplified measure through a quadratic approximation of the Shannon entropy. This in turns shows that the proposed centrality measure is strongly correlated with the negative degree centrality on the line graph. We evaluate our centrality measure through an extensive set of experiments on real-world as well as synthetic networks, and we compare it against commonly used alternative measures.
Keywords: Edge centrality Quantum information
1
·
Complex networks
·
Holevo quantity
·
Introduction
The study of complex networks has recently attracted increasing interest in the scientific community, as it allows to model and understand a large number of real-world systems [4]. This is particularly relevant given the growing amount of available data describing the interactions and dynamics of real-world systems. Typical examples of complex networks include metabolic networks [8], protein interactions [7], brain networks [17] and scientific collaboration networks [11]. One of the key problems in network science is that of identifying the most relevant nodes in a network. This importance measure is usually called the centrality of a vertex [9]. A number of centrality indices have been introduced in the literature [2,4–6,10,14], each of them capturing different but equally significant aspects of vertex importance. Commonly encountered examples are the degree, closeness and betweenness centrality [5,6,10]. A closely related problem c Springer International Publishing AG 2016 A. Robles-Kelly et al. (Eds.): S+SSPR 2016, LNCS 10029, pp. 143–152, 2016. DOI: 10.1007/978-3-319-49055-7 13
144
J. Lockhart et al.
is that of measuring the centrality of an edge [3,9]. Most edge centrality indices are developed as a variant of vertex centrality ones. A common way to define an edge centrality index is to apply the corresponding vertex centrality to the line graph of the network being studied. Recall that, given a graph G = (V, E), the line graph L(G) = (V , E ) is a dual representation of G where each node uv ∈ V corresponds to an edge (u, v) ∈ E, and there exists and edge between two nodes of L(G) if and only if the corr
Data Loading...
