Abstract
Assortativity or assortative mixing is the tendency of a network’s vertices to connect to others with similar characteristics, and has been shown to play a vital role in the structural properties of complex networks. Most of the existing assortativity measures have been developed on the basis of vertex degree information. However, there is a significant amount of additional information residing in the edges in a network, such as the edge directionality and weights. Moreover, the von Neumann entropy has proved to be an efficient entropic complexity level characterization of the structural and functional properties of both undirected and directed networks. Hence, in this paper we aim to combine these two methods and propose a novel edge assortativity measure which quantifies the entropic preference of edges to form connections between similar vertices in undirected and directed graphs. We apply our novel assortativity characterization to both artificial random graphs and real-world networks. The experimental results demonstrate that our measure is effective in characterizing the structural complexity of networks and classifying networks that belong to different complexity classes.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Chung, F.: Laplacians and the cheeger inequailty for directed graphs. Annals of Combinatorics 9, 1–19 (2005)
Cuzzocrea, A., Papadimitriou, A., Katsaros, D., Manolopoulos, Y.: Edge betweenness centrality: A novel algorithm for qos-based topology control over wireless sensor networks. Journal of Network and Computer Applications 35(4), 1210–1217 (2012)
Foster, J.G., Foster, D.V., Grassberger, P., Paczuski, M.: Edge direction and the structure of networks. Proceedings of the National Academy of Sciences of the United States of America 107(24), 10815–10820 (2010)
Han, L., Escolano, F., Hancock, E.R., Wilson, R.C.: Graph characterizations from von neumann entropy. Pattern Recognition Letters 33, 1958–1967 (2012)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: CHI (2010)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: Densification laws, shrinking diameters and possible explanations. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2005)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD) 1 (2007)
Newman, M.: Assortative mixing in networks. Phys. Rev. Lett. 89(208701) (2002)
Passerini, F., Severini, S.: The von neumann entropy of networks. International Journal of Agent Technologies and Systems, 58–67 (2008)
Ripeanu, M., Foster, I., Iamnitchi, A.: Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Computing Journal (2002)
Ye, C., Wilson, R.C., Comin, C.H., da F. Costa, L., Hancock, E.R.: Entropy and heterogeneity measures for directed graphs. In: Hancock, E., Pelillo, M. (eds.) SIMBAD 2013. LNCS, vol. 7953, pp. 219–234. Springer, Heidelberg (2013)
Ye, C., Wilson, R.C., Hancock, E.R.: Entropic graph embedding via multivariate degree distributions. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014. LNCS, vol. 8621, pp. 163–172. Springer, Heidelberg (2014)
Ye, C., Wilson, R.C., Hancock, E.R.: Graph characterization from entropy component analysis. In: 22nd International Conference on Pattern Recognition, ICPR 2014, Stockholm, Sweden, August 24-28, pp. 3845–3850 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Ye, C., Wilson, R.C., Hancock, E.R. (2015). An Entropic Edge Assortativity Measure. In: Liu, CL., Luo, B., Kropatsch, W., Cheng, J. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2015. Lecture Notes in Computer Science(), vol 9069. Springer, Cham. https://doi.org/10.1007/978-3-319-18224-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-18224-7_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18223-0
Online ISBN: 978-3-319-18224-7
eBook Packages: Computer ScienceComputer Science (R0)