Approximate von Neumann entropy for directed graphs

Cheng Ye, Richard C. Wilson, César H. Comin, Luciano da F. Costa, and Edwin R. Hancock
Phys. Rev. E 89, 052804 – Published 12 May 2014

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
2 More
  • Received 8 November 2013
  • Revised 24 February 2014

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

©2014 American Physical Society

Authors & Affiliations

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

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 89, Iss. 5 — May 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×