On the stability of network indices defined by means of matrix functions

Stefano Pozza, Francesco Tudisco

Research output: Working paper

Abstract

Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices f(A). These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of f(A) requires a significant computational effort. In this work we address the problem of estimating the changes in the entries of f(A) with respect to changes in the edge structure. Intuition suggests that, if the topology of connections in the new graph G~ is not significantly distorted, relevant components in G maintain their leading role in G~. We propose several bounds giving mathematical reasoning to such intuition and showing, in particular, that the magnitude of the variation of the entry f(A)kℓ decays exponentially with the shortest-path distance in G that separates either k or ℓ from the set of nodes touched by the edges that are perturbed. Moreover, we propose a simple method that exploits the computation of f(A) to simultaneously compute the all-pairs shortest-path distances of G, with essentially no additional cost. As the nodes whose edge connection tends to change more often or tends to be more often affected by noise have marginal role in the graph and are distant from the most central nodes, the proposed bounds are particularly relevant.
LanguageEnglish
Place of PublicationIthaca, N.Y.
Number of pages20
Publication statusPublished - 15 Sep 2017

Fingerprint

Matrix Function
Vertex of a graph
Shortest path
Mathematical reasoning
Tend
Network Analysis
Graph in graph theory
Decay
Topology
Computing
Costs

Keywords

  • numerical analysis
  • information theory
  • information networks

Cite this

Pozza, Stefano ; Tudisco, Francesco. / On the stability of network indices defined by means of matrix functions. Ithaca, N.Y., 2017.
@techreport{d4b5b1b4708c4f41b8b224b98a896e0b,
title = "On the stability of network indices defined by means of matrix functions",
abstract = "Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices f(A). These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of f(A) requires a significant computational effort. In this work we address the problem of estimating the changes in the entries of f(A) with respect to changes in the edge structure. Intuition suggests that, if the topology of connections in the new graph G~ is not significantly distorted, relevant components in G maintain their leading role in G~. We propose several bounds giving mathematical reasoning to such intuition and showing, in particular, that the magnitude of the variation of the entry f(A)kℓ decays exponentially with the shortest-path distance in G that separates either k or ℓ from the set of nodes touched by the edges that are perturbed. Moreover, we propose a simple method that exploits the computation of f(A) to simultaneously compute the all-pairs shortest-path distances of G, with essentially no additional cost. As the nodes whose edge connection tends to change more often or tends to be more often affected by noise have marginal role in the graph and are distant from the most central nodes, the proposed bounds are particularly relevant.",
keywords = "numerical analysis, information theory, information networks",
author = "Stefano Pozza and Francesco Tudisco",
year = "2017",
month = "9",
day = "15",
language = "English",
type = "WorkingPaper",

}

On the stability of network indices defined by means of matrix functions. / Pozza, Stefano; Tudisco, Francesco.

Ithaca, N.Y., 2017.

Research output: Working paper

TY - UNPB

T1 - On the stability of network indices defined by means of matrix functions

AU - Pozza, Stefano

AU - Tudisco, Francesco

PY - 2017/9/15

Y1 - 2017/9/15

N2 - Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices f(A). These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of f(A) requires a significant computational effort. In this work we address the problem of estimating the changes in the entries of f(A) with respect to changes in the edge structure. Intuition suggests that, if the topology of connections in the new graph G~ is not significantly distorted, relevant components in G maintain their leading role in G~. We propose several bounds giving mathematical reasoning to such intuition and showing, in particular, that the magnitude of the variation of the entry f(A)kℓ decays exponentially with the shortest-path distance in G that separates either k or ℓ from the set of nodes touched by the edges that are perturbed. Moreover, we propose a simple method that exploits the computation of f(A) to simultaneously compute the all-pairs shortest-path distances of G, with essentially no additional cost. As the nodes whose edge connection tends to change more often or tends to be more often affected by noise have marginal role in the graph and are distant from the most central nodes, the proposed bounds are particularly relevant.

AB - Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices f(A). These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of f(A) requires a significant computational effort. In this work we address the problem of estimating the changes in the entries of f(A) with respect to changes in the edge structure. Intuition suggests that, if the topology of connections in the new graph G~ is not significantly distorted, relevant components in G maintain their leading role in G~. We propose several bounds giving mathematical reasoning to such intuition and showing, in particular, that the magnitude of the variation of the entry f(A)kℓ decays exponentially with the shortest-path distance in G that separates either k or ℓ from the set of nodes touched by the edges that are perturbed. Moreover, we propose a simple method that exploits the computation of f(A) to simultaneously compute the all-pairs shortest-path distances of G, with essentially no additional cost. As the nodes whose edge connection tends to change more often or tends to be more often affected by noise have marginal role in the graph and are distant from the most central nodes, the proposed bounds are particularly relevant.

KW - numerical analysis

KW - information theory

KW - information networks

UR - https://arxiv.org/abs/1709.05132

M3 - Working paper

BT - On the stability of network indices defined by means of matrix functions

CY - Ithaca, N.Y.

ER -