We define the branching ratio of the input tree of a node in a finite directed multigraph, prove that it exists for every node, and show that it is equal to the largest eigenvalue of the adjacency matrix of the induced subgraph determined by all upstream nodes. This real eigenvalue exists by the Perron-Frobenius Theorem for non-negative matrices. We motivate our analysis with simple examples, obtain information about the asymptotics for the limit growth of the input tree, and establish other basic properties of the branching ratio.

Branching Ratios of Input Trees for Directed Multigraphs / P. Boldi, I. Stewart. - (2025 Jan 12). [10.48550/arXiv.2501.06812]

Branching Ratios of Input Trees for Directed Multigraphs

P. Boldi;
2025

Abstract

We define the branching ratio of the input tree of a node in a finite directed multigraph, prove that it exists for every node, and show that it is equal to the largest eigenvalue of the adjacency matrix of the induced subgraph determined by all upstream nodes. This real eigenvalue exists by the Perron-Frobenius Theorem for non-negative matrices. We motivate our analysis with simple examples, obtain information about the asymptotics for the limit growth of the input tree, and establish other basic properties of the branching ratio.
Mathematics - Combinatorics; Mathematics - Combinatorics; 05C12, 05C20, 05C38
Settore INFO-01/A - Informatica
12-gen-2025
http://arxiv.org/abs/2501.06812v1
File in questo prodotto:
File Dimensione Formato  
2501.06812v1.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 594.27 kB
Formato Adobe PDF
594.27 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/2434/1133375
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact