# Minimizing Hitting Time between Disparate Groups
with Shortcut Edges

Florian Adriaens<EMAIL_ADDRESS>University of
HelsinkiHelsinkiFinland ,  Honglian Wang<EMAIL_ADDRESS>KTH Royal Institute
of TechnologyStockholmSweden and  Aristides Gionis<EMAIL_ADDRESS>KTH Royal
Institute of TechnologyStockholmSweden

(2023)

###### Abstract.

Structural bias or segregation of networks refers to situations where two or
more disparate groups are present in the network, so that the groups are
highly connected internally, but loosely connected to each other. Examples
include polarized communities in social networks, antagonistic content in
video-sharing or news-feed platforms, etc. In many cases it is of interest to
increase the connectivity of disparate groups so as to, e.g., minimize social
friction, or expose individuals to diverse viewpoints. A commonly-used
mechanism for increasing the network connectivity is to add _edge shortcuts_
between pairs of nodes. In many applications of interest, edge shortcuts
typically translate to _recommendations_ , e.g., what video to watch, or what
news article to read next. The problem of reducing structural bias or
segregation via edge shortcuts has recently been studied in the literature,
and random walks have been an essential tool for modeling navigation and
connectivity in the underlying networks. Existing methods, however, either do
not offer approximation guarantees, or engineer the objective so that it
satisfies certain desirable properties that simplify the optimization task.

In this paper we address the problem of adding a given number of shortcut
edges in the network so as to _directly_ minimize the _average hitting time_
and the _maximum hitting time_ between two disparate groups. The objectives we
study are more natural than objectives considered earlier in the literature
(e.g., maximizing hitting-time _reduction_) and the optimization task is
significantly more challenging. Our algorithm for minimizing average hitting
time is a greedy bicriteria that relies on supermodularity. In contrast,
maximum hitting time is not supermodular. Despite, we develop an approximation
algorithm for that objective as well, by leveraging connections with average
hitting time and the asymmetric $k$-center problem.

Random walks, Edge augmentation, Social networks, Polarization

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
6–10, 2023; Long Beach, CA, USA††booktitle: Proceedings of the 29th ACM SIGKDD
Conference on Knowledge Discovery and Data Mining (KDD ’23), August 6–10,
2023, Long Beach, CA, USA††doi: 10.1145/3580305.3599434††isbn:
979-8-4007-0103-0/23/08††ccs: Theory of computation Design and analysis of
algorithms††ccs: Mathematics of computing Discrete mathematics Graph theory

##  1\. Introduction

The last decade has seen a surge in the development of methods for detecting,
quantifying, and mitigating polarization and controversy in social media. An
example of a polarized network is a conversation or endorsement graph
associated with a controversial topic on Twitter. The nodes represent users,
and the edges interactions between users in the form of posts, likes,
endorsements, etc., related to a controversial topic. It has been observed
that the interactions typically occur between like-minded individuals,
resulting in the reinforcement of ones own beliefs (Barberá, 2020; Chitra and
Musco, 2019).

_Structural bias_ arises in many types of networks beyond social networks,
such as _content_ and _information networks_. Recently, several methods have
been developed for reducing _structural bias_ (Haddadan et al., 2021) or
_segregation_ (Coupette et al., 2023; Fabbri et al., 2022) in _content
networks_. An example of a content network is the network obtained by “what to
watch next” recommendations in a video-sharing platform. Content in such
networks can often be divided into two or more groups, each of which is highly
connected internally, but loosely connected to each other. These groups could
be the result of differentiating between “harmful” (or radicalized) content
and “neutral” (or non-radicalized) content, or simply the result of different
opinion (pro/contra) on a certain issue. It might be beneficial for users
navigating these platforms to be exposed to diverse content—exposing
themselves to multiple viewpoints—in order to become better informed.

A particular line of research focuses on adding new edges (denoted as
_shortcut_ edges) to a network, with the goal of reducing some quantifiable
measure of polarization, controversy, structural bias, or segregation
(Coupette et al., 2023; Demaine and Zadimoghaddam, 2010; Fabbri et al., 2022;
Haddadan et al., 2021; Garimella et al., 2018; Parotsidis et al., 2015). Many
of these measures are defined on the basis of _random walks_ between groups of
nodes. In content graphs, random walks are a natural and simple model for how
a user navigates through content. For example, the Random Walk Controversy
(RWC) score of Garimella et al. (Garimella et al., 2018) has been reported to
“discriminate controversial topics with great accuracy” in Twitter
conversation graphs. The authors in that work suggest a method that adds a
fixed number of shortcut edges to a graph in order to reduce the RWC score of
the augmented graph (Garimella et al., 2018).

However, most of these random walk-based augmentation problems do not have
algorithms with provable approximation guarantees (Garimella et al., 2018), or
the optimized measure has been reformulated so that it exhibits a desirable
property (Coupette et al., 2023; Fabbri et al., 2022; Haddadan et al., 2021).

For example, the work of Haddadan et al. (Haddadan et al., 2021) considers
maximizing the gain function $\Delta_{g}({F})=g(\emptyset)-g(F)$ in the
context of bounded-length random walks in directed graphs. Here, $F$ is a set
of at most $k$ new shortcut edges that will be added to an input graph, and
the function $g$ is the _average expected hitting time_ for a random walk
starting in one group to hit the other group (see Definition 1). They prove
that $\Delta_{g}$ is a non-negative monotone submodular set function, and
thus, the well-known greedy algorithm of (Nemhauser et al., 1978) ensures a
$(1-1/e)$ approximation guarantee.

Similarly, the work of Fabbri et al. (Fabbri et al., 2022) considers a gain
function in the form of $\Delta_{f}({\cdot})=f(\emptyset)-f(\cdot)$ in the
context of degree-regular directed graphs and with _rewiring_ operations
instead of shortcut edge additions. Here, the function $f$ is the _largest
hitting time_ instead of the average (see Definition 1). Fabbri et al. show
that the existence of a multiplicative approximation algorithm implies
$\mathbf{P}=\mathbf{NP}$. This result leads them to propose heuristic
algorithms. However, their inapproximability result does not follow from the
use of random walks, nor from the rewire operations. Their reduction still
applies if one would replace “largest hitting time” with “largest shortest
path distance,” for example. Hence, their inapproximability result is an
artefact of maximizing a gain function in combination with the $\max$ operator
in the function $f$ (Definition 1).

The previous discussion motivates the following question: “ _What can we say
about directly _minimizing_ the functions $f$ and $g$, instead of indirectly
optimizing them by maximizing associated gain functions?_”

This paper provides several first algorithmic results and ideas regarding this
question for both functions $f$ and $g$. We take an abstract view and define
our problems on input graphs in their simplest form, without the additional
constraints (bounded-length random walks or degree-regular graphs) considered
in Haddadan et al. (2021) and Fabbri et al. (2022), respectively. We consider
uniform simple random walks of unbounded length on undirected, unweighted and
connected input graphs.

Results and techniques. For the first problem we study, _minimize average
hitting time_ (BMAH), we observe that the objective is supermodular and it can
be optimized by a greedy bicriteria strategy (Liberty and Sviridenko, 2017a),
which offers an $(1+\epsilon)$-approximation at the cost of adding
logarithmically more edges. In addition, we show how to speed up this
algorithm by deriving an approximation for the objective, which relies on
sampling a small number of bounded-length absorbing random walks and bounding
the error term using eigenvalue techniques. The length of these walks directly
depends on the _mixing time_ and _average degree_ of the red nodes, which are
bounded quantities in most real-life networks. We then show that running the
same greedy strategy of Liberty and Sviridenko (2017a) on the _approximative_
values, still provides a $(2+\epsilon)$-approximation factor.

For our second problem, _minimize maximum hitting time_ (BMMH), the objective
function is neither supermodular nor submodular, and thus, it is a more
challenging task. Nevertheless, we present two different algorithms, both with
approximation guarantees, albeit, weaker than in the case of average hitting
time. The first algorithm utilizes a relation between maximum and average
hitting time, and uses the greedy strategy designed for the BMAH problem. The
second algorithm leverages a novel connection between BMMH and the asymmetric
$k$-center problem (Kariv and Hakimi, 1979), and utilizes optimal methods
developed for the latter problem (Archer, 2001).

Table 1. Results summary. The approximation factor is computed with respect to an optimal solution that uses at most $k$ edges. $d_{\text{m}}$ is at most the maximum degree (see Section 6.2). | Approx. factor | Number of shortcut edges
---|---|---
BMAH | $1+\epsilon$ | $\mathcal{O}(k\log(n/\epsilon))$
BMAH | $2+\epsilon$ | $\mathcal{O}(k\log(n/\epsilon))$
BMMH | $\mathcal{O}(n^{3/4})$ | $\mathcal{O}(k\log n)$
BMMH | $\mathcal{O}\left(\log^{*}(k)\,d_{\text{m}}\right)$ | $k$

##  2\. Related work

A large body of work has been devoted to designing methods for optimizing
certain graph properties via edge additions, edge rewirings, or other graph-
edit operations. These approaches include methods for increasing graph
robustness (Chan and Akoglu, 2016), maximizing the centrality of a group of
nodes (Medya et al., 2018), improving the betweenness centrality of a node
(Bergamini et al., 2018), reducing the average shortest path distances over
all pairs of nodes (Meyerson and Tagiku, 2009; Parotsidis et al., 2015),
minimizing the diameter of the graph (Demaine and Zadimoghaddam, 2010;
Adriaens and Gionis, 2022), increasing resilience to adversarial attacks (Ma
et al., 2021), and more. Some of these approaches provide algorithms with
provable approximation guarantees, while the others are mostly practical
heuristics.

The setting of the problem we consider has also been studied in the context of
understanding phenomena of bias, polarization, and segregation in social
networks (Bakshy et al., 2015; Chen et al., 2018; Chitra and Musco, 2019;
Flaxman et al., 2016; Garimella et al., 2018; Guerra et al., 2013; Minici et
al., 2022; Ribeiro et al., 2020), and developing computational methods to
mitigate those adverse effects (Amelkin and Singh, 2019; Garimella et al.,
2017a, b; Gionis et al., 2013; Matakos et al., 2020; Musco et al., 2018; Tu et
al., 2020; Zhu et al., 2021; Zhu and Zhang, 2022). Most of the works listed
above seek to optimize a complex objective related to some dynamical diffusion
process, such as information cascades (Kempe et al., 2003), or opinion
dynamics (Friedkin and Johnsen, 1990). In all cases, the optimization
functions studied in previous work are significantly different from the
hitting-time objectives considered in this paper.

As discussed in the introduction, the work that is most closely related to
ours, is the paper by Haddadan et al. (2021), which seeks to reduce the
structural bias between two polarized groups of a network via edge insertions.
Their approach is based on hitting time for bounded-length random walks, but
contrary to our proposal, they seek to _maximize the reduction_ of hitting
time caused by edge insertions, rather than _directly minimizing the hitting
time_. Similar ideas have been proposed by other authors, e.g., Fabbri et al.
(2022) and more recenty Coupette et al. (2023), in the context of reducing
exposure to harmful content. We consider our work to be a compelling extension
of such previous ideas, not only due to optimizing a more natural objective,
but also for coping with a more challenging optimization problem, for which
our solution offers new technical ideas and insights.

##  3\. Preliminaries

Graphs. We consider undirected connected graphs $G=(V,E)$ with $|V|=n$ nodes,
where the nodes $V$ are bipartitioned into two groups $R$ and $B$. These
groups as referred to as the _red_ and _blue_ nodes, respectively. We only
consider bipartitions $V=\\{R,B\\}$ that are _valid_ , meaning that $R$ and
$B$ are disjoint and non-empty. For a non-valid bipartition, our problem
statements (Section 4.1) are either trivial or ill-defined. An edge is an
_inter-group_ edge if it has one blue and one red endpoint. For a subset of
nodes $X\subseteq V$, we let $E[X]$ be the subset of edges of $G$ that have
both endpoints in $X$, and $G[X]=(X,E[X])$ be the subgraph of $G$ _induced_ by
$X$. If $F$ is a set of non-edges of $G=(V,E)$, then $G+F$ denotes the graph
$(V,E\cup F)$. The degree of a node $v$ in $G$, which is the number of
neighbors of $v$ in $G$, is denoted as $d_{G}(v)$. We let $d_{R}$ be the
average of the degrees of red nodes.

Random walks. Every random walk will be a uniform simple random walk, unless
stated otherwise. By uniform simple random walk we mean that at each step one
of the neighbors of the current node is selected with uniform probability.
Given a graph $G=(V,E)$ and $A\subseteq V$, the random variable $\tau_{u}(A)$
indicates the first time that a random walk on $G$ starting from $u$ visits
$A$. If $u\in A$, we set $\tau_{u}(A)=0$. The expectation of this random
variable is denoted as
$H_{G}(u,A)=\operatorname{\mathbb{E}}_{G}[\tau_{u}(A)]$, where the subscript
emphasizes that the random walk is on $G$. With a slight abuse of notation,
$H_{G}(u,v)$ is thus the (expected) _hitting time_ for a walk starting from
$u$ to visit $v$ for the first time. Note that $H_{G}(u,u)=0$ and
$H_{G}(u,A)=0$ if and only if $u\in A$. It also holds that $H_{G}(u,A)\leq
H_{G}(u,B)$ when $B\subseteq A$, and in particular $H_{G}(u,A)\leq\min_{a\in
A}H_{G}(u,a)$.

Matrices and norms. We denote $\mathbf{A}$ as the adjacency matrix of a graph,
and $\mathbf{D}$ is the degree diagonal matrix. Let
$e_{r}\in\mathbb{R}^{r\times 1}$ be the vector of all-ones of size $r$, and
let $\left\lVert\cdot\right\rVert_{2}$ denote the spectral norm.

Additional definitions. For a graph $G=(V,E)$ with a valid bipartition
$V=\\{R,B\\}$, let $(R\times B)\setminus E$ be the set of inter-group non-
edges in $G$. Define the following two set functions $f,g:2^{(R\times
B)\setminus E}\rightarrow\mathbb{R}_{>0}$ as the _maximum_ and _average
hitting time_.

######  Definition 1 (Maximum and average hitting time).

For a set of inter-group non-edges $F\subseteq(R\times B)\setminus E$, we
define the _maximum hitting time from $R$ to $B$ on graph $G+F$_ by

$\displaystyle f(F)$ $\displaystyle\triangleq\max_{r\in R}H_{G+F}(r,B),$

and the _average hitting time from $R$ to $B$ on graph $G+F$_ by

$\displaystyle g(F)$ $\displaystyle\triangleq\frac{1}{|R|}\sum_{r\in
R}H_{G+F}(r,B).$

##  4\. Problems and observations

In this section, we formally define the problems we study, and we discuss
their properties.

###  4.1. Problems

We introduce and study the following two problems, which we denote as the BMMH
(Budgeted Minimum Maximum Hitting time) and BMAH (Budgeted Minimum Average
Hitting time) problems.

######  Problem 1 (Budgeted Minimum Maximum Hitting time problem (BMMH)).

Given an undirected connected graph $G=(V,E)$, with a valid bipartition
$V=\\{R,B\\}$, and a budget $k\in\mathbb{N}$, we seek to find a set of inter-
group non-edges $F\subseteq(R\times B)\setminus E$ with $|F|\leq k$ that
minimizes $f(F)$, where $f$ is the maximum hitting-time function defined in
Definition 1.

######  Problem 2 (Budgeted Minimum Average Hitting time problem (BMAH)).

Identical definition to Problem 1, but we aim to minimize the function $g$,
instead of $f$, where $g$ is the average hitting-time function defined in
Definition 1.

BMMH aims to augment $G$ with $k$ new inter-group edges, so as to minimize the
_largest_ hitting time to a blue node, for random walks starting from red
nodes. Likewise, BMAH aims to minimize the _average_ hitting time from red to
blue nodes. Note that for every red node we allow multiple new edges to be
incident to it, as long as the augmented graph remains simple.

###  4.2. Observations

The $\mathbf{NP}$-hardness of both BMMH and BMAH follows from a reduction from
the minimum set cover problem, very similar to the reduction detailed by
Haddadan et al. (2021) and omitted for brevity. We present several useful
observations regarding BMMH and BMAH that will guide the design of
approximation algorithms:

######  Observation 1.

Changing the blue endpoints of the edges in a feasible solution $F$ does not
change $f(F)$ or $g(F)$.

###### Proof.

Every walk starts from a red node and halts the moment a blue node is hit,
hence the identity of the blue endpoints of edges in $F$ do not matter. ∎

Both problems thus reduce to selecting a multiset of red endpoints, as we
allow multiple edges in $F$ to have the same red endpoint. If a red node is
connected to all the blue nodes already, we can of course not add any more new
edges incident to it.

######  Observation 2 (monotonicity).

If $Y\subseteq X$, then $f(X)\leq f(Y)$ and $g(X)\leq g(Y)$.

###### Proof.

Let $F$ be a feasible solution. For every $r\in R$, the hitting time
$H_{G+F}(r,B)$ is a monotonically decreasing set function of $F$, since the
edges in $F$ are inter-group edges. Every $e\in F$ only helps in reducing the
hitting time from $r$ to $B$. This can be proven more formally by a
straightforward coupling argument between a walker on $G$ and $G+F$ (Lovász,
1993; Haddadan et al., 2021). Since individual hitting times are monotone, the
functions $f$ and $g$ are monotone, as well. ∎

The following supermodularity property for individual hitting times is less
obvious, and a variant of it was proven by Haddadan et al. (2021) for bounded-
length random walks on directed graphs. We give a different and shorter proof
of supermodularity in our case of unbounded random walks, by using a coupling
argument.

######  Observation 3 (supermodularity of hitting times).

For all $r\in R$ and for all $e_{1}\neq e_{2}\in(R\times B)\setminus E$ it
holds that

(1) $H_{G+e_{2}}(r,B)-H_{G+\\{e_{1},e_{2}\\}}(r,B)\leq
H_{G}(r,B)-H_{G+e_{1}}(r,B).$

###### Proof.

Pick any $r\in R$. We assume all walks start from $r$. Consider the right-hand
side of Eq. (1). Couple walks on $G+e_{1}$ to walks on $G$ by simply following
the walker on $G$, until the walker hits the red endpoint $r_{1}\in R$ of the
edge $e_{1}$. If the walker hits $r_{1}$, follow the edge $e_{1}$ with
probability $\frac{1}{d_{G}(r_{1})+1}$. With probability
$\frac{d_{G}(r_{1})}{d_{G}(r_{1})+1}$, keep following the walker on $G$. It is
clear that the marginal distribution of this coupled walk is a uniform random
walk on $G+e_{1}$.

As long as $e_{1}$ is not traversed, the two coupled walks are identical. If
$e_{1}$ is traversed, the walks are identical up until the time prior to
traversing $e_{1}$, when they are both in $r_{1}$ for the last time. On this
moment, the walker on $G$ still needs to travel $H_{G}(r_{1},B)$ steps on
average to hit $B$, while the walker on $G+e_{1}$ needs 1 more step
(conditioned on $e_{1}$ being traversed). Hence for all $r\in R$ we have

$\displaystyle H_{G}(r,$ $\displaystyle B)-H_{G+e_{1}}(r,B)$
$\displaystyle=~{}$ $\displaystyle(H_{G}(r_{1},B)-1)\,\text{Pr[traversing
$e_{1}$ when walking on $G+e_{1}$]}.$

Similarly, we can write for the left-hand side of Eq. (1)

$\displaystyle H_{G+e_{2}}(r,B)-H_{G+\\{e_{1},e_{2}\\}}(r,B)$
$\displaystyle=(H_{G+e_{2}}(r_{1},B)-1)\text{Pr[traversing $e_{1}$ when
walking on $G+\\{e_{1},e_{2}\\}$]}.$

The result follows from Observation 2, since both $H_{G+e_{2}}(r_{1},B)\leq
H_{G}(r_{1},B)$ and

Pr[traversing $\displaystyle e_{1}\text{ when walking on
$G+\\{e_{1},e_{2}\\}$]}$ $\displaystyle\leq~{}\text{Pr[traversing $e_{1}$ when
walking on $G+e_{1}$]}.$

∎

Observation 3 states that individual hitting times are supermodular, hence the
objective function $g$ of BMAH is also supermodular. However, the objective
function $f$ of BMMH is not guaranteed to be supermodular, as a result of the
max operator. Observation 4 shows that even the weaker notion of
weakly-$\alpha$ supermodularity (Liberty and Sviridenko, 2017b) does not hold
for $f$.

######  Observation 4.

The function $g$ is supermodular, but the function $f$ is not weakly-
supermodular for any $\alpha\geq 1$.

###### Proof.

The supermodularity of $g$ is direct, as it is an average of supermodular
functions (Observation 3). We prove the second statement of the observation. A
non-negative non-increasing set function $\gamma$ on $[n]$ is said to be
weakly-$\alpha$ supermodular with $\alpha\geq 1$ if and only if for all
$S,T\subseteq[n]:\gamma(S)-\gamma(S\cup T)\leq\alpha\sum_{i\in T\setminus
S}(\gamma(S)-\gamma(S\cup\\{i\\}))$ (Liberty and Sviridenko, 2017b, Definition
2). Consider the following instance for BMMH. The input graph is a path of
five nodes. All the nodes are red, except the middle node is blue. Let
$S=\emptyset$ and $T$ be the two edges that connect both red endpoints to the
blue center. Then, $f(S)-f(S\cup T)>0$, but for all $i\in T\setminus
S:f(S)-f(S\cup\\{i\\})=0$. ∎

##  5\. Algorithms for minimizing
average hitting time

We first discuss our algorithms for the BMAH problem, as we can use them as a
building block for the BMMH problem.

###  5.1. A Greedy bicriteria algorithm

Algorithm 1 [Greedy] bicrit. $(1+\epsilon)$-approximation for BMAH.

1:$G=(R\cup B,E)$, parameter $k\geq 1$ and error $\epsilon>0$.

2:$F_{0}\leftarrow\emptyset$

3:while $(i\leftarrow
1;i\leq\lceil{k\ln{(\frac{n^{3}}{\epsilon})}}\rceil;i\leftarrow i+1)$ do

4: $F_{i}\leftarrow F_{i-1}\cup\operatorname*{arg\,min}_{e\in(R\times
B)\setminus(E\cup F_{i-1})}g(F_{i-1}\cup{\\{e\\}})$.

5:$F_{i}$.

According to Observation 4 the objective function $g$ of BMAH is supermodular.
It also holds that $g\geq 1$, as it takes at least one step to hit a blue node
starting from any red node. There are two main ways for minimizing a non-
negative monotone-decreasing supermodular function in the literature. One
approach gives bounds that depend on the _total curvature_ (Sviridenko et al.,
2017) of the objective function. For example, the work of Sviridenko et al.
(2017, Section 6.2) details a randomized algorithm with guarantee
$1+\frac{c}{(1-c)e}+\frac{\mathcal{O}(\epsilon)}{1-c}$, for any $\epsilon>0$
and curvature $c\in[0,1)$. However, we do not utilize this algorithm since it
is not straightforward how to bound the curvature of $g$, nor how to
practically implement their algorithm.

Instead, we follow the bicriteria approach of Liberty and Sviridenko (2017a),
where they show that the classic greedy algorithm gives a bicriteria
$(1+\epsilon)$-approximation by allowing the addition of more than $k$
elements. Their results are applicable if either the objective function is
bounded away from zero (which holds in our case, since $g\geq 1$), or one has
an approximate initial solution. An immediate consequence of their results is
Lemma 1.

######  Lemma 0.

The Greedy strategy (Algorithm 1) returns a $(1+\epsilon)$-approximation to an
optimal solution of BMAH (that adds at most $k$ edges) by adding at most
$\lceil{k\ln{(\frac{n^{3}}{\epsilon})}}\rceil$ edges.

###### Proof.

We may assume $k\geq 1$. Let $F^{*}$ denote an optimal solution to BMAH with
at most $k$ edges. We always have a crude approximate initial solution
$F_{0}=\emptyset$, since for any $F^{*}$ it holds that $g(\emptyset)\leq
n^{3}\leq n^{3}g(F^{*})$. The first inequality holds because hitting times in
connected graphs are upper bounded by $n^{3}$ (Lovász, 1993). The second
inequality follows from $g\geq 1$. The lemma essentially follows by
application of the results of Liberty and Sviridenko (2017a, Theorem 6). We
give a short proof here for completeness. Let $F_{\tau}$ be the output of
Algorithm 1, where $\tau=\lceil{k\ln{(\frac{n^{3}}{\epsilon})}}\rceil$. By
using the supermodularity and monotonicity of $g$, we get the following
recursion:

$\displaystyle g(F_{\tau})-g(F^{*})$
$\displaystyle\leq\left(g(\emptyset)-g(F^{*})\right)\left(1-1/k\right)^{\tau}$
$\displaystyle\leq(n^{3}-1)g(F^{*})\left(1-1/k\right)^{k\ln{(n^{3}/\epsilon)}}$
$\displaystyle\leq(n^{3}-1)g(F^{*})e^{-\ln{(n^{3}/\epsilon)}}\leq\epsilon
g(F^{*}).$

∎

Note that finding the new edge that minimizes line 3 in Algorithm 1 does not
require a search over $\mathcal{O}(n^{2})$ possible non-edges. By Observation
1 we only need to choose a red endpoint, reducing the search to
$\mathcal{O}(n)$ possible choices in each iteration.

###  5.2. Greedy+: Speeding up Greedy

In practice, lazy evaluation (Minoux, 2005) will typically reduce the number
of function evaluations that Algorithm 1 makes to $g$. Nonetheless, function
evaluations are still expensive. They require either solving a linear system
of equations with $\mathcal{O}(n)$ variables, or directly computing the
fundamental matrix $(\mathbf{I}-\mathbf{Q})^{-1}$ of an absorbing Markov chain
with absorbing states $B$, where $\mathbf{Q}$ denotes the probability
transition matrix between the transient red nodes (Kemeny and Snell, 1983).

####  5.2.1. $(1\pm\epsilon)$-estimation of $g$

We show how to get a fast estimate $\hat{g}$ that satisfies w.h.p.
$\hat{g}(\cdot)\in(1\pm\epsilon)g(\cdot)$, for some error $\epsilon>0$.

The high-level idea is to write $g$ as a certain quadratic form of the
fundamental matrix of an absorbing Markov chain with absorbing states being
the blue nodes. The fundamental matrix of an absorbing Markov chain can be
written as an infinite matrix power series (Kemeny and Snell, 1983). We will
estimate this infinite series by a truncated sum. The truncated sum can be
estimated efficiently by simulating random walks of bounded length, while the
error induced by the truncation can also be shown to be small. The point of
truncation will depend on certain graph parameters, such as the mixing time
and average degree of the red nodes. Since most real-life graphs typically
have bounded mixing time and bounded average degree, our approach is expected
to work well in practice. This idea of truncating a matrix power series has
been recently used by Peng et al. (Peng et al., 2021) and prior to that by
Andoni et al. (Andoni et al., 2018).

The following holds for any connected graph, so without loss of generality we
prove our estimates for $g(\emptyset)$. Let $r=|R|$ throughout this proof. Let
$h_{R}\in\mathbb{R}^{r\times 1}$ denote the vector of expected hitting times
from the red nodes until absorption by the blue nodes. Let
$\mathbf{Q}\in\mathbb{R}^{r\times r}$ be the transition matrix between red
nodes, obtained by deleting the rows and columns of corresponding blue nodes
in the random-walk transition matrix $\mathbf{P}=\mathbf{D}^{-1}\mathbf{A}$.
It is well-known (Kemeny and Snell, 1983) that
$h_{R}=(\mathbf{I}_{r}-\mathbf{Q})^{-1}e_{r}$. Since $g(\emptyset)$ is the
average of $h_{R}$, we can write

$g(\emptyset)=\frac{1}{r}e_{r}^{T}(\mathbf{I}_{r}-\mathbf{Q})^{-1}e_{r}=\frac{1}{r}e_{r}^{T}\displaystyle\sum_{i=0}^{+\infty}\mathbf{Q}^{i}e_{r},$

where the second equality follows from $\mathbf{Q}^{i}\to\mathbf{0}$, as
$i\to+\infty$, since $|B|\geq 1$ by our assumption of valid bipartition
(Kemeny and Snell, 1983, Theorem 1.11.1).

Now define
$p_{1}\triangleq\frac{1}{r}e_{r}^{T}\sum_{i=0}^{\ell}\mathbf{Q}^{i}e_{r}$ and
$p_{2}\triangleq\frac{1}{r}e_{r}^{T}\sum_{i=\ell+1}^{+\infty}\mathbf{Q}^{i}e_{r}$.
We first show how to estimate $p_{1}$.

######  Lemma 0.

Let $\epsilon,\delta\in(0,1)$. For every $u\in R$, run
$t\geq\frac{\ell^{2}}{\epsilon^{2}}\ln(\frac{2n}{\delta})$ absorbing random
walks ($B$ are the absorbing nodes) with bounded length $\ell$ and record how
many steps are taken. Take the empirical average over these $t$ trials, for
every $u$, and stack the results in a vector $\hat{h}$. With probability at
least $1-\delta$,
$\hat{h}\in(1\pm\epsilon)\sum_{i=0}^{\ell}\mathbf{Q}^{i}e_{r}$. Hence, also
with probability at least $1-\delta$, it holds that
$\frac{1}{r}e_{r}^{T}\hat{h}\in(1\pm\epsilon)p_{1}$.

###### Proof.

We can give a probabilistic interpretation to $p_{1}$. We argue that it is the
average of the hitting times—over all the red nodes as starting points—for
absorbing random walks with bounded length $\ell$. In other words, the walk
halts when either it has taken more than $\ell$ steps, or it hits a blue node,
whichever comes first. Consider such a bounded absorbing walk starting from
$u\in R$. Let $n_{uv}$ be the random variable counting the number of times the
walk visits red node $v\in R$. Let $n^{i}_{uv}$ be $1$ if this walk is in
state $v$ after exactly $i$ steps, and $0$ otherwise. Clearly
$n_{uv}=\sum_{i=0}^{\ell}n^{i}_{uv}$. So the expectation satisfies

$\displaystyle\operatorname{\mathbb{E}}[n_{uv}]$
$\displaystyle=\sum_{i=0}^{\ell}\operatorname{\mathbb{E}}[n^{i}_{uv}]=\sum_{i=0}^{\ell}(1\cdot\mathbf{Q}^{i}_{uv}+0\cdot(1-\mathbf{Q}^{i}_{uv}))=\sum_{i=0}^{\ell}\mathbf{Q}^{i}_{uv}.$

Thus $\sum_{i=0}^{\ell}\mathbf{Q}^{i}e_{r}$ is a vector where the $u$-th entry
is the hitting time of an absorbing (with absorbing states $B$) bounded (with
length $\ell$) random walk starting from red node $u$. And $p_{1}$ is the
average of this vector. To find a $(1\pm\epsilon)$-estimation of $p_{1}$ it
suffices to find a $(1\pm\epsilon)$-estimation of each entry of
$\sum_{i=0}^{\ell}\mathbf{Q}^{i}e_{r}$. Now it is straightforward to estimate
every $u$-th entry of $\sum_{i=0}^{\ell}\mathbf{Q}^{i}e_{r}$ within a factor
of $(1\pm\epsilon)$. Run $t$ walks from $u$ and compute the empirical average
of their lengths as the estimator. Such an estimation is exactly the topic of
the RePBubLik paper (Haddadan et al., 2021, Lemma 4.3), and the claim in Lemma
2 follows easily from Hoeffding’s inequality and the union bound. ∎

Next we show how to bound $p_{2}$ as a small fraction of $g(\emptyset)$, for a
sufficiently large choice of $\ell$.

######  Lemma 0.

If $\ell\geq\frac{\log(d_{R}/\epsilon(1-\lambda))}{\log(1/\lambda)}-1$, then
$p_{2}\leq\epsilon g(\emptyset)$.

###### Proof.

Let $\mathbf{D}_{R}\in\mathbb{R}^{r\times r}$ be a diagonal matrix with
diagonal entries being the degrees of the red nodes in $G$. All entries
$d_{1},\ldots,d_{r}$ are at least one, since $G$ is assumed to be connected.
Recall that $d_{R}=\frac{d_{1}+\ldots+d_{r}}{r}$ is the average of these
entries.

Let $\mathbf{A}_{R}\in\mathbb{R}^{r\times r}$ be the adjacency matrix of
$G[R]$. Note that $\mathbf{Q}=\mathbf{D}_{R}^{-1}\mathbf{A}_{R}$. Observe that
the matrix
$\mathbf{M}=\mathbf{D}_{R}^{-1/2}\mathbf{A}_{R}\mathbf{D}_{R}^{-1/2}=\mathbf{D}_{R}^{1/2}\mathbf{Q}\mathbf{D}_{R}^{-1/2}$
is real-valued, symmetric, and similar to $\mathbf{Q}$. So the real-valued
eigenvalues $\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{r}$ of
$\mathbf{M}$ are also the eigenvalues of $\mathbf{Q}$ (by similarity) and
$\mathbf{M}$ has a orthonormal eigendecomposition
$\mathbf{M}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}$. Let
$\lambda=\max\\{|\lambda_{1}|,|\lambda_{r}|\\}$ be the spectral radius of
$\mathbf{M}$ (and of $\mathbf{Q}$). By symmetry of $\mathbf{M}$, we have that
$\left\lVert\mathbf{M}\right\rVert_{2}=\lambda$. We know $\lambda<1$, since
$\mathbf{Q}$ is a _weakly-chained substochastic matrix_ ,111This is the case
when for all $i$: either the $i$-th row of $\mathbf{Q}$ sums to a value $<1$,
or from $i$ it is always possible to reach another $j$ for which every row
sums to a value $<1$. (Azimzadeh, 2018, Corollary 2.6). Hence,

$\displaystyle p_{2}$ $\displaystyle=\left\lVert
p_{2}\right\rVert_{2}\leq\frac{1}{r}\left\lVert\mathbf{D}_{R}^{-1/2}e_{r}\right\rVert_{2}\sum_{i=\ell+1}^{+\infty}\left\lVert\mathbf{M}^{i}\right\rVert_{2}\left\lVert\mathbf{D}_{R}^{1/2}e_{r}\right\rVert_{2}$
$\displaystyle\leq\frac{1}{r}\left\lVert\mathbf{D}_{R}^{-1/2}e_{r}\right\rVert_{2}\sum_{i=\ell+1}^{+\infty}\left\lVert\mathbf{M}\right\rVert^{i}_{2}\left\lVert\mathbf{D}_{R}^{1/2}e_{r}\right\rVert_{2}$
$\displaystyle\leq\frac{\lambda^{\ell+1}}{r(1-\lambda)}\sqrt{\left(d_{1}+\ldots+d_{r}\right)\left(\frac{1}{d_{1}}+\ldots+\frac{1}{d_{r}}\right)}$
$\displaystyle\leq\frac{\lambda^{\ell+1}}{(1-\lambda)}d_{R}\leq\epsilon\leq\epsilon
g(\emptyset).$

The first and second inequality use the similarity between $\mathbf{Q}$ and
$\mathbf{M}$, the orthonormal eigendecomposition of $\mathbf{M}$, and matrix
norm properties. The third inequality follows from $\lambda<1$. The fourth
inequality holds as $\sum_{i}1/d_{i}\leq\sum_{i}d_{i}$, as $d_{i}\geq 1$, and
by plugging in the choice of
$\ell\geq\frac{\log(d_{R}/\epsilon(1-\lambda))}{\log(1/\lambda)}-1$. The final
step follows from $g(\emptyset)\geq 1$. ∎

We combine Lemma 2 and Lemma 3 to obtain our final result.

######  Lemma 0.

Given an undirected connected graph $G=(V,E)$, with a valid bipartition
$V=\\{R,B\\}$, we can find an estimate
$\hat{g}(\emptyset)\in(1\pm\epsilon)g(\emptyset)$ with probability at least
$1-1/{n^{c}}$ (for some $c\geq 1$) in time

(2)
$\mathcal{O}\left(\frac{c\,n\,\ln(n)\,\log^{3}(d_{R}/\epsilon(1-\lambda))}{\epsilon^{2}\,\log^{3}(1/\lambda)}\right).$

###### Proof.

We use the estimate $\hat{g}=\frac{1}{r}e_{r}^{T}\hat{h}$ from Lemma 2 as our
estimate of $g(\emptyset)$ with parameter $\epsilon^{\prime}=\epsilon/2$.
Recall that $g(\emptyset)=p_{1}+p_{2}$. Since $\hat{g}$ is an estimation of
$p_{1}$ by Lemma 2, it holds (w.h.p.) that
$\hat{g}\leq(1+\epsilon/2)p_{1}\leq(1+\epsilon)g(\emptyset)$ since $p_{2}\geq
0$. On the other hand,
$\hat{g}\geq(1-\epsilon/2)p_{1}=(1-\epsilon/2)(g(\emptyset)-p_{2})\geq(1-\epsilon/2)(1-\epsilon/2)g(\emptyset)\geq(1-\epsilon)g(\emptyset)$,
where the second to last inequality uses Lemma 3.

The time complexity follows from Lemma 2 by plugging in $\delta=1/{n^{c}}$ and
the choice of $\ell$ from Lemma 3. We need to do this for every red node and
there could be $\mathcal{O}(n)$ of them. Every bounded random walk also needs
at most $\ell$ steps. ∎

####  5.2.2. Greedy on the estimated values

Lemma 4 states that we can find good estimates
$\hat{g}(\cdot)\in(1\pm\epsilon)g(\cdot)$ relatively fast and with good
probability. A natural question to ask is whether running the greedy
bicriteria approach from Algorithm 1 on $\hat{g}$ (instead of $g$) still
ensures some form of approximation guarantee, given that $\hat{g}$ is not
guaranteed to be supermodular. A similar question has been answered
affirmatively for the classic greedy algorithm of Nemhauser et al. (1978) for
maximizing a nonnegative monotone submodular function under a cardinality
constraint, by the work of Horel and Singer (2016). They showed that when
$\epsilon<1/k$, the greedy still gives a constant-factor approximation (Horel
and Singer, 2016, Theorem 5).

We show an analogue result for the bicriteria greedy approach (Liberty and
Sviridenko, 2017b) to minimization of our monotone decreasing nonnegative
supermodular objective function $g$, under a cardinality constraint.

######  Theorem 5.

Algorithm 2 returns a set $F_{\tau}$ that satisfies

(3) $g(F_{\tau})\leq(2+\epsilon)\text{OPT},$

where $\text{ OPT}=g(O)$ and $O$ is an optimal solution of BMAH with at most
$k$ edges.

###### Proof.

By non-negativity, supermodularity and monotonicty of $g$, we can write for
iteration $i$ in Algorithm 2

$\displaystyle g(F_{i})$ $\displaystyle-\text{OPT}\leq g(F_{i})-g(F_{i}\cup
O)\leq\sum_{e\in O}g(F_{i})-g(F_{i}\cup\\{e\\})$ $\displaystyle\leq\sum_{e\in
O}g(F_{i})-\frac{1}{1+\epsilon}\hat{g}(F_{i}\cup\\{e\\})\leq\sum_{e\in
O}g(F_{i})-\frac{1}{1+\epsilon}\hat{g}(F_{i+1})$ $\displaystyle\leq\sum_{e\in
O}g(F_{i})-\frac{1-\epsilon}{1+\epsilon}g(F_{i+1})\leq
k\left(g(F_{i})-\frac{1-\epsilon}{1+\epsilon}g(F_{i+1})\right).$

In the third and fifth inequality we made use of
$\hat{g}(\cdot)\in(1\pm\epsilon)g(\cdot)$, and the fourth inequality utilizes
the greedy choice in Algorithm 2. So we have the following recursion

(4)
$g(F_{i+1})\leq\left(\frac{1+\epsilon}{1-\epsilon}\right)(1-1/k)g(F_{i})+\left(\frac{1+\epsilon}{1-\epsilon}\right)\frac{\text{OPT}}{k}.$

This recursion is of the form of $u_{i+1}\leq au_{i}+b$, which after $\tau$
iterations satisfies $u_{\tau}\leq a^{\tau}u_{0}+\frac{1-a^{\tau}}{1-a}b$. Now
write $\epsilon=\delta/k$ for $\delta\in(0,1/4]$. With our specific choice of
$a=\frac{1+\epsilon}{1-\epsilon}(1-1/k)$ and
$\tau=\lceil{2k\ln{(\frac{n^{3}}{\epsilon})}}\rceil$ we upper bound
$a^{\tau}u_{0}=a^{\tau}g(\emptyset)$ as

$\displaystyle a^{\tau}g(\emptyset)$
$\displaystyle=\left(\left(\frac{k+\delta}{k-\delta}\right)(1-1/k)\right)^{{\tau}}g(\emptyset)\leq
e^{(2\delta-1)2\ln(n^{3}/\epsilon)}g(\emptyset)$ $\displaystyle\leq
e^{-\ln(n^{3}/\epsilon)}g(\emptyset)=\frac{\epsilon}{n^{3}}g(\emptyset)\leq\epsilon\text{OPT}.$

where the first inequality follows from Fact 1 and the last inequality from
the discussion in the proof of Lemma 1.

######  Fact 1.

Let $x\in\mathbb{R}$ with $|x|\leq 1$. Let $k\geq 1$ be a positive integer.
Then it holds that

(5) $\left(\frac{k+x}{k-x}\left(1-\frac{1}{k}\right)\right)^{k}\leq e^{2x-1}.$

Next we upper bound the second part $\frac{1-a^{\tau}}{1-a}b$. It can be
verified that $0\leq a<1$ for parameters $\epsilon=\delta/{k}$, $\delta\leq
1/4$ and $k\geq 1$. Thus,

$\displaystyle\frac{1-a^{\tau}}{1-a}b\leq\frac{1}{1-a}b=\frac{1+\epsilon}{1-2\epsilon
k+\epsilon}\,\text{OPT}\leq\frac{1}{1-2\delta}\,\text{OPT}\leq 2\,\text{OPT}.$

∎

Algorithm 2 [Greedy+] bicrit. $(2+\epsilon)$-approximation for BMAH.

1:$G=(R\cup B,E)$, parameter $k\geq 1$, error $\epsilon\in(0,\frac{1}{4k}]$
and estimates $\hat{g}(\cdot)\in(1\pm\epsilon)g(\cdot)$ as found by Lemma 4.

2:$F_{0}\leftarrow\emptyset$

3:while $(i\leftarrow
1;i\leq\lceil{2k\ln{(\frac{n^{3}}{\epsilon})}}\rceil;i\leftarrow i+1)$ do

4: $F_{i}\leftarrow F_{i-1}\cup\operatorname*{arg\,min}_{e\in(R\times
B)\setminus(E\cup F_{i-1})}\hat{g}(F_{i-1}\cup{\\{e\\}})$.

5:$F_{i}$.

##  6\. Algorithms for minimizing
maximum hitting time

Next we turn our attention to the BMMH problem. We first show that a
$\alpha$-approximation for BMAH results in an
$(2|R|^{3/4}\alpha)$-approximation for BMMH. We then give a completely
different approach based on the asymmetric $k$-center problem (Kariv and
Hakimi, 1979).

###  6.1. Relating the average and the maximum hitting times

The BMMH objective function $f$ is not supermodular (Observation 4), although
we know that for every $r\in R$ each individual hitting time $H_{G+F}(r,B)$ is
a supermodular and monotonically decreasing set function of $F$ (Observation 2
and Observation 3).

We exploit this idea, by upper bounding $f$ by an expression that involves $g$
(Theorem 1). Since also $g\leq f$, we can use any approximation algorithm for
minimizing $g$ (for instance, the methods in Sections 5.1 and 5.2) and use the
upper bound to derive an approximation guarantee for BMMH.

Theorem 1 relates the average and maximum hitting time from red to blue nodes.
We credit Yuval Peres (Peres, 2022) for the proof of Theorem 1, in case the
set $B$ is a singleton, and extend the proof here when $B$ contains more than
one node. Theorem 1 gives a remarkable non-trivial $\mathcal{O}(n^{3/4})$
upper bound on the ratio of the maximum and average hitting times between two
groups that constitute a bipartition of the graph. Theorem 2 shows that there
exists graphs for which this is tight. In contrast, if we disregard the
bipartition, and take the average and the maximum hitting time over _all
nodepairs_ instead, then it is known that this ratio can grow as bad as
$\mathcal{O}(n)$, but not worse (Filmus, 2015).

######  Theorem 1.

Given an undirected connected graph $G$ with a valid bipartation
$V=\\{R,B\\}$. Let $F\subseteq(R\times B)\setminus E$ be a set of non-edges.
Then,

(6) $g(F)\leq f(F)\leq 2|R|^{3/4}g(F).$

###### Proof.

It clearly suffices to prove this for $F=\emptyset$. Since $G$ is connected,
the hitting time between any two nodes is finite-valued. The first inequality
is immediate since the maximum is not less than the average. Consider the
second inequality. Let $\alpha>0$ be some real number, which we will later
choose carefully. Categorize the nodes into two groups, the ones with a “high”
hitting time and the ones with a “low” hitting time to the blue nodes. More
concretely, define

$S=\\{v\in V:H_{G}(v,B)\leq\alpha g(\emptyset)\\},$

and $S^{c}$ as the complement of this set. Since

$|R|g(\emptyset)=\sum_{r\in R}H_{G}(r,B)\geq\sum_{r\in
S^{c}}H_{G}(r,B)>|S^{c}|\alpha g(\emptyset),$

it follows that $|S^{c}|<|R|/\alpha$. The first inequality holds because
$S^{c}\subseteq R$ (since $B\subseteq S$), and the second inequality uses the
definition of $S^{c}$.

Now consider the graph $G^{*}$ with $|S^{c}|+1$ nodes, obtained by the
following contraction in $G$: All nodes in $S$ are contracted to a single
supernode $s$. If $w\in S^{c}$ has several edges connecting it to $S$ in $G$,
we only keep one of these edges. This edge connects $w$ to $s$ in $G^{*}$.
This contraction process has the property that for all $v\in S^{c}$ it holds
$H_{G}(v,S)\leq H_{G^{*}}(v,s)$, which is easily proved by a straightforward
coupling argument. Now we can bound $H_{G^{*}}(v,s)$. Since $G^{*}$ is
connected, contains no multi-edges, and has $|S^{c}|+1$ nodes, it follows that
$H_{G^{*}}(v,s)\leq|S^{c}|^{3}$ by a well-known result (see, for instance,
Lawler (1986), and Brightwell and Winkler (1990)). By the strong Markov
property (Levin and Peres, 2017, Appendix A.3), it holds for all $v\in V:$

$\displaystyle H_{G}(v,B)$ $\displaystyle\leq H_{G}(v,S)+\max_{u\in
S}H_{G}(u,B)$ (7) $\displaystyle\leq|S^{c}|^{3}+\alpha
g(\emptyset)<\big{(}(|R|/{\alpha})^{3}+\alpha\big{)}g(\emptyset),$

where the last inequality holds because $|S^{c}|<|R|/\alpha$ and
$g(\emptyset)\geq 1$. Now Eq. (6.1) is minimized for the choice
$\alpha=|R|^{3/4}$, and hence $f(\emptyset)\leq 2|R|^{3/4}g(\emptyset)$. ∎

To see the tightness of the upper bound in Theorem 1, consider the following
family of graphs.

######  Theorem 2.

There exists graphs for which the ratio $f(\emptyset)/g(\emptyset)\\\
\in\Omega(n^{3/4})$.

###### Proof.

Consider the following star-path-clique configuration. We have a star
consisting of $n$ nodes, with center node $x$. Attach to $x$ a
$(n^{1/4},n^{1/4})$-lollipop graph (see Brightwell and Winkler (1990)). More
precisely, attach to $x$ a path of $n^{1/4}$ nodes and to the other endpoint
of this path we attach a clique of also $n^{1/4}$ nodes. Set $B=\\{x\\}$ and
$R=V\setminus B$. Clearly $f(\emptyset)\in\Theta(n^{3/4})$ since a random walk
starting from a clique node needs a cubic number of expected steps with
respect to the size of the lollipop to reach $x$ (Brightwell and Winkler,
1990). On the other hand,

$g(\emptyset)\in\mathcal{O}\left(\frac{n\cdot 1+n^{1/4}\cdot
n^{3/4}}{n}\right)=\mathcal{O}(1),$

and the claim follows. ∎

Putting the pieces together, we get the following result.

######  Corollary 1.

An $\alpha$-approximation for BMAH is a $(2|R|^{3/4}\alpha)$-approximation for
BMMH.

###### Proof.

Consider the output $F$ of $\alpha$-approximation algorithm for BMAH. Let
$O_{g}$ (resp. $O_{f}$) be an optimal solution of BMAH (resp. BMMH). Using
Theorem 1 it holds that $f(F)\leq 2|R|^{3/4}g(F)\leq 2|R|^{3/4}\alpha
g(O_{g})\leq 2|R|^{3/4}\alpha g(O_{f})\leq 2|R|^{3/4}\alpha f(O_{f})$. ∎

###  6.2. An asymmetric $k$-center approach

Hitting times in both undirected and directed graphs form a quasi-metric, in
the sense that they satisfy all requirements to be a metric except symmetry,
since it generally holds that $H_{G}(u,v)\neq H_{G}(v,u)$. However, hitting
times do satisfy the triangle inequality (Lovász, 1993). We will try to
exploit this, by linking the BMMH problem to the following variant of the
asymmetric $k$-center problem.

######  Problem 3.

[Asymmetric $k$-center Problem with one fixed center] Given a quasi-metric
space $(V,d)$ and a point $x\in V$. Find a set of $k$ centers $F\subseteq V$,
$|F|\leq k$ that minimize

$\displaystyle\max_{v\in V}d(v,F\cup\\{x\\}),$

where for a set $A\subseteq V$ it holds $d(v,A)=\min_{a\in A}d(v,a)$.

Problem 3 is a variant of the classic asymmetric $k$-center problem (Kariv and
Hakimi, 1979). It is not hard to see that Problem 3 is as hard to approximate
as the classic problem. Additionally, existing algorithms (Archer, 2001;
Panigrahy and Vishwanathan, 1998) for the classic problem can easily be
modified to solve Problem 3.

We show a relationship between BMMH and Problem 3. Let $\mathcal{I}_{1}$ be an
instance to BMMH. Lemma 4 states that the optimum of Problem 3 on a well-
chosen quasi-metric space $\mathcal{I}_{2}$ (which depends on the instance
$\mathcal{I}_{1}$) is a lower bound for the optimum of BMMH on instance
$\mathcal{I}_{1}$. We define this quasi-metric space in Definition 2.

######  Definition 2 (modified hitting time quasi-metric).

Let $G=(R\cup B,E)$ be an input graph to BMMH. Associate with $B$ a single new
point $b$, and consider function
$d:(R\cup\\{b\\})\times(R\cup\\{b\\})\to\mathbb{R}_{\geq 0}$ defined as

(8) $d(u,v)\triangleq\begin{cases}H_{G}(u,v)&\text{if $u,v\in R$},\\\
H_{G}(u,B)&\text{if $u\in R$ and $v=b$},\\\ \max_{i\in B}H_{G}(i,v)&\text{if
$u=b$ and $v\in R$},\\\ 0&\text{if $u=v=b$}.\end{cases}$

######  Proposition 0.

$(R\cup\\{b\\},d)$ is a quasi-metric space.

###### Proof.

We prove the triangle inequality $d(x,y)\leq d(x,z)+d(z,y)$, as the identity
axiom is satisfied. The triangle inequality holds when $b\neq x,y,z$, because
of standard triangle inequality of hitting times. So consider the case where
$b$ is present in the inequality. There are three cases involving $u,v\in R$
and $b$:

  * •

$d(u,v)\leq d(u,b)+d(b,v)$ or equivalently $H_{G}(u,v)\leq
H_{G}(u,B)+\max_{i\in B}H_{G}(i,v)$. This holds because of the strong Markov
property when visiting the set $B$.

  * •

$d(u,b)\leq d(u,v)+d(v,b)$ or equivalently $H_{G}(u,B)\leq
H_{G}(u,v)+H_{G}(v,B)$. This holds because of triangle inequality of hitting
times.

  * •

$d(b,u)\leq d(b,v)+d(v,u)$ or equivalently $\max_{i\in
B}H_{G}(i,u)\leq\max_{j\in B}H_{G}(j,v)+H_{G}(v,u)$. Let
$i^{*}=\operatorname*{arg\,max}_{i\in B}H_{G}(i,u)$. This holds because
$H_{G}(i^{*},u)\leq H_{G}(i^{*},v)+H_{G}(v,u)\leq\max_{j\in
B}H_{G}(j,v)+H_{G}(v,u)$.

∎

######  Lemma 0.

Let $M^{*}$ be the optimum of BMMH for an input graph $G$. Let $C^{*}$ be the
optimum of Problem 3 on the quasi-metric space defined in Definition 2 with
$x=b$. Then, it holds that

$\displaystyle C^{*}\leq M^{*}.$

###### Proof.

Consider the red endpoints $C=\\{c_{1},\ldots,c_{k}\\}\subseteq R$ of a set of
edges $F$ to BMMH that achieves the optimum value $M^{*}$. Note that some
endpoints might be the same, so $C$ is a multiset. Let $G^{*}=G+F$ be the
augmentation of $G$ with $F$.

Create a feasible solution to Problem 3 by taking $C$ as the set of chosen
centers. We claim that for every $v\in R\cup\\{b\\}$ it holds that
$d(v,C\cup\\{b\\})\leq M^{*}$. We have three cases. If $v=b$, the claim is
trivially satisfied. If $v\neq b$ and $H_{G}(v,B)\leq M^{*}$, the claim also
holds, as from Definition 2 we have $d(v,C\cup\\{b\\})\leq
d(v,b)=H_{G}(v,B)\leq M^{*}$. So the remaining case is when $v\neq b$ and
$H_{G}(v,B)>M^{*}$. Since $H_{G^{*}}(v,B)\leq M^{*}$ (by definition of
$M^{*}$) there must exist a non-empty set of endpoints $I\subseteq C$, such
that for all $i\in I$:

$\displaystyle\text{Pr}[\text{walk starting from $v$ uses a new edge incident
to }i]>0,$

when walking on the graph $G^{*}$. Let $I$ be the largest such set. Using the
law of total expectation, decompose222In Eq. (9) we have assumed that
$\text{Pr}[\text{walk uses no new edges}]>0$. The analysis when this
probability is zero is easier and follows the same reasoning. $H_{G^{*}}(v,B)$
as

(9) $\displaystyle H_{G^{*}}(v,B)=~{}$ $\displaystyle H_{G^{*}}(v,B|\text{
walk uses no new edges})$ $\displaystyle\quad\cdot\text{Pr}[\text{walk uses no
new edges}]$ $\displaystyle+\sum_{i\in I}H_{G^{*}}(v,B|\text{ walk uses a new
edge incident to }i)$ $\displaystyle\quad\cdot\text{Pr}[\text{walk uses a new
edge incident to }i]\leq M^{*}.$

By our case assumption $H_{G}(v,B)>M^{*}$, it holds that

$\displaystyle H_{G^{*}}(v,B|\text{ walk uses no new
edges})=H_{G}(v,B)>M^{*}.$

Thus the only way Eq. (9) can hold is when

$\displaystyle\min_{i\in I}H_{G^{*}}(v,B\mid\text{walk uses a new edge
incident to }i)\leq M^{*}.$

Let $i^{*}$ be a center $i\in I$ that attains the minimum. The result follows
since

$\displaystyle d(v,$ $\displaystyle C\cup\\{b\\})\leq d(v,C)=\min_{c\in
C}H_{G}(v,c)\leq H_{G}(v,i^{*})$ $\displaystyle\leq
H_{G^{*}}(v,B\mid\text{walk uses a new edge incident to }i^{*})\leq M^{*}.$

∎

Algorithm 3 [ASyMM]
$\mathcal{O}\left(\beta\,d_{\text{m}}\right)$-approximation for BMMH.

1:$G=(R\cup B,E)$, parameter $k\geq 1$.

2:Run any $\beta$-approximation algorithm (Archer, 2001; Panigrahy and
Vishwanathan, 1998) for asymmetric $k$-center variant (Problem 3) on the
quasi-metric space defined in Definition 2, with fixed center $x=b$.

3:Let $C=\\{c_{1},\ldots,c_{k}\\}\subseteq R$ be the output of step 1. Return
a set $F$ of at most $k$ shortcut edges by connecting every $c_{i}$ to some
node in $B$.

Lemma 4 allows us to analyze Algorithm 3. We write $d_{\text{m}}=\max_{c\in
C}d_{G}(c)$ for the maximum degree of the nodes in $C$, and $\beta$ for the
approximation guarantee of an asymmetric $k$-center algorithm. The state-of-
the-art approximation for asymmetric $k$-center is
$\beta=\mathcal{O}(\log^{*}(k))$ by two different algorithms of Archer (2001).

######  Theorem 5.

Algorithm 3 is an $\mathcal{O}\left(\beta\,d_{\text{m}}\right)$-approximation
for BMMH.

###### Proof.

By using a $\beta$-approximation for Problem 3 and using Lemma 4 we get that
for all $r\in R$ it is $H_{G}(r,C)\leq\min_{c\in
C}H_{G}(r,c)\allowbreak\leq\beta C^{*}\leq\beta M^{*}$. Consider a random walk
that starts from any $r\in R$. In expectation we need at most $\beta M^{*}$
steps to encounter a node $c\in C$. We know that every $c\in C$ is incident to
_some_ edge connecting it to $B$. This is either a new shortcut edge $e\in F$
from Algorithm 3, or if we cannot add a new shortcut edge incident to $c$,
this implies that $c$ is already connected to all the blue nodes. In either
case, when the walk is at $c$, we have a chance of at least
$\frac{1}{d_{\text{m}}+1}$ to hit the blue nodes in the next step. On the
other hand, if the walk does not follow such an edge, the walk needs at most
another $\beta M^{*}$ steps in expectation to reach $C$ again, and the process
repeats. Of course, the walk might have encountered a blue node along the way,
but this is only beneficial. So we conclude that for all $r\in R$:

$\displaystyle H_{G+F}(r,B)$ $\displaystyle\leq(\beta
M^{*}+1)\frac{1}{d_{\text{m}}+1}+(2\beta
M^{*}+1)\frac{d_{\text{m}}}{d_{\text{m}+1}}\frac{1}{d_{\text{m}}+1}+$
$\displaystyle(3\beta
M^{*}+1)\left(\frac{d_{\text{m}}}{d_{\text{m}+1}}\right)^{2}\frac{1}{d_{\text{m}}+1}+\ldots=1+(d_{\text{m}}+1)\beta
M^{*}.$

The last step follows by splitting the sum as a geometric series and an
arithmetico-geometric series, which states that
$\sum_{i=1}^{\infty}ir^{i}=\frac{r}{(1-r)^{2}}$ for $0<r<1$. ∎

(a)

(b)

(c)

(d)

(e)

(a) Wiki Abort.

(b) Wiki Guns

(c) Amazon Mate

(d) Amazon MiHi

(d) Wiki Sociol.

(d)

Figure 1. The y-axis shows the performance of the algorithms in reducing the
functions $g$ (first row) and $f$ (second row) in terms of the number of newly
added shortcut edges $k$. The x-axis shows the number of new edges $k$ as a
fraction of $|R|$.

##  7\. Experimental Evaluation

Although our work is mostly theoretical, we will compare the performance of
our most scalable algorithm Greedy+ with several baselines on real-life
datasets. In particular, we want to measure how Greedy+ reduces the objective
functions of BMAH and BMMH when we add an incrementally larger set of shortcut
edges to the graph, and we want to verify if other existing algorithms are
effective for these two tasks.

Baselines. We will compare with the fastest variant of the RePBubLik
algorithm, which is the RePBubLik+ algorithm (Haddadan et al., 2021), as well
as with three simplified variants of RePBubLik+. We set the _parochial_ nodes
(Haddadan et al., 2021) of the algorithm equal to $R$. The RePBubLik+
algorithm ranks the parochial nodes according to their random-walk centrality
(only computed once), and includes a penalty factor that favours the insertion
of new shortcut edges to red nodes that have not been shortcut before. The
first variant, _PureRandom_ (Haddadan et al., 2021) selects the endpoints of
the new edges uniformly at random from $R$ and $B$. The second variant is
_Random Top- $N$ Central Nodes ($N$-RCN)_ (Haddadan et al., 2021), which sorts
the top $N$ red nodes in order of descending random-walk centrality and picks
$k$ source nodes uniformly from this set of $N$ nodes. The third variant is
_Random Top- $N$ Weighted Central Nodes ($N$-RWCN)_, which accounts
additionally accounts for the random-walk transition probabilities in the
ordering (Haddadan et al., 2021). Finally, we compare with the _ROV_ algorithm
(Garimella et al., 2017a). ROV outputs $k$ shortcut edges such that their
addition aims to minimize the Random Walk Controversy (RWC) score (Garimella
et al., 2018) of the augmented graph. The RWC score tries to capture how well
separated the two groups are with respect to a certain controversial topic. It
considers candidate edges between high-degree vertices of both groups $R$ and
$B$. Then the top-$k$ edges are picked with respect to the RWC score. All
parameters of the aforementioned algorithms are set to their standard
settings.

Table 2. Datasets used in the experiments. For each network, we extracted the largest connected component. $|E|_{R\leftrightarrow B}$ denotes the number of inter-group edges, and $|E|_{tot}$ the total number of edges. Data | $|R|$ | $|B|$ | $|E|_{R\leftrightarrow B}$ | $|E|_{\text{tot}}$
---|---|---|---|---
_Wiki Guns_ (Menghini et al., 2020) | 134 | 117 | 132 | 550
_Wiki Abort._ (Menghini et al., 2020) | 208 | 396 | 232 | 1585
_Amazon Mate_ (Leskovec and Krevl, 2014) | 160 | 11 | 16 | 287
_Amazon MiHi_ (Leskovec and Krevl, 2014) | 25 | 63 | 56 | 146
_Wiki Sociol._ (Menghini et al., 2020) | 648 | 2588 | 430 | 8745

Experimental setup. All experiments are performed on an Intel core i5 machine
at 1.8 GHz with 16 GB RAM. Our methods are implemented in Python 3.8 and we
made publicly available.333https://anonymous.4open.science/r/KDD-2023-Source-
Code-0E2C/ We use the same datasets as RePBubLik (Haddadan et al., 2021), see
Table 2.

Implementation of Greedy+. We set $\epsilon=\lambda=0.1$ in our experiments.
In order to draw a fair comparison with the other baselines, we run Greedy+
for $k$ steps and not more. We also simplify the way we calculate the average
$g$ over all the red nodes in each iteration. Lemma 2 states that we need to
run several walks starting from each $r\in R$ and then compute the empirical
average, but we only do this for a randomly chosen subset of $|R|/10$ red
nodes. This significantly sped up the process, without sacrificing too much in
quality.

Results. Figure 1 shows the performance of the proposed algorithms and
baselines. On the $x$-axis it shows the number of new shortcut edges $k$ as a
fraction of the total number of red nodes $|R|$. We observe that our algorithm
Greedy+ is competitive, performing very similar to RePBubLik+, for minimizing
both objective functions $f$ and $g$. Both these algorithms outperform the
other baselines. The slightly better performance for RePBubLik+ in some cases
might be due to specific parameter settings, as well as the fact RePBubLik+ is
repeated 10 times whereas our algorithm only once. Intuitively RePBubLik+ and
Greedy+ are in fact expected to perform very similar since they both are
practical approximative versions (with different ways of estimating) of the
same underlying greedy algorithm: picking the next edge that maximizes the
RePBubLik+ objective function is theoretically the same edge that Greedy (see
Algorithm 1) would select. We note that the y-axis shows the _exact_ function
evaluations of $f$ and $g$, which was done by solving a linear system with
$\mathcal{O}(n)$ variables (see Sect. 5.2), which was relatively time
consuming and an important reason why we restricted ourselves to smaller
datasets.

##  8\. Conclusion

In this paper we studied the problem of minimizing average hitting time and
maximum hitting time between two disparate groups in a network by adding new
edges between pairs of nodes. In contrast to previous methods that modify the
objective so that it becomes a submodular function and the optimization
becomes straightforward, we minimize hitting time directly. Our approach leads
to having a more natural objective at the cost of a more challenging
optimization problem. For the two problems we define we present several
observations and new ideas that lead to novel algorithms with provable
approximation guarantees. For average hitting time we show that the objective
is supermodular and we apply a known bicriteria greedy method; furthermore, we
show how to efficiently approximate the computation of the greedy step by
sampling bounded-length random walks. For maximum hitting time, we show that
it relates to average hitting time, and thus, we can reuse the greedy method.
In addition, we also demonstrate a connection with the asymmetric $k$-center
problem.

###### Acknowledgements.

This research is supported by the Helsinki Institute for Information
Technology HIIT, Academy of Finland projects AIDA (317085) and MLDB (325117),
the ERC Advanced Grant REBOUND (834862), the EC H2020 RIA project SoBigData++
(871042), and the Wallenberg AI, Autonomous Systems and Software Program
(WASP) funded by the Knut and Alice Wallenberg Foundation.

## References

  * (1)
  * Adriaens and Gionis (2022) Florian Adriaens and Aristides Gionis. 2022.  Diameter Minimization by Shortcutting with Degree Constraints. In _2022 IEEE International Conference on Data Mining (ICDM)_. 843–848.  https://doi.org/10.1109/ICDM54844.2022.00095
  * Amelkin and Singh (2019) Victor Amelkin and Ambuj K Singh. 2019.  Fighting opinion control in social networks via link recommendation. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 677–685.
  * Andoni et al. (2018) Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. 2018\.  On solving linear systems in sublinear time.  _arXiv preprint arXiv:1809.02995_ (2018).
  * Archer (2001) Aaron Archer. 2001\.  Two $O(\log^{*}k)$-approximation algorithms for the asymmetric $k$-center problem. In _Integer Programming and Combinatorial Optimization: 8th International IPCO Conference Utrecht, The Netherlands, June 13–15, 2001 Proceedings 8_. Springer, 1–14.
  * Azimzadeh (2018) Parsiad Azimzadeh. 2018\.  A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-matrix.  _Math. Comp._ 88, 316 (2018), 783–800.
  * Bakshy et al. (2015) Eytan Bakshy, Solomon Messing, and Lada A Adamic. 2015\.  Exposure to ideologically diverse news and opinion on Facebook.  _Science_ 348, 6239 (2015), 1130–1132.
  * Barberá (2020) Pablo Barberá. 2020\.  Social media, echo chambers, and political polarization.  _Social media and democracy: The state of the field, prospects for reform_ 34 (2020).
  * Bergamini et al. (2018) Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D’angelo, Henning Meyerhenke, Lorenzo Severini, and Yllka Velaj. 2018\.  Improving the betweenness centrality of a node by adding links.  _Journal of Experimental Algorithmics (JEA)_ 23 (2018), 1–32.
  * Brightwell and Winkler (1990) Graham Brightwell and Peter Winkler. 1990.  Maximum hitting time for random walks on graphs.  _Random Structures & Algorithms_ 1, 3 (1990), 263–276.
  * Chan and Akoglu (2016) Hau Chan and Leman Akoglu. 2016.  Optimizing network robustness by edge rewiring: A general framework.  _Data Mining and Knowledge Discovery_ 30 (2016), 1395–1425.
  * Chen et al. (2018) Xi Chen, Jefrey Lijffijt, and Tijl De Bie. 2018.  Quantifying and minimizing risk of conflict in social networks. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1197–1205.
  * Chitra and Musco (2019) Uthsav Chitra and Christopher Musco. 2019.  Understanding filter bubbles and polarization in social networks.  _arXiv preprint arXiv:1906.08772_ (2019).
  * Coupette et al. (2023) Corinna Coupette, Stefan Neumann, and Aristides Gionis. 2023\.  Reducing Exposure to Harmful Content via Graph Rewiring. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_.
  * Demaine and Zadimoghaddam (2010) Erik D Demaine and Morteza Zadimoghaddam. 2010.  Minimizing the diameter of a network using shortcut edges. In _Algorithm Theory-SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings 12_. Springer, 420–431.
  * Fabbri et al. (2022) Francesco Fabbri, Yanhao Wang, Francesco Bonchi, Carlos Castillo, and Michael Mathioudakis. 2022\.  Rewiring what-to-watch-next recommendations to reduce radicalization pathways. In _Proceedings of the ACM Web Conference 2022_. 2719–2728.
  * Filmus (2015) Yuval Filmus. 2015\.  https://cs.stackexchange.com/questions/42917/average-vs-worst-case-hitting-time.  (2015).
  * Flaxman et al. (2016) Seth Flaxman, Sharad Goel, and Justin M Rao. 2016\.  Filter bubbles, echo chambers, and online news consumption.  _Public opinion quarterly_ 80, S1 (2016), 298–320.
  * Friedkin and Johnsen (1990) Noah E Friedkin and Eugene C Johnsen. 1990.  Social influence and opinions.  _Journal of Mathematical Sociology_ 15, 3-4 (1990), 193–206.
  * Garimella et al. (2017a) Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2017a.  Reducing controversy by connecting opposing views. In _Proceedings of the tenth ACM international conference on web search and data mining_. 81–90.
  * Garimella et al. (2017b) Kiran Garimella, Aristides Gionis, Nikos Parotsidis, and Nikolaj Tatti. 2017b.  Balancing information exposure in social networks.  _Advances in neural information processing systems_ 30 (2017).
  * Garimella et al. (2018) Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018.  Quantifying controversy on social media.  _ACM Transactions on Social Computing_ 1, 1 (2018), 1–27.
  * Gionis et al. (2013) Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. 2013\.  Opinion maximization in social networks. In _Proceedings of the 2013 SIAM International Conference on Data Mining_. SIAM, 387–395.
  * Guerra et al. (2013) Pedro Guerra, Wagner Meira Jr, Claire Cardie, and Robert Kleinberg. 2013.  A measure of polarization on social media networks based on community boundaries. In _Proceedings of the international AAAI conference on web and social media_ , Vol. 7. 215–224.
  * Haddadan et al. (2021) Shahrzad Haddadan, Cristina Menghini, Matteo Riondato, and Eli Upfal. 2021.  RePBubLik: Reducing Polarized Bubble Radius with Link Insertions. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ (Virtual Event, Israel) _(WSDM ’21)_. Association for Computing Machinery, New York, NY, USA, 139–147.  https://doi.org/10.1145/3437963.3441825
  * Horel and Singer (2016) Thibaut Horel and Yaron Singer. 2016.  Maximization of Approximately Submodular Functions. In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ (Barcelona, Spain) _(NIPS’16)_. Curran Associates Inc., Red Hook, NY, USA, 3053–3061.
  * Kariv and Hakimi (1979) Oded Kariv and S Louis Hakimi. 1979.  An algorithmic approach to network location problems. I: The $p$-centers.  _SIAM journal on applied mathematics_ 37, 3 (1979), 513–538.
  * Kemeny and Snell (1983) John G Kemeny and J Laurie Snell. 1983.  _Finite Markov chains: with a new appendix ”Generalization of a fundamental matrix”_.  Springer.
  * Kempe et al. (2003) David Kempe, Jon Kleinberg, and Éva Tardos. 2003\.  Maximizing the spread of influence through a social network. In _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_. 137–146.
  * Lawler (1986) Gregory F Lawler. 1986\.  Expected hitting times for a random walk on a connected graph.  _Discrete Mathematics_ 61, 1 (1986), 85–92.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Levin and Peres (2017) David A Levin and Yuval Peres. 2017.  _Markov chains and mixing times_. Vol. 107.  American Mathematical Soc.
  * Liberty and Sviridenko (2017a) Edo Liberty and Maxim Sviridenko. 2017a.  Greedy Minimization of Weakly Supermodular Set Functions. In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)_ _(LIPIcs, Vol. 81)_. Dagstuhl, Germany, 19:1–19:11.
  * Liberty and Sviridenko (2017b) Edo Liberty and Maxim Sviridenko. 2017b.  Greedy minimization of weakly supermodular set functions. In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Lovász (1993) László Lovász. 1993\.  Random walks on graphs.  _Combinatorics, Paul erdos is eighty_ 2, 1-46 (1993), 4\.
  * Ma et al. (2021) Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. 2021.  Graph adversarial attack via rewiring. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1161–1169.
  * Matakos et al. (2020) Antonis Matakos, Cigdem Aslay, Esther Galbrun, and Aristides Gionis. 2020.  Maximizing the diversity of exposure in a social network.  _IEEE Transactions on Knowledge and Data Engineering_ 34, 9 (2020), 4357–4370.
  * Medya et al. (2018) Sourav Medya, Arlei Silva, Ambuj Singh, Prithwish Basu, and Ananthram Swami. 2018.  Group centrality maximization via network design. In _Proceedings of the 2018 SIAM International Conference on Data Mining_. SIAM, 126–134.
  * Menghini et al. (2020) Cristina Menghini, Aris Anagnostopoulos, and Eli Upfal. 2020\.  Auditing Wikipedia’s Hyperlinks Network on Polarizing Topics.  _arXiv preprint arXiv:2007.08197_ (2020).
  * Meyerson and Tagiku (2009) Adam Meyerson and Brian Tagiku. 2009.  Minimizing average shortest path distances via shortcut edge addition. In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings_. Springer, 272–285.
  * Minici et al. (2022) Marco Minici, Federico Cinus, Corrado Monti, Francesco Bonchi, and Giuseppe Manco. 2022.  Cascade-based echo chamber detection. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 1511–1520.
  * Minoux (2005) Michel Minoux. 2005\.  Accelerated greedy algorithms for maximizing submodular set functions. In _Optimization Techniques: Proceedings of the 8th IFIP Conference on Optimization Techniques Würzburg, September 5–9, 1977_. Springer, 234–243.
  * Musco et al. (2018) Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. 2018\.  Minimizing polarization and disagreement in social networks. In _Proceedings of the 2018 world wide web conference_. 369–378.
  * Nemhauser et al. (1978) George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions—I.  _Mathematical programming_ 14 (1978), 265–294.
  * Panigrahy and Vishwanathan (1998) Rina Panigrahy and Sundar Vishwanathan. 1998.  An $o(\log^{*}n)$ Approximation Algorithm for the Asymmetric $p$-Center Problem.  _Journal of Algorithms_ 27, 2 (1998), 259–268.
  * Parotsidis et al. (2015) Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2015.  Selecting shortcuts for a smaller world. In _Proceedings of the 2015 SIAM International Conference on Data Mining_. SIAM, 28–36.
  * Peng et al. (2021) Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. 2021\.  Local Algorithms for Estimating Effective Resistance. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1329–1338.
  * Peres (2022) Yuval Peres. 2022\.  Personal communication.  (2022).
  * Ribeiro et al. (2020) Manoel Horta Ribeiro, Raphael Ottoni, Robert West, Virgílio AF Almeida, and Wagner Meira Jr. 2020.  Auditing radicalization pathways on YouTube. In _Proceedings of the 2020 conference on fairness, accountability, and transparency_. 131–141.
  * Sviridenko et al. (2017) Maxim Sviridenko, Jan Vondrák, and Justin Ward. 2017\.  Optimal approximation for submodular and supermodular optimization with bounded curvature.  _Mathematics of Operations Research_ 42, 4 (2017), 1197–1218.
  * Tu et al. (2020) Sijing Tu, Cigdem Aslay, and Aristides Gionis. 2020.  Co-exposure Maximization in Online Social Networks. In _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. 3232–3243.
  * Zhu et al. (2021) Liwang Zhu, Qi Bao, and Zhongzhi Zhang. 2021.  Minimizing polarization and disagreement in social networks via link recommendation.  _Advances in Neural Information Processing Systems_ 34 (2021), 2072–2084.
  * Zhu and Zhang (2022) Liwang Zhu and Zhongzhi Zhang. 2022.  A Nearly-Linear Time Algorithm for Minimizing Risk of Conflict in Social Networks. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 2648–2656.