Large-scale networks arise in many applications. It is often of interest to be able to identify the most important nodes of a network or to determine the ease of traveling between them. We are interested in carrying out these tasks for directed networks. These networks have a nonsymmetric adjacency matrix A. Benzi et al. [6] recently proposed that these tasks can be accomplished by studying certain matrix functions, such as hyperbolic cosine and sine, of A TA and AAT. For small to medium-sized networks, the required computations can be easily carried out by first computing the singular value decomposition of A. However, for large networks this is impractical. We propose to first compute a partial singular value decomposition of A, which allows us to determine a subset of nodes that contains the most important nodes or a subset of nodes between which it is easy to travel. We then apply Gauss quadrature to rank the nodes in these subsets. Several computed examples illustrate the performance of the approach proposed

Analysis of directed networks via partial singular value decomposition and Gauss quadrature

FENU, CATERINA;RODRIGUEZ, GIUSEPPE
2014

Abstract

Large-scale networks arise in many applications. It is often of interest to be able to identify the most important nodes of a network or to determine the ease of traveling between them. We are interested in carrying out these tasks for directed networks. These networks have a nonsymmetric adjacency matrix A. Benzi et al. [6] recently proposed that these tasks can be accomplished by studying certain matrix functions, such as hyperbolic cosine and sine, of A TA and AAT. For small to medium-sized networks, the required computations can be easily carried out by first computing the singular value decomposition of A. However, for large networks this is impractical. We propose to first compute a partial singular value decomposition of A, which allows us to determine a subset of nodes that contains the most important nodes or a subset of nodes between which it is easy to travel. We then apply Gauss quadrature to rank the nodes in these subsets. Several computed examples illustrate the performance of the approach proposed
Complex networks; Low-rank approximation; HITS; Partial SVD; Gauss quadrature; Hubs and authorities
File in questo prodotto:
File Dimensione Formato  
netsvd13.pdf

Solo gestori archivio

Tipologia: versione editoriale
Dimensione 620.1 kB
Formato Adobe PDF
620.1 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/11584/97590
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 12
social impact