- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Approximate von Neumann entropy for directed graphs

Cheng Ye1,*, Richard C. Wilson1,†, César H. Comin2,‡, Luciano da F. Costa2,§, and Edwin R. Hancock1,¶

  • 1Department of Computer Science, University of York, York, YO10 5GH, United Kingdom
  • 2Institute of Physics at São Carlos, University of São Paulo, PO Box 369, São Carlos, São Paulo, 13560-970, Brazil

  • *cy666@york.ac.uk
  • †richard.wilson@york.ac.uk
  • ‡appdnails@gmail.com
  • §ldfcosta@gmail.com
  • edwin.hancock@york.ac.uk
PDF

Phys. Rev. E 89, 052804 – Published 12 May, 2014

DOI: https://doi.org/10.1103/PhysRevE.89.052804

Abstract

In this paper, we develop an entropy measure for assessing the structural complexity of directed graphs. Although there are many existing alternative measures for quantifying the structural properties of undirected graphs, there are relatively few corresponding measures for directed graphs. To fill this gap in the literature, we explore an alternative technique that is applicable to directed graphs. We commence by using Chung's generalization of the Laplacian of a directed graph to extend the computation of von Neumann entropy from undirected to directed graphs. We provide a simplified form of the entropy which can be expressed in terms of simple node in-degree and out-degree statistics. Moreover, we find approximate forms of the von Neumann entropy that apply to both weakly and strongly directed graphs, and that can be used to characterize network structure. We illustrate the usefulness of these simplified entropy forms defined in this paper on both artificial and real-world data sets, including structures from protein databases and high energy physics theory citation networks.

View figure in article

Article Text

References (32)

  1. M. Newman, SIAM Rev. 45, 167 (2003).
  2. R. Albert and A. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  3. C. Castellano, S. Fortunato, and V. Loreto, Rev. Mod. Phys. 81, 591 (2009).
  4. L. d. F. Costa, O. Oliveira, G. Travieso, F. A. Rodrigues, P. R. Villas Boas, L. Antiqueira, M. P. Viana, and L. E. Correa Rocha, Adv. Phys. 60, 329 (2011).
  5. E. Estrada, The Structure of Complex Networks: Theory and Applications (Oxford University Press, Oxford, UK, 2011).
  6. L. d. F. Costa and F. A. Rodrigues, Europhys. Lett. 85, 48001 (2009).
  7. M. Newman, Networks: An Introduction (Oxford University Press, Oxford, UK, 2010).
  8. L. d. F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas, Adv. Phys. 56, 167 (2007).
  9. F. Passerini and S. Severini, Int. J. Agent Technol. Syst. 1, 58 (2009).
  10. F. Chung, Ann. Combin. 9, 1 (2005).
  11. E. Estrada, M. Fox, D. Higham, and G. Oppo (Eds.) Network Science. Complexity in Nature and Technology (Springer, Berlin, 2010), XI, p. 245.
  12. D. Feldman and J. Crutchfield, Phys. Lett. A 238, 244 (1998).
  13. M. Dehmer, A. Mowshowitz, and F. Emmert-Streib, Advances in Network Complexity (Wiley-Blackwell, Boston, 2013).
  14. S. Riis, Comput. Res. Repository. 0711 (2007).
  15. D. Berwanger, E. Gradel, L. Kaiser, and R. Rabinovich, Theor. Comput. Sci. 463, 2 (2012).
  16. F. Escolano, B. Bonev, and E. Hancock, Structural, Syntactic, and Statistical Pattern Recognition (Springer, Berlin, 2012), pp. 190–198.
  17. F. Escolano, E. Hancock, and M. Lozano, Phys. Rev. E 85, 036206 (2012).
  18. K. Anand, G. Bianconi, and S. Severini, Phys. Rev. E 83, 036109 (2011).
  19. S. Braunstein, S. Ghosh, and S. Severini, Ann. Combin. 10, 291 (2006).
  20. N. Biggs, Algebraic Graph Theory. Cambridge Tracts in Mathematics No. 67 (Cambridge University Press, Cambridge, 1974).
  21. L. Han, F. Escolano, E. Hancock, and R. Wilson, Pattern Recog. Lett. 33, 1958 (2012).
  22. S. Ihara, Information Theory for Continuous Systems (World Scientific Pub. Co. Inc., Singapore, 1993), p. 308.
  23. L. Antiqueira, F. Rodrigues, and L. d. F. Costa, J. Stat. Mech.: Theor. Exper. (2009) L09005.
  24. D. Watts and S. Strogatz, Nature (London) 393, 440 (1998).
  25. A. Barabási and R. Albert, Science 286, 509 (1999).
  26. K. Riesen and H. Bunke, in Structural, Syntactic, and Statistical Pattern Recognition (Springer, Berlin, 2008), Vol. 5342, pp. 287–297.
  27. H. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I. Shidyalov, and P. Bourne, Nucleic Acids Res. 28, 235 (2000).
  28. I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg, Nucleic Acids Res. 32, 081 (2004).
  29. J. Gehrke, P. Ginsparg, and J. Kleinberg, SIGKDD Explor. 5, 149 (2003).
  30. J. Leskovec, J. Kleinberg, and C. Faloutsos, in Proceedings ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD) (ACM, New York, 2005), pp. 177–187.
  31. J. Leskovec, D. Huttenlocher, and J. Kleinberg, in Proceedings ACM SIGCHI Conference on Human Factors in Computing Systems (CHI) (ACM, New York, 2010), pp. 1361–1370.
  32. M. Ripeanu, I. Foster, and A. Iamnitchi, IEEE Internet Computing 6, 50 (2002).

Outline

Information

Phys. Rev. E 89, 052804– Published 12 May, 2014
  • Received 8 November 2013
  • Revised 24 February 2014

©2014 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation