Higher order assortativity in complex networks

Abstract

Assortativity was first introduced by Newman and has been extensively studied and applied to many real world networked systems since then. Assortativity is a graph metrics and describes the tendency of high degree nodes to be directly connected to high degree nodes and low degree nodes to low degree nodes. It can be interpreted as a first order measure of the connection between nodes, i.e. the first autocorrelation of the degree-degree vector. Even though assortativity has been used so extensively, to the author's knowledge, no attempt has been made to extend it theoretically. This is the scope of our paper. We will introduce higher order assortativity by extending the Newman index based on a suitable choice of the matrix driving the connections. Higher order assortativity will be defined for paths, shortest paths, random walks of a given time length, connecting any couple of nodes. The Newman assortativity is achieved for each of these measures when the matrix is the adjacency matrix, or, in other words, the correlation is of order 1. Our higher order assortativity indexes can be used for describing a variety of real networks, help discriminating networks having the same Newman index and may reveal new topological network features.

arXiv comment24 pages, 16 figures

References in corpus (10)

• Emergence of scaling in random networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Characterization of complex networks: A survey of measurements
• Quantifying randomness in real networks
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Rich-club connectivity dominates assortativity and transitivity of complex networks
• Revising the simple measures of assortativity in complex networks
• "Clumpiness" Mixing in Complex Networks

Cited by in corpus (8)

• A new measure for community structures through indirect social connections
• A general formulation of long-range degree correlations in complex networks
• Assortativity measures for weighted and directed networks
• Network rewiring in the $r$-$K$ plane
• Analytic solution of the two-star model with correlated degrees
• How visas shape and make visible the geopolitical architecture of the planet
• Identification of intrinsic long-range degree correlations in complex networks
• Higher order assortativity for directed weighted networks and Markov chains