# Ranking edges by their impact on the spectral complexity of information
diffusion over networks††thanks: JK and DT were supported in part by the
National Science Foundation (DMS-2052720 and EDT-1551069) and the Simons
Foundation (grant #578333). PJM was supported in part by the National Science
Foundation (BCS-2140024).

Jeremy Kazimer Department of Mathematics, University at Buffalo, State
University of New York (SUNY), Buffalo, NY 14260, USA Manlio De Domenico
CoMuNe Lab, Department of Physics and Astronomy ”Galileo Galilei”, University
of Padua, 35131, Italy Peter J. Mucha Department of Mathematics, Dartmouth
College, Hanover, NH, 03755, USA Dane Taylor Department of Mathematics,
University at Buffalo, State University of New York (SUNY), Buffalo, NY 14260,
USA<EMAIL_ADDRESS>
###### Abstract

Despite the numerous ways now available to quantify which parts or subsystems
of a network are most important, there remains a lack of centrality measures
that are related to the complexity of information flows and are derived
directly from entropy measures. Here, we introduce a ranking of edges based on
how each edge’s removal would change a system’s von Neumann entropy (VNE),
which is a spectral-entropy measure that has been adapted from quantum
information theory to quantify the complexity of information dynamics over
networks. We show that a direct calculation of such rankings is
computationally inefficient (or unfeasible) for large networks: e.g. the
scaling is $\mathcal{O}(N^{3})$ per edge for networks with $N$ nodes. To
overcome this limitation, we employ spectral perturbation theory to estimate
VNE perturbations and derive an approximate edge-ranking algorithm that is
accurate and fast to compute, scaling as $\mathcal{O}(N)$ per edge. Focusing
on a form of VNE that is associated with a transport operator $e^{-\beta{L}}$,
where ${L}$ is a graph Laplacian matrix and $\beta>0$ is a diffusion timescale
parameter, we apply this approach to diverse applications including a network
encoding polarized voting patterns of the 117th U.S. Senate, a multimodal
transportation system including roads and metro lines in London, and a
multiplex brain network encoding correlated human brain activity. Our
experiments highlight situations where the edges that are considered to be
most important for information diffusion complexity can dramatically change as
one considers short, intermediate and long timescales $\beta$ for diffusion.

###### keywords:

network science, perturbation theory, information diffusion, spectral
complexity, von Neumann entropy, edge ranking

94A17, 05C82, 60J60, 28D20, 68P30

##  1 Introduction

Centrality analysis [10, 77] — i.e., determining the importance of
substructures including nodes [11, 32, 44], edges [43, 89, 113, 68], and
subgraphs [33, 109] — is a fundamental pursuit of network science. Quantifying
their importance supports diverse applications ranging from the ranking of
webpages [13, 63], athletes/athletic teams [92, 15, 81], and
academics/academic institutions [94, 27, 18, 107], to the identification of
potential intervention targets for dynamical processes over networks: examples
include congestion points for transportation systems [53, 49], influencers in
social networks [61, 62, 66], vaccination strategies [95, 91], as well as
points of fragility for critical infrastructures [51, 89] and biological
networks [54, 2]. Given the broad impact of this interdisciplinary field, new
methodological advances continue to be developed including the extension of
centralities to generalized types of networks (e.g., temporal networks [80,
107], multilayer and multiplex networks [23, 24, 98, 115, 25, 108],
hypergraphs and simplicial complexes [34, 8, 116]), comparing various
centralities for specific applications [56, 103], deriving centralities that
cater to particular dynamical systems [89, 112], and building stronger
theoretical foundations using tools from statistics [21], mathematics [31],
and machine learning [46].

Herein, we aim to further align the study of centrality with information
theory and entropy measures, and in particular, to contribute to the growing
interface between network science and quantum information theory [82, 4, 23,
22, 70, 39, 41]. For a recent overview of the topic, we refer the reader to
[40]. Our approach is partly motivated by node entanglement [42], which was
recently proposed as a node centrality measure stemming from the study of a
network’s von Neumann entropy (VNE) [76]. VNE was originally developed as an
information-theoretic measure to quantify disorder within quantum-mechanical
systems, and it has played a crucial role in the development of quantum
information theory [76, 122]. More recently, it has been extended as a
spectral-entropy measure that quantifies the structural complexity of graphs
[12, 23, 70], has been generalized to preserve the sub-additivity property
[22], and has been applied to a variety of interconnected systems, from
molecular biology [38] to neuroscience [7]. Of particular relevance is
previous research showing that VNE is a natural measure to quantify the
complexity of the interplay between structure and information diffusion over a
network [41, 40]. We also note in passing that there exist other centrality
measures [79, 17, 88, 69, 118, 117] that also utilize entropy in some way, but
which are not derived from VNE nor relate to the complexity of information
diffusion.

In this work, we develop a VNE-based measure for edge importance. (Although
our methods easily extend to nodes and subgraphs, we will not explicitly use
them so here.) We develop a framework that ranks edges based on how VNE would
change if each edge were separately removed. We interpret these rankings from
the perspective of information diffusion over networks [41, 40] so that the
node rankings are directly associated with the spectral complexity of
information diffusion. The top-ranked edge is the one whose removal would most
increase VNE, thereby most increasing the spectral complexity of information
diffusion. As such, our approach complements the numerous existing
centralities that relate to information-spreading dynamics over networks
including betweenness [37], Katz centrality [59], communicability [30, 32],
and many others [31, 61, 62, 66, 9]. These existing methods typically aim to
identify nodes/edges that are important as either sources for broadcasting
information or are crucial bottlenecks for information pathways, and as such,
they do not provide a notion of centrality as it relates to the
complexity/heterogeneity of _information diffusion_. Our work highlights how
the extension of some concepts used in quantum information theory to network
science, and centrality analysis in particular, can provide complementary
insights toward the importance of network substructures (e.g., edges) with
respect to a system’s functional complexity and how their roles change as one
considers different timescales for information diffusion.

Our methodology is also motivated by prior centrality analyses [89, 73, 110,
113] that utilize spectral perturbation theory to more efficiently estimate
the impact of node, edge, or subgraph removals on the perturbed spectral
properties of networks (or functions thereof [112]). Specifically, as a
spectral-entropy measure, the computation of VNE requires calculation of the
full set of eigenvalues for a graph’s Laplacian matrix. (See Sec. 2 for our
general definition.) Naively recomputing the eigenvalues to obtain the new VNE
that occurs after an edge removal is computationally expensive and is
infeasible for large networks. For example, when finding the rankings of $M$
edges, one would need to compute $M$ different spectral decompositions, each
of which can have a computational cost scaling as $\mathcal{O}(N^{3})$ for a
network with $N$ nodes. Thus motivated, we employ spectral perturbation theory
to efficiently approximate changes to VNE and approximate the subsequent
ranking of edges based on those perturbations. We show that the computational
complexity of the approximate rankings reduces to $\mathcal{O}(N)$ per edge,
allowing the framework to effectively scale to large networks.

We investigate the true and approximate rankings of edges in terms of VNE
change for three empirical networks: a voting similarity network for the 117th
U.S. Senate, a multimodal transportation network encoding roads and metro
lines, and a multiplex brain network with two layers that represent correlated
brain activity at different frequency bands. We focus on a version of VNE
based on a transport operator $e^{-\beta{L}}$, where ${L}$ is a graph
Laplacian matrix and $\beta>0$ is a _diffusion timescale parameter_.
Interestingly, we find that our measure for a network’s most important edges
is significantly influenced by $\beta$ in that the top-ranked edges at a short
timescale are often very different from those at an intermediate and/or long
timescale. This result is interesting because it highlights the multiscale
nature of importance for fundamental units of a network. Our numerical
experiments reveal three different types of network structures that
systematically cause such a reordering effect: community structure in the U.S.
Senate voting network; the relative speed between roads and metro lines for
the transportation network; and the strength of coupling between network
layers for the multiplex brain network. These experiments also highlight the
potential broad utility of our proposed entropy-based rankings for diverse
applications across the social, physical, and biological sciences.

The remainder of this paper is organized as follows: we present background
information in Sec. 2, methodology in Sec. 3, numerical experiments in Sec. 4,
and a discussion in Sec. 5.

##  2 Background information

We first provide background information Laplacian matrices and their spectral
properties (Sec. 2.1), VNE as a measure of spectral complexity for information
diffusion (Sec. 2.2), and prior centrality measures that stem from spectral
perturbation theory (Sec. 2.3).

###  2.1 Laplacian matrices and the diffusion equation

Let ${G}(\mathcal{E},\mathcal{V})$ be a graph with a set
$\mathcal{V}=\\{1,\dots,N\\}$ of nodes and a set
$\mathcal{E}=\\{(i,j)\\}\in\mathcal{V}\times\mathcal{V}$ of undirected edges,
each of which can have a positive weight $W_{ij}>0$. We assume that there are
no self-edges. The graph can be equivalently defined by a symmetric adjacency
matrix

(1) $A_{ij}=\begin{cases}W_{ij},&(i,j)\in\mathcal{E}\\\
0,&\mbox{otherwise}.\end{cases}$

We define $M=\frac{1}{2}\sum_{ij}A_{ij}$ as the total weight of edges. (The
factor of $1/2$ arises since each edge appears twice in the matrix $A$.) For
unweighted graphs, $A_{ij}=A_{ji}=1$ for each edge $(i,j)$ so that $M$ equals
the number of edges. We further define $D=\mbox{diag}[d_{1},\dots,d_{N}]$,
where each $d_{i}=\sum_{j}A_{ij}$ encodes the weighted degree (i.e., strength)
of node $i$. The unnormalized Laplacian matrix is given by a size-$N$ square
matrix

(2) $L=D-A.$

The matrix $L$ is important to many diverse applications including graph
partitioning [35], analysis of spanning trees [71], synchronization of
nonlinear dynamical systems [83, 97, 112], electricity flow [29] manifold
learning [6, 19], harmonic analysis [20], graph sparsification [100, 101], and
neural networks [14, 124]. Of particular relevance, one can define the
diffusion equation over a graph by

(3) $\frac{d}{dt}{\bf x}(t)=-\hat{\beta}L{\bf x}(t),$

where ${\bf x}(t)=[x_{1}(t),\dots,x_{N}(t)]$, ${x}_{i}(t)$ is the density at
node $i$ at time $t$, and $\hat{\beta}>0$ is a diffusion rate.

Theory development for many Laplacian-matrix-related applications often stems
from studying the spectral properties (i.e., eigenvalues and eigenvectors) of
$L$. As a real symmetric matrix, $L$ is diagonalizable, $L=U\Lambda U^{T}$,
where $\Lambda=\mbox{diag}[\lambda_{1},\dots,\lambda_{N}]$ is a diagonal
matrix whose diagonal entries encode the eigenvalues
$0=\lambda_{1}<\lambda_{2}\leq\dots\leq\lambda_{N}$, and their corresponding
eigenvectors, ${\bf u}^{(k)}$, make up the orthonormal columns of $U=[{\bf
u}^{(1)},\dots,{\bf u}^{(N)}]$. We assume that the network is connected (i.e.,
$L$ is irreducible) so that $\lambda_{2}>0$. By construction, $L{\bf 1}=0$,
where ${\bf 1}=[1,\dots,1]^{T}$, which implies $\lambda_{1}=0$ is an
eigenvalue and ${\bf u}^{(1)}=N^{-1/2}{\bf 1}$ is its associated normalized
eigenvector. To facilitate later analyses, we also define the vector of
eigenvalues: $\vec{\lambda}=[\lambda_{1},\dots,\lambda_{N}]$. Using a spectral
decomposition, Eq. (3) has the general solution

(4) ${\bf x}(t)=e^{-\hat{\beta}tL}{\bf
x}(0)=Ue^{-\hat{\beta}t\Lambda}U^{T}{\bf
x}(0)=\sum_{k=1}^{N}\alpha_{k}e^{-\hat{\beta}t\lambda_{k}}{\bf u}^{(k)},$

where $\alpha_{k}=\langle{\bf u}^{(k)},{\bf x}(0)\rangle$ is the projection of
the initial condition onto the $k$th eigenvector (each of which is an
invariant subspace of the diffusion dynamics). Herein, we will often combine
the diffusion rate and time parameter into a single _timescale parameter_
$\beta=\hat{\beta}t$.

Before continuing, we highlight that matrix $L$ given by Eq. (2) is often
called a _combinatorial Laplacian_ , and there exist normalized versions of
Laplacians that are also widely studied. For example, $\tilde{L}=D^{-1}L$ is
an asymmetric normalized Laplacian, and under the substitution
$\tilde{L}\mapsto L$, Eq. (4) would describe a continuous-time Markov chain
[36]. Similarly, $\hat{L}=D^{-1/2}LD^{-1/2}$ defines a symmetric normalized
Laplacian that shares the same eigenvalues as $\tilde{L}$ and is broadly
important for machine learning applications. In this work, we will focus on
$L$, noting that our methodology and findings can be easily extended to
applications involving these other matrices.

###  2.2 Information diffusion and von Neumann entropy (VNE)

While the diffusion equation given by Eq. (3) is often associated with heat
flow, it can also be used as a model for other types of diffusion including
the propagation of quanta of information over complex networks [39, 42, 7].
Adopting the common “bra–ket” mathematical notation of quantum mechanics, we
begin by using $\beta=\hat{\beta}t$ to rewrite the solution to Eq. (3) by

(5) $\vec{\phi}(\beta)={\bf
x}(t)=\vec{\phi}(0)e^{-\beta{L}}=Z_{\beta}(L)\langle\vec{\phi}(0)|\rho_{\beta}(L),$

where

(6)
$Z_{\beta}(L)\equiv\text{Trace}(e^{-\beta{L}})=\sum^{N}_{k=1}e^{-\beta\lambda_{k}}$

normalizes a _propagator matrix_ $e^{-\beta{L}}$ to yield an associated
_density matrix_

(7) $\displaystyle\rho_{\beta}(L)$ $\displaystyle=\frac{e^{-\beta
L}}{Z_{\beta}(L)}=\sum_{k=1}^{N}s_{k}|{\bf u}^{(k)}\rangle\langle{\bf
u}^{(k)}|\,,$

where

(8) $s_{k}=\frac{e^{-\beta\lambda_{k}}}{Z_{\beta}(L)}.$

These expressions use the eigenvalues $\lambda_{k}$ and eigenvectors ${\bf
u}^{(k)}$ of $L$, which were defined in the previous section. (Note that
$|{\bf u}^{(k)}\rangle\langle{\bf u}^{(k)}|={\bf u}^{(k)}[{\bf u}^{(k)}]^{T}$
denotes an outer product in traditional mathematical notation, whereas
$\langle{\bf u}^{(k)}|{\bf u}^{(k)}\rangle=[{\bf u}^{(k)}]^{T}{\bf u}^{(k)}$
is an inner product.)

We note that in the classical interpretation of diffusion, if a particle is
first observed at node $i$ and later observed at node $j$, then it is believed
to have taken some well-defined (although possibly unknown) path from $i$ to
$j$. In contrast, the quantum transport of a quantum particle that is emitted
at node $i$ is considered to be de-localized (i.e., exists across all paths)
until it is later detected at node $j$. In either case, one can interpret a
vector $\vec{\phi}(\beta)$ to be an _information field_ at timescale
$\beta\geq 0$ for information dynamics that are initialized with an initial
field $\vec{\phi}(0)=\sum_{i=1}^{N}p_{i}\langle i|$, where $p_{i}$ is the
probability that information is “seeded” at node $i$ and $\langle i|$ is a
unit vector in which all entries are zeros except for the $i$th entry, which
is a one. We assume $\sum_{i}p_{i}=1$. Each entry $[\rho_{\beta}(L)]_{ij}$
gives the probability of transport of information quanta from node $i$ to $j$
at timescale $\beta$. Moreover, each eigenspace-restricted transport operator
$s_{k}|{\bf u}^{(k)}\rangle\langle{\bf u}^{(k)}|$ defines a $k$th _information
stream_ over which an information quanta can be transported. By construction,
$\text{Trace}(\rho_{\beta}(L))=\sum_{k}s_{k}=1$ so that each $s_{k}$ defines
the probability of transport along the $k$th information stream at timescale
$\beta$.

For both classical and quantum diffusion it is natural to examine whether
transport is localized onto a small set of information streams (i.e., a few
eigenmodes) or whether it is dispersed across many information streams (i.e.,
many eigenmodes). Such an inquiry is said to examine the _spectral complexity_
of information diffusion. Here, we focus on classical diffusion according to
Eq. (3) but seek to utilize the toolset of quantum information theory to
measure the spectral complexity of information diffusion, and we will later
use it to measure the importance (i.e., centrality) of edges. To this end, we
quantify the spectral complexity of information diffusion using von Neumann
entropy (VNE). VNE was introduced by John von Neumann as a measure for quantum
information [76] and can quantify, for example, the departure of a quantum-
mechanical system from its pure state. Applications include using VNE to
identify entangled spin-orbital bound states [123], examining non-equilibrium
thermodynamics of bosons [72], and developing complementary analyses for
quantum phenomena [52]. Due to its widespread applicability and inherent
ability to capture uncertainty for entangled quantum states, VNE has become a
cornerstone for modern quantum information theory [122].

Recently, this formalism was extended to study structural information for
graphs [12, 23, 70], although its more reliable generalization that preserves
the sub-additivity property of VNE, was proposed later in [22] and further
developed in [41]. (See [40] for a review). Applications have included the
study of global trade networks [23] and the functional connectivity of brain
networks [78, 7]. We will utilize the sub-additive-preserving definition of
VNE to develop an entropy-based centrality measure for edges in graphs.

We begin be defining a generalized notion of VNE for networks that
incorporates and extends earlier versions.

######  Definition 2.1 (von Neumann Entropy for Graphs).

Let ${G}(\mathcal{E},\mathcal{V})$ be a graph and $L$ be an associated
Laplacian matrix. Assume $L$ has the diagonalization $L=U\Lambda U^{-1}$,
where $\Lambda=\text{diag}(\vec{\lambda})$,
$\vec{\lambda}=[\lambda_{1},\dots,\lambda_{N}]^{T}$ with
$\lambda_{i}\in\mathbb{R}$, and $U$ contains the associated (right)
eigenvectors as columns. Further, let $\rho(L)$ be a matrix-valued analytic
function that admits the diagonalization
$\rho(L)=U\mbox{diag}[f_{1}(\vec{\lambda}),\dots,f_{N}(\vec{\lambda})]U^{-1}$
and satisfies $1=\operatorname{Tr}(\rho(L))=\sum_{i}f_{i}(\vec{\lambda})$. We
then define a general form for VNE of graph $G(\mathcal{E},\mathcal{V})$ by

$\displaystyle h(L)$
$\displaystyle=-\operatorname{Tr}[\rho(L)\log_{2}\rho(L)]$ (9)
$\displaystyle=-\sum_{k=1}^{N}f_{k}(\vec{\lambda})\log_{2}f_{k}(\vec{\lambda}),$

where $\vec{\lambda}$ By convention, we define $0\log_{2}(0)=0$.

######  Remark 2.2.

Because $1=\sum_{k}f_{k}(\vec{\lambda})$, one can interpret each
$f_{k}(\vec{\lambda})$ as a probability, and then VNE coincides with Shannon
entropy for the set $\\{f_{k}(\vec{\lambda})\\}$ of probabilities.

######  Remark 2.3.

We define a matrix-valued function $\rho(L)$ that satisfies
$\text{Trace}(\rho(L))=1$ to be a “trace-normalized matrix transformation”. In
principle, matrix $L$ need not be restricted to Laplacian matrices, and it
could represent any graph-encoding matrix that is diagonalizable and has real-
valued eigenvalues.

The earliest application of VNE to graphs that we know of can be attributed to
Braunstein et al. [12], wherein the authors restricted their attention to the
choice of function $f_{k}(\vec{\lambda})=\lambda_{k}/\sum_{j}\lambda_{j}$ for
possibly weighted graphs, and we will refer to the associated VNE as _uniform
VNE_. For unweighted graphs, $\sum_{j}\lambda_{j}=2M$ gives twice the number
of edges. However, it has been shown that this definition does not preserve
the desired property of sub-additivity for entropies [23].

More recently, De Domenico and Biamonte [22] proposed using
$\rho(L)=\rho_{\beta}(L)$, as defined in Eq. (7), in which case
$f_{k}(\vec{\lambda})=s_{k}$, as defined in Eq. (8). Importantly, this
definition does satisfy the sub-additivity property.

######  Proposition 2.4 (Sub-additivity of VNE [22]).

Consider the VNE $h(L^{1})$ and $h(L^{2})$ for two graphs with equally-sized
Laplacian matrices $L^{1},L^{2}\in\mathbb{R}^{N\times N}$, where $h$ is given
by Eq. (2.1) with $\rho$ given by Eq. (7). Further, define an edge-aggregated
graph with an associated Laplacian $L^{1}+L^{2}$. Then the VNE of the edge-
aggregated graph satisfies the bound

(10) $\displaystyle h(L^{1}+L^{2})\leq h(L^{1})+h(L^{2}).$

Our definition of VNE above allows $L$ to represent either a normalized or
unnormalized Laplacian matrix. Here, we focus on the choice of the
combinatorial Laplacian matrix $L$ given by Eq. (2), and we refer to the
corresponding VNE measure as _diffusion-kernel VNE_. We note in passing,
however, that VNE has also been studied using a left normalized (also called
random-walk) Laplacian matrix $\mathcal{L}=D^{-1}L$ [39], and we will refer to
that form as _continuous-time random-walk VNE._ Regardless of the choice of
matrix $L$, large VNE values indicate that diffusion transport is dispersed
across many information streams (i.e., many eigensubspaces), whereas small VNE
values indicate that it is localized to one, or a few, information streams
(i.e., concentrated onto a smaller eigensubspace). See [41, 7, 40] for the
exploration of other relationships between VNE and information diffusion
dynamics, including discussions on trapped fields and information field
diversity.

###  2.3 Spectral Perturbation Theory for Centrality Analysis

Given that diffusion-kernel VNE measures the spectral complexity of
information diffusion, the remainder of this paper will focus on VNE-based
analyses of networks. Specifically, we propose to rank edges (although our
methods easily extend to nodes and subgraphs) according to how each edge’s
removal would change the graph’s VNE.

Our work is largely motivated by prior centrality measures that quantify
importance by considering how structural modifications lead to perturbations
for the spectral properties of graph-encoding matrices. Of particular
relevance is recent work [42] that proposed a node ranking by examining how
VNE changes occur after node removals, and _node entanglement_ was defined as
a centrality measure inspired by the concept of quantum entanglement for
quantum-mechanical systems. Herein, we will develop a complementary edge
centrality measure that ranks edges based on how each edge’s removal would
change the graph’s VNE. Importantly, centrality measures relating to spectral
changes can be computationally expensive if many eigenvalues and eigenvectors
are involved in the measures’ definitions. In particular, VNE requires
knowledge of all the eigenvalues, and so the direct recomputation of VNE for
the Laplacian matrices of graphs after the removal of nodes or edges would be
impractical for large graphs.

Given this limitation, herein we propose to build on existing techniques that
leverage spectral perturbation theory to approximate centrality measures and
rankings in a way that is more computationally efficient. For example, the
_dynamical importance_ [89] of a node or edge is defined as the decrease that
would occur for the adjacency matrix’s spectral radius if that node or edge is
removed (see also [113]). Other related work includes considering the impact
of structural modifications on the spectra of Laplacian matrices [73, 70, 99]
as well as functions of such eigenvalues and eigenvectors [112]. Such
centrality measures can be efficiently approximated by developing linear
approximations for how structural perturbations of graphs give rise to
spectral perturbations. We also refer the reader to [107, 108] for the use of
more advanced matrix-perturbation techniques (namely singular perturbation
theory) that have arisen in the context of centrality measures for multiplex
and temporal networks. We note in passing that these perturbative analyses of
networked-coupled dynamical systems are closely related to the notions of
eigenvalue and eigenvector elasticities [57, 58].

Spectral perturbation theory for network modifications often stems from the
following first-order approximation.

######  Theorem 2.5 (Perturbation of Simple Eigenvalues [5]).

Let ${X}$ be a symmetric $N\times N$ matrix with eigenvalues
$\\{\lambda_{j}\\}$ and normalized eigenvectors $\\{{\bf u}^{(j)}\\}$.
Consider an eigenvalue $\lambda_{i}$ that is simple in that it has algebraic
multiplicity one: $\lambda_{i}\not=\lambda_{j}$ for any other $j$ and
$\lambda_{i}$ has a 1-dimensional eigenspace spanned by the eigenvector ${\bf
u}^{(i)}\in\mathbb{R}^{N}$. Further, consider a fixed symmetric perturbation
matrix $\Delta{X}$, and let ${X}(\epsilon)={X}+\epsilon\Delta{X}$. We denote
the eigenvalues and eigenvectors of ${X}(\epsilon)$ by $\lambda_{j}(\epsilon)$
and ${\bf u}^{(j)}(\epsilon)$, respectively. It then follows that

(11) $\displaystyle\lambda_{i}(\epsilon)$
$\displaystyle=\lambda_{i}+\epsilon\lambda^{\prime}_{i}(0)+\mathcal{O}(\epsilon^{2}),$

where $\lambda_{i}^{\prime}(0)$ is the derivative of $\lambda_{i}(\epsilon)$
with respect to $\epsilon$ at $\epsilon=0$ and is given by

(12) $\displaystyle\lambda_{i}^{\prime}(0)$ $\displaystyle=({\bf
u}^{(i)})^{T}\Delta{X}{\bf u}^{(i)}.$

######  Proof 2.6.

See [5].

######  Remark 2.7.

The first-order approximation given by Eq. (11) is accurate when the
perturbation is sufficiently small,
$|\epsilon\lambda^{\prime}_{i}(0)|\ll|\lambda_{i}|$.

To study how edge perturbations change the spectral properties of a Laplacian
matrix $L$ given by Eq. (2), we can set $X=L$ and study a perturbation $\Delta
L$ encoding the changed edge(s).

######  Proposition 2.8 (Weighted Edge Perturbations).

When the weighted and undirected network is modified by adding an edge $(p,q)$
of weight $A_{pq}$, the Laplacian perturbation matrix takes the form

(16)
$\displaystyle\Delta{L}_{ij}^{(pq)}=\left\\{\begin{array}[]{rl}A_{pq},&{(i,j)\in\\{(p,p),(q,q)\\}}\\\
-A_{pq},&{(i,j)\in\\{(p,q),(q,p)\\}}\\\
0,&\text{otherwise}.\end{array}\right.$

Similarly, when the network is modified by removing an edge $(p,q)$, the
corresponding Laplacian perturbation matrix is $-\Delta{L}_{ij}^{(pq)}$. We
emphasize that in this notation we use $A_{pq}$ to be the (nonzero) weight of
the edge when present — that is, the weight of the newly added edge or the
weight of the edge prior to its removal.

Versions of Proposition 2.8 have appeared in various literatures, usually
under the assumption of unweighted networks (see, e.g., [112, 70], in which
case $A_{ij}\in\\{0,1\\}$). Moreover, such a matrix perturbation easily
extends to sets of edges, thereby extending to node and subgraph
perturbations.

######  Proposition 2.9 (Weighted Edge-Set Perturbations [112]).

When a weighted and undirected network is modified by adding a set of weighted
edges $\mathcal{E}^{+}$ and removing a set of weighted edges
$\mathcal{E}^{-}$, the Laplacian perturbation matrix takes the form

(17)
$\displaystyle\Delta{L}_{ij}^{(\mathcal{E}^{+},\mathcal{E}^{-})}=\sum_{(p,q)\in\mathcal{E}^{+}}\Delta{L}_{ij}^{(pq)}-\sum_{(p,q)\in\mathcal{E}^{-}}\Delta{L}_{ij}^{(pq)},$

where $\Delta{L}_{ij}^{(pq)}$ is given by Eq. (16).

These forms for $\Delta L$ can be combined with Thm. 2.5 to provide first-
order approximations for the impact of network modifications on the
eigenvalues of a Laplacian matrix.

######  Lemma 2.10 (First-order Spectral Impact of Edge Additions and
Removals).

Let $\Delta{L}^{(pq)}$ and $-\Delta{L}^{(pq)}$, respectively, denote the
perturbation matrix for a graph Laplacian under the addition and removal of a
weighted edge $(p,q)$ with weight $A_{pq}$ as defined in Prop. 2.8. Then the
simple eigenvalues $\lambda_{i}(\epsilon)$ of the perturbed matrix
$L\pm\epsilon\Delta L^{(pq)}$ are given by Eq. (11) with

(18) $\displaystyle\lambda_{i}^{\prime}(0)=\pm({\bf
u}^{(i)})^{T}\Delta{L}^{(pq)}{\bf u}^{(i)}$ $\displaystyle=\pm
A_{pq}({u}^{(i)}_{p}-{u}^{(i)}_{q})^{2}.$

Similar results were previously given in [73], which focused on the choices
$i\in\\{2,N\\}$ to develop a first-order approximation for the eigenratio
$\lambda_{2}/\lambda_{N}$ that is a spectral measure of synchronizability for
a network of identical oscillators.

In the general case in which one removes a set $\mathcal{E}^{-}$ and/or adds a
set $\mathcal{E}^{+}$ of weighted edges, one finds the following.

######  Lemma 2.11 (First-order Spectral Impact of Edge-Set Modifications).

Let $\Delta{L}_{ij}^{(\mathcal{E}^{+},\mathcal{E}^{-})}$ denote the
perturbation matrix for a graph Laplacian under the addition and removal of
weighted edge sets $\mathcal{E}^{+}$ and $\mathcal{E}^{-}$, respectively. Then
the simple eigenvalues $\lambda_{i}(\epsilon)$ of the perturbed matrix
$L+\epsilon\Delta L$ are given by Eq. (11) with

(19) $\displaystyle\lambda_{i}^{\prime}(0)$
$\displaystyle=\sum_{(p,q)\in\mathcal{E}^{+}}A_{pq}({u}^{(i)}_{p}-{u}^{(i)}_{q})^{2}-\sum_{(p,q)\in\mathcal{E}^{-}}A_{pq}({u}^{(i)}_{p}-{u}^{(i)}_{q})^{2}.$

In the next section, we extend this spectral approximation theory to
diffusion-kernel VNE to develop VNE-based edge-ranking algorithms that are
computationally efficient and can scale to large networks. It is also worth
noting that the above-mentioned spectral perturbation theory has been
previously used to study graph VNE [70], although that work focused on a
formulation in which $\rho(\lambda_{i})=\lambda_{i}/2M$ [12]. Moreover, that
work did not use VNE to develop a perturbation-based centrality measure, but
instead analyzed the perturbative and limiting behavior for VNE for graph
ensembles that are obtained through stochastic edge-rewiring algorithms.
Notably, results similar to Lemmas 2.10 and 2.11, albeit for unweighted graphs
with $A_{ij}\in\\{0,1\\}$, were presented in [70] to study perturbations of
VNE with the uniform density function.

##  3 VNE perturbations measure the importance of edges

We now present our main theoretical and algorithmic results. Specifically, we
introduce algorithms that rank edges according to their contribution to the
spectral complexity of information diffusion over networks, as measured by
diffusion-kernel VNE. In Sec. 3.1, we develop these rankings and discuss their
limitation to small graph sizes. In Sec. 3.2, we develop an approximate-
ranking algorithm that efficiently scales to large graphs and is based on
spectral perturbation theory. In Sec. 3.3, we present experiments to compare
these two rankings, which are based on the true and approximate values for how
VNE would be perturbed by edge removals. (Further experiments are deferred to
Sec. 4.)

###  3.1 Edge rankings by VNE increases upon edge removals

Given a graph $G(\mathcal{V},\mathcal{E})$ with $N$ nodes and $|\mathcal{E}|$
undirected edges with weights $\\{A_{ij}\\}$, we seek to rank the edges so
that the most important edge $(p,q)\in\mathcal{E}$ is the one that would
maximize the VNE of a residual graph that results from removing edge $(p,q)$.
More precisely, let $L$ be the unnormalized graph Laplacian of
$G(\mathcal{V},\mathcal{E})$ given by Eq. (2) and $-\Delta L^{(pq)}$ be the
change to $L$ given by Eq. (16) that would occur upon the removal of edge
$(p,q)\in\mathcal{E}$. Further, let $h(L)$ be the graph’s VNE, as given by Eq.
(2.1). Then the change to VNE that would occur upon the removal of edge
$(p,q)$ is given by

(20) $\displaystyle Q_{pq}=h(L-\Delta L^{(pq)})-h(L).$

In principle, $Q_{pq}$ is not necessarily positive, although our experiments
suggest that $Q_{pq}>0$ for most edges. Considering the set $\\{Q_{pq}\\}$ of
VNE perturbations for $(p.q)\in\mathcal{E}$, the top-ranked edge is a solution
to the following optimization problem

(21) $(p,q)=\text{argmax}_{(p,q)\in\mathcal{E}}~{}Q_{pq}.$

######  Definition 3.1 (Edge Rankings by VNE Increases).

Given a graph ${G}=(\mathcal{V},\mathcal{E})$ with unnormalized Laplacian $L$,
consider the changes $Q_{pq}$ to VNE given by Eq. (20), which would occur upon
the removals of edges $(p,q)\in\mathcal{E}$. Then, we define the rankings

(22) $\displaystyle
R_{pq}=1+|\mathcal{E}^{\prime}|,~{}\text{where}~{}\mathcal{E}^{\prime}=\\{(n,m)\in\mathcal{E}:Q_{nm}>Q_{pq}\\}$

so that $R_{pq}\in\\{1,\dots,|\mathcal{E}|\\}$ gives the rank of each edge
$(p,q)\in\mathcal{E}$.

Computationally, these rankings can be easily computed using the ‘argsort’
function, as indicated in Algorithm 1.

Algorithm 1 Edge Rankings by VNE Increases

0: Graph $G(\mathcal{V},\mathcal{E})$ with nodes $\mathcal{V}$, weighted edges
$\mathcal{E}$, and unnormalized Laplacian $L$.

0: Cardinality $|\mathcal{E}|>0$

1: Compute set $\\{\lambda_{i}\\}$ of eigenvalues for $L$.

2: Compute VNE $h(L)$ according to Eq. (2.1).

3: for $(p,q)\in\mathcal{E}$ do

4: Compute set $\\{\lambda_{i}^{\prime}\\}$ of perturbed eigenvalues for
$L^{\prime}=L-\Delta L^{(pq)}$.

5: Compute the change $Q_{pq}$ according to Eq. (20).

6: end for

7: Apply ‘argsort’ function to the set $\\{{Q}_{pq}\\}$ to obtain the set
$\\{R_{pq}\\}$ of rankings.

######  Remark 3.2.

One can rank edges according to perturbations to VNE given by Eq. (2.1) for
any choice of the function $\rho(\lambda)$. We will focus herein on the
diffusion-kernel VNE in which $\rho(\lambda)$ is given by Eq. (8).

######  Remark 3.3.

Note that the $Q_{pq}$ values for different edges $(p,q)$ can be the same, in
which case the rankings are not unique. Such scenarios can be handled in a
variety of ways. We resolve edges with tied rankings randomly. That is, if $k$
edges are tied for rank $R$, then we randomly assign them ranks $R$, $R+1$, …,
$R+k$.

Before continuing, we highlight that the direct computation of rankings
$R_{pq}$ will be infeasible for large graphs due to the large computational
cost. That is, computing all eigenvalues $\\{\lambda_{i}\\}$ of a matrix $L$
is an expensive task that can have computational complexity
$\mathcal{O}(N^{3})$, where $N$ is the matrix size. Moreover, in order to
compute the VNE change $Q_{pq}$ given by Eq. (20) for an edge $(p,q)$, one
needs to first compute the perturbed eigenvalues $\\{\lambda_{i}^{\prime}\\}$
for a perturbed Laplacian $L^{\prime}=L-\Delta L^{(p,q)}$. Since this must be
done for each edge, constructing the set $\\{Q_{pq}\\}$ for
$(p,q)\in\mathcal{E}$ has computational complexity
$\mathcal{O}(|\mathcal{E}|N^{3})$ for $N$ nodes and $|\mathcal{E}|$ edges.
Performing such a task would be impractical for large graphs. For example, in
Sec. 3.3 we estimate that the runtime to compute the set $\\{Q_{pq}\\}$ for a
graph with $N=8000$ nodes would take approximately 1300 hours (about 54 days)
to complete on a standard desktop. Thus motivated, in the next section we
develop an approximate ranking algorithm that is much more efficient and can
be readily applied to larger graphs.

###  3.2 Perturbation theory for VNE and efficient edge ranking

Implementing Algorithm 1 can be computationally infeasible for large graphs,
and here we develop approximate rankings based on the spectral perturbation
theory that we presented in Sec. 2.3. Recall that we define VNE (see Def. 2.1)
using a spectral map ${\bf f}:\mathbb{R}^{N}\mapsto\mathbb{R}^{N}$ that is
defined entry-wise by

(23) ${\bf
f}(\vec{\lambda})=[{f}_{1}(\vec{\lambda}),\dots,{f}_{N}(\vec{\lambda})]^{T},$

where $\vec{\lambda}=[\lambda_{1},\dots,\lambda_{N}]^{T}$ is a vector of
eigenvalues. For uniform VNE, one has $f_{k}(\vec{\lambda})=\lambda_{k}/(2M)$,
which depends only on the $k$th eigenvalue since $\sum_{k}\lambda_{k}=2M$ is a
conserved quantity equal to total edge weight. In contrast, for diffusion-
kernel VNE one has that
$f_{k}(\vec{\lambda})=s_{k}=e^{-\beta\lambda_{k}}/Z(\beta)$, as defined by Eq.
(8). In this latter case, each $f_{k}(\vec{\lambda})$ depends on all the
eigenvalues due to the denominator term
$Z(\beta)=\sum_{k}e^{-\beta\lambda_{k}}$.

We now approximate how structural modifications change VNE to first order.

######  Lemma 3.4 (First-Order Perturbation of VNE).

Let $L$ be a diagonalizable Laplacian matrix given by Eq. (2) for an
undirected graph and $L^{\prime}=L+\epsilon\Delta L$ denote its perturbation
for a small scalar $\epsilon$. Further, let $h(L)$ be the graph’s VNE given by
Def. 2.1. Letting $H(\epsilon)\equiv h(L+\epsilon\Delta L)$ be the
$\epsilon$-perturbed VNE, then $H(\epsilon)$ has the first-order approximation

(24) $H(\epsilon)=H(0)+\epsilon H^{\prime}(0)+\mathcal{O}(\epsilon^{2}),$

where $H(0)=h(L)$ is the VNE of the original graph. Morever, when the
eigenvalues $\lambda_{i}$ of $L$ are simple, then the derivative

$H^{\prime}(0)=\left.\sum_{i,j}\dfrac{\partial h}{\partial
f_{i}}\dfrac{\partial
f_{i}}{\partial\lambda_{j}}\dfrac{\partial\lambda_{j}}{\partial\epsilon}\right|_{\epsilon=0},$

can be constructed using partial derivatives with
$\left.{\partial\lambda_{j}}/{\partial\epsilon}\right|_{\epsilon=0}=\lambda^{\prime}_{j}(0)=({\bf
u}^{(j)})^{T}\Delta{L}{\bf u}^{(j)}$ given by Eq. (12) in Thm. 2.5. Here,
${\bf u}^{(j)}$ is the eigenvector associated with $\lambda_{j}$.

######  Remark 3.5.

Each derivative $\lambda^{\prime}_{j}(0)=({\bf u}^{(j)})^{T}\Delta{L}{\bf
u}^{(j)}$ assumes $\lambda_{j}$ to be a simple (i.e., non-repeated) eigenvalue
(recall also Lemmas 2.10 and 2.11). When repeated eigenvalues arise, we
propose to approximate $H^{\prime}(0)$ by neglecting the contribution of
repeated eigenvalues. That said, we have yet to encounter such a situation in
our experiments with VNE. It is our experience that the Laplacian matrices of
empirical networks rarely contain repeated eigenvalues unless they contain
some particular type of symmetry.

Lemma 3.4 can be generally applied to different choices for the density
function $\rho(L)$ described in Def. 2.1. For example, it can recover a
previously shown result for uniform VNE.

######  Theorem 3.6 (First-Order Perturbation of Uniform VNE [70]).

Consider a uniform density function
$f_{i}(\vec{\lambda})=\rho(\lambda_{i})=\lambda_{i}/\sum_{j}\lambda_{j}$ and
the full set of assumptions in Lemma 3.4. Then the perturbed VNE is given by
Eq. (24) with

(25) $H^{\prime}(0)=-\frac{1}{2M}\sum_{i}({\bf u}^{(i)})^{T}\Delta{L}{\bf
u}^{(i)}\left[\log_{2}\left(\frac{\lambda_{i}}{\sum_{j}\lambda_{j}}\right)+\frac{1}{\ln(2)}\right].$

In [70], Thm. 3.6 was developed to study the effects of graph rewiring on
uniform VNE, and in particular, how the distribution of VNE across a random-
graph ensemble that is obtained via edge rewiring can converge to that for
well-known random graph ensembles, including ensembles associated with the
Erdős-Rényi $G_{NM}$ and configuration models. Turning our attention back to
diffusion-kernel VNE, we obtain the following.

######  Theorem 3.7 (First-Order Perturbation of diffusion-kernel VNE).

Consider the diffusion-kernel density function
$f_{i}(\vec{\lambda})=\rho(\lambda_{i})$ given by Eq. (8) and the full set of
assumptions in Lemma 3.4. Then the perturbed VNE is given by Eq. (24) with

(26) $\displaystyle H^{\prime}(0)$
$\displaystyle=-\beta\sum_{i=1}^{N}f_{i}(\vec{\lambda})\left[\log_{2}(f_{i}(\vec{\lambda}))+\frac{1}{\ln\left(2\right)}\right]\left[-\lambda_{i}^{\prime}(0)+\sum_{j}^{N}f_{j}(\vec{\lambda})\lambda_{j}^{\prime}(0)\right],$

where $\lambda_{i}^{\prime}(0)=({\bf u}^{(i)})^{T}\Delta{L}{\bf u}^{(i)}$.

######  Proof 3.8.

See Appendix A.

In principle, a Laplacian perturbation matrix $\Delta L$ can encode a broad
family of structural modifications to a graph. For example, Lemma 2.10 in Sec.
2.3 showed that $\lambda_{i}^{\prime}(0)=\pm({\bf
u}^{(i)})^{T}\Delta{L}^{(p,q)}{\bf u}^{(i)}=\pm
A_{pq}(u_{p}^{(i)}-u_{q}^{(i)})^{2}$ for the addition (+) or removal (-) of an
edge $(p,q)$ having weight $A_{pq}$. Moreover, Lemma 2.11 showed that
$\lambda_{i}(0)=\sum_{(p,q)\in\mathcal{E}^{+}}A_{pq}(u_{p}^{(i)}-u_{q}^{(i)})^{2}-\sum_{(p,q)\in\mathcal{E}^{-}}A_{pq}(u_{p}^{(i)}-u_{q}^{(i)})^{2}$
for the addition of a set $\mathcal{E}^{+}$ of edges and the removal of a set
$\mathcal{E}^{-}$ of edges. Thus, one can compute Eq. (25) and Eq. (26) very
efficiently for a given edge modification or a set of edge modifications. See
Appendix B for an experiment that provides numerical validation for Thm. 3.7
by estimating the change to VNE induced by removing $k$ edges for $0\leq k\leq
20$.

With this approximation theory in hand, we now return our attention to the
ranking of edges based on the change $Q_{pq}=h(L-\Delta L^{(pq)})-h(L)$ to VNE
that would occur after the individual removal of each edge
$(p,q)\in\mathcal{E}$. Combining Thm. 3.7 with Lemma 2.10, we approximate

(27) $\displaystyle Q_{pq}\approx\tilde{Q}_{pq}\equiv H^{\prime}(0),$

where $H^{\prime}(0)$ is appropriately defined for the particular type of VNE
(i.e., as represented by the spectral mapping $f_{i}(\vec{\lambda})$) and
$\lambda_{j}^{\prime}(0)=-A_{pq}(u_{p}^{(j)}-u_{q}^{(j)})^{2}$. Herein, we
will focus on diffusion-kernel VNE in which $H^{\prime}(0)$ is given by Eq.
(26), which uses
$f_{i}(\vec{\lambda})={e^{-\beta\lambda_{i}}}/{\sum_{j}e^{-\beta\lambda_{j}}}$.
In principle, one can use a similar approach to approximate edge rankings
based on VNE perturbations for other choices of $f_{i}(\vec{\lambda})$.
Finally, we also highlight that due to the linearity of first-order
approximations, one can also estimate the change to VNE that would occur due
to the removal of a subset $\mathcal{E}^{1}\subset\mathcal{E}$ of edges by
$H^{\prime}(0)=\sum_{(p,q)\in\mathcal{E}^{1}}Q_{pq}.$

Given the approximate perturbations $\\{\tilde{Q}_{pq}\\}$, we now define an
approximate ranking of edges.

######  Definition 3.9 (Edge Rankings by First-Order Approximate VNE
Increases).

Given a graph ${G}=(\mathcal{V},\mathcal{E})$ with unnormalized Laplacian $L$,
consider the approximate changes $\tilde{Q}_{pq}$ to VNE given by Eq. (27).
Then, then we define the rankings

(28)
$\displaystyle\tilde{R}_{pq}=1+|\mathcal{E}^{\prime}|,~{}\text{where}~{}\mathcal{E}^{\prime}=\\{(n,m)\in\mathcal{E}:\tilde{Q}_{nm}>\tilde{Q}_{pq}\\}$

so that $\tilde{R}_{pq}\in\\{1,\dots,|\mathcal{E}|\\}$ gives the approximate
rank of each edge $(p,q)\in\mathcal{E}$.

We summarize the computation of this ranking in Algorithm 2.

Algorithm 2 Edge Rankings by First-Order-Approximate VNE Increases

0: Graph $G(\mathcal{V},\mathcal{E})$ with nodes $\mathcal{V}$, weighted edges
$\mathcal{E}$, and unnormalized Laplacian $L$.

0: Cardinality $|\mathcal{E}|>0$

1: Compute set $\\{\lambda_{i}\\}$ of eigenvalues for $L$.

2: Compute VNE $h(L)$ according to Eq. (2.1).

3: for $(p,q)\in\mathcal{E}$ do

4: Compute the approximate change $\tilde{Q}_{pq}$ to VNE according to Eq.
(27).

5: end for

6: Apply ‘argsort’ function to the set $\\{\tilde{Q}_{pq}\\}$ to obtain the
set $\tilde{R}_{pq}\\}$ of approximate rankings.

Before continuing, we highlight that one possible limitation of this approach
is that Lemma 3.4, Thm. 3.6 and Thm. 3.7 define $H^{\prime}(0)$ in a way that
assumes that the eigenvalues $\lambda_{j}$ of $L$ are simple. We propose to
neglect the contributions of repeated eigenvalues as a simple heuristic. Our
experience with empirical network data suggests that such situations are rare
unless some particular type of symmetry is present, and indeed we have yet to
encounter such a situation with our experiments for VNE. Moreover, we predict
that if eigenvalue repetition occurs, it is more likely to arise for large
eigenvalues (i.e., for which $e^{-\beta\lambda_{j}}$ is small), as opposed to
the smaller, more important eigenvalues for which the $e^{-\beta\lambda_{j}}$
terms are larger. Therefore, we expect that the neglection of
$\lambda_{i}^{\prime}(0)$ terms for repeated eigenvalues will have a
particularly small effect on an estimate $H^{\prime}(0)$ for diffusion-kernel
VNE and the subsequent rankings of edges.

###  3.3 Comparison of Algorithms 1 and 2

Recall that our main motivation for developing approximate rankings was that
it is can be computationally expensive (or infeasible) to directly compute the
set $\\{Q_{pq}\\}$, which requires one to compute the exact change to VNE that
occurs after removing each edge $(p,q)$. More specifically, upon each edge
removal, we must recompute all eigenvalues of a size-$N$ matrix, which has
$\mathcal{O}(N^{3})$ scaling per edge.111Notably, we implemented our
algorithms using the NumPy Python package, and the eigenpair computations are
based on LAPACK algorithms [50], which has $\mathcal{O}(N^{3})$ complexity
[26]. In contrast, the approximate rankings utilize spectral perturbation
theory and the eigenvalues of a size-$N$ matrix only must be computed once.
Then for each edge, one computes $\tilde{Q}_{pq}=H^{\prime}(0)$ using Eq.
(26), which has $\mathcal{O}(N)$ complexity and is a much more efficient
approach.

In Fig. 1, we compare Algorithms 1 and 2 in two ways. First, we show in Fig.
1(A) that the approximate rankings $\\{\tilde{R}_{pq}\\}$ are much more
efficient to compute than the true rankings $\\{{R}_{pq}\\}$ for an example
graph. Second, we show in Fig. 1(B) that these two sets of rankings can be
very similar $\tilde{R}_{pq}\approx R_{pq}$. Their similarity is somewhat
expected, since $\tilde{Q}_{pq}\approx Q_{pq}$ by construction.

Figure 1: Comparison of Algorithms 1 and 2. (A) We estimate the runtimes that
are required to execute these algorithms for Erdős–Rényi $G_{NM}$ graphs with
increasing size with $N$ nodes and $M=5N$ edges, so that mean degree remains
fixed as $N$ increases. The inset is a logarithmic scale to reveal their
runtimes’ scaling behaviors (see text). Note that Algorithm 1 would
potentially take hundreds of hours for each $N$, so we extrapolated these
times from that required to compute for a single edge, instead of running the
algorithm to completion. In contrast, Algorithm 2 completed in under a minute
for all values of $N$ plotted. (B) We compare the fractional overlap
$|\mathcal{E}^{(\ell)}\cap\tilde{\mathcal{E}}^{(\ell)}|/\ell$ for the $\ell$
top-ranked edges for the two rankings $R_{pq}$ and $\tilde{R}_{pq}$ in a
$G_{NM}$ graph with $N=100$ nodes and $M=1000$ edges. The inset shows that
they are strongly correlated: $R_{pq}\approx\tilde{R}_{pq}$ for all edges
$(p,q)\in\mathcal{E}$. We computed a Pearson correlation coefficient of
$0.996$.

In Fig. 1(A), we support our predictions for the computational complexity for
both algorithms by studying the scaling behavior for the algorithms’ runtimes
for graphs of increasing size $N$. We considered Erdős–R’ényi $G_{NM}$ graphs
with $N$ nodes and $M=N\langle d\rangle/2$ edges, where $\langle d\rangle=10$
is the mean degree. We then generated a sequence of graphs with increasing
size $N$, and for each graph we empirically estimated the runtime required to
compute the rankings $R_{pq}$ and $\tilde{R}_{pq}$. For the approximate
rankings $\\{\tilde{R}_{pq}\\}$, we computed them directly using Algorithm 2.
However, we found that it was computationally infeasible to directly run
Algorithm 1 for these graphs with sizes $N>2000$, and so we instead estimated
the algorithms’ runtime by measuring the time required to compute $Q_{pq}$ for
a single edge. Then we approximated the total run time by multiplying this
duration by $M$, since the algorithm requires us to compute $Q_{pq}$ for all
edges. We considered $N\in[2000,10^{4}]$ and found that in all cases Algorithm
2 completes in less than a minute, whereas Algorithm 1 would take hundreds of
hours to perform all of these computations (i.e., were we to attempt running
it in its entirety). The subpanel in Fig. 1(A) showing the runtimes in a log-
log scale, and we applied least-squares linear fits to empirically estimate
the runtime complexities to be $\mathcal{O}(MN^{2.99})$ for Algorithm 1 and
$\mathcal{O}(MN^{0.26})$ for Algorithm 2. We remark that the sub-linear
scaling with $N$ may be occurring as a result of NumPy utilizing strides [50],
which is known to decrease the runtime complexity for vector operations on
their data structures [119].

In Fig. 1(B), we provide evidence to support our claim that the approximate
and true rankings are similar: $\tilde{R}_{pq}\approx R_{pq}$. Here, we
computed the rankings ${R}_{pq}$ and $\tilde{R}_{pq}$ for an Erdős–Rényi
$G_{NM}$ graph with $N=100$ nodes and $M=1000$ edges. For each set of
rankings, we considered $\ell$ top-ranked edges and measured the _fractional
overlap_ between these two sets, or more precisely, the size of their overlap.
That is, letting ${\mathcal{E}}^{(\ell)}$ and $\tilde{\mathcal{E}}^{(\ell)}$
be the sets of top-ranked edges according to $R_{pq}$ and $\tilde{R}_{pq}$,
respectively, we plot
${|\mathcal{E}^{(\ell)}\cap\tilde{\mathcal{E}}^{(\ell)}|}/{\ell}$ versus the
set size $\ell$. Note that this is a fraction that lies between 0 and 1, since
the sets of top-ranked edges have the same cardinality:
$\ell=|{\mathcal{E}}^{(\ell)}|=|\tilde{\mathcal{E}}^{(\ell)}|$. Observe in
Fig. 1(B) that this fraction is very large for many values of $\ell$, implying
that the rankings $\\{R_{pq}\\}$ and $\\{\tilde{R}_{pq}\\}$ are very similar
for this graph. This is further shown in the subplot, where we provide a
scatter plot that compares $\tilde{R}_{pq}$ versus ${R}_{pq}$ for each edge
$(p,q)\in\mathcal{E}$.

Given the similarity between rankings $\\{R_{pq}\\}$ and
$\\{\tilde{R}_{pq}\\}$, and the observation that computing $\\{R_{pq}\\}$
directly using Algorithm 1 is inefficient (or infeasible) for large graphs, we
will focus our attention to studying the approximate rankings
$\\{\tilde{R}_{pq}\\}$ given by Algorithm 2 for the remainder of this paper.

##  4 Three empirical case studies reveal structural/dynamical mechanisms that
influence the importance of edges

Here, we apply our VNE-based measures for edge importance to three empirical
network datasets: (Sec. 4.1) a voting-similarity network for the U.S. Senate,
(Sec. 4.2) a multimodal transportation system, and (Sec. 4.3) a multiplex
brain network. In each empirical network, we will show that the edges that are
deemed most important can drastically change by considering different
timescale parameters $\beta$. In so doing, we will examine the crucial role
that is played by the interplay between $\beta$ and some network property:
(Sec. 4.1) community structure due to political polarization, (Sec. 4.2) edge
weights that encode different speeds along roads and metro lines, and (Sec.
4.3) the strength of coupling between layers of a multiplex network.

###  4.1 U.S. Senate voting-similarity network with community structure

In our first experiment, we study the importance of edges according to
Algorithm 2 for a network that encodes voting similarity among U.S. Senators,
and we will compare the rankings of _interparty edges_ that connect Senators
in different parties to the rankings of _intraparty edges_ between Senators in
the same party. More generally, we ask the following: which edges are most
important in a graph that contains community structure, the edges between
communities or the ones inside of communities? As we shall show, the answer
will depend sensitively on the timescale of the dynamics considered.

For brevity, we defer a detailed description of the voting-similarity network
that we study to Appendix C. Here, we provide a summary. We created a Python
Module called _VoteView-python_ [60] that extracts data from the VoteView
repository [67] that summarizes the voting records of members of the U.S.
Congress. Following techniques similar to those in [120, 75, 74], we
constructed a graph with an associated adjacency matrix such that each entry
$A_{ij}$ encodes the fraction of bills in which Senators $i$ and $j$ vote
identically. We restrict our attention to the 117th U.S. Senate considering
bills from January 3, 2021 until June 30, 2022 (noting that the 117th Congress
had not yet concluded when we conducted this experiment.) We also thresholded
the matrix, setting $A_{ij}$ to zero for any fraction less than $0.4$. The
resulting procedure yielded a graph with $N=100$ nodes and
$|\mathcal{E}|=2,656$ undirected, weighted edges. Due to strong party
polarization, the graph contains two large-scale communities that indicate,
respectively, the Republican and Democratic parties. (Independents are
incorporated into the community associated with the Democrats, in agreement
with how those two Senators currently caucus.)

Figure 2:  Rankings of inter- and intraparty edges for a polarized political
network. (A) We visualize the rankings $\tilde{R}_{pq}$ of edges given by
Algorithm 2 using grayscale for a graph that encodes voting similarity among
the 117th U.S. Senate. The three columns depict three choices of timescale
parameter $\beta$. Nodes represent Senators and the node colors red and blue
indicate, respectively, the two major political parties: Republicans and
Democrats (including independents). (B) For the same three values of $\beta$,
we plot empirically measured distributions $p(H^{\prime}(0))$ of the
approximate change $H^{\prime}(0)$ to diffusion-kernel VNE given by Eq. (26).
In each panel, we show two distributions: one in which $p(H^{\prime}(0))$ is
measured across intraparty edges, and one in which $p(H^{\prime}(0))$ is
measured across interparty edges. (C) The solid black curve depicts the mean
rank $\langle\tilde{R}_{pq}\rangle_{inter}$ across interlayer edges versus
$\beta$. The colored curves indicate the values of
$\langle\tilde{R}_{pq}\rangle_{inter}$ for a comparable random-graph model
with two communities and different amounts of connectivity between communities
(see text). Our main finding is that the interparty edges have the top
rankings for larger $\beta$, the lowest rankings for intermediate $\beta$, and
intermediate rankings for smaller $\beta$.

In Fig. 2, we study the effect of $\beta$ on the rankings $\tilde{R}_{pq}$
given by Algorithm 2 for intralayer and interlayer edges for the voting-
similarity network. In Fig. 2(A), we visualize the voting-similarity network
and use edge color (in grayscale) to depict the $\tilde{R}_{pq}$ values for
three choices for $\beta\in\\{10^{-2},10^{-1},10^{0}\\}$. Senators’ party
affiliations (i.e., Republican vs. Democrats and independents) are indicated
by the node colors (red vs. blue). Observe that the resulting network contains
two well-separated communities due to party polarization. That said, there is
an arrow pointing to a set of Senators $\\{$Susan Collins (R), Lisa Murkowski
(R), Rob Portman (R), Mitt Romney (R), Shelley Capito (R), Lindsey Graham
(R)$\\}$ whose voting patterns are not as strongly polarized along party
lines. These Senators are found to have many edges to both Republicans and
Democrats, and as such, their node degrees are approximately 12x higher than
those for other Senators.

Observe in the right-most column of Fig. 2(A) for $\beta=1$ that the top-
ranked edges are the interparty edges that connect Senators in different
political parties. Interestingly, for $\beta=10^{-1}$ (center column) the
interparty edges are the ones with the lowest rankings, and for
$\beta=10^{-2}$ (left column) the rankings of interparty and intraparty edges
are similar. This nonlinear effect of $\beta$ on $\tilde{R}_{pq}$ is further
supported in panels (B) and (C). In Fig. 2(B), we display a probability
distribution $P(H^{\prime}(0))$ of our approximate perturbations
$H^{\prime}(0)$ given by Eq. (26) for the same three values of $\beta$.
Particularly, we separate the distributions according to interparty edges
(gold) and intraparty edges (grey). For small $\beta$, these two distributions
have a similar support. For medium $\beta$, we observe that the perturbations
to VNE due to removing intraparty edges are larger than those for interparty
edges. Similar to panel (A), we observe for large $\beta$ that the ordering
flips—that is, the largest perturbations are now due to the removal of
interparty edges as opposed to intraparty edges. These findings corroborate
our network visualization in panel (A). Lastly, in Fig. 2(C) we use a solid
black curve to plot the average ranking $\langle\tilde{R}_{pq}\rangle_{inter}$
of interparty edges as a function of $\beta$. As expected based on our
findings in panels (A) and (B), $\langle\tilde{R}_{pq}\rangle_{inter}$ takes
on an intermediate value for small $\beta$, is very large for a medium value
of $\beta$, and then is very small for large $\beta$.

To gain theoretical insight, in Fig. 2(C) we also plot
$\langle\tilde{R}_{pq}\rangle_{inter}$ values for a comparable random-graph
model yield graphs with two communities, each containing 50 nodes (see the
colored dotted, dot-dashed, and dashed curves). Specifically, we study a
stochastic block model with $N=100$ nodes and with two communities of equal
size. Nodes $\\{1,\dots,50\\}$ are assigned to community 1 and nodes
$\\{51,\dots,100\\}$ are assigned to community 2. Then, we create
_intracommunity edges_ between pairs of nodes in the same community uniformly
at random with probability $p_{in}$ and _intercommunity edges_ are created
between pairs of nodes in different communities uniformly at random with
probability $p_{out}$. We fix the mean $\left(p_{in}+p_{out}\right)/2$ so that
the expected number of edges, $N(N-1)\left(p_{in}+p_{out}\right)/2$, matches
that for the voting similarity network. We then considered three choices for
the difference $(p_{in}-p_{out})\in\\{0.25,0.575,0.911\\}$, which is a measure
for structural polarization (also called community prevalence [111]). We note
that the last value, 0.911, closely matches the empirically measured
difference in edge probability for intraparty and interparty edges for the
voting-similarity network. And in fact, stochastic block models are a popular
graphical model for political polarization [96] and other sources for
community structure [85, 1]. In Fig. 2(C), we plot
$\langle\tilde{R}_{pq}\rangle_{inter}$ (now corresponding to intercommunity
edges) for three choices of $(p_{in}-p_{out})$. Observe for the larger two
values of $(p_{in}-p_{out})$ that as $\beta$ increases, the average
$\langle\tilde{R}_{pq}\rangle_{inter}$ exhibits a peak and then becomes very
small. This phenomenon is very similar to what we observe for the voting
similarity network (black solid curve). Thus, this behavior for rankings
$\tilde{R}_{pq}$ appears to occur due to the presence of community structure
(that is, and not due to some other possible structural property of the
empirical voting-similarity network).

###  4.2 Multimodal transportation system with roads and metro lines that have
different speeds

In our next case study, we study the importance of edges for a multimodal
transportation network that encodes roads and metro lines in London [106]. In
this data (which is available at [104]), vertices represent intersections and
there are two types of edges to encode these two mode of transportation.
Notably, the metro lines connect 11 major stations in London, their locations
were mapped to the nearest road intersection.

Given these two types of edges, in this section we study which has higher
rankings, roads or metro lines, and we investigate how these rankings
$\tilde{R}_{pq}$ change as one varies the relative speed between roads and
metro lines. That is, in addition to studying how the rankings
$\tilde{R}_{pq}$ change for different values of the timescale parameter
$\beta$, we will also introduce _balancing parameter_ $\chi\in[0,1]$ that
controls the extent to which metro lines are faster or slower than roads. More
specifically, we define an undirected, weighted transportation network with an
adjacency matrix

(29) $\displaystyle{\bf A}=\chi{\bf A}_{metro}+\left(1-\chi\right){\bf
A}_{road},$

where ${\bf A}_{metro}$ and ${\bf A}_{road}$ are adjacency matrices in which
edges only encode metro lines and roads, respectively. Note that there is no
diffusion across metro lines (or roads) in the limit $\chi\to 0$ (or $\chi\to
1$). Finally, we note that it is important to study different relative speeds
of roads and metro lines, since it has been shown, for example, to
significantly influence the locations where congestions can occur [102].

In Fig. 3(A), we provide a visualization of the multimodal transportation
network with node locations reflecting their geospatial coordinates (i.e.,
latitudes and longitudes). Thick and thin lines represent metro lines and
roads, respectively, and the edge colors reflect their rankings
$\tilde{R}_{pq}$ for the choices $\chi=0.6$ and $\beta=10^{-1}$. In Fig. 3(B),
we present a similar network visualization, except that we now consider a
larger timescale parameter: $\beta=10^{0}$. By comparing panels (A) and (B),
observe for $\beta=10^{-1}$ that the top-ranked edges are metro lines. In
contrast, metro lines have the lowest rankings for $\beta=10^{0}$.

In Fig. 3(C), we plot the average ranking
$\langle\tilde{R}_{pq}\rangle_{metro}$ across metro lines versus the timescale
parameter $\beta$. The three thick colored curves reflect three choices for
$\chi$. The thin curves depict the $\tilde{R}_{pq}$ values for each individual
metro line. In Fig. 3(D), we show similar information by plotting
$\langle\tilde{R}_{pq}\rangle_{metro}$ versus $\chi$ for a few choices of
$\beta\in[0.01,3]$. Together, panels (C) and (D) highlight that the metro
lines have the top rankings when $\beta$ is sufficiently small and $\chi$ is
sufficiently large. That is, transport across metro lines must be sufficiently
faster than that across roads, and one only considers diffusion at a short
timescale.

From a topological perspective, metro lines introduce long-range, ‘short-cut’
connections across a road network that is largely a two-dimensional geometric
substrate [106]. We find it interesting that the importance of such long-range
edges are so sensitive to timescale. We hypothesize that this phenomenon may
be related to the following observation: if someone moves between two
spatially distant nodes across a small timescale $\beta$, then they must have
traversed a metro line. This is no longer true at a large timescale $\beta$,
since there are many paths that one could take. Thus, one might expect short-
cut edges to have a greater impact on diffusion dynamics (and rankings derived
therefrom) at shorter timescales versus longer timescales.

Figure 3: Transportation network with metro lines and roads having different
speeds. (A) Visualization of a London transportation system in which metro
lines and roads are depicted by thick and thin lines, respectively. Edge
colors depict their rankings $\tilde{R}_{pq}$ for a small timescale
$\beta=10^{-1}$. (B) Same information as panel (A), except for a larger
timescale $\beta=10^{0}$. Observe that the metro lines have the highest
rankings in (A), but the lowest rankings in (B). (C) Thick curves depict the
average edge ranking $\langle\tilde{R}_{pq}\rangle_{metro}$ across metro lines
versus $\beta$ for three choices of the _tuning parameter_ $\chi$ (which
controls whether diffusion is faster over metro lines or roads). Each thin
curve indicates how the ranking $\tilde{R}_{pq}$ for each metro line varies
with $\beta$. (C) Similar information as panel (C), except we now plot
$\langle\tilde{R}_{pq}\rangle_{metro}$ versus $\chi$, and different curves
indicate several choices of $\beta$. In general, we find that metro lines
(which introduce long-range “short-cuts’ across the road network) are the top-
ranked edges provided that $\chi$ is sufficiently large and $\beta$ is
sufficiently small.

###  4.3 Multiplex Brain Network with Interlayer Coupling

In our final case study, we study the importance of edges for a multiplex
brain network in which nodes represent brain regions and different _network
layers_ encode coordinated brain activity patterns at different frequency
bands. Our focus of this section is to investigate how the edge rankings
$\tilde{R}_{pq}$ change as one varies the strength $\omega\geq 0$ of coupling
between layers (as well as the timescale parameter $\beta$).

We study an empirical network obtained from [47] that was constructed from
functional magnetic resonance imaging (fMRI) data in which nodes encode
regions of interest (ROI) in human brains and edges encode a measure for
spectral coherence between fMRI signals that are aggregated across each ROI
[48]. In particular, the frequency content of an fMRI signal for each ROI was
decomposed into different frequency bands, and then coherence relationships
were identified for each frequency band. The result was a set of _network
layers_ in which each layer encodes spectral-coherence relationships at a
particular frequency band.

Figure 4: Multiplex network representing coherent fMRI signals among brain
regions. (A) Toy illustration of a multiplex network with two layers
representing two frequency bands: $\delta$ and $\theta$ waves. The solid black
and red dotted lines represent, respectively, intralayer and interlayer edges.
Interlayer edges are weighted by a coupling strength $\omega\geq 0$. (B)
Average ranking $\langle\tilde{R}_{pq}\rangle_{inter}$ across interlayer edges
versus $\beta$ for several choices of $\omega\in[0.05,5]$. (C) Similar
information as panel (B), except we now consider a synthetic model in which
each layer is an Erdős-Rényi $G_{NM}$ random graph in which $N$ and $M$ match
the values for the empirical network layers. Observe a similar trend in panels
(A) and (B): interlayer edges have the top rankings when $\beta$ is very
large, and these rankings take on their lowest values when $\beta$ has some
intermediate value.

Focusing on the frequency bands of $\delta$-waves (2-4 Hz) and $\theta$-waves
(4.5-7.5 Hz), we considered two adjacency matrices ${\bf A}^{(\delta)}$ and
${\bf A}^{(\theta)}$, respectively. Both matrices are size $N=148$ and encode
two types of relationships among a common set of nodes
$\mathcal{V}=\\{1,\dots,N\\}$. That is, a nonzero matrix entry
${A}^{(\delta)}_{ij}$ encodes a relation between brain regions $i$ and $j$ at
the $\delta$ frequency band, whereas ${A}^{(\theta)}_{ij}$ encodes a similar
spectral-coherence relationship, but at the $\theta$ frequency band. To focus
our study on sparse networks, we also applied a threshold to these matrices as
described in Appendix D. This resulted in each layer containing $M=1,652$
undirected, weighted edges.

Given these two network layers encoded by ${\bf A}^{(\delta)}$ and ${\bf
A}^{(\theta)}$, which we refer to as _intralayer adjacency matrices_ , we then
constructed a two-layer multiplex network by coupling them together.
Specifically, we consider a _supra-adjacency matrix_ [45]

(30) $\mathbb{A}=\begin{bmatrix}{\bf A}^{(\delta)}&0\\\ 0&{\bf
A}^{(\theta)}\end{bmatrix}+\omega\begin{bmatrix}0&{\bf I}\\\ {\bf
I}&0\end{bmatrix},$

where ${\bf I}$ is the identity matrix and $\omega\geq 0$ is an _interlayer
coupling strength_ that tunes how strongly the layers are coupled together.
Coupling matrices in this way is called uniform, diagonal coupling.

As visualized in Fig. 4(A), coupling network layers following Eq. (30)
introduces _interlayer edges_ (red dotted lines) that connect each node $i$ in
the first layer to itself in the second layer. (The two network layers are
indicated by the gray shaded regions, and the set of nodes is the same for
both layers.) That is, there is one interlayer edge connecting each node in
one layer to itself in the other layer. In contrast, we will refer to the
edges encoded by ${\bf A}^{(\delta)}$ and ${\bf A}^{(\theta)}$ as _intralayer
edges_. Notably, interlayer edges have a weight given by $\omega$, whereas the
possible weights for intralayer edges are encoded by the matrix entries in
${\bf A}^{(\delta)}$ and ${\bf A}^{(\theta)}$.

Similar to our study in Sec. 4.1 (where we examined the rankings of interparty
edges), we will now pay particular attention to the rankings $\tilde{R}_{pq}$
of interlayer edges. We ask the following: When do the interlayer edges have
the top rankings? In Fig. 4(B), we plot the average ranking
$\langle\tilde{R}_{pq}\rangle_{inter}$ across interlayer edges versus the
timescale parameter $\beta$. Different curves indicate different choices of
the interlayer coupling strength $\omega\in[0.05,5]$. Observe that the
interlayer edges have the top rankings only when $\beta$ is very large.
Moreover, for intermediate values of $\beta$, there exists a peak that
corresponds to when the interlayer edges obtain their lowest rankings.
Interestingly, these two phenomena are reminiscent of our findings for
interparty edges that we presented in Sec. 4.1. By comparing the different
curves for different $\omega$, we can observe that the peak is sharper for
larger $\omega$ values, whereas it is more of a plateau for smaller $\omega$
(and can even have two optima). In Appendix D, we show that qualitatively
similar results occur for 24 other multiplex brain networks taken from [48].

In Fig. 4(C), we support these findings by studying
$\langle\tilde{R}_{pq}\rangle_{inter}$ for a random-graph model in which the
two layers are given by Erdős-Rényi $G_{NM}$ networks for $N=148$ and
$M=7,052$ in which the number of edges $M$ is chosen so that the numbers of
intralayer edges in each layer matches those for ${\bf A}^{(\delta)}$ and
${\bf A}^{(\theta)}$. We plot $\langle\tilde{R}_{pq}\rangle_{inter}$ versus
$\beta$ for this generative model in Fig. 4(C) for different choices of
$\omega$, where one can observe that the behavior is qualitatively similar
that which was shown in Fig. 4(B). Despite this similarity, there are some
differences between the curves panels (B) and (C), which could result because
the empirical network contains rich structural features (e.g., heterogeneous
weights for intralayer edges and non-random edges) that are lacking from the
simple model that we study in panel (C).

##  5 Discussion

In this paper, we have proposed a centrality measure derived from von Neumann
entropy (VNE) to identify and rank network edges according to their impact on
the spectral complexity of information diffusion over a graph. Our work
complements prior work [42] that similarly uses VNE to obtain a centrality
measure but which only considered the importance of nodes. In Sec. 3.1, we
developed a measure for the importance of each edge $(p,q)\in\mathcal{E}$ by
considering how VNE would change upon its removal. We rank the edges according
to these VNE perturbations, and the resulting top-ranked edge is the one such
that its removal would most increase VNE (and subsequently, most increase the
spectral complexity of information diffusion at timescale $\beta$). Our
approach complements existing centrality measures that are related to
information spreading [37, 59, 32, 31, 61, 62, 66] but which do not consider
the spectral complexity of information diffusion, as measured by VNE.

Because the direct computation of VNE perturbations are computationally
expensive (or infeasible) for large-scale graphs, in Sec. 3.2 we developed an
approximate ranking of edges based on first-order approximation theory that
can efficiently predict these VNE perturbations. That said, we note that the
computational challenges are not fully resolved for VNE-based analyses of
graphs. First, VNE requires one to compute a full set of matrix eigenvalues,
which has a general scaling of $\mathcal{O}(N^{3})$ for graphs with $N$ nodes.
In principle, this poor computational scaling could be mitigated by
incorporating spectral approximation techniques such as those that rely on
message passing [16], subgraph motifs [86, 87], kernel polynomial methods
[121, 28], or random matrix theory [84, 105, 111]. Also, for our goal of
approximating how VNE is perturbed due to structural modifications to a
network, it may be practical to approximate VNE perturbations using only a
subset of eigenvalue perturbations, alleviating the need to compute all
eigenvalues. That said, the number of eigenvalues required to maintain some
level of approximation accuracy would vary greatly depending on the diffusion
timescale $\beta$ that is considered. For example, when $\beta$ is very large,
one would expect that $H^{\prime}(0)$ given by Eq. (26) could be accurately
approximated using only a few of the smallest eigenvalues $\lambda_{i}$ (i.e.,
since $e^{-\beta\lambda_{i}}$ would be negligible for larger eigenvalues).
Here, we intentionally explored a wide range of timescales $\beta$, which can
also be computationally expensive. Thus, it may also be beneficial to develop
methods that explore the $\beta$-parameter space more systematically by
incorporating, e.g., one’s external knowledge about some dynamical,
structural, or preferential criteria.

Despite these challenges, we utilized our approximation theory for perturbed
diffusion-kernel VNE to study the entropic importance of edges via three case
studies with empirical networks to investigate structural/dynamical mechanisms
that can systematically influence the entropic importance of edges. In Sec.
4.1, we studied a network encoding voting similarity in the 117th U.S. Senate
and studied the importance of interparty edges (i.e., those that connect
across the two large-scale communities that result from party polarization).
In Sec. 4.2, we studied a multimodal transportation network and studied the
importance of edges representing metro lines as opposed to those representing
roads. In Sec. 4.3, we studied a multiplex brain network and studied the
importance of interlayer edges that couple network layers versus intralayer
edges that connect nodes within a particular layer. In each of these case
studies, we found that the edges that are deemed to be the most important
drastically change by considering different diffusion timescales (i.e.,
different values of the parameter $\beta$).

Notably, our proposed techniques for measuring the importance of edges with
respect to VNE is expected to have many applications beyond our three cases
studies. As an entropy-based measure, we expect our techniques to help reveal
new ways to leverage information theory to study diverse types of biological,
social, and physical systems. Because diffusion-kernel VNE has a well-defined
interpretation for the diffusion equation [see Eq. (3)], it can also
contribute to the related literature on Laplacian-based algorithms for data
analysis and machine learning [6, 19, 64, 55, 14, 124]. As one example, our
ranking of edges could contribute towards the development of Laplacian-based
algorithms for graph sparsification [100, 101] as well as link prediction [65,
114].

More broadly, our investigation of the multiscale aspects of entropic
importance in this paper (i.e., whereby the most important edges depend
sensitively on the diffusion timescale $\beta$ that is considered) does also
open up new lines of scientific inquiry. For instance, we observed ‘ranking
regimes’ in which the entropic importances of edges remain relatively
insensitive to $\beta$ as well as ‘regime transitions’ in which rankings
drastically change as $\beta$ varies. (See [107, 108] for further discussion
on mutliscale centrality regimes and transitions.) Our case studies explored
three structural scenarios in which such behavior can arise, and it would be
beneficial to develop a deeper understanding in future research. Moreover,
while we focused herein on a formulation of VNE that is related to information
diffusion, our methods could be extended to other applications by considering
other dynamical systems and their related matrices. For example, by
considering a normalized Laplacian matrix $\tilde{{\bf L}}={\bf D}^{-1}{\bf
L}$, VNE-based methods would more appropriately describe information theory
related to continuous-time random walks [22] as opposed to diffusion. One
could also consider spectral entropies relating to adjacency matrices and non-
backtracking matrices [3]. Another direction could involve using Hodge
Laplacian matrices [93, 90, 125] to extend VNE and VNE-related centrality
measures to simplicial complexes (which are a higher-order generalization of
graphs). Common to all of these scenarios, it would be beneficial to consider
how structural modifications impact VNE, how these VNE perturbations can be
used for centrality analysis, and how spectral perturbation theory can support
the development of computationally efficient methodologies.

##  Appendix A Proof of Theorem 3.7

Equation (3.4) establishes that the first-order derivative of VNE can be
expanded in terms of partial derivatives

$H^{\prime}(0)=\left.\sum_{i,j}\dfrac{\partial h}{\partial
f_{i}}\dfrac{\partial
f_{i}}{\partial\lambda_{j}}\dfrac{\partial\lambda_{j}}{\partial\epsilon}\right|_{\epsilon=0},$

where we define VNE as $h({\bf
f})=-\sum_{i}f_{i}(\vec{\lambda})\log_{2}(f_{i}(\vec{\lambda}))$, Our proof
only requires that we solve for these terms. It was shown in [70] that the
first terms are given by

(31) $\displaystyle\dfrac{\partial h}{\partial f_{i}}$
$\displaystyle=-\log_{2}\left(f_{i}(\vec{\lambda})\right)-\frac{1}{\ln\left(2\right)}.$

Considering the diffusion-kernel VNE given by

$f_{i}(\vec{\lambda})=\frac{e^{-\beta\lambda_{i}}}{\sum_{k}e^{-\beta\lambda_{k}}},$

we obtain the derivatives $\partial f_{i}/\partial\lambda_{j}$ separately for
$j=i$ and $j\not=i$. For $j\not=i$, we find

$\displaystyle\dfrac{\partial f_{i}}{\partial\lambda_{j}}$
$\displaystyle=\frac{\left(\sum_{k}e^{-\beta\lambda_{k}}\right)(0)-(e^{-\beta\lambda_{i}})\left(-\beta
e^{-\beta\lambda_{j}}\right)}{\left[\sum_{k}e^{-\beta\lambda_{k}}\right]^{2}}$
$\displaystyle=0+\beta\dfrac{e^{-\beta\lambda_{i}}}{\sum_{k}e^{-\beta\lambda_{k}}}\dfrac{e^{-\beta\lambda_{j}}}{\sum_{k}e^{-\beta\lambda_{k}}}$
(32) $\displaystyle=\beta f_{i}(\vec{\lambda})f_{j}(\vec{\lambda}).$

For $j=i$, we find

$\displaystyle\dfrac{\partial f_{i}}{\partial\lambda_{i}}$
$\displaystyle=\frac{\left(\sum_{k}e^{-\beta\lambda_{k}}\right)(-\beta
e^{-\beta\lambda_{i}})-(e^{-\beta\lambda_{i}})\left(-\beta
e^{-\beta\lambda_{i}}\right)}{\left[\sum_{k}e^{-\beta\lambda_{k}}\right]^{2}}$
$\displaystyle=-\beta\left[\frac{\left(\sum_{k}e^{-\beta\lambda_{k}}\right)(e^{-\beta\lambda_{i}})}{\left[\sum_{k}e^{-\beta\lambda_{k}}\right]^{2}}-\frac{(e^{-\beta\lambda_{i}})\left(e^{-\beta\lambda_{i}}\right)}{\left[\sum_{k}e^{-\beta\lambda_{k}}\right]^{2}}\right]$
(33) $\displaystyle=-\beta
f_{i}(\vec{\lambda})\left(1-f_{i}(\vec{\lambda})\right).$

Combing these results, we obtain

$\displaystyle\sum_{j}\dfrac{\partial
f_{i}}{\partial\lambda_{j}}\dfrac{\partial\lambda_{j}}{\partial\epsilon}$
$\displaystyle=-\beta
f_{i}(\vec{\lambda})\left[\left(1-f_{i}(\vec{\lambda})\right)\frac{\partial\lambda_{i}}{\partial\epsilon}-\sum_{j\neq
i}^{N}f_{j}(\vec{\lambda})\frac{\partial\lambda_{j}}{\partial\epsilon}\right]$
(34) $\displaystyle=-\beta
f_{i}(\vec{\lambda})\left[\frac{\partial\lambda_{i}}{\partial\epsilon}-\sum_{j=1}^{N}f_{j}(\vec{\lambda})\frac{\partial\lambda_{j}}{\partial\epsilon}\right].$

Finally, we use that

(35)
$\left.\dfrac{\partial\lambda_{i}}{\partial\epsilon}\right|_{\epsilon=0}=\lambda_{i}^{\prime}(0)=({\bf
u}^{(i)})^{T}\Delta{L}{\bf u}^{(i)}$

is given by Eq. (12). We combine these terms to recover Eq. (26).

##  Appendix B Numerical validation of Theorem 3.7

Figure 5:  Numerical validation of first-order perturbation theory for
diffusion-kernel VNE. (A) Comparison of $h(L+\Delta L)$ and our first-order
prediction, $h(L)+H^{\prime}(0)$, with $H^{\prime}(0)$ given by Thm. 3.7, for
a perturbed graph. We consider an Erdős-Rényi $G_{NM}$ random graph with
$N=100$ nodes and $M=1500$ unweighted edges, and each perturbation matrix
$\Delta L$ encodes the removal of $k$ edges (recall Lemmas 2.10 and 2.11).
Observe that the first-order approximation becomes less accurate for larger
perturbations (i.e., larger $k$). (B) Numerical validation that the
approximation error $E(\epsilon)\equiv|h(L+\epsilon\Delta L)-[h(L)+\epsilon
H^{\prime}(0)]|$ vanishes in the limit of small $\epsilon$ as
$\mathcal{O}(\epsilon^{2})$, that is, $\log(E(\epsilon))\varpropto
2\log(\epsilon)$. We plot $E(\epsilon)$ for the same network as in panel (A)
in a log-log scale and compute a least-squares linear fit to obtain
empirically measured slopes $\\{2.042,2.022,2.036\\}$, respectively, for three
choices of $k\in\\{1,10,20\\}$. These are all nearly equal to the predicted
slope of 2, supporting our claim that Thm. 3.7 has second-error error.

In Fig. 5, we provide numerical validation for Thm. 3.7. First, we computed
the VNE $h(L)$ of a random graph that was sampled from the Erdős-Rényi
$G_{NM}$ model with $N=100$ nodes and $M=2000$ edges. In Fig. 5(A), we plot
the perturbed VNE $h(L+\Delta L)$ (blue dotted curve) after removal of $k$
edges with $k\in\\{0,\dots,20\\}$. Edges were selected for removal uniformly
at random. For comparison, the red dashed curve depicts our first-order
approximation $h(L+\Delta L)\approx h(L)+H^{\prime}(0)$ with $H^{\prime}(0)$
given by Eq (26). Note that the deletion of edge $(p,q)\in\mathcal{E}$
corresponds to $\epsilon=1$ and $\Delta L=-\Delta L^{(pq)}$, which is defined
in Eq. (16). The $\Delta L$ matrix after the removal of several edges is given
by Eq. (19). We observe that the first-order approximation is more accurate
when the perturbation is smaller (i.e., smaller $k$), as expected.

In Fig. 5(B), we support our claim that the approximation $h(L+\epsilon\Delta
L)\approx h(L)+\epsilon H^{\prime}(0)$ is first-order accurate by showing that
the approximation error has a second-order scaling behavior. Specifically, we
plot the approximation error $E(\epsilon)\equiv|h(L+\epsilon\Delta
L)-[h(L)+\epsilon H^{\prime}(0)]|$ versus $\epsilon$ and find that the error
decays as $\mathcal{O}(\epsilon^{2})$. Note that in a log-log scale, this
scaling corresponds to a linear relationship $\log(E(\epsilon))\varpropto
2\log(\epsilon)$. In Fig. 5(B), we plot $\log(E(\epsilon))$ versus
$\log(\epsilon)$ for three choices of $k\in\\{1,10,20\\}$, and we computed a
least-squares linear fit to each curve. We empirically observed the slopes to
be approximately 2.014, 2.022, and 2.026 for these three lines, respectively.
Because these are all very close to our analytically predicted slope of 2, we
can be confident that our first-order approximation does in fact have second-
order error.

##  Appendix C Further description of the voting similarity network in Sec.
4.1

Here, we describe our construction of an empirical network that encodes voting
similarity among persons in the 117th U.S Senate. We first downloaded voting-
pattern data from VoteView [67] to create a tensor with entries
$\gamma_{ijk}=1$ when Senator $i$ and $j$ vote identically on bill $k$ and
$\gamma_{ijk}=0$ otherwise. Letting $b_{ij}$ denote the number of bills in
which both $i$ and $j$ vote, we define a weighted adjacency matrix with
entries $\tilde{A}_{ij}=\frac{1}{b_{ij}}\sum_{k}\gamma_{ijk}\in[0,1]$
indicating for each pair of Senators the fraction of bills on which they vote
identically. Equivalently, we only sum over bills $k$ in which both $i$ and
$j$ cast a vote. Finally, we obtain a sparse network with an adjacency matrix
${\bf A}$ by applying a threshold $\tau$ to $\tilde{{\bf A}}$. That is, we
define

(36) ${A}_{ij}=\begin{cases}\tilde{A}_{ij},&\tilde{A}_{ij}>\tau\\\
0,&\text{otherwise}.\end{cases}$

After exploring a wide range of $\tau$ values, we selected $\tau=0.40$, that
is a minimum voting-together fraction of $0.40$. The resulting graph is a
weighted voting-similarity network [120, 75, 74] that is undirected, and each
edge $(i,j)$ has a weight $A_{ij}>0.4$.

Figure 6: Network encoding voting similarity among the 117th U.S. Senate. (A)
Visualization of the adjacency matrix ${\bf A}$, where $A_{ij}$ encodes the
fraction of bills in which Senators $i$ and $j$ vote identically (ignoring
fractions less that $0.4$). By sorting node ids by the Senator’s political
affiliations so that nodes $\\{1,\dots,50\\}$ are Republicans and nodes
$\\{51,\dots,100\\}$ are either Democrats or independents, the resulting
2-community structure manifests as two large ‘blocks’ in the matrix. (B)
Histogram depicts the probability distributions for edge weights
$\\{A_{ij}\\}$, which we measure separately across intraparty and interparty
edges.

We note that there are other ways to construct voting-similarity networks,
including, e.g., by restricting attention to non-unanimous roll calls [120] as
opposed to considering all bills (as we have done). Note that for convenience,
we removed Kamala Harris and Kelly Loeffler from the data set because they
participated in the 117th Senate for less than a month before resigning or
being replaced. We also relabeled the independents to be Democrats since the
current independents caucus with the Democrats and because, for simplicity, we
would like to focus this experiment on a network having two communities of
approximately equal size.

Recall from Sec. 4.1 that we would like to compare the rankings
$\tilde{R}_{pq}$ of edges within and between communities, i.e., intraparty and
interparty edges. As such, we selected $\tau=0.4$ so that the resulting
network has few edges between the two communities. In this case, we found 474
interparty edges and 2182 intraparty edges. This occurs due to party
polarization; that is, the vast majority of edges are intraparty edges that
connect Senators having the same party affiliation, whereas relatively few
edges are interparty edges. Since most Senators are Republicans or Democrats
(and the current independents largely act as Democrats in their roll call
voting), the resulting network has two large communities. As shown in Fig.
6(A), these communities manifest as ’blocks’ in the adjacency matrix ${\bf
A}$. In Fig. 6(B), we depict the distributions of edge weights $\\{A_{ij}\\}$,
which we measure separately across intraparty and interparty edges.

##  Appendix D Further description of the multiplex brain network in Sec. 4.3

Here, we provide additional discussion for our experiments with multiplex
brain networks. We first downloaded adjacency matrices that encode network
layers from [47]. See [48] for a paper discussing this data and related
experiments. Each adjacency matrix encodes spectral coherence for a distinct
particular frequency band. Diagonal entries in the matrices are set to zero to
ensure that there are no self-edges. For each network layer, nodes represent
brain regions and weighted edges represent coherence values. The full data
includes six network layers for each person, and there are data for 25 healthy
persons and 25 persons with Alzheimers disease. We focused on two network
layers that represent the frequency bands of $\delta$ and $\theta$ waves by
examining two adjacency matrices ${\bf A}^{(\delta)}$ and ${\bf A}^{(\theta)}$
for the first person in the data set.

In Fig. 7(A), we plot histograms of the coherence values ${A}^{(\delta)}_{ij}$
and ${A}^{(\theta)}_{ij}$ encoded in these two matrices. Because we would like
to study sparse networks, we chose a threshold of $\tau=1.52$ and remove edges
having a weight less than $\tau$. Observe that the two distributions
$p({A}^{(\delta)}_{ij})$ and $p({A}^{(\theta)}_{ij})$ are similar, and so the
two ‘sparsified’ network layers have similar weight distributions and a
similar number of edges.

In Fig. 7(B), we present a plot that is similar to Fig. 4(B). Here, we plot
the mean ranking $\langle\tilde{R}_{pq}\rangle_{inter}$ of interlayer edges
versus timescale parameter $\beta$ for the coupling strength $\omega=1$. The
different curves represent the 25 different healthy human brains in the study,
and the dashed black curve gives the mean curve. Observe that all curves are
qualitatively similar, suggesting that the effect of $\beta$ on edges’
entropic importance is robust across the brain data.

Figure 7: Multiplex network encoding spectral coherence among brain regions.
(A) Histograms depicting the probability distributions edges weights
$\\{A_{ij}^{(\delta)}\\}$ and $\\{A_{ij}^{(\theta)}\\}$ for two network layers
encoding spectral-coherence relations among the fMRI activity brain regions at
two frequency bands. (B) We plot the mean ranking
$\langle\tilde{R}_{pq}\rangle_{inter}$ of interlayer edges versus timescale
parameter $\beta$ the coupling strength $\omega=1$. Different curves represent
the 25 healthy human brains in the data set [47, 48]. The black dashed line
depicts the mean curve.

## References

  * [1] Emmanuel Abbe, Community detection and stochastic block models: recent developments, The Journal of Machine Learning Research, 18 (2017), pp. 6446–6531.
  * [2] Stefano Allesina and Mercedes Pascual, Googling food webs: Can an eigenvector measure species’ importance for coextinctions?, PLoS Computational Biology, 5 (2009), p. e1000494.
  * [3] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin, Non-backtracking random walks mix faster, Communications in Contemporary Mathematics, 9 (2007), pp. 585–603.
  * [4] Kartik Anand, Ginestra Bianconi, and Simone Severini, Shannon and von neumann entropy of random networks with heterogeneous expected degree, Physical Review E, 83 (2011), p. 036109.
  * [5] Kendall E Atkinson, An introduction to numerical analysis, John Wiley & Sons, 2008.
  * [6] Mikhail Belkin and Partha Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in Neural Information Processing Systems, 14 (2001).
  * [7] Barbara Benigni, Arsham Ghavasieh, Alessandra Corso, Valeria d’Andrea, and Manlio De Domenico, Persistence of information flow: A multiscale characterization of human brain, Network Neuroscience, 5 (2021), pp. 831–850.
  * [8] Austin R Benson, Three hypergraph eigenvector centralities, SIAM Journal on Mathematics of Data Science, 1 (2019), pp. 293–312.
  * [9] Giulia Bertagnolli, Claudio Agostinelli, and Manlio De Domenico, Network depth: identifying median and contours in complex networks, Journal of Complex Networks, 8 (2020), p. cnz041.
  * [10] Stephen P Borgatti, Centrality and network flow, Social networks, 27 (2005), pp. 55–71.
  * [11] Ulrik Brandes, A faster algorithm for betweenness centrality, Journal of mathematical sociology, 25 (2001), pp. 163–177.
  * [12] Samuel L Braunstein, Sibasish Ghosh, and Simone Severini, The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states, Annals of Combinatorics, 10 (2006), pp. 291–317.
  * [13] Sergey Brin and Lawrence Page, The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems, 30 (1998), pp. 107–117.
  * [14] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst, Geometric deep learning: going beyond euclidean data, IEEE Signal Processing Magazine, 34 (2017), pp. 18–42.
  * [15] Thomas Callaghan, Peter J Mucha, and Mason A Porter, Random walker ranking for ncaa division ia football, The American Mathematical Monthly, 114 (2007), pp. 761–777.
  * [16] George T. Cantwell and M. E. J. Newman, Message passing on networks with loops, Proceedings of the National Academy of Sciences, 116 (2019), pp. 23398–23403.
  * [17] Vanniarajan Chellappan and Krishna M Sivalingam, Application of entropy of centrality measures to routing in tactical wireless networks, in 2013 19th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN), IEEE, 2013, pp. 1–6.
  * [18] Aaron Clauset, Samuel Arbesman, and Daniel B Larremore, Systematic inequality and hierarchy in faculty hiring networks, Science Advances, 1 (2015).
  * [19] Ronald R Coifman and Stéphane Lafon, Diffusion maps, Applied and Computational Harmonic analysis, 21 (2006), pp. 5–30.
  * [20] Ronald R Coifman and Mauro Maggioni, Diffusion wavelets, Applied and Computational Harmonic Analysis, 21 (2006), pp. 53–94.
  * [21] Caterina De Bacco, Daniel B Larremore, and Cristopher Moore, A physical model for efficient ranking in networks, Science Advances, 4 (2018), p. eaar8260.
  * [22] Manlio De Domenico and Jacob Biamonte, Spectral entropies as information-theoretic tools for complex network comparison, Physical Review X, 6 (2017), p. 041062.
  * [23] Manlio De Domenico, Vincenzo Nicosia, Alexandre Arenas, and Vito Latora, Structural reducibility of multilayer networks, Nature Communications, 6 (2015).
  * [24] Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez, and Alex Arenas, Ranking in interconnected multilayer networks reveals versatile nodes, Nature Communications, 6 (2015), pp. 1–6.
  * [25] Daryl R DeFord and Scott D Pauls, A new framework for dynamical models on multiplex networks, Journal of Complex Networks, 6 (2018), pp. 353–381.
  * [26] James W. Demmel, Osni A. Marques, Beresford N. Parlett, and Christof VÃ¶mel, Performance and accuracy of lapack’s symmetric tridiagonal eigensolvers, SIAM Journal on Scientific Computing, 30 (2008), pp. 1508–1526.
  * [27] Ying Ding, Erjia Yan, Arthur Frazho, and James Caverlee, Pagerank for ranking authors in co-citation networks, Journal of the American Society for Information Science and Technology, 60 (2009), pp. 2229–2243.
  * [28] Kun Dong, Austin R Benson, and David Bindel, Network density of states, in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019, pp. 1152–1161.
  * [29] Peter G Doyle and J Laurie Snell, Random walks and electric networks, vol. 22, American Mathematical Soc., 1984.
  * [30] Ernesto Estrada, Naomichi Hatano, and Michele Benzi, The physics of communicability in complex networks, Physics Reports, 514 (2012), pp. 89–119.
  * [31] Ernesto Estrada and Desmond J Higham, Network properties revealed through matrix functions, SIAM Review, 52 (2010), pp. 696–714.
  * [32] Ernesto Estrada, Desmond J Higham, and Naomichi Hatano, Communicability betweenness in complex networks, Physica A: Statistical Mechanics and its Applications, 388 (2009), pp. 764–774.
  * [33] Ernesto Estrada and Juan A Rodriguez-Velazquez, Subgraph centrality in complex networks, Physical Review E, 71 (2005), p. 056103.
  * [34] Ernesto Estrada and Grant J Ross, Centralities in simplicial complexes. applications to protein interaction networks, Journal of Theoretical Biology, 438 (2018), pp. 46–60.
  * [35] Miroslav Fiedler, Laplacian of graphs and algebraic connectivity, Banach Center Publications, 25 (1989), pp. 57–70.
  * [36] David Freedman, Markov chains, Springer Science & Business Media, 2012\.
  * [37] Linton C Freeman, A set of measures of centrality based on betweenness, Sociometry, (1977), pp. 35–41.
  * [38] Arsham Ghavasieh, Sebastiano Bontorin, Oriol Artime, Nina Verstraete, and Manlio De Domenico, Multiscale statistical physics of the pan-viral interactome unravels the systemic nature of sars-cov-2 infections, Communications Physics, 4 (2021), pp. 1–13.
  * [39] Arsham Ghavasieh and Manlio De Domenico, Enhancing transport properties in interconnected systems without altering their structure, Physical Review Research, 2 (2020), p. 013155.
  * [40] A Ghavasieh and M De Domenico, Statistical physics of network structure and information dynamics, Journal of Physics: Complexity, 3 (2022), p. 011001.
  * [41] Arsham Ghavasieh, Carlo Nicolini, and Manlio De Domenico, Statistical physics of complex information dynamics, Physical Review E, 102 (2020), p. 052304.
  * [42] Arsham Ghavasieh, Massimo Stella, Jacob Biamonte, and Manlio De Domenico, Unraveling the effects of multiscale network entanglement on empirical systems, Communications Physics, 4 (2021), pp. 1–10.
  * [43] Michelle Girvan and Mark EJ Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, 99 (2002), pp. 7821–7826.
  * [44] David F Gleich, Pagerank beyond the web, Siam Review, 57 (2015), pp. 321–363.
  * [45] Sergio Gomez, Albert Diaz-Guilera, Jesus Gomez-Gardenes, Conrad J Perez-Vicente, Yamir Moreno, and Alex Arenas, Diffusion dynamics on multiplex networks, Physical Review Letters, 110 (2013), p. 028701.
  * [46] Felipe Grando, Lisandro Z Granville, and Luis C Lamb, Machine learning in network centrality measures: Tutorial and outlook, ACM Computing Surveys (CSUR), 51 (2018), pp. 1–32.
  * [47] Jérémy Guillon, Codebase: Brain Network Toolbox https://github.com/brain-network/bnt, 2016.
  * [48] Jérémy Guillon, Yohan Attal, Olivier Colliot, Valentina La Corte, Bruno Dubois, Denis Schwartz, Mario Chavez, and Fabrizio de Vico Fallani, Loss of brain inter-frequency hubs in alzheimer’s disease, Scientific reports, 7 (2017), pp. 1–13.
  * [49] Roger Guimera, Stefano Mossa, Adrian Turtschi, and LA Nunes Amaral, The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles, Proceedings of the National Academy of Sciences, 102 (2005), pp. 7794–7799.
  * [50] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant, Array programming with NumPy, Nature, 585 (2020), pp. 357–362.
  * [51] Paul Hines and Seth Blumsack, A centrality measure for electrical networks, in Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), IEEE, 2008, pp. 185–185.
  * [52] Federico Holik, Angel Plastino, and Manuel Sáenz, Natural information measures in cox’approach for contextual probabilistic theories, arXiv preprint arXiv:1504.01635, (2015).
  * [53] Petter Holme, Congestion and centrality in traffic flow on complex networks, Advances in Complex Systems, 6 (2003), pp. 163–176.
  * [54] Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai, Lethality and centrality in protein networks, Nature, 411 (2001), pp. 41–42.
  * [55] Lucas GS Jeub, Prakash Balachandran, Mason A Porter, Peter J Mucha, and Michael W Mahoney, Think locally, act locally: Detection of small, medium-sized, and large communities in large networks, Physical Review E, 91 (2015), p. 012821.
  * [56] Ferenc Jordán, Zsófia Benedek, and János Podani, Quantifying positional importance in food webs: a comparison of centrality indices, Ecological Modelling, 205 (2007), pp. 270–275.
  * [57] Christian E. Kampmann, Feedback loop gains and system behavior, in Proceedings of the 1996 International System Dynamics Conference, System Dynamics Society Cambridge, MA, 1996, pp. 21–25.
  * [58] Christian E. Kampmann and Rogelio Oliva, Loop eigenvalue elasticity analysis: three case studies, System Dynamics Review: The Journal of the System Dynamics Society, 22 (2006), pp. 141–162.
  * [59] Leo Katz, A new status index derived from sociometric analysis, Psychometrika, 18 (1953), pp. 39–43.
  * [60] Jeremy Kazimer, Voteview python: A python module for data extraction and network analysis https://github.com/k-z-m-r/voteview-python, 2021.
  * [61] David Kempe, Jon Kleinberg, and Éva Tardos, Maximizing the spread of influence through a social network, in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 137–146.
  * [62] Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán A Makse, Identification of influential spreaders in complex networks, Nature Physics, 6 (2010), pp. 888–893.
  * [63] Jon M Kleinberg, Mark Newman, Albert-László Barabási, and Duncan J Watts, Authoritative sources in a hyperlinked environment, Princeton University Press, 2011.
  * [64] Kyle Kloster and David F Gleich, Heat kernel based community detection, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014, pp. 1386–1395.
  * [65] Jérôme Kunegis and Andreas Lommatzsch, Learning spectral graph transformations for link prediction, in Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 561–568.
  * [66] Sune Lehmann and Yong-Yeol Ahn, Complex Spreading Phenomena in Social Systems, Springer, 2018.
  * [67] Jeffrey B Lewis, Keith Poole, Howard Rosenthal, Adam Boche, Aaron Rudkin, and Luke Sonnet, Voteview: Congressional roll-call votes database, See https://voteview. com/(accessed 27 July 2018), (2018).
  * [68] Huan Li and Zhongzhi Zhang, Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms, CoRR, abs/1708.05959 (2017).
  * [69] Yichuan Li, Weihong Cai, Yao Li, and Xin Du, Key node ranking in complex networks: A novel entropy and mutual information-based approach, Entropy, 22 (2020).
  * [70] Zichao Li, Peter J Mucha, and Dane Taylor, Network-ensemble comparisons with stochastic rewiring and von Neumann entropy, SIAM Journal on Applied Mathematics, 78 (2018), pp. 897–920.
  * [71] Stephen B Maurer, Matrix generalizations of some theorems on trees, cycles and cocycles in graphs, SIAM Journal on Applied Mathematics, 30 (1976), pp. 143–148.
  * [72] T Mendes-Santos, G Giudici, R Fazio, and M Dalmonte, Measuring von neumann entanglement entropies without wave functions, New Journal of Physics, 22 (2020), p. 013044.
  * [73] Attilio Milanese, Jie Sun, and Takashi Nishikawa, Approximating spectral impact of structural perturbations in large networks, Physical Review E, 81 (2010), p. 046112.
  * [74] James Moody and Peter J Mucha, Portrait of political party polarization, Network Science, 1 (2013), pp. 119–121.
  * [75] Peter J Mucha and Mason A Porter, Communities in multislice voting networks, Chaos: An Interdisciplinary Journal of Nonlinear Science, 20 (2010), p. 041108.
  * [76] Johann v Neumann, Mathematische grundlagen der quantenmechanik, vol. 38, Springer-Verlag, 2013.
  * [77] Mark EJ Newman, Networks: An introduction, Oxford University Press, 2010\.
  * [78] Carlo Nicolini, Giulia Forcellini, Ludovico Minati, and Angelo Bifone, Scale-resolved analysis of brain functional connectivity networks with spectral entropy, NeuroImage, 211 (2020), p. 116603.
  * [79] Alexander G. Nikolaev, Raihan Razib, and Ashwin Kucheriya, On efficient use of entropy centrality for social network analysis and community detection, Social Networks, 40 (2015), pp. 154–162.
  * [80] Raj Kumar Pan and Jari Saramäki, Path lengths, correlations, and centrality in temporal networks, Physical Review E, 84 (2011), p. 016105.
  * [81] Juyong Park and Mark EJ Newman, A network-based ranking system for us college football, Journal of Statistical Mechanics: Theory and Experiment, 2005 (2005), p. P10014.
  * [82] Filippo Passerini and Simone Severini, The von neumann entropy of networks, arXiv preprint arXiv:0812.2597, (2008).
  * [83] Louis M Pecora and Thomas L Carroll, Master stability functions for synchronized coupled systems, Physical Review Letters, 80 (1998), p. 2109.
  * [84] Tiago P Peixoto, Eigenvalue spectra of modular networks, Physical Review Letters, 111 (2013), p. 098701.
  * [85] , Nonparametric bayesian inference of the microcanonical stochastic block model, Physical Review E, 95 (2017), p. 012317.
  * [86] Victor M Preciado and Ali Jadbabaie, From local measurements to network spectral properties: Beyond degree distributions, in 49th IEEE Conference on Decision and Control (CDC), IEEE, 2010, pp. 2686–2691.
  * [87] , Moment-based spectral analysis of large-scale networks using local structural information, IEEE/ACM Transactions on Networking, 21 (2012), pp. 373–382.
  * [88] Tong Qiao, Wei Shan, Ganjun Yu, and Chen Liu, A novel entropy-based centrality approach for identifying vital nodes in weighted networks, Entropy, 20 (2018).
  * [89] Juan G Restrepo, Edward Ott, and Brian R Hunt, Characterizing the dynamical importance of network nodes and links, Physical Review Letters, 97 (2006), p. 094102.
  * [90] Emily Ribando-Gros, Rui Wang, Jiahui Chen, Yiying Tong, and Guo-Wei Wei, Graph and hodge laplacians: Similarity and difference, arXiv preprint arXiv:2204.12218, (2022).
  * [91] Julie Rushmore, Damien Caillaud, Richard J Hall, Rebecca M Stumpf, Lauren Ancel Meyers, and Sonia Altizer, Network-based vaccination improves prospects for disease control in wild chimpanzees, Journal of the Royal Society Interface, 11 (2014), p. 20140349.
  * [92] Serguei Saavedra, Scott Powers, Trent McCotter, Mason A Porter, and Peter J Mucha, Mutually-antagonistic interactions in baseball networks, Physica A: Statistical Mechanics and its Applications, 389 (2010), pp. 1131–1141.
  * [93] Michael T Schaub, Austin R Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie, Random walks on simplicial complexes and the normalized hodge 1-laplacian, SIAM Review, 62 (2020), pp. 353–391.
  * [94] Benjamin M Schmidt and Matthew M Chingos, Ranking doctoral programs by placement: A new method, PS: Political Science & Politics, 40 (2007), pp. 523–529.
  * [95] Leah B Shaw and Ira B Schwartz, Enhanced vaccine control of epidemics in adaptive networks, Physical Review E, 81 (2010), p. 046120.
  * [96] Snehal M Shekatkar and Sukratu Barve, Importance of initial conditions in the polarization of complex networks, EPL (Europhysics Letters), 122 (2018), p. 38002.
  * [97] Per Sebastian Skardal, Dane Taylor, and Jie Sun, Optimal synchronization of complex networks, Physical Review Letters, 113 (2014), p. 144101.
  * [98] Albert Solé-Ribalta, Manlio De Domenico, Sergio Gómez, and Alex Arenas, Random walk centrality in interconnected multilayer networks, Physica D: Nonlinear Phenomena, 323 (2016), pp. 73–79.
  * [99] Zhao Song and Dane Taylor, Asymmetric coupling optimizes interconnected consensus systems, arXiv preprint arXiv:2106.13127, (2021).
  * [100] Daniel A Spielman and Nikhil Srivastava, Graph sparsification by effective resistances, SIAM Journal on Computing, 40 (2011), pp. 1913–1926.
  * [101] Daniel A Spielman and Shang-Hua Teng, Spectral sparsification of graphs, SIAM Journal on Computing, 40 (2011), pp. 981–1025.
  * [102] Emanuele Strano, Saray Shai, Simon Dobson, and Marc Barthelemy, Multiplex networks in metropolitan areas: generic features and local effects, Journal of The Royal Society Interface, 12 (2015), p. 20150651.
  * [103] Frank W Takes and Eelke M Heemskerk, Centrality in the global network of corporate control, Social Network Analysis and Mining, 6 (2016), pp. 1–18.
  * [104] Dane Taylor, Data release: London transit network https://sites.google.com/site/danetaylorresearch/data, 2015.
  * [105] Dane Taylor, Rajmonda S Caceres, and Peter J Mucha, Super-resolution community detection for layer-aggregated multilayer networks, Physical Review X, 7 (2017), p. 031056.
  * [106] Dane Taylor, Florian Klimm, Heather A. Harrington, Miroslav KramÃ¡r, Konstantin Mischaikow, Mason A. Porter, and Peter J. Mucha, Topological data analysis of contagion maps for examining spreading processes on networks, Nature Communications, 6 (2015).
  * [107] Dane Taylor, Sean A Myers, Aaron Clauset, Mason A Porter, and Peter J Mucha, Eigenvector-based centrality measures for temporal networks, Multiscale Modeling & Simulation, 15 (2017), pp. 537–574.
  * [108] Dane Taylor, Mason A Porter, and Peter J Mucha, Tunable eigenvector-based centralities for multiplex and temporal networks, Multiscale Modeling & Simulation, 19 (2021), pp. 113–147.
  * [109] Dane Taylor and Juan G Restrepo, Network connectivity during mergers and growth: optimizing the addition of a module, Physical Review E, 83 (2011), p. 066112.
  * [110] Dane Taylor and Juan G. Restrepo, Network connectivity during mergers and growth: Optimizing the addition of a module, Physical Review E, 83 (2011).
  * [111] Dane Taylor, Saray Shai, Natalie Stanley, and Peter J Mucha, Enhanced detectability of community structure in multilayer networks through layer aggregation, Physical Review Letters, 116 (2016), p. 228301.
  * [112] Dane Taylor, Per Sebastian Skardal, and Jie Sun, Synchronization of heterogeneous oscillators under network modifications: Perturbation and optimization of the synchrony alignment function, SIAM Journal on Applied Mathematics, 76 (2016), pp. 1984—2008.
  * [113] Hanghang Tong, B Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos, Gelling, and melting, large graphs by edge manipulation, in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012, pp. 245–254.
  * [114] Leo Torres, Kevin S Chan, and Tina Eliassi-Rad, Glee: Geometric laplacian eigenmap embedding, Journal of Complex Networks, 8 (2020), p. cnaa007.
  * [115] Francesco Tudisco, Francesca Arrigo, and Antoine Gautier, Node and layer eigenvector centralities for multiplex networks, SIAM Journal on Applied Mathematics, 78 (2018), pp. 853–876.
  * [116] Francesco Tudisco and Desmond J Higham, Node and edge nonlinear eigenvector centrality for hypergraphs, Communications Physics, 4 (2021), pp. 1–10.
  * [117] Frank Tutzauer, Entropy as a measure of centrality in networks characterized by path-transfer flow, Social Networks, 29 (2007), pp. 249–265.  Special Section: Advances in Exponential Random Graph (p*) Models.
  * [118] Frank Tutzauer and Benjamin S. Elbirt, Entropy-based centralization and its sampling distribution in directed communication networks, Communication Monographs, 76 (2009), pp. 351 – 375.
  * [119] Stefan van der Walt, S. Chris Colbert, and Gael Varoquaux, The numpy array: A structure for efficient numerical computation, Computing in Science Engineering, 13 (2011), pp. 22–30.
  * [120] Andrew Scott Waugh, Liuyi Pei, James H Fowler, Peter J Mucha, and Mason A Porter, Party polarization in congress: A network science approach, arXiv preprint arXiv:0907.3509, (2009).
  * [121] Alexander Weiße, Gerhard Wellein, Andreas Alvermann, and Holger Fehske, The kernel polynomial method, Reviews of modern physics, 78 (2006), p. 275.
  * [122] Mark M Wilde, Quantum information theory, Cambridge University Press, 2013.
  * [123] Wen-Long You, Andrzej M. Ole/’s, and Peter Horsch, von neumann entropy spectra and entangled excitations in spin-orbital models, Physical Review B, 86 (2012).
  * [124] Hao Zhu, Ke Sun, and Peter Koniusz, Contrastive laplacian eigenmaps, Advances in Neural Information Processing Systems, 34 (2021), pp. 5682–5695.
  * [125] Cameron Ziegler, Per Sebastian Skardal, Haimonti Dutta, and Dane Taylor, Balanced hodge laplacians optimize consensus dynamics over simplicial complexes, Chaos: An Interdisciplinary Journal of Nonlinear Science, 32 (2022), p. 023128.