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 metric 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. Indeed, Newman assortativity is about “being adjacent”, but even though two nodes may not by connected through an edge, they could have possibly a strong level of connectivity through a large number of walks and paths between them. This is the scope of our paper. We introduce, for undirected and unweighted networks, higher order assortativity by extending the Newman index based on a suitable choice of the matrix driving the connections. Higher order assortativity be defined for paths, shortest paths and random walks of a given length. The Newman assortativity is a particular case of each of these measures when the matrix is the adjacency matrix, or, in other words, the autocorrelation is of order 1. Our higher order assortativity indices help discriminating networks having the same Newman index and may reveal new topological network features. An application to airline network (Italy and US) and to Enron email network, as well as examples and simulations, are discussed.

Arcagni, A., Grassi, R., Stefani, S., Torriero, A. (2017). Higher order assortativity in complex networks. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 262(2), 708-719 [10.1016/j.ejor.2017.04.028].

Higher order assortativity in complex networks

ARCAGNI, ALBERTO GIOVANNI
Primo
;
GRASSI, ROSANNA
Secondo
;
STEFANI, SILVANA
Penultimo
;
TORRIERO, ANNA
Ultimo
2017

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 metric 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. Indeed, Newman assortativity is about “being adjacent”, but even though two nodes may not by connected through an edge, they could have possibly a strong level of connectivity through a large number of walks and paths between them. This is the scope of our paper. We introduce, for undirected and unweighted networks, higher order assortativity by extending the Newman index based on a suitable choice of the matrix driving the connections. Higher order assortativity be defined for paths, shortest paths and random walks of a given length. The Newman assortativity is a particular case of each of these measures when the matrix is the adjacency matrix, or, in other words, the autocorrelation is of order 1. Our higher order assortativity indices help discriminating networks having the same Newman index and may reveal new topological network features. An application to airline network (Italy and US) and to Enron email network, as well as examples and simulations, are discussed.
Articolo in rivista - Articolo scientifico
(I) Networks; Assortativity; Degree correlation; Paths; Random walks;
Networks; Assortativity; Degree correlation; Paths; Random Walks
English
2017
262
2
708
719
reserved
Arcagni, A., Grassi, R., Stefani, S., Torriero, A. (2017). Higher order assortativity in complex networks. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 262(2), 708-719 [10.1016/j.ejor.2017.04.028].
File in questo prodotto:
File Dimensione Formato  
195329.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 919.73 kB
Formato Adobe PDF
919.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/151545
Citazioni
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 18
Social impact