Two-walks degree assortativity in graphs and networks

摘要

Degree assortativity is the tendency for nodes of high degree (resp. low degree) in a graph to be connected to high degree nodes (resp. to low degree ones). It is usually quantified by the Pearson correlation coefficient of the degree–degree correlation. Here we extend this concept to account for the effect of second neighbours to a given node in a graph. That is, we consider the two-walks degree of a node as the sum of all the degrees of its adjacent nodes. The two-walks degree assortativity of a graph is then the Pearson correlation coefficient of the two-walks degree–degree correlation. We found here analytical expression for this two-walks degree assortativity index as a function of contributing subgraphs. We then study all the 261,000 connected graphs with 9 nodes and observe the existence of assortative–assortative and disassortative–disassortative graphs according to degree and two-walks degree, respectively. More surprisingly, we observe a class of graphs which are degree disassortative and two-walks degree assortative. We explain the existence of some of these graphs due to the presence of certain topological features, such as a node of low-degree connected to high-degree ones. More importantly, we study a series of 49 real-world networks, where we observe the existence of the disassortative–assortative class in several of them. In particular, all biological networks studied here were in this class. We also conclude that no graphs/networks are possible with assortative–disassortative structure.