Abstract
In this paper, we aim to develop novel methods for measuring the structural complexity for 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 a number of alternative techniques that are applicable to directed graphs. We commence by using Chung’s generalisation 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 vertex 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. Next we explore how to extend Estrada’s heterogeneity index from undirected to directed graphs. Our measure is motivated by the simplified von Neumann entropy, and involves measuring the heterogeneity of differences in in-degrees and out-degrees. Finally, we perform an analysis which reveals a novel linear relationship between heterogeneity and resistance distance (commute time) statistics for undirected graphs. This means that the larger the difference between the average commute time and shortest return path length between pairs of vertices, the greater the heterogeneity index. Based on this observation together with the definition of commute time on a directed graph, we define an analogous heterogeneity measure for directed graphs. We illustrate the usefulness of the measures defined in this paper for datasets describing Erdos-Renyi, ’small-world’, ’scale-free’ graphs, Protein-Protein Interaction (PPI) networks and evolving networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Amancio, D.R., Oliveira Jr., O.N., Costa, L.da F.: On the Concepts of Complex Networks to Quantify the Difficulty in Finding the Way Out of Labyrinths. Physica A 390, 4673–4683 (2011)
Antiqueira, L., Rodrigues, F.A., Costa, L.da F.: Modeling Connectivity in Terms of Network Activity. Journal of Statistical Mechanics: Theory and Experiment 0905.4706 (2009)
Barabasi, A.L., Albert, R.: Emergence of Scaling in Random Networks. Science 286, 509–512 (1999)
Berwanger, D., Gradel, E., Kaiser, L., Rabinovich, R.: Entanglement and the Complexity of Directed Graphs. Theoretical Computer Science 463, 2–25 (2012)
Boley, D., Ranjan, G., Zhang, Z.: Commute Times for a Directed Graph Using an Asymmetric Laplacian. Linear Algebra and Its Applications 435, 224–242 (2011)
Chung, F.: Laplacians and the Cheeger Inequailty for Directed Graphs. Annals of Combinatorics 9, 1–19 (2005)
Costa, L.da F., Rodrigues, F.A.: Seeking for Simplicity in Complex Networks. Europhysics Letters 85, 48001 (2009)
Escolano, F., Hancock, E.R., Lozano, M.A.: Heat Diffusion: Thermodynamic Depth Complexity of Networks. Physical Review E 85, 036206 (2012)
Escolano, F., Bonev, B., Hancock, E.R.: Heat Flow-Thermodynamic Depth Complexity in Directed Networks. In: Gimel’farb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M., Omachi, S., Windeatt, T., Yamada, K. (eds.) SSPR&SPR 2012. LNCS, vol. 7626, pp. 190–198. Springer, Heidelberg (2012)
Estrada, E.: Quantifying Network Heterogeneity. Physical Review E 82, 066102 (2010)
Franceschini, A., Szklarczyk, D., Frankild, S., Kuhn, M., Simonovic, M., Roth, A., Lin, J., Minguez, P., Bork, P., von Mering, C., Jensen, L.J.: STRING v9.1: protein-protein interaction networks, with increased coverage and integration. Nucleic Acids Res. 41, D808–D815 (2013)
Han, L., Escolano, F., Hancock, E.R., Wilson, R.C.: Graph Characterizations from Von Neumann Entropy. Pattern Recognition Letters 33, 1958–1967 (2012)
Passerini, F., Severini, S.: The Von Neumann Entropy of Networks. International Journal of Agent Technologies and Systems, 58–67 (2008)
Qiu, H., Hancock, E.R.: Clustering and Embedding Using Commute Times. IEEE Transactions on Pattern Analysis and Machine Intelligence 29, 1873–1890 (2007)
Ren, P., Wilson, R.C., Hancock, E.R.: Graph Characterization via Ihara Coefficients. IEEE Transactions on Neural Networks 22, 233–245 (2011)
Riis, S.: Graph Entropy, Network Coding and Guessing Games. The Computing Research Repository 0711.4175 (2007)
von Luxburg, U., Radl, A., Hein, M.: Hitting and Commute Times in Large Graphs are often Misleading. Data Structures and Algorithms 1003.1266 (2010)
Watts, D.J., Strogatz, S.H.: Collective Dynamics of ’Small-World’ Networks. Nature 393, 440–442 (1998)
Xiao, B., Hancock, E.R., Wilson, R.C.: Graph Characteristics from the Heat Kernel Trace. Pattern Recognition 42, 2589–2606 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ye, C., Wilson, R.C., Comin, C.H., da F. Costa, L., Hancock, E.R. (2013). Entropy and Heterogeneity Measures for Directed Graphs. In: Hancock, E., Pelillo, M. (eds) Similarity-Based Pattern Recognition. SIMBAD 2013. Lecture Notes in Computer Science, vol 7953. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39140-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-39140-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39139-2
Online ISBN: 978-3-642-39140-8
eBook Packages: Computer ScienceComputer Science (R0)