# A Fast Algorithm for Moderating Critical Nodes via Edge Removal

Changan Liu, Xiaotian Zhou, Ahad N. Zehmakan, and Zhongzhi Zhang,  This work
was supported by the National Natural Science Foundation of China (No.
U20B2051 and No. 62372112). (Corresponding author: Zhongzhi Zhang.) Changan
Liu, Xiaotian Zhou, and Zhongzhi Zhang are with Shanghai Key Laboratory of
Intelligent Information Processing, School of Computer Science, Fudan
University, Shanghai 200433, China. Changan Liu is also with Center for
Complex Decision Analysis, Fudan University, Shanghai 200433, China.
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Ahad N. Zehmakan is with the School of Computing, the
Australian National University, Canberra, Australia.
E-mail<EMAIL_ADDRESS>Manuscript received xxxx; revised xxxx.

###### Abstract

Critical nodes in networks are extremely vulnerable to malicious attacks to
trigger negative cascading events such as the spread of misinformation and
diseases. Therefore, effective moderation of critical nodes is very vital for
mitigating the potential damages caused by such malicious diffusions. The
current moderation methods are computationally expensive. Furthermore, they
disregard the fundamental metric of information centrality, which measures the
dissemination power of nodes.

We investigate the problem of removing $k$ edges from a network to minimize
the information centrality of a target node $v$ while preserving the network’s
connectivity. We prove that this problem is computationally challenging: it is
NP-complete and its objective function is not supermodular. However, we
propose three approximation greedy algorithms using novel techniques such as
random walk-based Schur complement approximation and fast sum estimation. One
of our algorithms runs in nearly linear time in the number of edges.

To complement our theoretical analysis, we conduct a comprehensive set of
experiments on synthetic and real networks with over one million nodes. Across
various settings, the experimental results illustrate the effectiveness and
efficiency of our proposed algorithms.

###### Index Terms:

Social networks, critical nodes, information diffusion, edge removal,
combinatorial optimization.

##  1 Introduction

A broad range of dynamic processes on graphs have been analyzed to attain a
more profound comprehension of diverse real-world phenomena, such as the
spread of misinformation on online social media platforms, the proliferation
of computer viruses over the internet, and the dissemination of diseases among
individuals [1, 2, 3, 4]. As a result, there has been a burgeoning interest in
investigating the influence of the underlying graph structure on various
characteristics of these dynamic processes [5, 6, 7, 8]. Specifically, a
considerable amount of attention has been focused on comprehending to what
extent certain objectives can be achieved through the manipulation of the
network structure. Examples of such manipulation strategies comprise
eliminating nodes (such as blocking an account on an online social platform or
administering a vaccine to an individual), adding edges (such as link
recommendation in online social networks or constructing a physical link
between two routers), or removing edges (such as restricting two individuals
from meeting through quarantine measures or not exposing the posts from one
user to another in an online platform) [7, 9, 10, 11]. Furthermore, the
intended objective can vary widely, ranging from minimizing the number of
nodes infected by a virus to maximizing the fairness of workload among routers
across different internet service providers, or reducing the proportion of
users exposed to misinformation [2, 11, 12, 4, 13].

The real-world networks exhibit heterogeneous nature with critical nodes being
far more essential in network structure and function [14, 7], such as
information diffusion and system stability [7, 15, 16]. This confers an
unbridled degree of power to such nodes, which could potentially result in
significant financial, sociological, and political damages. For instance,
subsequent to the hack of The Associated Press Twitter account, a false report
was disseminated claiming that “Breaking: Two Explosions in the White House
and Barack Obama is injured”. This rumor resulted in losses of 10 billion USD
within a few hours and caused the United States stock market to crash within
minutes [17]. As another example, infectious diseases cause 10 million deaths
each year globally, accounting for 23% of the total disease related deaths,
where critical nodes play a massive role in the extent of the spread [18].
Consequently, there has been an increasing interest in shedding light on
managing and alleviating the impact of a set of target nodes, especially
influential nodes [19, 20, 21, 22].

Another application space where the problem of mitigating some target nodes
have gained substantial attention is the realm of privacy protection in
networks. In this setup, the goal is to protect the privacy of users or
conceal critical entities in the network by implementing structural
anonymization [23, 24]. Please refer to Sections 5.1 and 5.2 for more details
on these topics when appropriate.

Two commonly employed graph operations to attain the aforementioned objectives
are node and edge removal. Edge removal has garnered greater attention
recently [22, 25, 26], since it is less intrusive (i.e., disrupts the original
functionality and flow of the network less aggressively) and provides
controlling power in a more granular level (note that usually removing a node
is equivalent to removing all its adjacent edges). In this work, we focus on
edge removal as well.

Previous studies [23, 27, 24, 28] have investigated the problem of removing a
fixed number of edges to achieve an objective with respect to a subset of
target nodes. The objective could vary from minimizing the spreading power of
the target nodes under a specific information diffusion model such as the
Independent Cascade (with the goal of halting the propagation of a piece of
misinformation) [21, 22, 26, 29, 12] to minimizing the centrality of the
target nodes measured by degree [23] or closeness [24] (with the aim of
concealment). Additionally, numerous algorithms, predominantly heuristics,
have been put forth [29, 12].

The existing works have two major limitations. Firstly, despite a plethora of
centrality indices proposed in the literature [14], these prior works do not
consider information centrality [30, 31], in spite of its obvious advantages.
For example, information centrality captures the way node-to-node transmission
takes place (especially, on social networks) [32] and possesses higher
discrimination power than others [9, 33]. Again for instance, information
centrality has been applied to various fields, such as estimation from
relative measurements [34] and leader selection for noisy consensus [35].
Secondly, they are computationally relatively expensive which renders them
impractical in various real-world scenarios. Suppose a misinformation
detection algorithm has spotted a potential rumor (as the one from above about
White House) and the goal is to moderate the spreading power of the initiating
node by temporarily removing some edges (i.e., not exposing the content from
some users to some others), then having a very fast mitigation algorithm in
place is very crucial. (Note that pre-calculations are not usually a viable
solution here, since these graphs undergo constant reformulation). Another
example of this would be an internet service provider seeking to control the
network traffic in response to a malfunctioning or malevolent router.

In light of the above limitations, our study aims to fill this gap by devising
an objective function capturing information centrality and provide an
algorithm that can handle networks of million nodes. In our formulation of the
problem of moderating critical nodes, the objective is to remove $k$ edges to
minimize the information centrality of a target node, while preserving network
connectivity. (The constraint of network connectivity ensures the preservation
of network’s functionality [16, 7], a consideration also addressed in other
works investigating problems related to edge removal [28, 24, 36].)

We prove that this problem is NP-complete. Furthermore, while its objective
function is monotonically decreasing, it is not supermodular, posing
difficulties in solving it using traditional greedy algorithms. However, we
still adopt the standard greedy algorithm in our setup since it has been
frequently observed to deliver satisfactory results for many non-supermodular
problems [37, 38]. Despite its simplicity and efficacy, it requires execution
of matrix inversion operations, incurring a prohibitive computational cost and
rendering it unfeasible for large networks. As the first step towards a faster
algorithm, we use the random walk-based approximate Schur complement method
[39] to present a faster algorithm, called ApproxiSC. To speed up the
computation even further, we also leverage the sum estimation method [40, 41],
which allows us to provide the algorithm FastICM which runs in nearly linear
time in the number of edges, as our main contribution.

The rest of our paper proceeds as follows. We first introduce some necessary
preliminaries related to our work in Section 2. Then, we provide an exact
formulation of our problem in Section 3 and give an overview of our main
theoretical and experimental findings and the techniques used in Section 4. We
discuss related works in Section 5. Then, we study the computational
complexity of our problem and prove related properties of the corresponding
objective function in Section 6. In Section 7, we present the deterministic
greedy algorithm, followed by the fast greedy algorithms in Section 8. We
report our performance experiments evaluating the efficiency and effectiveness
of our algorithms in Section 9 and conclude the paper in Section 10.

##  2 Preliminaries

In this section, we introduce some useful notations and tools to facilitate
the description of our problem and algorithms.

###  2.1 Notations

We use normal lowercase letters like $a,b,c$ to denote scalars in
$\mathbb{R}$, normal uppercase letters like $A,B,C$ to denote sets, bold
lowercase letters like $\bm{\mathit{a}},\bm{\mathit{b}},\bm{\mathit{c}}$ to
denote vectors, and bold uppercase letters like
$\bm{\mathit{A}},\bm{\mathit{B}},\bm{\mathit{C}}$ to denote matrices. Let
$\bm{\mathit{J}}$ be the matrix of appropriate dimensions with all entries
being ones. We use $\bm{\mathit{A}}_{[S,F]}$ to denote the submatrix of
$\bm{\mathit{A}}$ with row indices in $S$ and column indices in $F$. We write
$\bm{\mathit{A}}_{ij}$ to denote the entry at row $i$ and column $j$ of
$\bm{\mathit{A}}$ and $\boldsymbol{\mathit{a}}_{i}$ to denote the $i$-th
element of vector $\boldsymbol{\mathit{a}}$. We use $\bm{\mathit{A}}_{-T}$ to
denote the submatrix of $\bm{\mathit{A}}$ obtained from $\bm{\mathit{A}}$ by
deleting rows and columns corresponding to elements in set $T$, and use
$\bm{\mathit{a}}_{-T}$ to denote the vector obtained from $\bm{\mathit{a}}$ by
deleting elements in set $T$. An $n\times n$ matrix $\bm{\mathit{A}}$ is
positive semi-definite if
$\bm{\mathit{x}}^{\top}\bm{\mathit{A}}\bm{\mathit{x}}\geq 0$ holds for all
$\bm{\mathit{x}}\in\mathbb{R}^{n}$. For two positive semi-definite matrices
$\bm{\mathit{A}}$ and $\bm{\mathit{B}}$, we use
$\bm{\mathit{B}}\preceq\bm{\mathit{A}}$ to denote that matrix
$\bm{\mathit{A}}-\bm{\mathit{B}}$ is a semi-definite matrix. Below, we
introduce the notion of $\epsilon$-approximation.

######  Definition 2.1.

Given two positive semi-definite matrices $\bm{\mathit{A}}$ and
$\bm{\mathit{B}}$ and a real number $\epsilon\in(0,1)$, we say that
$\bm{\mathit{B}}$ is an $\epsilon$-approximation of $\bm{\mathit{A}}$ (abbr.
$\bm{\mathit{B}}\approx_{\epsilon}\bm{\mathit{A}}$)

$(1-\epsilon)\bm{\mathit{A}}\preceq\bm{\mathit{B}}\preceq(1+\epsilon)\bm{\mathit{A}}.$

If $\bm{\mathit{A}}$ and $\bm{\mathit{B}}$ are degenerated to positive scalars
$a,b>0$, $b$ is called an $\epsilon$-approximation of $a$ (abbr.
$b\approx_{\epsilon}a$) if $(1-\epsilon)\,a\leq b\leq(1+\epsilon)\,a$.

###  2.2 Graphs and Related Matrices

Consider a connected undirected graph $\mathcal{G}=(V,E)$ where $V$ is the set
of nodes and $E\subseteq V\times V$ is the set of edges. Let $n=|V|$ and
$m=|E|$ denote the number of nodes and the number of edges, respectively. The
Laplacian matrix of $\mathcal{G}$ is the symmetric matrix
$\bm{\mathit{L}}=\bm{\mathit{D}}-\bm{\mathit{A}}$, where $\bm{\mathit{A}}$ is
the adjacency matrix whose entry $\bm{\mathit{A}}_{ij}=1$ if node $i$ and node
$j$ are adjacent, and $\bm{\mathit{A}}_{ij}=0$ otherwise, and
$\bm{\mathit{D}}$ is the degree diagonal matrix
$\bm{\mathit{D}}=\text{diag}(\bm{\mathit{d}}_{1},\cdots,\bm{\mathit{d}}_{n})$
where $\bm{\mathit{d}}_{i}$ is the degree of node $i$. We write
$\bm{\mathit{e}}_{i}$ to denote the $i$-th standard basis vector. We fix an
arbitrary orientation for all edges in $\mathcal{G}$, and for each edge
$e=(u,v)\in E$, we define
$\bm{\mathit{b}}_{e}=\bm{\mathit{b}}_{uv}=\bm{\mathit{e}}_{u}-\bm{\mathit{e}}_{v}$,
where $u$ and $v$ are head and tail of $e$, respectively. Then,
$\bm{\mathit{L}}$ can be rewritten as $\bm{\mathit{L}}=\sum\nolimits_{e\in
E}\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top}$. Matrix $\bm{\mathit{L}}$ is
singular and positive semidefinite with its Moore-Penrose pseudoinverse being
$\bm{\mathit{L}}^{\dagger}=\left(\bm{\mathit{L}}+\frac{1}{n}\bm{\mathit{J}}\right)^{-1}-\frac{1}{n}\bm{\mathit{J}}$.
The transition matrix is
$\bm{\mathit{P}}=\bm{\mathit{D}}^{-1}\bm{\mathit{A}}$, which is a row-
stochastic matrix.

For any non-empty node sets $F\subset V$ and $T=V\backslash F$, we can
partition the Laplacian matrix $\bm{\mathit{L}}$ into 4 blocks:

$\displaystyle\bm{\mathit{L}}:=\left[\begin{array}[]{ll}\bm{\mathit{L}}_{[F,F]}&\bm{\mathit{L}}_{[F,T]}\\\
\bm{\mathit{L}}_{[T,F]}&\bm{\mathit{L}}_{[T,T]}\end{array}\right]$

Then, the Schur complement of graph $\mathcal{G}$ onto node set $T$, denoted
by $\mathcal{S}(T)$, is the matrix in closed form as

$\displaystyle\mathcal{S}(T)=\bm{\mathit{L}}_{[T,T]}-\bm{\mathit{L}}_{[T,F]}\bm{\mathit{L}}_{[F,F]}^{-1}\bm{\mathit{L}}_{[F,T]}.$

$\mathcal{S}(T)$ is a Laplacian matrix of a graph with node set $T$, and we
use $\mathcal{G}(\mathcal{S}(T))$ to denote the corresponding graph of
$\mathcal{S}(T)$.

###  2.3 Information Centrality

Given a graph $\mathcal{G}=(V,E)$ and two vertices $x,y\in V$, the effective
resistance, which is a form of Euclidean distance [42],
$\mathcal{R}^{\mathcal{G}}_{xy}$ between nodes $x$ and $y$ is defined as
$\mathcal{R}^{\mathcal{G}}_{xy}=\bm{\mathit{b}}_{xy}^{\top}\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{xy}$.
We refer to the maximum value of pairwise effective resistance in a graph as
the effective resistance diameter, and denote it by $\phi$. Based on the
physical definition of the effective resistance [42], $\phi$ is less than the
diameter of the graph, which is often small in real-life networks [43].

For any node set $T\subset V$, the Schur complement onto $T$ can be viewed as
a vertex sparsifier that preserves pairwise effective resistance [44, 39],
which means

$\displaystyle\mathcal{R}_{xy}^{\mathcal{G}}=\mathcal{R}_{xy}^{\mathcal{G}(\mathcal{S}(T))},$
(1)

holds for any pair of nodes $x,y\in T$.

For a network $\mathcal{G}=(V,E)$ and a node $v\in V$, we use
$\mathcal{R}_{v}^{\mathcal{G}}$ to denote the sum of effective resistances
between $v$ and all nodes in $V\backslash\\{v\\}$ (we will refer to
$\mathcal{R}_{v}^{\mathcal{G}}$ as the resistance distance of node $v$
throughout the paper), i.e., $\mathcal{R}_{v}^{\mathcal{G}}=\sum_{u\in
V\backslash\\{v\\}}\mathcal{R}_{uv}^{\mathcal{G}},$ which can be restated [45]
in a matrix form as

$\displaystyle\mathcal{R}_{v}^{\mathcal{G}}=n\bm{\mathit{L}}^{\dagger}_{vv}+\mathrm{Tr}\left(\bm{\mathit{L}}^{\dagger}\right).$
(2)

The information centrality $\mathcal{I}_{v}^{\mathcal{G}}$ correlates to the
resistance distance $\mathcal{R}_{v}^{\mathcal{G}}$ [30, 32], and can be
expressed by:

$\displaystyle\mathcal{I}_{v}^{\mathcal{G}}=\frac{n}{\mathcal{R}_{v}^{\mathcal{G}}}=\frac{n}{n\bm{\mathit{L}}^{\dagger}_{vv}+\mathrm{Tr}\left(\bm{\mathit{L}}^{\dagger}\right)}$
(3)

which is defined on connected networks.

We will remove the superscripts of $\mathcal{R}^{\mathcal{G}}_{xy}$,
$\mathcal{R}^{\mathcal{G}}_{v}$ and $\mathcal{I}_{v}^{\mathcal{G}}$ when
$\mathcal{G}$ is clear from the context.

###  2.4 Supermodular Optimization

Let $X$ be a finite set, and $2^{X}$ be the set of all subsets of $X$. Let
$f:2^{X}\to\mathbb{R}$ be a set function on $X$. Then, $f$ is called monotone
decreasing if for any subsets $S\subset H\subset X$, $f(S)>f(H)$ holds.
Furthermore, we say function $f$ is supermodular if for any subsets $S\subset
H\subset X$ and any element $a\in X\backslash H$, it satisfies
$f(S\cup\\{a\\})-f(S)\leq f(H\cup\\{a\\})-f(H)$.

The standard greedy algorithm has proven to be an effective solution for the
cardinality-constrained set function problem in supermodular optimization,
with a guaranteed $(1-1/e)$ approximation ratio. However, many crucial set
functions do not satisfy the supermodularity requirement. Nevertheless, the
greedy algorithm still frequently produces desirable results for a broad range
of non-supermodular applications [38, 37].

##  3 Problem Formulation

In this section, we formulate the problem of minimizing the information
centrality of a target node by removing edges.

Consider a connected unweighted undirected network $\mathcal{G}=(V,E)$ and a
target node $v$. For any edge set $P\subset E$, define $\mathcal{G}\setminus
P=(V,E\backslash P)$ as the remaining graph resulted by removing edges in edge
set $P$. Then we define the set function of the information centrality,
$\mathcal{I}_{v}(P)=\mathcal{I}_{v}(\mathcal{G}\setminus P)$. Similarly, we
can define the set function of the sum of the effective resistance
$\mathcal{R}_{v}(P)$. These two definitions are valid whenever the removal of
edges in set $P$ maintains the connectivity of the network.

Rayleigh’s monotonicity law [42] asserts that the effective resistance between
any pair of nodes will increase when an edge is removed; hence, the resistance
distance $\mathcal{R}_{v}(P)$ is monotonically increasing, and the information
centrality $\mathcal{I}_{v}(P)$ is monotonically decreasing. Then the
following problem arises naturally: How to optimally remove a subset $P\subset
E$ from the network subject to a cardinality constraint $k$ specifying the
maximum number of edges that can be removed so that $\mathcal{I}_{v}$ is
minimized while preserving the connectivity of the graph. Mathematically, the
information centrality minimization problem can be stated as follows.

######  Problem 1.

(Information Centrality Minimization, InforCenMin) Given a connected
undirected network $\mathcal{G}=(V,E)$, a predefined target node $v$, and an
integer $k$, we aim to find the edge set $P\subset E$ with $\left|P\right|=k$,
so that the information centrality $\mathcal{I}_{v}(P)$ is minimized while
simultaneously retaining the connectivity of the network. This set
optimization problem can be formulated as:

$P^{*}=\operatorname*{arg\,min}_{P\subset E,|P|=k,\mathcal{G}\setminus
P\textrm{ is connected}}\mathcal{I}_{v}(P).$ (4)

Simply removing edges incident to the target node seems effective to reduce
its information centrality. However, removing nonadjacent edges can provide
greater benefits in some cases. For example, consider the Dolphin [46] network
with 62 nodes, 159 edges, and targeting the green node in Fig. 1. We find that
none of the top-10 edges (colored in red) leading to the largest reduction in
the target node’s information centrality are adjacent to it. This suggests
that the scope of edge removal should not be simplified.

Figure 1: The Dolphin network with the green target node.

##  4 Our Contribution

We investigate the InforCenMin problem, both theoretically and experimentally,
where the goal is to minimize the information centrality of a target node
given the possibility to remove $k$ edges while keeping the underlying graph
connected. This is a very natural and intuitive formulation of the problem of
moderating critical nodes in a network, which in particular takes the very
important parameter of information centrality into account.

We first prove that the problem is NP-complete, building on a reduction from
the Hamiltonian cycle problem [47]. Furthermore, we show that while the
objective function of our problem is monotonically decreasing, it does not
enjoy supermodularity property, by providing an explicit counterexample. As a
result, the traditional greedy approaches would not facilitate us with any
theoretical guarantees. However, since such greedy approaches have proven to
be a useful base for devising effective and efficient algorithms in the past
[37, 38] (even when super-modularity does not hold) we rely on them as a
starting point too.

We first propose a simple algorithm where edges are deleted following the
classic greedy approach. This algorithm, called ExactSM, runs in $O(n^{3})$,
which makes it impractical for very large networks. As the first step towards
a faster algorithm, we use the random walk-based approximate Schur complement
method [48, 39] to present a faster algorithm. In this algorithm, called
ApproxiSC, after each edge removal, the new value of the resistance distance
and the connectivity status can be determined very quickly by carefully
modifying the set of random walks. To further speed up the computation, as the
next step we also leverage the sum estimation method [40, 41], which allows us
to provide the algorithm FastICM that runs in nearly linear time in the number
of edges. The sum estimation method permits us to approximate the resistance
distance of the target node by sampling limited pairs of effective
resistances. Our theoretical analyses confirm that the combination of the
above techniques is well-suited to our problem. Specifically, the absolute
error between the approximate resistance distance upon the removal of any edge
and the corresponding exact value is at most $\alpha n$, for a small error
parameter $\alpha$.

Besides our theoretical analyses, we conduct a comprehensive set of
experiments on real-world networks from Network Repository [46] and SNAP [49]
and on synthetic graph models, namely Barabási–Albert (BA) [50] and
Watts–Strogatz (WS) [43]. We compare our algorithms against several other
algorithms and observe that our algorithms significantly outperform others
while producing results very close to optimal solution. Furthermore, our
linear time FastICM algorithm enjoys an extremely fast run time in practice as
well. In particular, it completes the task for networks with more than one
million nodes in a few hours on a standard 32G-Linux box. Therefore, our
algorithms not only allow a rigorous theoretical analysis but also outperform
other algorithms in practice, in both aspects of effectiveness and efficiency.

##  5 RELATED WORK

In this section, we review the literature related to ours, including
minimizing spread of misinformation in social networks, privacy protection of
networks, edge removal strategies, and edge centrality measures. Specifically,
prior work provided in Sections 5.1 and 5.2 would let us place our
contribution in a bigger picture and draw the connection to some adjacent
topics, while the results in Sections 5.3 and 5.4 are more closely related.

###  5.1 Minimizing Spread of Misinformation

Consider the setup where a rumor starts spreading in a social network from a
known set of nodes and following a predefined spreading dynamics such as the
Independent Cascade model [51]. Then, the goal is to contain the spread by
blocking $k$ edges [21, 22]. A greedy algorithm is developed in [22] where in
each iteration an edge with maximum containment ability is selected, and some
heuristics are proposed in [21]. In [26], considering the cost for blocking
each edge, some budget constraints are defined for critical edge
identification. Some heuristic algorithms are then proposed to solve the
problem. Applying the maximum influence arborescence method [29], an
approximation method is proposed in [12]. These algorithms have several
shortcomings. Firstly, they are usually tailored for a particular rumor
spreading model such as the Independent Cascade model rather using a more
generic notion of information centrality. Secondly, they disregard the
important constraint of connectivity, and they might produce disconnected
networks. Furthermore, they often fail to cover large networks due to their
time complexity.

###  5.2 Network Privacy Protection

One area which is closely related to our work is privacy protection in
networks. Most works in this area focus on protecting the privacy of users by
structural anonymization. The goal is to modify graph structure to anonymize
the underlying network, using various methodologies such as $k$-Anonymity, and
differential privacy-based approaches [52, 53]. One important objective here
is to anonymize the key nodes in a network by reducing their centrality.
Previous studies have investigated the problem of removing edges to decrease
the centrality of some target node with regard to degree centrality [23],
closeness centrality [24], and the likelihood that the target node appears in
an absorbing random walk [28]. However, the notion of information centrality
has not been analyzed in this framework.

###  5.3 Edge Removal Strategies

Admittedly, as a practical approach of graph edit, edge removal operation has
been extensively used for different application purposes, such as controlling
disease spreading [10, 11], minimizing the number of spanning trees [54], and
optimizing eigenvalues of related matrices [55, 56]. In social networks,
removing edges can correspond to unfriending, not exposing the posts/comments,
or maintaining social distance. In computer networks, removing edges is
similar to cutting a fiber or bringing down a physical/virtual link
temporarily. Many studies on edge removal require the final graph to remain
connected. For instance, in [36], the authors have studied the problem of
decreasing the greatest eigenvalue of the adjacency matrix by link removal
while preserving network connectivity. The authors of [57] have investigated
the problem of expanding the network diameter by eliminating edges such that
the resulting graph remains connected. This is because connectivity is usually
essential for the network to preserve its main functionality.

###  5.4 Edge Centrality

The drop in the information centrality of a node caused by deleting an edge
can be used as a measure of its importance. There have been many metrics
proposed in the literature to assess the importance of a single edge or a
group of edges. Individual edge centrality measures comprise, among others,
edge betweenness [58], spanning edge centrality [59], and biharmonic distance
related edge centrality [60]. Additionally, the importance of an edge can be
determined based on the centrality of its endpoints, such as the sum or
product of the degree, closeness, and betweenness centrality of the endpoints
[61]. Group edge centrality measures are typically designed to quantify the
effect of deleting these edges on specific objective functions, such as the
inverse geodesic length [62], the total pairwise connectivity [63], and the
forest index [64]. These existing edge centrality measurements are tailored
for distinct use cases. Our proposed metric is defined based on the reduction
in the information centrality of a target node.

##  6 Complexity Challenges

In this section, we study the computational complexity of the InforCenMin
problem. We first consider the decision version of the problem and prove that
it is NP-complete in Theorem 6.1.

######  Problem 2.

(Information Centrality Minimization, Decision Version, InforCenMinD) Given a
connected undirected graph $\mathcal{G}=(V,E)$ with $n$ nodes, $m$ edges, and
node $v$ being the target node, an integer $k\in\mathbb{N}^{+}$, a real number
$x\in\mathbb{R}^{+}$, decide whether or not there is a set $P$ of $k$ edges to
be removed from $\mathcal{G}$ such that $\mathcal{I}_{v}$ is at most $x$ in
the connected subgraph $\mathcal{G}\setminus P$?

######  Theorem 6.1.

The InforCenMinD problem is NP-complete.

Proof. We demonstrate a polynomial time reduction from the Hamiltonian cycle
problem, which is NP-complete [47]. We presume that edge deletion reserves the
network’s connectivity. Given that we can guess the $k$ edges to be removed
and compute $\mathcal{I}_{v}$ in polynomial time, it is apparent that the
problem is in NP. The smallest $\mathcal{I}_{v}$ that could possibly be
assigned to a node in a connected undirected network with $n$ nodes is
$\mathcal{I}_{v}^{\rm{min}}=n/\sum_{i=1}^{n-1}i=\frac{2}{(n-1)(n-2)}$ (e.g.,
node $v$ in Fig. 2).

Figure 2: A $5$-node path graph targeting at node $v$.

Graph $\mathcal{G}$ contains a Hamiltonian cycle if and only if $\mathcal{G}$
has a connected subgraph $\mathcal{G}^{\prime}$ with $n$ nodes, $n-1$ edges
and the information centrality of its end node being
$\mathcal{I}_{v}^{\rm{min}}$. So by choosing $k=m-n+1$, and
$x=\mathcal{I}_{v}^{\rm{min}}$, we have a reduction from the Hamiltonian cycle
problem to the InforCenMinD problem, proving its NP-completeness. $\Box$

A very common technique to tackle NP-hard problems, such as InforCenMin, is to
prove that the objective function enjoys both monotonicity and super-
modularity, which consequently would provide us with a Hill Climbing algorithm
with a constant approximation guarantee [37, 38]. While as stated in Lemma
6.2, our objective function is monotone, it does not possess super-modularity
property, proven in Lemma 6.3.

######  Lemma 6.2.

(Monotonicity) For two subsets $S$ and $H$ of edges satisfying $S\subset
H\subset E$, and $\mathcal{G}\setminus H$ is a connected graph, we have

$\mathcal{I}_{v}(H)<\mathcal{I}_{v}(S).$

######  Lemma 6.3.

(Non-supermodularity) $\mathcal{I}_{v}(\cdot)$ is not supermodular.

Proof. To exemplify the non-supermodularity of the objective function (4),
consider the network in Fig. 3 (a), a $5$-node graph with node $1$ being the
target node and $e_{1}$ and $e_{2}$ being edges to delete. We define two edge
sets, $S=\emptyset$ and $H=\\{e_{1}\\}$. Then, we have
$\mathcal{I}_{v}(S)=1.8$, $\mathcal{I}_{v}({S\cup{\\{e_{2}\\}})}=1.4$,
$\mathcal{I}_{v}({H})=1.3$, and $\mathcal{I}_{v}({H\cup{\\{e_{2}\\}})}=0.7$.
Thus, we have

$\mathcal{I}_{v}(S)-\mathcal{I}_{v}({S\cup{\\{e_{2}\\}})}=0.4<0.6=\mathcal{I}_{v}({H})-\mathcal{I}_{v}({H\cup{\\{e_{2}\\}})}.$

This result clearly contradicts the definition of supermodularity.
Consequently, the set function of the InforCenMin problem is not supermodular.
$\Box$

Figure 3: Two $5$-node toy networks.

##  7 Deterministic Greedy Algorithm

The InforCenMin problem is inherently combinatorial. Its optimal solution can
be computed using the following naïve brute-force approach. For each set $P$
of the $\tbinom{m}{k}$ possible subsets of edges, determine the connectivity
of $\mathcal{G}\setminus P$, and calculate $\mathcal{I}_{v}(P)$ in the reduced
graph by inverting the Laplacian matrix. Finally, output the subset $P^{*}$ of
$k$ edges whose deletion leads to greatest decrease in $\mathcal{I}_{v}$ while
keeping the connectivity of the graph. Since inverting the Laplacian matrix
could take $\Omega(n^{3})$ time and there are $\tbinom{m}{k}$ possible
subsets, the algorithm’s time complexity is in $\Omega\left({m\choose
k}n^{3}\right)$. Thus, albeit its simplicity, this method is computationally
unaffordable even for small networks due to its exponential time complexity in
$k$.

To tackle this issue, one may consider the heuristic approach of picking the
top-$k$ edges with the greatest individual effect on reducing the information
centrality of the target node. However, due to the interdependence of edges,
the cumulative effect of removing a group of edges is often not equivalent to
the sum of individual edge effects. For example, see the network in Fig. 3
(b), where node 2 is the target node, and edges $e_{2}$ and $e_{3}$ are the
top-2 edges whose removal has the greatest individual effect on the
information centrality of node 2. Surprisingly, removing these top-$2$ edges
reduces the information centrality of node 2 to 0.71 while removing edges
$e_{1}$ and $e_{2}$ would reduce it to $0.56$.

An alternative heuristic is the standard greedy algorithm which starts with an
empty set $P$. Then, in each iteration $i\in\\{1,2,\ldots,k\\}$, it adds the
edge that results in the largest decrease in information centrality of the
target node, while preserving connectivity. However, this greedy approach is
computationally expensive because of two obstacles present during each
iteration: 1) determining whether removal of a certain edge would disconnect
the graph could take $\Omega(n)$ time; 2) the computation of the new
information centrality through inversion of the matrix might take
$\Omega(n^{3})$ time. As a result, the total running time could amount to
$\Omega(kmn^{3})$, which is unaffordable for large networks.

To overcome the first obstacle, some researches focusing on the dynamic
connectivity problem resolve connectivity queries in $O(\log n/\log\log\log
n)$ time [65, 66]. However, these works remain in the realm of theory and can
hardly be applied in practice. Moreover, the computational bottleneck caused
by 2) is larger; thus, we first focus on reducing the time complexity of
updating information centrality.

Let
$\mathcal{I}_{v}^{\Delta}(e)=\mathcal{I}_{v}(\\{e\\})-\mathcal{I}_{v}(\emptyset)$
denote the margin gain of the information centrality by removing edge $e$. We
provide an efficient method for computing $\mathcal{I}_{v}^{\Delta}(e)$ in the
following lemma.

######  Lemma 7.1.

Let $\mathcal{G}=(V,E)$ be a connected graph with Laplacian matrix
$\bm{\mathit{L}}$. Let $e=(x,y)\in E$ be a candidate edge satisfying that
$\mathcal{G}\setminus\\{e\\}$ is connected. Then,

$\displaystyle\mathcal{I}_{v}^{\Delta}(e)=\frac{-(nb+n^{2}c)}{\left(na\bm{\mathit{L}}^{{\dagger}}_{vv}+nc+a\mathrm{Tr}\left(\bm{\mathit{L}}^{{\dagger}}\right)+b\right)\left(n\bm{\mathit{L}}^{{\dagger}}_{vv}+\mathrm{Tr}\left(\bm{\mathit{L}}^{{\dagger}}\right)\right)},$

where
$a=1-\bm{\mathit{b}}_{e}^{\top}\bm{\mathit{L}}^{{\dagger}}\bm{\mathit{b}}_{e}$,
$b=\bm{\mathit{b}}_{e}^{\top}\bm{\mathit{L}}^{2{\dagger}}\bm{\mathit{b}}_{e}$
and $c=\left(\bm{\mathit{L}}^{{\dagger}}\bm{\mathit{b}}_{e}\right)_{v}^{2}$.

Proof. By definition, we have

$\displaystyle\mathcal{I}_{v}(\\{e\\})=\frac{n}{n(\bm{\mathit{L}}-\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top})^{\dagger}_{vv}+\mathrm{Tr}\left((\bm{\mathit{L}}-\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top})^{\dagger}\right)}.$

By Sherman-Morrison formula [67], we have

$(\bm{\mathit{L}}-\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top})^{\dagger}=\bm{\mathit{L}}^{\dagger}+\frac{\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top}\bm{\mathit{L}}^{{\dagger}}}{1-\bm{\mathit{b}}_{e}^{\top}\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{e}}.$
(5)

Note that
$\bm{\mathit{b}}_{e}^{\top}\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{e}$
equals the effective resistance between nodes $x$ and $y$, whose value is 1
whenever removing this edge partitions the graph into two components and is
less than 1 otherwise. Thus, the gain in information centrality can be written
as

$\displaystyle\mathcal{I}_{v}^{\Delta(e)}=$
$\displaystyle\frac{n}{n\big{(}\bm{\mathit{L}}-\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top}\big{)}_{vv}^{{\dagger}}+\mathrm{Tr}\left((\bm{\mathit{L}}-\bm{\mathit{b}}_{e}\bm{\mathit{b}}_{e}^{\top})^{{\dagger}}\right)}$
$\displaystyle-\frac{n}{n\bm{\mathit{L}}^{\dagger}_{vv}+\mathrm{Tr}\left(\bm{\mathit{L}}^{\dagger}\right)}$
$\displaystyle=$
$\displaystyle\frac{-(nb+n^{2}c)}{\left(na\bm{\mathit{L}}^{{\dagger}}_{vv}+nc+a\mathrm{Tr}\left(\bm{\mathit{L}}^{{\dagger}}\right)+b\right)\left(n\bm{\mathit{L}}^{{\dagger}}_{vv}+\mathrm{Tr}\left(\bm{\mathit{L}}^{{\dagger}}\right)\right)},$

completing the proof. $\Box$

According to Lemma 7.1, if $\bm{\mathit{L}}^{\dagger}$ is known, we can
efficiently compute the marginal gain of the information centrality for one
edge by rank-1 update in $O(n)$ time. Then, we propose a deterministic greedy
algorithm $\textsc{ExactSM}(\mathcal{G},v,k)$. As outlined in Algorithm 1, the
first step of this algorithm is to set the result edge set $P$ to empty and
compute $\bm{\mathit{L}}^{{\dagger}}$ in $O(n^{3})$ time (Line 1). Then we add
$k$ edges to $P$ iteratively (Lines 2-11). In each iteration, for each
candidate edge $e\in E$, we determine the connectivity of the graph
$\mathcal{G}\setminus\\{e\\}$ in $O(n)$ time (Line 4) and compute the marginal
gain of the information centrality in $O(n)$ time (Line 7). After obtaining
$\mathcal{I}^{\Delta}_{v}(\cdot)$ for each candidate edge, we select the edge
that leads to the smallest marginal gain (Line 8), update the solution (Line
9) and graph (Line 10), and update $\bm{\mathit{L}}^{\dagger}$ according to
Equation (5) in $O(n^{2})$ time. In summary, the total running time of
Algorithm 1 is $O(n^{3}+kmn+kn^{2})$.

Input : A connected graph $\mathcal{G}=(V,E)$; a target node $v\in V$; an
integer $k\leq m$

Output : A subset of $P\subset E$ with $|P|=k$

1 Set $P\leftarrow\emptyset$; compute $\bm{\mathit{L}}^{\dagger}$

2 for  _$i=1$ to $k$_ do

3 for  _$e\in E$_ do

4 if  _$\mathcal{G}\setminus\\{e\\}$ is not connected_ then

5 Set $\mathcal{I}^{\Delta}_{v}(e)=0$

6 else

7 Compute $\mathcal{I}_{v}^{\Delta}(e)$ by Lemma 7.1

8

9 Select $e_{i}$ s.t. $e_{i}\leftarrow\mathrm{arg\,min}_{e\in
E}\mathcal{I}^{\Delta}_{v}(e)$

10 Update solution $P\leftarrow P\cup\\{e_{i}\\}$

11 Update the graph $\mathcal{G}\leftarrow(V,E\backslash\\{e_{i}\\})$

12 Update
$\bm{\mathit{L}}^{\dagger}\leftarrow\bm{\mathit{L}}^{\dagger}+\frac{\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{e_{i}}\bm{\mathit{b}}_{e_{i}}^{\top}\bm{\mathit{L}}^{\dagger}}{1-\bm{\mathit{b}}_{e_{i}}^{\top}\bm{\mathit{L}}^{\dagger}\bm{\mathit{b}}_{e_{i}}}$

13return $P$

Algorithm 1 $\textsc{ExactSM}(\mathcal{G},v,k)$

##  8 FAST RANDOMIZED GREEDY ALGORITHM

The deterministic greedy algorithm, while faster than the brute-force
approach, is not feasible for large networks due to the high computational
cost of determining the information centrality marginal gain and graph
connectivity. On the positive side, information centrality and the resistance
distance are shown to be correlated in Equation (3). This permits us to
leverage random walk-based approximate Schur complement method [48, 39] to
present a faster algorithm, called ApproxiSC in Section 8.1. To speed up the
computation even further, we then utilize the sum estimation method [40, 41],
which allows us to present the algorithm FastICM in Section 8.2 which runs in
nearly linear time in the number of edges.

###  8.1 A Simple Sampling Algorithm

To efficiently calculate and update the information centrality, the main
computational bottleneck is the fast calculation of effective resistance
Equation (3). Several approximation methods have been proposed to estimate
pairwise effective resistance in sublinear time [39, 68]. However, a naïve
approach would need to approximate $n$ distinct pairwise effective resistance
and then update them for $m$ potential candidate edge. This seems to be
computationally expensive. To address this issue, we approach the problem from
a different angle, which facilitates us with a much faster mechanism to
approximate the effective resistances.

As mentioned in Section 2.3, the Schur complement can be considered as a
vertex sparsifier preserving pairwise effective resistance. This motivates us
that if we can efficiently compute and update the Schur complement, the
aforementioned challenges could be resolved. However, calculating the Schur
complement directly is time-consuming. Building upon the ideas of sparsifying
random walk polynomials [69] and Schur complement [48, 70], we approximate it
using a collection of random walks that can be maintained upon edge removal
with a reasonable time complexity. The following lemma, borrowed from [39, 69,
48, 70], asserts that these walks provide an accurate estimate of the Schur
complement.

######  Lemma 8.1.

[39] Let $\mathcal{G}=(V,E)$ be an undirected unweighted graph with a subset
of nodes $T\subset V$. Assume $\epsilon\in(0,1)$, and let $\rho=O\left((\log
n)\epsilon^{-2}\right)$ be some sampling concentration parameter. Suppose that
$\mathcal{H}$ is an initially empty graph. For every edge $e=(i,j)\in E$,
repeat the following procedure $\rho$ times:

  1. 1.

Simulate a random walk $w_{1}$ starting from node $i$ until it first hits $T$
at some node $t_{1}$.

  2. 2.

Simulate a random walk $w_{2}$ starting from node $j$ until it first hits $T$
at some node $t_{2}$.

  3. 3.

Combine these two walks (including $e$) as two sides to get a walk
$w=(t_{1}=u_{0},\cdots,u_{\tilde{l}}=t_{2})$, where $\tilde{l}$ is the length
of the combined walk.

  4. 4.

Add the edge $(t_{1},t_{2})$ to graph $\mathcal{H}$ with weight
$1/\left(\rho\tilde{l}\right)$.

Then, the Laplacian matrix $\bm{\mathit{L}}_{\mathcal{H}}$ of the resulting
graph $\mathcal{H}$ satisfies
$\bm{\mathit{L}}_{\mathcal{H}}\approx_{\epsilon}\mathcal{S}(T)$ with
probability of at least $1-O(1/n)$.

Based on Lemma 8.1, we can approximate the Schur complement for an arbitrary
terminal set $T\subseteq V$ and obtain a graph $\mathcal{H}$ satisfying
$\bm{\mathit{L}}_{\mathcal{H}}\approx_{\epsilon}\mathcal{S}(T)$. Let
$\tilde{\mathcal{R}}_{xy}$ be the effective resistance between any pair of
nodes $x,y\in T$ on graph $\mathcal{H}$, then based on the fact that matrix
approximations also preserve approximations of their quadratic forms, we have

$\tilde{\mathcal{R}}_{xy}\approx_{\epsilon}\mathcal{R}_{xy}^{\mathcal{G}(\mathcal{S}(T))}=\mathcal{R}_{xy}^{\mathcal{G}}.$
(6)

####  8.1.1 Approximation of Effective Resistance

To approximate $\mathcal{R}_{uv}$, a direct way is to set $T=\\{u,v\\}$, and
then estimate $\mathcal{R}_{uv}$ as the reciprocal of the weight between $u$
and $v$ in the resulting graph $\mathcal{H}$ from Lemma 8.1. However, even if
the target node $v$ is fixed, the approximation of the effective resistance
between $v$ and all other nodes is expensive as it may result in redundant
walk sampling. To address this issue, we carefully modify the sampling steps
in Lemma 8.1.

First, we set $T=\\{v\\}$, and sample an initial collection of walks using
steps (1)-(3) in Lemma 8.1. For each node $u$, we set $T_{2}=\\{u,v\\}$, and
traverse and shorten all the walks at the first position they hit $T_{2}$,
then add the weight of edge $(u,v)$ to the two-node graph $\mathcal{H}$. This
yields a new collection of random walks and an approximation of
$\mathcal{S}(T_{2})$. However, repeating this process for every node takes at
least $\Omega(mn(\log n)/\epsilon^{2})$ time, which is computationally
infeasible for large networks.

We notice that most nodes may appear in a small fraction of the sampled walks;
thus, we do not necessarily need to traverse all the walks for each node $u$.
So we propose an approach where we traverse each sampled walk exactly once.
More precisely, for any walk $w$, we traverse it once and keep track of which
nodes appear accompanied by the positions they first appear on both sides. If
a node $u$ is only encountered on one side of the walk, setting
$T_{2}=\\{u,v\\}$ will contribute an edge weight to the resulting graph
$\mathcal{H}$. For example, consider the walk in Fig. 4(a)-(b) which starts
from the red edge and initially stops at $v$. By setting $T_{2}=\\{u,v\\}$,
this walk contributes a weight of $\frac{1}{8\rho}$ to edge $(u,v)$ in
$\mathcal{H}$. After summing up the weights contributed by all the walks, we
can approximate $\mathcal{R}_{uv}$ as the reciprocal of the weight of edge
$(u,v)$ in $\mathcal{H}$.

Figure 4: Pipeline of our algorithm. (a) Set $T=\\{v\\}$ and sample an initial
walk (colored in blue) starting from the red edge. (b) For an initial
approximation of the effective resistance $\mathcal{R}_{uv}$, set
$T_{2}=\\{u,v\\}$ and shortcut the initial walk at the first positions it hit
$T$ such that it contributes a weight of $\frac{1}{8\rho}$ to edge $(u,v)$
(colored in yellow) in the approximate graph. (c) When trying to remove edge
$e=(x,y)$, set $T_{4}=\\{u,v,x,y\\}$ and shortcut the walk at the first
positions it hit $T$. (d) After modifying all walks, reduce the weight of edge
$(x,y)$ in the approximate graph by 1.

In summary, we sample random walks according to Lemma 8.1 by setting
$T=\\{v\\}$, and approximate the effective resistances between node $v$ and
all nodes $u\in V\backslash\\{v\\}$ by traversing the sampled walks once.
According to Equation (6), we can approximate the resistance distance
$\mathcal{R}_{v}$ by $\tilde{\mathcal{R}}_{v}=\sum_{u\in
V\backslash\\{v\\}}\tilde{\mathcal{R}}_{uv},$ which satisfies
$\left|\mathcal{R}_{v}-\tilde{\mathcal{R}}_{v}\right|\leq\varepsilon\mathcal{R}_{v}\leq
n\epsilon\phi$, where $\phi$ is the effective resistance diameter of the
network [71].

Following Lemma 8.1, we need to sample $O(m(\log n)/\epsilon^{2})$ walks.
Another critical factor that we need to take into account is the length of
sampled walks with an average value of $l_{\text{avg}}=\sum_{u\in
V\backslash\\{v\\}}2\bm{\mathit{d}}_{u}F_{u,v}/m$, where $F_{u,v}$ represents
the hitting time from node $u$ to node $v$. However, some walks may be
excessively long, making our computations expensive. To address this issue, we
adopt the $l$-truncated random walk concept [72], where walks are accepted if
they shorter than $l$, and disregarded otherwise. Of course, this would result
in less accurate solutions. However, we pursue to balance accuracy and
efficiency in the choice of $l$. We should stress that this extension is based
on the observation that a walk’s contribution to a related edge in
$\mathcal{H}$ decreases as its length increases, with a walk longer than $l$
contributing less than $1/(\rho l)$ to the corresponding edge. The following
lemma ensures that the expected ratio of invalid walks can be made arbitrarily
small for a suitably chosen value of $l$.

######  Lemma 8.2.

[73] Given a connected graph $\mathcal{G}=(V,E)$, a node set $T=\\{v\\}$, and
a ratio of invalid walks $\gamma>0$, if the maximum length $l$ of random walks
satisfies
$l=\log(m\gamma/\sqrt{n-1}\left\|\bm{\mathit{d}}_{-T}\right\|_{2})/\log(\lambda)$,
where $\lambda$ is the spectral radius of matrix $\bm{\mathit{P}}_{-T}$, then
the expected ratio of invalid walks is less than $\gamma$.

Input : A connected graph $\mathcal{G}=(V,E)$; a node $v\in V$; a node set
$Q$; the maximum length $l$; and a real number $\epsilon\in(0,1)$

Output : Approximate effective resistance array $\mathcal{R}$

1

2Let $\rho=O((\log n)\epsilon^{-2})$;
$\mathcal{C}\leftarrow\mathbf{0}_{n\times 1}$,
$\mathcal{R}\leftarrow\mathbf{0}_{n\times 1}$, $T\leftarrow\\{v\\}$ and
$W\leftarrow\emptyset$

3 for  _each edge $e=(i,j)\in E$ and $p=1,\cdots,\rho$_ do

4 Generate a random walk $w_{1}(e,p)$ from $i$ until it reaches $T$ or its
length is $l$

5 Generate a random walk $w_{2}(e,p)$ from $j$ until it reaches $T$ or its
length is $l$

6 if  _both walks reach $T$_ then

7 Combine them to form a walk $w(e,p)$

8 Add $w(e,p)$ to $W$

9

10

11for  _each walk $w\in W$_ do

12 for  _each node $u\in w\cap Q$_ do

13 if  _$u$ appears first on one side (A) and not on the other (B)_ then

14 Let $\tilde{l}$ be the length from $u$ to $v$ on $B$ side

15 Update
$\mathcal{C}\left[u\right]\leftarrow\mathcal{C}\left[u\right]+1/(\rho\tilde{l})$

16

17

18Let $\mathcal{R}_{i}\leftarrow 1/\mathcal{C}_{i}$ for all
$i=1,2,\ldots,|\mathcal{C}|$

return $\mathcal{R}$ and $W$

Algorithm 2 Initialization$(\mathcal{G},v,Q,l,\epsilon)$

Based on above analysis, we propose an algorithm Initialization which returns
an array $\mathcal{R}$ containing the effective resistances between $v$ and
all nodes in a given set $Q$ (with $Q=V\backslash\\{v\\}$ in this section),
together with a collection of random walks $W$ for future computations. The
outline of Initialization is presented in Algorithm 2.

####  8.1.2 Updating Effective Resistance

The removal of an edge alters the effective resistances. Recalculating them by
resampling walks from scratch is computationally inefficient. To address this
issue, we propose an efficient algorithm, called DeleteEdge, which updates
effective resistances by modifying the existing walks upon edge removal, as
outlined in Algorithm 3. Before discussing the algorithm in more detail, we
introduce a node-walk mapping data structure, which maps nodes to the walks
that contain them to facilitate the subsequent computation of effective
resistances, and is constructed as follows.

  * •

First, assign two pristine arrays to each node: the walk array and the
position array, aimed at capturing the walks that the node participates in and
their corresponding positions, respectively.

  * •

Systematically traverse any walk $w\in W$, and scrutinize any node $u$ that is
encountered for the first time at position $p$ on either side of the walk.
Then append $w$ and $p$ to the walk array and the position array corresponding
to $u$.

The following example illustrates how this data structure works.

Figure 5: Illustration of the node-walk mapping data structure.

Example. Fig. 5 demonstrates two instances of the node-walk map. Specifically,
node $x$ is successively encountered at positions $p_{1}$ and $p_{2}$ on the
left

Input : A connected graph $\mathcal{G}=(V,E)$; a collection of random walks
$W$; a node $v\in V$; a node set $Q$; a set $P$ of removed edges

Output : $\\{(e,\bar{\mathcal{R}}_{v}(P\cup\\{e\\}))|e\in E\\}$

1 for  _each edge $e=(x,y)\in E$_ do

2 Identify the set of walks $\tilde{W}$ that $x$ or $y$ appears on using the
node-walk map

3 for  _$w\in\tilde{W}$_ do

4 for  _$u\in w\cap Q$_ do

5 $T\leftarrow\\{u,v,x,y\\}$

6 Update the edge weights of $\mathcal{H}_{u}$

7

8

9 if  _$\mathcal{H}_{x}$ or $\mathcal{H}_{y}$ is disconnected_ then

10 Set $\bar{\mathcal{R}}_{v}(P\cup\\{e\\})=0$

11 else

12 for  _$u\in Q$_ do

13 Update the effective resistance $\tilde{\mathcal{R}}_{uv}$

14 $\bar{\mathcal{R}}_{v}(P\cup\\{e\\})\leftarrow\sum_{u\in
Q}\tilde{\mathcal{R}}_{uv}$

15

return $\\{(e,\bar{\mathcal{R}}_{v}(P\cup\\{e\\}))|e\in E\\}$

Algorithm 3 DeleteEdge$(\mathcal{G},W,v,Q,P)$

side of walk $w_{1}$, so we append $w_{1}$ and $p_{1}$ to the walk array and
the position array corresponding to $x$. For walk $w_{2}$, node $x$ appears on
both sides, leading us to record $p_{2}$ and $p_{3}$. In turn, for walk
$w_{3}$, we document position $p_{4}$, where node $x$ is first encountered on
the right side. Similar steps can be taken to fill the walk array and position
array for node $y$.

Utilizing the node-walk mapping data structure, we present an efficient method
for updating the effective resistances upon removal of an edge $e=(x,y)$. The
core idea is to reduce the edge removal operation to adding nodes to set $T$
as shown in Fig. 4 (c)-(d). This reduction is feasible because if nodes
$x,y\in T$, then removing edge $e$ in the original graph $\mathcal{G}$ equates
to a decrement in edge $e$’s weight from the Schur complement graph
$\mathcal{G}(\mathcal{S}(T))$ by $1$. In the following analysis, we fix node
$u$. We first sample the random walks with $T=\\{v\\}$ and then set
$T_{4}=\\{u,v,x,y\\}$ and denote the resulting approximate Schur complement
graph as $\mathcal{H}_{u}$. To modify these walks, we utilize the node-walk
map to expeditiously determine the walks and positions of nodes $u,x,y$. The
corresponding walks are then shortened and the edge weights in graph
$\mathcal{H}_{u}$ are updated. The final step involves subtracting the edge
weight between $x$ and $y$ by $1$. The sufficient condition for the reduced
graph being connected is that node $x$ remains accessible from node $y$, which
suffices to demonstrate that $v$ is reachable from both $x$ and $y$, which can
be readily assessed using the updated four-node graph. Consequently, the
connectivity of the reduced graph and the new effective resistance between
nodes $u$ and $v$ can be easily determined.

Although this method is simple, it still could take $\Omega(mn)$ time for
updating all pairs of effective resistances for any edge. However, thanks to
the initialization process, we store the information of the Schur complement
onto each two-node set $T_{2}=\\{u,v\\}$ for each $u\in V\backslash\\{v\\}$.
This would facilitate us to update the four-node graph efficiently.
Specifically, we use the node-walk mapping data structure to locate the
positions of nodes $x$ and $y$. Then, we shorten walks and update edge weights
for all possible four-node sets $T_{4}=\\{q,v,x,y\\}$ where $q$ is a node co-
occurring with $x$ or $y$ on any walk, and update the edge weights of
$\mathcal{H}_{q}$. More accurately, for edges $(q,v),(x,v),(y,v)$, the weights
are derived from subtracting the weight of $\mathcal{G}(\mathcal{S}(T_{2}))$
by the weight reduction due to walk truncation, and for edges
$(q,x),(q,y),(x,y)$, the weights are computed by the newly specified walk
segments. Finally, we subtract the edge weight between $x$ and $y$ by 1, check
the connectivity and compute the effective resistance on the updated four-node
graph. We note that the average occurrence of each node in all sampled random
walks is $O(mn^{-1}l(\log n)\epsilon^{-2})$, thus the overall time complexity
is reduced to $O(m^{2}n^{-1}l^{2}(\log n)\epsilon^{-2})$.

To visualize the process of modifying walks, see the walk in Fig. 4, which is
affected by the removal of edge $(x,y)$. This walk no longer contributes
weight to edge $(u,v)$, but contributes weight to edge $(x,y)$.

####  8.1.3 A Sampling Algorithm for InforCenMin

By integrating the techniques for initializing and modifying random paths to
approximate effective resistances, we offer a fast algorithm ApproxiSC to
address the problem InforCenMin. The pseudocode of this algorithm is
summarized in Algorithm 4. Besides the input graph $\mathcal{G}$, the
cardinality constraint $k$ and the target node $v$, its input also contains an
integer $l$ that constrains the maximum length of random walks and an error
parameter $\epsilon$. We first set $P\leftarrow\emptyset$. Then in each
iteration, we initialize the random walks for the current graph by making a
call to Initialization. Then, we use DeleteEdge to obtain a set of tuples
consisting of an edge and the corresponding $\tilde{\mathcal{R}}_{v}$ in the
reduced graph. The edge that results in the largest margin gain of
$\tilde{\mathcal{R}}_{v}$ while preserving graph connectivity will be
selected. This process is repeated until $k$ edges have been added to $P$.

Input : A connected graph $\mathcal{G}=(V,E)$; an integer $k<m$; a node $v\in
V$; the length constraint $l$; an error parameter $\epsilon\in(0,1)$

Output : An edge set $P\subset E$ satisfying constraint $k$

1 Set $P\leftarrow\emptyset$

2 for  _$i=1$ to $k$_ do

3 $\mathcal{R},W\leftarrow\textsc{Initialization}(\mathcal{G},v,V,l,\epsilon)$

4 $\\{(e,\tilde{\mathcal{R}}_{v}(P\cup\\{e\\}))|e\in
E\\}\leftarrow\textsc{DeleteEdge}(\mathcal{G},W,v,V,P)$

5 Select $e_{i}$ s.t. $e_{i}\leftarrow\operatorname*{arg\,max}_{e\in
E}\tilde{\mathcal{R}}_{v}(P\cup\\{e\\})$

6 Update solution $P\leftarrow P\cup\\{e_{i}\\}$

7 Update the graph $\mathcal{G}\leftarrow(V,E\backslash\\{e_{i}\\})$

return $P$

Algorithm 4 $\textsc{ApproxiSC}(\mathcal{G},k,v,l,\epsilon)$

We next analyze the time complexity of ApproxiSC, which consists of two parts:
approximating the effective resistances and updating them upon edge removal
for all existing edges. In the updating process, we also need to check the
connectivity of the resulting graph. Generating the random walks takes
$O(ml(\log n)\epsilon^{-2})$ time, initializing the effective resistances
takes $O(ml(\log n)\epsilon^{-2})$ time, and updating them takes
$O(m^{2}n^{-1}l^{2}(\log n)\epsilon^{-2})$ time. Furthermore, the connectivity
can be checked relatively quickly using the derived graph $\mathcal{H}$. In
summary, the overall time complexity of our proposed algorithm ApproxiSC is in
$O(kml(\log n)\epsilon^{-2}+km^{2}n^{-1}l^{2}(\log n)\epsilon^{-2})$.

###  8.2 A More Efficient Algorithm

The simple sampling algorithm ApproxiSC is much faster than the original
deterministic algorithm we began with. Nevertheless, in this section we
further reduce its time complexity by proposing a faster sampling algorithm,
with a similar accuracy guarantee.

####  8.2.1 Fast Simulating Random Walks

Each iteration of ApproxiSC involves simulating $m\lceil(\log
n)/\epsilon^{2}\rceil$ $l$-truncated random walks, which is computationally
expensive as $k$ grows. However, we observe adding an edge $e$ to $P$ only
impacts walks that go through it. Hence, we can speed up the process by only
modifying a small fraction of walks when $e$ is deleted, while reusing the
rest for subsequent approximations. Next, we elaborate on this more efficient
approach.

First, we sample random walks for initialization. Then in each iteration,
after selecting an edge $e$, we modify the affected walks. To efficiently
locate these walks, we set up an edge-walk mapping data structure. This data
structure, similar to the node-walk mapping data structure shown in Fig. 5,
records the walks and the positions where $e$ first appears, which can be
built once the walks are sampled. For each affected walk $w$, we truncate it
at the first appearance of edge $e$, and extend it with a new random walk from
the truncated position to $v$, or until the total length reaches $l$. Both
edge-walk and node-walk map, as well as the effective resistance array
$\mathcal{R}$, are then updated. Since the average number of walks that
include edge $e$ is $O(mn^{-1}l(\log n)\epsilon^{-2})$, updating the walks is
efficient.

####  8.2.2 Fast Approximation of the Resistance Distance

ApproxiSC approximates effective resistances between the target node $v$ and
all other nodes in the network. However, it is only the sum of these
resistances, $\mathcal{R}_{v}$, that is of interest, rather than individual
ones. Next, we show that evaluating $\mathcal{R}_{v}$ can be achieved through
computing the effective resistances between $v$ and a smaller subset
${\tilde{V}}\subseteq V$.

Based on the techniques developed in previous sum estimation works [40, 41],
we show that the sum of $n$ bounded elements can be approximated by a sample
of them in the following lemma.

######  Lemma 8.3.

Given $n$ bounded elements $x_{1},x_{2},\ldots,x_{n}\in[0,a]$, an error
parameter $\beta>an^{-1/2}\log^{1/2}n$, we randomly select $t=O(a\sqrt{n(\log
n)}/\beta)$ elements $x_{c_{1}},x_{c_{2}},\ldots,x_{c_{t}}$ by Bernoulli
trials with success probability $p=an^{-1/2}\log^{1/2}n/\beta$ satisfying
$0<p<1$. We have $\bar{x}=\sum_{i=1}^{t}x_{c_{i}}/p$ as an approximation of
the sum of the original $n$ elements $x=\sum_{i=1}^{n}x_{i}$, satisfying
$|x-\bar{x}|\leq n\beta$.

Based on the above lemma, let $\phi$ be the effective resistance diameter,
$\alpha$ be an error parameter, $\beta=\frac{\alpha}{2}$, and
$\epsilon=\frac{\alpha}{2\phi}$. Let $t=O(\phi\sqrt{n(\log n)}/\beta)$,
$\tilde{V}=\\{x_{1},x_{2},\ldots,x_{t}\\}$ be a randomly selected subset, and
$\hat{\mathcal{R}}_{v}=\sum_{u\in{\tilde{V}}}\tilde{\mathcal{R}}_{uv}n/(\phi\sqrt{n(\log
n)}/\beta)$, $\tilde{\mathcal{R}}_{v}$ can be approximated by
$\hat{\mathcal{R}}_{v}$, satisfying

$\displaystyle|\hat{\mathcal{R}}_{v}-\tilde{\mathcal{R}}_{v}|\leq n\beta,$ (7)

and further $\mathcal{R}_{v}$ can be approximated by $\hat{\mathcal{R}}_{v}$
satisfying

$\displaystyle|\mathcal{R}_{v}-\hat{\mathcal{R}}_{v}|\leq n\alpha.$ (8)

By setting $Q=\tilde{V}$, Initialization and DeleteEdge can be simplified by
just approximating and updating effective resistances between node $v$ and
nodes in set $\tilde{V}$.

####  8.2.3 Fast Algorithm for InforCenMin

Equipped with the techniques of fast sampling of random walks and efficient
computing of the sum of effective resistances, we are now prepared to propose
a faster algorithm FastICM for Problem 1, outlined in Algorithm 5.

FastICM performs $k$ rounds (Lines 5-9) for iteratively selecting $k$ edges.
Given a network $\mathcal{G}=(V,E)$ with an effective resistance diameter
$\phi$, we randomly select a node set ${\tilde{V}}\subset V$ of
$O(\phi\sqrt{n(\log n)}/\beta)$ nodes, simulate $m\lceil\phi^{2}(\log
n)/\alpha^{2}\rceil$ $l$-truncated random walks, and approximate the effective
resistances. It takes $O(ml(\log
n)\phi^{2}\alpha^{-2}+mn^{-1/2}l\log^{3/2}n\alpha^{-3}\phi^{3})$ time for the
three operations. Then, the algorithm takes
$O(km^{2}n^{-3/2}l^{2}\log^{3/2}n\alpha^{-3}\phi^{3})$ time to update the sum
of effective resistances for each candidate edge in all $k$ rounds. Thus, the
overall time complexity of FastICM is $O(ml(\log n)\phi^{2}\alpha^{-2}$
$+mn^{-1/2}l\log^{3/2}n\alpha^{-3}\phi^{3}(1+kml/n))$. Theorem 8.4
characterizes the performance of FastICM.

######  Theorem 8.4.

For any $k>0$, an error parameter $\alpha\in(0,1)$, a maximum length $l$ of
walks, and the effective resistance diameter $\phi$, FastICM runs in
$O(ml(\log
n)\phi^{2}\alpha^{-2}+mn^{-1/2}l\log^{3/2}n\alpha^{-3}\phi^{3}(1+kml/n))$
time, and outputs a solution set $P$ by greedily selecting $k$ edges, such
that for the edge selected in each iteration, the information centrality of
the target node is maximally decreased.

Input : A connected graph $\mathcal{G}=(V,E)$; an integer $k<m$; a node $v\in
V$; the maximum length of random walks $l$; a real number $\alpha\in(0,1)$;
the effective resistance diameter $\phi$

Output : An edge set $P\subset E$ satisfying constraint $k$

1 Set $\beta=\frac{\alpha}{2}$ and $\epsilon=\frac{\alpha}{2\phi}$;
$P\leftarrow\emptyset$

2 Sample the node set ${\tilde{V}}\subset V$ of $t=O(\phi\sqrt{n(\log
n)}/\beta)$

3
$\mathcal{R},W\leftarrow\textsc{Initialization}(\mathcal{G},v,{\tilde{V}},l,\epsilon)$

4 for  _$i=1$ to $k$_ do

5 $\\{(e,\hat{\mathcal{R}}_{v}(P\cup\\{e\\}))|e\in
E\\}\leftarrow\textsc{DeleteEdge}(\mathcal{G},W,v,{\tilde{V}},P)$

6 Select $e_{i}$ s.t. $e_{i}\leftarrow\operatorname*{arg\,max}_{e\in
E}\hat{\mathcal{R}}_{v}(P\cup\\{e\\})$

7 Update solution $P\leftarrow P\cup\\{e_{i}\\}$

8 Update the graph $\mathcal{G}\leftarrow(V,E\backslash\\{e_{i}\\})$

9 Update the collection of walks $W$ following the method stated in Section
8.2.1

10

return $P$

Algorithm 5 $\textsc{FastICM}(\mathcal{G},k,v,l,\alpha,\phi)$

##  9 EXPERIMENT

In this section, we evaluate the efficiency and effectiveness of the proposed
algorithms through experiments on diverse real-world and synthetic networks of
varying types and sizes.

###  9.1 Experimental Setup

In this section, we present the basic experimental settings, which encompass
the machine configuration, datasets, baseline algorithms, and choices of
parameters.

Machine Configuration. Experiments, implemented in Julia, are conducted on a
Linux server with 32G RAM and 4.2 GHz Intel i7-7700 CPU and with a single
thread. The source code is publicly available on
https://github.com/hahaabc/fasticm.

Datasets. We test our algorithms on both real-world networks, from publically
available datasets of Network Repository [46] and SNAP [49], and synthetic
graphs. The name and some statistics of the experimented real-life networks
are presented in Table I, sorted by the number of nodes.

Various synthetic graph models have been introduced to mimic the real-world
networks by capturing fundamental properties consistently observed in such
networks, such as small diameter and scale-free degree distribution [50]. We
use the well-established and popular BA [50] and WS [43] models. The
parameters for these graphs have been chosen such that the average degree
closely matches that of real-world networks of comparable size, as in Table I.
(All experiments are conducted on the largest component of these graphs due to
the connectivity requirement in our problem.)

TABLE I: Some statistics of the experimented real-world networks. We denote
the number of nodes and edges in the largest connected component by $n$ and
$m$, respectively, and use $Dim.$ to represent the diameter of a network.

Network | $n$ | $m$ | $Dim.$ | Network | $n$ | $m$ | $Dim.$
---|---|---|---|---|---|---|---
karate | 34 | 78 | 5 | Erdös | 6,927 | 11,850 | 4
Dolphins | 62 | 159 | 8 | Oregon | 10,900 | 31,180 | 9
Bomb Train | 64 | 243 | 6 | ca-HepPh | 11,204 | 117,619 | 13
Polbooks | 105 | 441 | 7 | Caida | 26,475 | 53,381 | 17
Hamster | 921 | 4,032 | 8 | Twitter | 404,719 | 713,319 | 8
Virgili | 1,133 | 5,451 | 8 | Delicious | 536,108 | 1,365,961 | 14
ca-GrQc | 5,242 | 14,496 | 17 | FourSquare | 639,014 | 3,214,986 | 4
as20000102 | 6,474 | 13,895 | 9 | YoutubeSnap | 1,134,890 | 2,987,624 | 20
|  |  |  |  |  |  |

Baselines. To better illustrate the effectiveness of our two algorithms, we
compare them against the following algorithms. We should stress that all these
algorithms are enforced to satisfy the connectivity constraint.

  * •

Optimum: find an optimal edge set of size $k$ using brute-force search.

  * •

Random: randomly choose $k$ edges.

  * •

Betweenness: select $k$ edges with the highest betweenness centrality. The
betweenness of an edge here accounts for the number of shortest paths between
the target node and other nodes which pass through that edge.

  * •

Spanning: select $k$ edges with the highest spanning edge centrality [59],
which is defined as the fraction of spanning trees of a graph that contain a
certain edge.

  * •

Solver: pick $k$ edges using Algorithm 1 equipped with the approximation
technique in [9] plus the connectivity verification process.

Parameters. For algorithms ApproxiSC and FastICM, we need to set some
parameters. Firstly, smaller values of error parameter $\epsilon$ in ApproxiSC
and error parameter $\alpha$ in FastICM provide more accurate results, while
larger values result in higher efficiency. We set $\epsilon=0.005$ and
$\alpha=0.05$ in our experiments because as it will be observed in our
experiments in Section 9.4, they provide a suitable trade-off between accuracy
and efficiency. The parameter $\phi$ in FastICM is the effective resistance
diameter of the graph. Since it is inherently difficult to determine its exact
value, we instead use the diameter of the graph (reported in Table I), which
gives an upper bound on $\phi$. The length $l$ of sampled walks can be
determined by Lemma 8.2, which involves the spectral radius of matrix
$\bm{\mathit{P}}_{-\\{v\\}}$, and the ratio of invalid walks $\gamma$. We set
the ratio of invalid walks to a relatively small value, namely $0.1\%$.
(According to our experiments, $0.1\%$ achieves a good trade-off between
effectiveness and efficiency. Otherwise, there is nothing particularly unique
about this value.) Computing the spectral radius takes much time for large
networks, so we generously estimate it as $\lambda=0.95$. Unless otherwise
specified, the values of the other parameters are set by default when varying
a parameter.

###  9.2 Effectiveness of Proposed Algorithms

To evaluate the performance of our algorithms, we compare the quality of the
returned edges by the Optimum and Random strategies against ours. The
comparison is conducted on four small networks, consisting of two random
graphs BA and WS with 50 nodes and two real-world networks, namely Karate and
Dolphins. Due to the small size of these networks, we can compare the outcome
of our algorithms against the optimal solution (obtained using brute-force
search). We select 10 random target nodes. For every network and every $k$
from $1$ to $5$, we run each algorithm 10 times, each time for one of the
selected target nodes, and calculate the average final information centrality
of target nodes. The lower the obtained value, the better the performance of
the algorithm.

The results, depicted in Fig. 6, demonstrate that the performance of the
algorithms is consistent across all datasets and that our algorithms perform
almost equally to the optimal solutions, reaching parity in the case of the
Karate network. On the other hand, the Random scheme consistently
underperforms, while the performance of Solver is similar to that of ours.

Figure 6: Average information centrality of target nodes following edge
removals, returned by different algorithms on four networks: BA (a), WS (b),
Karate (c), and Dolphins (d).

As further evidence of the effectiveness of our algorithms, we test them on
four larger real-world networks. Since finding optimal solutions through
brute-force searching is not feasible due to computational limitations, we
compare the results of our algorithms against Random, Betweenness, Spanning,
and Solver algorithms. Similar to above, we randomly select 10 distinct target
nodes to mitigate the impact of node positions on the results. We first
determine the initial information centrality of each target node and then
degrade it by removing up to $k=10$ edges using our greedy algorithms and four
others. After each edge removal, we calculate and record the updated
information centrality. Finally, we average over the information centrality of
all target nodes in each round and exhibit the results in Fig. 7. Our
algorithms outperform the other algorithms on all tested networks.

Figure 7: Average information centrality of target nodes following edge
removals for different algorithms on four networks: Bomb train (a), Virgili
(b), ca-GrQc (c), and Erdös (d).

###  9.3 Efficiency of Proposed Algorithms

In the previous section, we observed that our algorithms consistently
outperform other algorithms and produce near optimal solutions. Here, we focus
on the run time analysis of these algorithms on different networks.

For each network, 20 target nodes are selected randomly, for each of which,
$k=10$ edges are removed to minimize its information centrality using these
algorithms. The average value of final information centrality for the targeted
nodes and the average run time are reported in Table II for all four
algorithms. As expected, the value of information centrality is pretty close
for all three algorithms. However, ApproxiSC and FastICM are extremely more
efficient than the other two algorithms, especially on larger networks. As
explained before, Solver is slower than ApproxiSC and FastICM mainly due to
its additional connectivity verification cost. FastICM can handle massive
networks, such as FourSquare (with 639,014 nodes) and YoutubeSnap (with
1,134,890 nodes), in only a few hours while ExactSM and Solver fail to end
before our cut-off time of 24 hours.

TABLE II: The average final information centrality of 20 randomly chosen target nodes and running times for removing $k=10$ edges using FastICM (FIM), ApproxiSC (ASC), ExactSM (ESM) and Solver (SOL) algorithms on several real-world networks. Network | Information Centrality | Time (seconds)
---|---|---
FIM | ASC | ESM | SOL | FIM | ASC | ESM | SOL
Polbooks | 2.667 | 2.661 | 2.603 | 2.621 | 3 | 6 | 8 | 20
Hamster | 2.172 | 2.145 | 2.145 | 2.145 | 4 | 6 | 9 | 42
Virgili | 2.704 | 2.704 | 2.686 | 2.687 | 4 | 9 | 16 | 73
ca-GrQc | 1.614 | 1.600 | 1.598 | 1.600 | 70 | 83 | 517 | 371
as20000102 | 1.349 | 1.340 | 1.336 | 1.339 | 144 | 194 | 3,175 | 298
Erdös | 1.115 | 1.099 | 1.086 | 1.086 | 281 | 319 | 6,336 | 350
Oregon | 1.612 | 1.612 | 1.586 | 1.603 | 814 | 912 | 19,357 | 1,568
ca-HepPh | 2.621 | 2.610 | 2.605 | 2.610 | 412 | 621 | 7,570 | 1,075
Caida | 1.379 | 1.364 | - | 1.374 | 2,047 | 2,580 | - | 4,789
Twitter | 1.932 | 1.911 | - | - | 3,358 | 8,981 | - | -
Delicious | 2.012 | 1.931 | - | - | 7,287 | 25,823 | - | -
FourSquare | 1.491 | 1.401 | - | - | 19,461 | 68,981 | - | -
YoutubeSnap | 1.194 | 1.111 | - | - | 11,454 | 57,401 | - | -

###  9.4 Impact of Error Parameters

Recall that ApproxiSC and FastICM have the error parameters $\epsilon$ and
$\alpha$, respectively. These error parameters balance efficiency and
approximation guarantee. We examine their effect on two exemplary datasets,
namely Hamster and Virgili. Intuitively speaking, increasing error parameters
yields a looser approximation guarantee, which as a result may impact the
quality of the selected edge set. Let $\Delta$ be the difference between the
final information centrality derived by ApproxiSC (analogously, FastICM) and
ExactSM after edge removal. We report in Fig. 8 the resulting $\Delta$ after
removing 10 edges and the corresponding time consumed for selecting these
edges. As expected, smaller $\epsilon$ (analogously, $\alpha$) yield more
accurate results, while larger values demonstrate greater efficiency. The
results in Fig. 8 should also justify our default choices of $\epsilon=0.005$
and $\alpha=0.05$ in our experiments since they provide an acceptable balance
between the time cost and approximation guarantee. (In these experiments, we
have again used 10 randomly chosen target nodes.)

Figure 8: Impact of error parameters $\epsilon$ and $\alpha$ in ApproxiSC and
FastICM algorithms tested on two networks, Hamster(a), and Virgili (b).

##  10 Conclusion and Future Work

Inspired by the imperative of possessing effective mechanisms to mitigate the
potential deleterious effects incurred by a compromised/malicious node within
a network, we have delved into the problem of moderating critical nodes. We
investigated the setup where the goal is to minimize information centrality of
a target node by removing $k$ edges while maintaining the network’s
connectivity. We proved the problem to be NP-complete and its objective
function to be monotonically decreasing but non-supermodular. By advancement
and development of several novel proof techniques such as random walk-based
Schur complement approximation, we provided two fast approximation algorithms
and their theoretical analysis. Furthermore, our extensive experiments on
various real-world and synthetic networks demonstrated that our proposed
algorithms provide solutions very close to optimal in most cases. One of our
algorithms, which has a nearly linear run time, can cover networks with over
one million nodes on a single machine. Therefore, our algorithms not only
permit for a rigorous theoretical analysis, but also perform effectively and
efficiently in practice.

We aspire this work to create the necessary grounds for further studies of
moderating critical nodes in networks and to be the starting point for a long
line of research on this topic. Below, we propose some potential avenues for
future research to tackle the limitations of the present work.

  * •

Connectivity. We considered the constraint of keeping the underlying network
connected while removing edges. Motivated by various real-world applications,
it would be important to investigate various notations of connectivity, e.g.,
$t$-connectivity (for $t\geq 2$), conductance, or algebraic definitions of
connectivity.

  * •

Edge Costs. In our setup, the cost of removing all edges is the same. However,
in the real world, removing some edges might be more costly than the others.
Therefore, it would be interesting to investigate the problem when each edge
has a cost assigned to it.

  * •

Multiple Target Nodes. A natural generalization of the moderation problem is
to analysis the setup where one aims to minimize the overall information
centrality of several target nodes at once.

  * •

Weighted Networks. In practice, edges have weights associated with them. For
example, in a social network, an edge weight corresponds to the strength of
the social tie between the corresponding two nodes and in an internet network,
it could correspond to the bandwidth of the link between two routers. We
believe to generalize our algorithms to cover the weighted setup, the
introduction of novel ideas and advancement of existing techniques are
required.

  * •

Correlation with diffusion models. In the future, we will try to find how
information centrality correlates with specific diffusion models (cascades,
thresholds, etc.)

## References

  * [1] C. Song, C. Yang, H. Chen, C. Tu, Z. Liu, and M. Sun, “Ced: Credible early detection of social media rumors,” _IEEE Trans. Knowl. Data Eng._ , vol. 33, no. 8, pp. 3035–3047, 2021.
  * [2] A. Zareie and R. Sakellariou, “Rumour spread minimization in social networks: A source-ignorant approach,” _Online Social Networks and Media_ , vol. 29, p. 100206, 2022.
  * [3] Z. Wang, D. Hou, C. Gao, X. Li, and X. Li, “Lightweight source localization for large-scale social networks,” in _Proceedings of the ACM Web Conference_. ACM, 2023, pp. 286–294.
  * [4] S. Freitas, D. Yang, S. Kumar, H. Tong, and D. H. Chau, “Graph vulnerability and robustness: A survey,” _IEEE Trans. Knowl. Data Eng._ , vol. 35, no. 6, pp. 5915–5934, 2023.
  * [5] G. Bertagnolli, R. Gallotti, and M. De Domenico, “Quantifying efficient information exchange in real network flows,” _Communications Physics_ , vol. 4, no. 1, p. 125, 2021.
  * [6] L. Sun, X. Rui, and W. Chen, “Scalable adversarial attack algorithms on influence maximization,” in _Proceedings of the 16th ACM International Conference on Web Search and Data Mining_. ACM, 2023, pp. 760–768.
  * [7] X.-L. Ren, N. Gleinig, D. Helbing, and N. Antulov-Fantulin, “Generalized network dismantling,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 14, pp. 6554–6559, 2019.
  * [8] Y. Yi, Z. Zhang, and S. Patterson, “Scale-free loopy structure is resistant to noise in consensus dynamics in complex networks,” _IEEE Trans. Cybern._ , vol. 50, no. 1, pp. 190–200, 2020.
  * [9] L. Shan, Y. Yi, and Z. Zhang, “Improving information centrality of a node in complex networks by adding edges,” in _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , 2018, p. 3535–3541.
  * [10] E. A. Enns, J. J. Mounzer, and M. L. Brandeau, “Optimal link removal for epidemic mitigation: A two-way partitioning approach,” _Mathematical Biosciences_ , vol. 235, no. 2, pp. 138–147, 2012.
  * [11] J. Marcelino and M. Kaiser, “Reducing influenza spreading over the airline network.” _PLoS Currents_ , vol. 1, 2009.
  * [12] R. Yan, Y. Li, W. Wu, D. Li, and Y. Wang, “Rumor blocking through online link deletion on social networks,” _ACM Transactions on Knowledge Discovery from Data_ , vol. 13, no. 2, pp. 1–26, 2019.
  * [13] S. Tsioutsiouliklis, E. Pitoura, K. Semertzidis, and P. Tsaparas, “Link recommendations for PageRank fairness,” in _Proceedings of the Web Conference_. ACM, 2022, pp. 3541–3551.
  * [14] L. Lü, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, and T. Zhou, “Vital nodes identification in complex networks,” _Physics Reports_ , vol. 650, pp. 1–63, 2016.
  * [15] D. C. Hofmann and O. Gallupe, “Leadership protection in drug-trafficking networks,” _Global Crime_ , vol. 16, no. 2, pp. 123–138, 2015.
  * [16] C. Fan, L. Zeng, Y. Sun, and Y.-Y. Liu, “Finding key players in complex networks through deep reinforcement learning,” _Nature Machine Intelligence_ , vol. 2, no. 6, pp. 317–324, 2020.
  * [17] F. Peter, “bogus’ ap tweet about explosion at the white house wipes billions off us markets,” _The Telegraph_ , 2013.
  * [18] A. K. Nandi and H. R. Medal, “Methods for removing links in a network to minimize the spread of infections,” _Computers & Operations Research_, vol. 69, pp. 10–24, 2016.
  * [19] S. Wang, X. Zhao, Y. Chen, Z. Li, K. Zhang, and J. Xia, “Negative influence minimizing by blocking nodes in social networks,” in _Proceedings of the 17th AAAI Conference on Late-Breaking Developments in the Field of Artificial Intelligence_ , 2013, pp. 134–136.
  * [20] K. Tanınmış, N. Aras, İ. K. Altınel, and E. Güney, “Minimizing the misinformation spread in social networks,” _Iise Transactions_ , vol. 52, no. 8, pp. 850–863, 2020.
  * [21] E. B. Khalil, B. Dilkina, and L. Song, “Scalable diffusion-aware optimization of network topology,” in _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2014, pp. 1226–1235.
  * [22] Q. Yao, C. Zhou, L. Xiang, Y. Cao, and L. Guo, “Minimizing the negative influence by blocking links in social networks,” in _Trustworthy Computing and Services: International Conference, ISCTCS 2014, Beijing, China, November 28-29, 2014, Revised Selected papers_. Springer, 2015, pp. 65–73.
  * [23] M. Waniek, T. P. Michalak, M. J. Wooldridge, and T. Rahwan, “Hiding individuals and communities in a social network,” _Nature Human Behaviour_ , vol. 2, no. 2, pp. 139–147, 2018.
  * [24] J. Ji, G. Wu, C. Duan, Y. Ren, and Z. Wang, “Greedily remove $k$ links to hide important individuals in social network,” in _International Symposium on Security and Privacy in Social Networks and Big Data_ , 2019, pp. 223–237.
  * [25] G. Tong, W. Wu, L. Guo, D. Li, C. Liu, B. Liu, and D.-Z. Du, “An efficient randomized algorithm for rumor blocking in online social networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 2, pp. 845–854, 2017.
  * [26] C. J. Kuhlman, G. Tuli, S. Swarup, M. V. Marathe, and S. Ravi, “Blocking simple and complex contagion by edge removal,” in _2013 IEEE 13th International Conference on Data Mining_. IEEE, 2013, pp. 399–408.
  * [27] J. Ji, G. Wu, J. Shuai, Z. Zhang, Z. Wang, and Y. Ren, “Heuristic approaches for enhancing the privacy of the leader in iot networks,” _Sensors_ , vol. 19, no. 18, 2019.
  * [28] R. Laishram, P. Hozhabrierdi, J. Wendt, and S. Soundarajan, “Netprotect: network perturbations to protect nodes against entry-point attack,” in _Proceedings of the 13th ACM Web Science Conference 2021_ , 2021, pp. 93–101.
  * [29] W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” in _Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2010, pp. 1029–1038.
  * [30] K. Stephenson and M. Zelen, “Rethinking centrality: Methods and examples,” _Social Networks_ , vol. 11, no. 1, pp. 1–37, 1989.
  * [31] M. J. Newman, “A measure of betweenness centrality based on random walks,” _Social Networks_ , vol. 27, no. 1, pp. 39–54, 2005.
  * [32] U. Brandes and D. Fleischer, “Centrality measures based on current flow,” in _Proceedings of the 22nd Annual Conference on Theoretical Aspects of Computer Science_ , 2005, p. 533–544.
  * [33] H. Li, R. Peng, L. Shan, Y. Yi, and Z. Zhang, “Current flow group closeness centrality for complex networks?” in _Proceedings of World Wide Web Conference_ , 2019, pp. 961–971.
  * [34] P. Barooah and J. P. Hespanha, “Estimation from relative measurements: Electrical analogy and large graphs,” _IEEE Trans. Signal Process._ , vol. 56, no. 6, pp. 2181–2193, 2008.
  * [35] I. Poulakakis, G. F. Young, L. Scardovi, and N. E. Leonard, “Information centrality and ordering of nodes for accuracy in noisy decision-making networks,” _IEEE Trans. Autom. Control_ , vol. 61, no. 4, pp. 1040–1045, 2016.
  * [36] A. Gusrialdi, Z. Qu, and S. Hirche, “Distributed link removal using local estimation of network topology,” _IEEE Transactions on Network Science and Engineering_ , vol. 6, no. 3, pp. 280–292, 2018.
  * [37] J. Guo, Y. Li, and W. Wu, “Targeted protection maximization in social networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 3, pp. 1645–1655, 2019.
  * [38] A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, “Guarantees for greedy maximization of non-submodular functions with applications,” in _Proceedings of the 34th International Conference on Machine Learning_ , 2017, pp. 498–507.
  * [39] D. Durfee, Y. Gao, G. Goranci, and R. Peng, “Fully dynamic spectral vertex sparsifiers and applications,” in _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019, pp. 914–925.
  * [40] U. Feige, “On sums of independent random variables with unbounded variance and estimating the average degree in a graph,” _SIAM Journal on Computing_ , vol. 35, no. 4, pp. 964–984, 2006.
  * [41] L. Beretta and J. Tětek, “Better sum estimation via weighted sampling,” in _Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2022, pp. 2303–2338.
  * [42] P. G. Doyle and J. L. Snell, _Random Walks and Electric Networks_. Mathematical Association of America, 1984.
  * [43] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [44] F. Dorfler and F. Bullo, “Kron reduction of graphs with applications to electrical networks,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 60, no. 1, pp. 150–163, 2012.
  * [45] E. Bozzo and M. Franceschet, “Resistance distance, closeness, and betweenness,” _Social Networks_ , vol. 35, no. 3, pp. 460–469, 2013.
  * [46] R. Rossi and N. Ahmed, “The network data repository with interactive graph analytics and visualization,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2015, pp. 4292–4293.
  * [47] R. M. Karp, _Reducibility among Combinatorial Problems_. Springer, 2010.
  * [48] D. Durfee, J. Peebles, R. Peng, and A. B. Rao, “Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees,” in _IEEE 58th Annual Symposium on Foundations of Computer Science_ , 2017, pp. 926–937.
  * [49] J. Leskovec and R. Sosič, “SNAP: A general-purpose network analysis and graph-mining library,” _ACM Transactions on Intelligent Systems and Technolog_ , vol. 8, no. 1, p. 1, 2016.
  * [50] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” _Reviews of Modern Physics_ , vol. 74, no. 1, p. 47, 2002.
  * [51] D. Kempe, J. Kleinberg, and É. 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_. ACM, 2003, pp. 137–146.
  * [52] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” _Proceedings of the VLDB Endowment_ , vol. 4, no. 11, pp. 1146–1157, 2011.
  * [53] M. Milani, Y. Huang, and F. Chiang, “Data anonymization with diversity constraints,” _IEEE Trans. Knowl. Data Eng._ , vol. 35, no. 4, p. 3603–3618, apr 2023.
  * [54] V. B. Rao, “Most-vital edge of a graph with respect to spanning trees,” _IEEE Transactions on Reliability_ , vol. 47, no. 1, pp. 6–7, 1998.
  * [55] C. Chen, H. Tong, B. A. Prakash, T. Eliassi-Rad, M. Faloutsos, and C. Faloutsos, “Eigen-optimization on large graphs by edge manipulation,” _ACM Transactions on Knowledge Discovery from Data_ , vol. 10, no. 4, p. 49, 2016.
  * [56] Z. Zhang, Z. Zhang, and G. Chen, “Minimizing spectral radius of non-backtracking matrix by edge removal,” in _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. ACM, 2021, pp. 2657–2667.
  * [57] A. A. Schoone, H. L. Bodlaender, and J. Van Leeuwen, “Diameter increase caused by edge deletion,” _Journal of Graph Theory_ , vol. 11, no. 3, pp. 409–427, 1987.
  * [58] U. Brandes and C. Pich, “Centrality estimation in large networks,” _International Journal of Bifurcation and Chaos_ , vol. 17, no. 07, pp. 2303–2318, 2007.
  * [59] C. Mavroforakis, R. Garcia-Lebron, I. Koutis, and E. Terzi, “Spanning edge centrality: Large-scale computation and applications,” in _Proceedings of the 24th International Conference on World Wide Web_. ACM, 2015, pp. 732–742.
  * [60] Y. Yi, L. Shan, H. Li, and Z. Zhang, “Biharmonic distance related centrality for edges in weighted networks,” in _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , 2018, pp. 3620–3626.
  * [61] M. Bellingeri, D. Bevacqua, F. Scotognella, R. Alfieri, and D. Cassi, “A comparative analysis of link removal strategies in real complex weighted networks,” _Scientific Reports_ , vol. 10, no. 1, pp. 1–15, 2020.
  * [62] S. Gaspers and K. Najeebullah, “Optimal surveillance of covert networks by minimizing inverse geodesic length,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 533–540.
  * [63] T. N. Dinh, Y. Xuan, M. T. Thai, P. M. Pardalos, and T. Znati, “On new approaches of assessing network vulnerability: Hardness and approximation,” _IEEE/ACM Transactions on Networking_ , vol. 20, no. 2, pp. 609–619, 2012\.
  * [64] L. Zhu, Q. Bao, and Z. Zhang, “Measures and optimization for robustness and vulnerability in disconnected networks,” _IEEE Trans. Inf. Forensics Security_ , vol. 18, pp. 3350–3362, 2023.
  * [65] C. Wulff-Nilsen, “Faster deterministic fully-dynamic graph connectivity,” in _Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2013, pp. 1757–1769.
  * [66] B. M. Kapron, V. King, and B. Mountjoy, “Dynamic graph connectivity in polylogarithmic worst case time,” in _Proceedings of the 32nd annual ACM symposium on Theory of computing_ , 2013, pp. 1131–1142.
  * [67] C. D. Meyer, Jr, “Generalized inversion of modified matrices,” _SIAM Journal on Applied Mathematics_ , vol. 24, no. 3, pp. 315–323, 1973.
  * [68] P. Peng, D. Lopatta, Y. Yoshida, and G. Goranci, “Local algorithms for estimating effective resistance,” in _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. ACM, 2021, pp. 1329–1338.
  * [69] D. Cheng, Y. Cheng, Y. Liu, R. Peng, and S.-H. Teng, “Efficient sampling for Gaussian graphical models via spectral sparsification,” in _Conference on Learning Theory_ , 2015, pp. 364–390.
  * [70] R. Kyng, Y. T. Lee, R. Peng, S. Sachdeva, and D. A. Spielman, “Sparsified cholesky and multigrid solvers for connection Laplacians,” in _Proceedings of the 48th Annual ACM Symposium on Theory of Computing_ , 2016, pp. 842–850.
  * [71] W. Xu and Z. Zhang, “Optimal scale-free small-world graphs with minimum scaling of cover time,” _ACM Transactions on Knowledge Discovery from Data_ , vol. 17, no. 7, p. 93, 2023.
  * [72] P. Sarkar, A. W. Moore, and A. Prakash, “Fast incremental proximity search in large graphs,” in _Proceedings of the 25th International Conference on Machine Learning_ , 2008, pp. 896–903.
  * [73] X. Zhou and Z. Zhang, “Opinion maximization in social networks via leader selection,” in _Proceedings of the ACM Web Conference_. ACM, 2023, p. 133–142.

|  Changan Liu received the B.Eng. degree in School of Software from Dalian
University of Technology, Dalian, China, in 2019. He is currently pursuing the
Ph.D. degree in School of Computer Science, Fudan University, Shanghai, China.
His research interests include network science, computational social science,
graph data mining, and social network analysis.
---|---
|  Xiaotian Zhou received the B.S. degree in mathematics science from Fudan
University, Shanghai, China, in 2020. He is currently pursuing the Ph.D.
degree in School of Computer Science, Fudan University, Shanghai, China. His
research interests include network science, computational social science,
graph data mining, and social network analysis.
---|---
|  Ahad N. Zehmakan received his PhD degree in 2020 from ETH Zurich and is
currently an Assistant Professor of Computer Science in the School of
Computing at the Australian National University. His research interests
include graph and randomized algorithms, information spreading in social
networks, random graph models, complexity theory, parallel and distributed
computing, and network security.
---|---
|  Zhongzhi Zhang (M’19) received the B.Sc. degree in applied mathematics from
Anhui University, Hefei, China, in 1997 and the Ph.D. degree in management
science and engineering from Dalian University of Technology, Dalian, China,
in 2006.
From 2006 to 2008, he was a Post-Doctoral Research Fellow with Fudan
University, Shanghai, China, where he is currently a Full Professor with the
School of Computer Science. He has published over 160 papers in international
journals or conferences. Since 2019, he has been selected as one of the most
cited Chinese researchers (Elsevier) every year. His current research
interests include network science, graph data mining, social network analysis,
computational social science, spectral graph theory, and random walks.
Dr. Zhang was a recipient of the Excellent Doctoral Dissertation Award of
Liaoning Province, China, in 2007, the Excellent Post-Doctor Award of Fudan
University in 2008, the Shanghai Natural Science Award (third class) in 2013,
the CCF Natural Science Award (second class) in 2022, and the Wilkes Award for
the best paper published in The Computer Journal in 2019. He is a member of
the IEEE.
---|---