Skip to main content
SpringerLink
Log in

Measuring Vertex Centrality Using the Holevo Quantity

  • Conference paper
  • First Online:
Graph-Based Representations in Pattern Recognition (GbRPR 2017)

Part of the book series: Lecture Notes in Computer Science ((LNIP,volume 10310))

Abstract

In recent years, the increasing availability of data describing the dynamics of real-world systems led to a surge of interest in the complex networks of interactions that emerge from such systems. Several measures have been introduced to analyse these networks, and among them one of the most fundamental ones is vertex centrality, which quantifies the importance of a vertex within a graph. In this paper, we propose a novel vertex centrality measure based on the quantum information theoretical concept of Holevo quantity. More specifically, we measure the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph. More specifically, we find that the centrality of a vertex v can be broken down in two parts: (1) one which is negatively correlated with the degree centrality of v, and (2) one which depends on the emergence of non-trivial structures in the graph when v is disconnected from the rest of the graph. Finally, we evaluate our centrality measure on a number of real-world as well as synthetic networks, and we compare it against a set of commonly used alternative measures.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

References

  1. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. de Beaudrap, N., Giovannetti, V., Severini, S., Wilson, R.: Interpreting the von Neumann entropy of graph Laplacians, and coentropic graphs. Panorama Math. Pure Appl. 658, 227 (2016)

    MathSciNet  MATH  Google Scholar 

  3. Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92, 1170–1182 (1987)

    Article  Google Scholar 

  4. Erdös, P., Rényi, A.: On random graphs. Publ. Math. Debrecen 6, 290–297 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  5. Estrada, E.: The Structure of Complex Networks. Oxford University Press, New York (2011)

    Google Scholar 

  6. Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)

    Article  Google Scholar 

  7. Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215–239 (1979)

    Article  MathSciNet  Google Scholar 

  8. Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., Sakaki, Y.: A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Nat. Acad. Sci. 98(8), 4569 (2001)

    Article  Google Scholar 

  9. Jeong, H., Tombor, B., Albert, R., Oltvai, Z., Barabási, A.: The large-scale organization of metabolic networks. Nature 407(6804), 651–654 (2000)

    Article  Google Scholar 

  10. Li, J.Q., Chen, X.B., Yang, Y.X.: Quantum state representation based on combinatorial Laplacian matrix of star-relevant graph. Quantum Inf. Process. 14(12), 4691–4713 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Lockhart, J., Minello, G., Rossi, L., Severini, S., Torsello, A.: Edge centrality via the Holevo quantity. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016. LNCS, vol. 10029, pp. 143–152. Springer, Cham (2016). doi:10.1007/978-3-319-49055-7_13

    Chapter  Google Scholar 

  12. Newman, M.E.: A measure of betweenness centrality based on random walks. Social Netw. 27(1), 39–54 (2005)

    Article  Google Scholar 

  13. Newman, M.: Scientific collaboration networks. i. network construction and fundamental results. Phys. Rev. E 64(1), 016131 (2001)

    Google Scholar 

  14. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2010)

    Google Scholar 

  15. Padgett, J.F., Ansell, C.K.: Robust action and the rise of the medici, 1400–1434. Am. J. Sociol. 98(6), 1259–1319 (1993)

    Article  Google Scholar 

  16. Passerini, F., Severini, S.: Quantifying complexity in networks: the von Neumann entropy. Int. J. Agent Technol. Syst. (IJATS) 1(4), 58–67 (2009)

    Article  Google Scholar 

  17. Rossi, L., Torsello, A., Hancock, E.R.: Node centrality for continuous-time quantum walks. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014. LNCS, vol. 8621, pp. 103–112. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44415-3_11

    Chapter  Google Scholar 

  18. Rossi, L., Torsello, A., Hancock, E.R.: Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence. Phys. Rev. E 91(2), 022815 (2015)

    Article  MathSciNet  Google Scholar 

  19. Rossi, L., Torsello, A., Hancock, E.R., Wilson, R.C.: Characterizing graph symmetries through quantum Jensen-Shannon divergence. Phys. Rev. E 88(3), 032806 (2013)

    Article  Google Scholar 

  20. Sporns, O.: Network analysis, complexity, and brain function. Complexity 8(1), 56–60 (2002)

    Article  MathSciNet  Google Scholar 

  21. Stanley, W., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University, Cambridge (1994)

    MATH  Google Scholar 

  22. Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1977)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Engineering and Applied Science, Aston University, Birmingham, UK

    Luca Rossi

  2. DAIS, Università Ca’ Foscari Venezia, Venice, Italy

    Andrea Torsello

Authors
  1. Luca Rossi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrea Torsello
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luca Rossi .

Editor information

Editors and Affiliations

  1. Università degli Studi di Salerno, Fisciano, Italy

    Pasquale Foggia

  2. Chinese Academy of Sciences, Beijing, China

    Cheng-Lin Liu

  3. Università degli Studi di Salerno, Fisciano, Italy

    Mario Vento

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Rossi, L., Torsello, A. (2017). Measuring Vertex Centrality Using the Holevo Quantity. In: Foggia, P., Liu, CL., Vento, M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2017. Lecture Notes in Computer Science(), vol 10310. Springer, Cham. https://doi.org/10.1007/978-3-319-58961-9_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-58961-9_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-58960-2

  • Online ISBN: 978-3-319-58961-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation