Network analysis with the aid of the path length matrix
Silvia Noschese, Lothar Reichel
Abstract
Abstract Let a network be represented by a simple graph $$\mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> with n vertices. A common approach to investigate properties of a network is to use the adjacency matrix $$A=[a_{ij}]_{i,j=1}^n\in \mathbb {R}^{n\times n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>=</mml:mo> <mml:msubsup> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>a</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>n</mml:mi> </mml:msubsup> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> associated with the graph $$\mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> , where $$a_{ij}>0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> if there is an edge pointing from vertex $$v_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> to vertex $$v_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:math> , and $$a_{ij}=0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> otherwise. Both A and its positive integer powers reveal important properties of the graph. This paper proposes to study properties of a graph $$\mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> by also using the path length matrix for the graph. The $$(ij)^{th}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mi>j</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>th</mml:mi> </mml:mrow> </mml:msup> </mml:math> entry of the path length matrix is the length of the shortest path from vertex $$v_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> to vertex $$v_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:math> ; if there is no path between these vertices, then the value of the entry is $$\infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>∞</mml:mi> </mml:math> . Powers of the path length matrix are formed by using min-plus matrix multiplication and are important for exhibiting properties of $$\mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> . We show how several known measures of communication such as closeness centrality, harmonic centrality, and eccentricity are related to the path length matrix, and we introduce new measures of communication, such as the harmonic K -centrality and global K -efficiency, where only (short) paths made up of at most K edges are taken into account. The sensitivity of the global K -efficiency to changes of the entries of the adjacency matrix also is considered.