Observatorio de I+D+i UPM

Memorias de investigación
Ponencias en congresos:
Two-walks degree assortativity in graphs and networks
Año:2017
Áreas de investigación
  • Física química y matemáticas
Datos
Descripción
Networks represent the topological skeleton of complex systems that are formed by many interactingelements. The understanding of these structures and their patterns of connections is crucial for comprehending the evolutionary, functional, and dynamical processes taking place in these systems. It is well known that, generally, links do not connect nodes regardless of their characteristics. Assortativity is a global metric of a graph that characterizes the nodes?s tendency to link to other nodes of similar (or different) type. Usually, this concept is applied to the degree of a node (i.e. the number of its adjacent nodes). Thus, 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 commonly quantified by the Pearson correlation coefficient of the degree-degree correlation. In this work we propose an extension of the concept of degree assortativity to one that account for the correlation between the degrees of the nodes and their nearest neighbours in graphs and networks. For this purpose, 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 - two-walks degree correlation. We found an analytical expression for this new assortative index as a function of contributing subgraphs, and we also proved that there are a few more fragments contributing to the two-walks degree assortativity than to the degree assortativity. This clearly indicates that the new quantity accounts for more structural information than the previous one. 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.
Internacional
Si
Nombre congreso
1st Latin American Conference on Complex Networks (LANET2017) [www.lanetconference.org/lanet2017/index.html]
Tipo de participación
970
Lugar del congreso
Puebla (México)
Revisores
Si
ISBN o ISSN
CDP08UPM
DOI
Fecha inicio congreso
25/09/2017
Fecha fin congreso
29/09/2017
Desde la página
68
Hasta la página
68
Título de las actas
LANET 2017 - 1st Latin American Conference on Complex Networks - Applications to social, biological, and technological systems [www.lanetconference.org/lanet2017/book_abstracts.pdf]
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Alfonso Allen-Perkins (Universidad Politécnica de Madrid)
  • Autor: Juan Manuel Pastor Ruiz (UPM)
  • Autor: Ernesto Estrada (University of Strathclyde, United Kingdom)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Sistemas Complejos
  • Departamento: Ingeniería Agroforestal
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)