Two-walks degree assortativity in graphs and networks

DOI10.1016/J.AMC.2017.05.025zbMATH Open1426.05156arXiv1704.03943OpenAlexW2607465787MaRDI QIDQ1739993FDOQ1739993

Authors: Alfonso Allen-Perkins, Juan Manuel Pastor, Ernesto Estrada 

Publication date: 29 April 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: Degree ssortativity 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 sually 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 surprinsingly, 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.

Full work available at URL: https://arxiv.org/abs/1704.03943

Recommendations

• Higher order assortativity in complex networks
• Assortativity in complex networks
• Degree distribution and assortativity in line graphs of complex networks
• Assortativity measures for weighted and directed networks
• Influence of assortativity and degree-preserving rewiring on the spectra of networks

zbMATH Keywords

graphswalksassortativityreal-world networks

Mathematics Subject Classification ID

Measures of association (correlation, canonical correlation, etc.) (62H20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Stochastic network models in operations research (90B15)

Cites Work

• Statistical mechanics of complex networks
• Complex networks: structure and dynamics
• The Structure and Function of Complex Networks
• Assortativity in complex networks
• A new status index derived from sociometric analysis
• Collective dynamics of `small-world' networks
• Exploring complex networks
• Title not available (Why is that?)
• Finding and counting given length cycles
• Dynamical Processes on Complex Networks
• EFFECTS OF DEGREE CORRELATION ON THE SYNCHRONIZATION OF NETWORKS OF OSCILLATORS

Cited In (8)

• Multi-hop assortativities for network classification
• Higher order assortativity in complex networks
• Degree-degree correlation in networks with preferential attachment based growth
• Spatial associations in global household bicycle ownership
• Degree correlations in signed social networks
• Influence of assortativity and degree-preserving rewiring on the spectra of networks
• Assortativity in complex networks
• Degree distribution and assortativity in line graphs of complex networks

Uses Software

• Pajek
• Pajek datasets

This page was built for publication: Two-walks degree assortativity in graphs and networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1739993)