Two-walks degree assortativity in graphs and networks

Alfonso Allen-Perkins, Juan Manuel Pastor and Ernesto Estrada

Applied Mathematics and Computation, 2017, vol. 311, issue C, 262-271

Abstract: 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.

Keywords: Graphs; Real-world networks; Walks; Assortativity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317303235
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:311:y:2017:i:c:p:262-271

DOI: 10.1016/j.amc.2017.05.025

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().