For every unassigned user $i$, $B(u_i)$ contains at most $\abar-1$ unassigned users in the final matching.

As shown in the proof of Lemma <ref>, $\rec(i)=\emptyset$ in the final matching only if $\left| \userset_i \right| < \abar$ when user $i$ was examined. In later steps of the algorithm, some users in $\userset_i$ may become assigned, but no users in $B(u_i)$ can change from assigned to unassigned. Thus, the final set of unassigned users in $B(u_i)$ is a subset of $\userset_i$, and therefore has size at most $\abar-1$.

Lemma <ref> provides a way to bound the density of unassigned users in each neighborhood ball.

§.§.§ Placing All Users into Large Balls

For each representative user $k\in \userset^*$, define a large ball centered at $k$, $B'(u_k)$, as a ball centered at $u_k$ with radius $d$. Note that $B(u_k) \subseteq B'(u_k)$. Define a ring centered at $k$ to be their difference, or the region in the large ball $B'(u_k)$ that is not in the neighborhood ball $B(u_k)$: $C(u_k) := B'(u_k) \backslash B(u_k)$.

See Figure <ref> for an illustration of large balls and rings.

A neighborhood ball $B(u_k)$ (red) and a large ball $B'(u_k)$ (green) centered at $u_k$ in $\mathbb{R}^3$. Only the intersections of their boundaries with the type space are shown (the two circles). The ring $C(u_k)$ is the region between the boundaries.

Cross section of the intersections of $B(u_k)$ and $B'(u_k)$ with the type space.

Neighborhood ball, large ball and ring in $\mathbb{R}^3$

Every user is in at least one large ball.

Consider any user $i$. If $i$ is unassigned, by Lemma <ref>, there must exist representative user $k$ such that $\left\lVert u_i - u_k \right\rVert \leq d$, so $u_i \in B'(u_k)$. If $i$ is assigned, it must be within a neighborhood ball centered at a representative user $k$, so $u_i \in B(u_k) \subseteq B'(u_k)$.

Note that a user can be in multiple large balls, regardless of whether the user is assigned. Since Proposition <ref> associates each user with at least one large ball, it offers us a way to bound the density of unassigned users in the entire instance by bounding the number of unassigned users in each large ball. Additionally, the neighborhood ball associated with each large ball must be fully assigned (by definition of large balls and representative users), so the bound only needs to be on each ring, which is our next step.

§.§.§ Bounding the Number of Unassigned Users in Rings

In this step, we provide an upper bound on the number of unassigned users in each ring $C(u_k)$ when dimensionality is fixed. We do so by first showing each ring can be covered by a fixed number of “coverage balls” of radius $r$, even though they may not be centered at users. We then bound the number of unassigned users in each coverage ball.

For any representative user $k$, the set of all unit vectors in the ring $C(u_k)$ can be covered by a finite number of balls of radius $r$, which we denote as coverage balls, and the number of such coverage balls only depends on dimension $D$. Formally, there exists a function $f:\mathbb{N} \mapsto \mathbb{N}$ where $f\left(D\right)$ gives the number of coverage balls required in $D$ dimensions, and a list of coverage ball centers $x_1, \dots, x_{f\left(D\right)} \in \left\{ x\in \mathbb{R}^D_{\geq 0}: \left\lVert x \right\rVert = 1 \right\}$, such that

$$ \bigcup_{i=1}^{f\left(D\right)} B(x_i) \supseteq C(u_k) \cap \left\{ x\in \mathbb{R}^D_{\geq 0}: \left\lVert x \right\rVert = 1 \right\}, $$

where $x_1, \dots, x_{f\left(D\right)}$ are not necessarily user types. In addition, when $D=3$, $f\left(D\right) = 6$.

[A covering of the ring $C(u_k)$ by 6 balls of radius $r$]A covering of the ring $C(u_k)$ (region between blue and red circles) by 6 balls of radius $r$. The dotted blue circle represents the “middle ball” with radius $r'$, and the six points on it are $x_1,\dots,x_6$. Notice that on the type space, the intersection of all 6 balls covers the entire ring.

It is easy to see the existence of a finite $f\left(D\right)$, as the ring $C(u_k)$ is a compact set in $\mathbb{R}^D$. When $D=3$, Figure <ref> illustrates the proof by construction. The sequence of coverage ball centers $\{x_1, \dots, x_6\}$ can be found by first defining a “middle ball” with radius $r'$ that is between $r$ (that of $B(u_k)$) and $d$ (that of $B'(u_k)$), then picking the 6 points on the intersection of its boundary and $\left\{ x\in \mathbb{R}^D_{\geq 0}: \left\lVert x \right\rVert = 1 \right\}$ that divides the circle evenly.

When $D>3$, a variant of Lemma <ref> is true by replacing $6$ with a constant that is at most $\kappa_D + 1$.

We now bound the number of unassigned users in each coverage ball $B(x_i)$. Since $x_i$ does not necessarily correspond to a user type, Lemma <ref> cannot be applied directly. However, we can derive a density bound on any ball of radius $r$ regardless of its center, including coverage balls. We first show a technical result:

Let $x$ be any vector in $\mathbb{R}^D_{\geq 0}$ such that $\left\lVert x \right\rVert = 1$, $B(x)=\left\{ y\in \mathbb{R}^D: \left\lVert x-y \right\rVert \leq r \right\}$ be a ball of radius $r$ centered at $x$, and $P$ be the hyperplane containing the intersection of $B(x)$ and the set of unit vectors, namely the circle $\left\{ y\in \mathbb{R}^D: \left\lVert x-y \right\rVert = r \land \left\lVert y \right\rVert = 1 \right\}$. Let $a,b$ be arbitrary points on the convex surface $B(x) \cap \left\{ y\in \mathbb{R}^D: \left\lVert y \right\rVert = 1 \right\}$, and $a',b'$ be their projections onto $P$ in the direction of the vector $x$. Then,

\begin{align}
\left\lVert a-b \right\rVert \geq r \implies \left\lVert a'-b' \right\rVert \geq \frac{d}{2}.  \label{eqn:conj_proj_radius_d/2}
\end{align}

Note $d/2$ is the radius of the circle $\left\{ y\in \mathbb{R}^D: \left\lVert x-y \right\rVert = r \land \left\lVert y \right\rVert = 1 \right\}$.

Intuitively, Lemma <ref> establishes a relationship between the convex surface in a ball $B(x)$ of radius $r$ and its projection onto the planar surface containing its boundary. This distinction is necessary because the region of all unit vectors in $B(x)$ is convex, so there's a reduction in distance when projected onto the plane. The conjecture can then allow us to utilize the properties of the kissing number (Corollary <ref>) on the planar surface. Figure <ref> provides a clearer illustration of the projection.

[A ball of radius $r$ centered at $x$ and its projection onto the plane $P$]A ball of radius $r$ centered at $x$ (blue) and its projection onto the plane $P$ (cyan). The point $x$ on the convex type space is projected to $x'\in P$, such that a radius of the ball (red, length $r$) between two unit vectors becomes a radius of the projected circle in $P$ (black, length $d/2$). In this case, both equalities in Conjecture <ref> hold. Also note the 6 green points correspond to the “kissing number arrangement” used in the last part of proof of Lemma <ref>, even though their distance before projection is also $d/2$ which is less than $r$.

Note that both equalities in (<ref>) hold when $a=x$ and $b$ is on the boundary of $B(x)$. This choice of $a$ and $b$ makes the greatest angle with the hyperplane $P$ out of all choices that ensure $\left\lVert a-b \right\rVert \geq r$, and thus, the ratio $\left\lVert a'-b' \right\rVert / \left\lVert a-b \right\rVert$ is the smallest (i.e., the distance is reduced by the greatest factor during the projection). Thus, for any other $a,b$, the ratio $\left\lVert a'-b' \right\rVert / \left\lVert a-b \right\rVert $ is greater, resulting in a greater $\left\lVert a'-b' \right\rVert$.

We can now bound the density of unassigned users in any ball of radius $r$, which can be applied to coverage balls:

Let $x$ be an arbitrary vector in $\mathbb{R}^D_{\geq 0}$ such that $\left\lVert x \right\rVert = 1$. Then, $B(x)$ contains at most $\kappa_D (\abar-1)$ unassigned users.

Let $\userset_x = \left\{ i\in \userset_0: u_i \in B(x) \land R(i) = \emptyset \right\}$ be all unassigned users in $B(x)$. Let $\userset'_x = \left\{ \phi(1), \dots, \phi(M) \right\}$ be an ordered sequence produced via the following procedure:

* Initialize $\userset:=\userset_x$.

* Choose a user $i$ from $\userset$. Add $i$ to $\userset'_x$, and remove all users in $\userset$ with distance at most $r$ from $u_i$.

* Repeat until $\userset=\emptyset$. Denote the length of the final sequence with $M$.

Note that when user $\phi(i)$ is added to $\userset'_x$, the set of users removed from $\userset$ in the same step is a subset of users in the ball $B(u_{\phi(i)})$. This means for all unassigned users $j\in \userset_x$, there exists at least one $i\in [1,M]$ such that $u_j \in B(u_{\phi(i)})$, and $j$ was removed from $\userset$ when the earliest $\phi(i)$ was examined. Thus,

\begin{align*}
\userset_x &= \userset_x \cap \left( \bigcup_{i=1}^M B\left( u_{\phi(i)} \right) \right).  %
\end{align*}

Intuitively, the procedure divides all unassigned users in $\userset_x$ into $M$ neighborhood balls completely.
Thus, the total number of unassigned users in $B(x)$ is at most

\begin{align*}
\left| \userset_x \right| &\leq \sum_{i=1}^M \left| \userset_x \cap B\left( u_{\phi(i)} \right) \right| \leq \sum_{i=1}^M \left( \text{number of unassigned users in } B\left( u_{\phi(i)} \right) \right) \leq M(\abar-1).
\end{align*}

The last inequality uses Lemma <ref>, which implies that each ball $B\left( u_{\phi(i)} \right)$ defined on an unassigned user $u_{\phi(i)}$ contains at most $\abar-1$ unassigned users.

It remains to show $M\leq \kappa_D$. Note that $\left\lVert u_{\phi(i)} - u_{\phi(j)} \right\rVert > r$ whenever $i\neq j$. Let $u'_{\phi(i)}$ be the projection of $u_{\phi(i)}$ onto the plane $P$ containing the circle $\left\{ y\in \mathbb{R}^D: \left\lVert x-y \right\rVert = r \land \left\lVert y \right\rVert = 1 \right\}$ in the direction of $x$. By Conjecture <ref>, $\left\lVert u'_{\phi(i)} - u'_{\phi(j)} \right\rVert \geq d/2$ for all $i\neq j$, and all $u'_{\phi(i)}$ lie within the circle with radius $d/2$. By Corollary <ref>, there can be at most $\kappa_D$ such points, so $M\leq \kappa_D$.

Combining Lemma <ref> and Lemma <ref> gives a bound on the number of unassigned users in $C(u_k)$:

For any representative user $k$, the ring $C(u_k)$ contains at most $\kappa_D f\left(D\right) \left(\abar-1\right)$ unassigned users. In particular, when $D=3$, this quantity is $36 \left(\abar-1\right)$.

§.§.§ Deriving an Approximation Ratio from Ring Density

We first consider the fraction of users retained by the algorithm:

Let $\userset_{LC}$ be the set of all users included in the matching produced by the  algorithm. Then, $\frac{\left|\userset_{LC} \right|}{\left|\userset_0 \right|} \geq \frac{1}{1+\kappa_D f\left(D\right)} $. In particular, when $D=3$, $\left|\userset_{LC} \right|/\left|\userset_0 \right| \geq 1/37 $.

The number of all users, $\left| \userset_{0}\right|$, satisfies

\begin{align*}
\left| \userset_{0}\right| &\leq \sum_{k\in \userset^*} \left| \userset_{0} \cap B'(u_k) \right| \quad \text{(Proposition \ref{prop:neighbor_apx_large_balls})}  \\
&= \sum_{k\in \userset^*} \left( \left| \userset_{0} \cap B(u_k) \right| + \left| \userset_{0} \cap C(u_k) \right| \right)  \\
&\leq \sum_{k\in \userset^*} \left( \left| \userset_{0} \cap B(u_k) \right| + \kappa_D f\left(D\right) \left(\abar-1\right) \right) \quad \text{(Proposition \ref{prop:neighbor_apx_ring_density})}  \\
&= \left| \userset_{LC}\right| + \sum_{k\in \userset^*} \kappa_D f\left(D\right) \left(\abar-1\right) \quad \text{(All users in $B(u_k)$ are assigned and they have no overlaps)},
\end{align*}

\begin{align*}
\frac{\left| \userset_{LC}\right|}{\left| \userset_{0}\right|} &\geq \frac{\left| \userset_{LC}\right|}{\left| \userset_{LC}\right| + \sum_{k\in \userset^*} \kappa_D f\left(D\right) \left(\abar-1\right)}  \\
&\geq \frac{\sum_{k\in \userset^*} \abar}{\sum_{k\in \userset^*} \abar + \sum_{k\in \userset^*} \kappa_D f\left(D\right) \left(\abar-1\right)}  \quad \text{(Each neighborhood ball has at least $\abar$ assigned users)}  \\
&= \frac{\abar}{\abar + \kappa_D f\left(D\right) \left(\abar-1\right)}  \\
&\geq \frac{1}{1+\kappa_D f\left(D\right)}.
\end{align*}

Finally, we prove Theorem <ref> by deriving an approximation ratio on total engagement from number of users:
[Proof of Theorem <ref>]
In any stable set, each user gets engagement at least $K\cdot \ebar$ and at most $K$. Thus,

\begin{align*}
\frac{\longtermengagement\left( \CAseq \right)}{\longtermengagement\left( \FLseq \right)} &\geq \frac{\left| \userset_{LC}\right| \cdot K \cdot \ebar}{\left| \userset_{FL}\right| \cdot K} \geq \frac{\left| \userset_{LC}\right| \cdot K \cdot \ebar}{\left| \userset_{0}\right| \cdot K} \geq \frac{\ebar}{1+\kappa_D f\left(D\right)}.
\end{align*}

where $\userset_{FL}$ is the set of users in the maximum stable set, i.e., the  algorithm's recommendations. Thus, $r\left( \ebar, D\right) \geq \frac{\ebar}{1+\kappa_D f\left(D\right)}$. In particular, when $D=3$, this lower bound evaluates to $\ebar/37$ since $f\left(D\right) = 6$.

The corresponding conjecture when $D>3$, Conjecture <ref>, is derived by substituting $f\left(D\right)$ with a hypothesized value in Conjecture <ref>, which is the only step in the entire proof that does not give a concrete numerical result on higher values of $D$.

This proof shows a lower bound on the approximation ratio of the  algorithm. The lower bound is very loose, due to the approach used in bounding the density of rings (Lemmas <ref> and <ref>) that give a maximum density of $\kappa_D f\left(D\right) \left(\abar-1\right)$ unassigned users, or $36 \left(\abar-1\right)$ unassigned users when $D=3$. We conjecture that a tighter bound for the $D=3$ case may be $18(\abar-1)$, which would give a $\ebar/19$ approximation if proven true.

§.§ Example where Neighborhood-Based Algorithms Fail

The  algorithm is among a class of algorithms that we call “neighborhood-based algorithms“, which examine local clusters of users and creators, and assign complete bipartite matchings within each cluster when applicable. This means when the density Assumption <ref> holds, the matching that such algorithms output must be the union of several complete bipartite matchings between subsets of users and creators.

We present an example where such algorithms, including the  algorithm, only achieves a fraction of long-term total engagement relative to the  algorithm. This suggests that in these cases, any recommendation algorithm that aims to do well relative to  needs to capture the “global structure” of the instance when assigning matchings, instead of focusing on local clusters.

Choose $\abar\geq 7$ to be an arbitrary integer, and $d\in [0,1]$ to be an arbitrary real value. Consider the instance shown in Figure <ref>, with $9$ creators, $5\abar-20$ users, $K=5$, and $\ebar$ is chosen such that the happy distance is $d$. User and creator types lie on the unit sphere in $\mathbb{R}^3$, and their projection onto the $\mathbb{R}^2$ space is shown in Figure <ref>: a non-negative unit vector is first chosen to be a “center node”, then 5 other “corner nodes” are evenly distributed on a sphere of radius $d$ from the center node. This means each of the corners is of distance $d$ from the center, but the pairwise distances between any two corners are all greater than $d$. Place 4 creators and 5 users at the center, and 1 creator and $\left(\bar{a}-5\right)$ users at each corner. This means each corner user is only happy with the 4 center creators and the creator in its own corner, while each center user is happy with all creators.

User and creator types projected onto $\mathbb{R}^2$. Solid dots are creators, and open dots are users. Each user receives $K=5$ recommendations, and $d$ is the happy distance.

The  recommendation, which is the only matching that retains all users and creators. Red edges are recommendations for each of the $\left(\bar{a}-5\right)$ users at each corner, which are the nearest creator and all 4 center creators. Blue edges are recommendations for each of the 5 center users, which include all 5 corner creators.

*$t\geq 2$

Matching given by , , and any neighborhood-based algorithm. It only obtains around $1/5$ of 's long-term engagement.

Illustration of Example <ref>

The only matching that satisfies all user and creator constraints is the one given by the  algorithm, as shown in Figure <ref>. Each corner user is assigned to the nearest corner creator and 4 center creators (who are the only 5 creators that the user is happy with), and each center user is assigned to all 5 corner creators. It is easy to see that no other matching can satisfy all user and creator constraints: recommendations for corner users (red edges) are effectively fixed, so the only degree of freedom is in recommendations for the 5 center users, but each corner creator requires all 5 center users for her audience constraint to be satisfied.

On the other hand, ,  and any neighborhood-based algorithm will give the matching in Figure <ref>, which only achieves approximately $1/5$ of the total engagement of .

Note that Example <ref> satisfies the density Assumption <ref>. While this suggests an upper bound of around $1/5$ for the approximation ratio $r\left( \ebar, 3 \right)$ in 3 dimensions, this is not a tight upper bound for the  algorithm. There are other examples where  only achieves long-term engagement that is approximately $1/19$ of , but other neighborhood-based algorithms that examine neighborhood balls in non-arbitrary order can do better.

However, neighborhood-based algorithms may still not do well even when Assumption <ref> holds. The choice of 5 corners is not a coincidence: 5 is one less than $\kappa_2=6$, so it is the maximum number of corner points that can be placed on the circumference while keeping all pairwise distances between them above $d$. This means the example can generalize to higher dimensions with $O\left( \kappa_D \right)$ corners, such that ,  and any other neighborhood-based algorithm only achieves approximation ratio $O\left( 1/ \kappa_D \right)$. It also means such algorithms have no hope of achieving a constant factor approximation that is independent of $D$, even with the density assumption.

§ DETAILS OF THE  2 ALGORITHM (CR2)

In Section <ref>, we briefly described the intuition behind the  2 (CR2) algorithm, which improves upon CR1 using augmenting paths to assign maximum potential audience to a creator based on the current matching. In this section, we present the CR2 algorithm in greater detail, including a motivating example, the formal definition of augmenting paths, explanations of how and why they can be used to assign users to a new creator, and finally, the CR2 algorithm itself with pseudocode.

§.§ Motivation

One drawback of CR1 is that it often assigns an unnecessarily large number of users to creators who are examined earlier in the algorithm. For example, consider an instance with $K=1$ that contains two creators $c_1$, $c_2$ and $2\abar$ users, who are split into four subsets with $\abar/2$ users each: $\userset_1$ and $\userset_2$, whose users are only happy with $c_1$ and $c_2$ respectively; and $\userset_{1,2}$ and $\userset_{2,1}$, whose users are all happy with both $c_1$ and $c_2$. Suppose the CR1 algorithm first examines $c_2$ (note that both creators have a potential audience size of $3\abar/2$). The algorithm will assign all $3\abar/2$ users in $\userset_1$,  $\userset_{1,2}$ and $\userset_{2,1}$ to $c_1$. Doing so reduces the potential audience size of $c_2$ to $\abar/2$, so she will be skipped in the next iteration as her constraint can no longer be satisfied. This means $c_2$ and all users in $\userset_{2}$ will leave the platform. However,  can retain both creators and all $2\abar$ users, by assigning $\userset_{1,2}$ to $c_1$ and $\userset_{2,1}$ to $c_2$.

The CR2 algorithm aims to resolve this issue by adding an “error correction” mechanism, which notices that when $c_2$ is examined, users in $\userset_{2,1}$ are unnecessary for $c_1$ (thus it was an “error” to assign excess audience to $c_1$ earlier in the algorithm), and these users can be reassigned to $c_2$ for her constraint to be satisfied. It implements this mechanism using augmenting paths. In this example, for any user $i\in \userset_{2,1}$, the recommendation or “edge” $\left( u_i, c_1 \right)$ is in the current matching but $\left( u_i, c_2 \right)$ is not. (Recall from Figure <ref> that our problem can also be seen as a many-to-many bipartite matching, where an edge from $u$ to $c$ exists in a bipartite graph if and only if $u$ is happy with $c$.) If we think of these two recommendations as a “path” of length 2, it is an augmenting path whose edges alternate between being in the current matching and not. The CR2 algorithm then “flips” all edges along the path, effectively reassigning $u_i$ from $c_1$ to $c_2$, allowing $c_2$ to gain a user, while $c_1$'s constraint is still satisfied even after losing a user. This can be done for all users in $\userset_{2,1}$, and combined with $\userset_2$ (where each user $u\in \userset_2$ forms an augmenting path $\left( u, c_2 \right)$ of length 1), they give $c_2$ enough audience.

§.§ Augmenting Paths

We first formalize the idea of viewing our problem as a bipartite matching:

* Given an instance of our problem, its bipartite graph representation is a bipartite graph $G = \left( \userset \cup \creatorset, E \right)$ whose vertices are all users and creators, and where there exists an undirected edge between user $i$ and creator $j$, denoted $\left( u_i, c_j \right)$, if and only if user $i$ is happy with creator $j$.

* Additionally, given a set of recommendations $\rec$ (a matching between some users and some creators that many not satisfy all participation constraints), we define the edge set representation of $\rec$ as a set of edges $S\subseteq E$, such that $\left( u_i, c_j \right) \in S$ if and only if $j\in \rec\left(i\right)$.

We also define $a^{\rec}_j := \left\{ i\in \userset : j\in \rec(i) \right\}$ to be the audience of creator $j$ under matching $\rec$. Now, we give a formal definition of an augmenting path:

Given a creator $j$ and a matching $\rec$, let $S$ be the edge set representation of $\rec$. Then, an augmenting path associated with creator $j$ is a path in the graph with the following characteristics:

* The path starts at $c_j$.

* The path ends at either a user $u_i$ such that $\left| \rec(i) \right| < K$ (i.e., the user has capacity for more recommendations), or a creator $c_k$ such that $\left| a^{\rec}_k \right| > \abar$ (i.e., the creator already receives strictly more than $\abar$ users, and can afford to lose one user).

* Each odd-numbered edge (from a creator to a user) is not in $S$, and each even-numbered edge (from a user to a creator) is in $S$.

* The path does not contain any cycles.

The following proposition characterizes the effects of “adding” an augmenting path to a matching:

Let $\rec$ be an initial matching and $S$ be its edge set representation.
Given a creator $j$ and an augmenting path $P$ associated with $j$, let $\rec'$ and $S'$ be the resultant matching and edge sets after “adding” $P$ to $\rec$ and $S$. Formally, $S'$ is the XOR of $P$ and $S$, and $\rec'$ is the matching induced by $S'$. (We denote this as $S' = S \oplus P$ and $\rec' = \rec \oplus P$.)

Then, the following properties hold:

* Creator $c_j$ satisfies $a^{\rec'}_j = a^{\rec}_j + 1$. If $P$ ends at a creator $c_k$, then $a^{\rec'}_k = a^{\rec}_k - 1$. For all other creators $c_{j'}$, $a^{\rec'}_{j'} = a^{\rec}_{j'}$.

* If $P$ ends at a user $u_i$, then $\left| \rec'\left(i\right) \right| = \left| \rec\left(i\right) \right| + 1$. For all other users $u_{i'}$, $\left| \rec'\left(i'\right) \right| = \left| \rec\left(i'\right) \right|$.

* If $P$ ends at a user $u_i$ and $\rec'$ does not satisfy her participation constraints (due to insufficient number of recommendations), then $\rec$ also does not satisfy $u_i$'s constraints. For all other users, and for all creators other than $c_j$, $\rec'$ satisfies her constraints if and only if $\rec$ satisfies her constraints.

Proposition <ref> effectively states that each augmenting path is equivalent to creator $c_j$ getting a new user, while respecting all other participation constraints that have already been satisfied. The proof is trivial and left as an exercise.

§.§ Description of the CR2 Algorithm

At the core of CR2 algorithm is an improvement over CR1 that is motivated by Proposition <ref>: we can replace the step of “assigning a user to creator $j$” in CR1 with “finding an augmenting path associated with $j$”. This achieves the same effect of increasing creator $j$'s audience size by 1, but unlike CR1 where the new audience is always assigned to $c_j$ directly (equivalent to an augmenting path of length 1), the augmenting path approach allows indirect assignments (path ending at a user that's not connected to $c_j$ directly) and redistributions of audiences among creators.
This means the set of users that can be assigned to $c_j$ under the augmenting path approach is a superset of the CR1 approach, so using the former increases the likelihood of satisfying $c_j$'s audience constraint.[This “improvement” does not mean CR2 always returns a final matching with greater total engagement than CR1 on all instances. This is because due to the greedy nature of the  algorithms, sometimes there are “wrong” creators that should be avoided, i.e., not including this creator will result in a better matching. Nevertheless, in the simulations we present in Appendix <ref>, CR2 shows a significant improvement over CR1 on average, which suggests CR2's other benefits generally outweigh the problem of picking the wrong creators occasionally.]

Therefore, CR2 uses the augmenting path approach when examining each new creator $c_j$ and providing her as much audience as possible. A pseudocode of CR2 is presented in Algorithm <ref>.

2 (CR2) algorithm for time $t$

[1]
$\userset_t = \{1, \ldots, U\} \gets$ current set of users, in arbitrary order
$\creatorset_t = \{1, \ldots, C\} \gets$ current set of creators
$\rect:\userset_t \mapsto P(\creatorset_t) \gets$ recommendations (initially empty, i.e., $\rect(i)=\emptyset \ \forall i\in \userset_t$)
$\creatorset_t \neq \emptyset$
$a(j) := \left\{ i \in \userset_t: u_i^T c_j \geq \ebar \text{ and } \left| \rect(i) \right| < K \right\}, \ \forall j \in \creatorset_t$  Potential audience function for creator $j$
$j \gets $ creator in $\creatorset_t$ with smallest value of $\left| a(j) \right|$  Smallest size of potential audience
$\creatorset_t \gets \creatorset_t \backslash \left\{j\right\}$
$P \gets$ Augmenting path associated with creator $j$
Prioritize augmenting paths that end at users
$P \neq \emptyset$  Repeatedly BFS for augmenting paths until none can be found
$\rect \gets \rect \oplus P$  Add $P$ to current matching
$P \gets$ Augmenting path associated with creator $j$
creator $j$ has fewer than $\abar$ users in $\rect$  Failed to add $j$ as she cannot be satisfied
$\rect \gets$ Restore original matching before examining $j$  Undo all augmenting paths

$\rect$  Recommendation for time $t$, note that some users may leave

The only change in CR2 is replacing Lines <ref>-<ref> in CR1 (Algorithm <ref>) which simply try to add all potential audience of creator $j$ and check if they meet her audience constraint, with Lines <ref>-<ref> in Algorithm <ref> which find as many augmenting paths associated with $j$ as possible.

In terms of implementation, we find augmenting paths one by one using a breadth-first search (BFS) that starts at $c_j$. We prefer augmenting paths that end at users over those that end at creators, since the former increases the total number of edges in the matching by one, and makes progress towards giving the user $K$ recommendations. Therefore, during the BFS, we record all completed augmenting paths once any possible end point is reached, but only terminate the search immediately when the end point is a user. If none are found, then a path that ends at a creator is used.

Several properties of CR1 remain true in CR2. Both prioritize creators whose constraints are the hardest to satisfy. In both algorithms, once a creator is added to the returned set, it will never be removed (even though its audience size may decrease in CR2 while being at least $\abar$), and that the number of recommendations for each user can only increase during the execution. On the other hand, CR2 inherits several drawbacks of CR1, such as possibly choosing the “wrong” sets of users and creators, ignoring user engagement values, and not necessarily returning a stable set due to users with insufficient recommendations (so CR2 may need to be executed again at time $t+1$).

§ SIMULATION RESULTS

In this appendix, we present simulations on randomly generated instances with small parameter values. The main objectives of these simulations are to:

* Evaluate the average performance of  relative to , and identify choices of parameters in which  performs poorly. This generalizes Proposition <ref> and Theorem <ref> to less restrictive and non-asymptotic setups, while also uncovering additional scenarios that lack theoretical justifications.

* Evaluate the average performance of CR2 to , and show that it achieves high approximation ratios relative to , especially in the aforementioned situations where  performs poorly.

Empirically, most instances generated using uniform priors $\distribution$ for user and creator types do not satisfy the density Assumption <ref>. As such, we did not run the  algorithm in simulations.

We first document the setup of our simulations, then list the main observations, and present plots of average approximation ratios to support each observation.

§.§ Simulation Setup

Our simulations are on simple randomized instances with small instance sizes, in terms of four main parameters $U$, $C$, $K$ and $\abar$.
Typically, all four parameters are fixed in a single test case. We then compare different test cases and their trends under changes in parameters (e.g., increasing $U$).

All users and creators have their types generated i.i.d. from the uniform distribution $\distribution$ over all non-negative unit vectors, following the random instances framework that we established in Section <ref>. However, their constraint values are deterministic, with creator constraints given by $\abar$.

We define the user constraint value $\ebar$ as the expected engagement from a random user to an independent random creator, multiplied by a parameter $\ebar_m$ which is set to $0.6$ in all plots presented below:

$$ \ebar = \ebar_m \mathbb{E}_{u,c\sim \distribution} \left[ u^T c \right]. $$

Intuitively, the multiplier $\ebar_m$ measures the strength of user constraints. A greater $\ebar_m$ means users are more demanding in the quality of recommendations, whereas a smaller $\ebar_m$ means they are happy with creators whose types are less similar to theirs. Note that $\ebar$ does not depend on $U, C$ and $K$, and only depends on $D$ and $\ebar_m$. In practice, we sample the value of $\mathbb{E}_{u,c\sim \distribution} \left[ u^T c \right]$ using Monte Carlo simulations, by generating 10,000 pairs of random user and creator types for each $D$ and finding their average dot products. While we only present plots with $\ebar_m=0.6$, we have verified that similar conclusions hold with $\ebar_m=0.8$ or $1$.

Additionally, the plots below all have dimensionality $D=10$. However, similar observations can be drawn with $D=2$ and $D=5$.

For each test case with fixed $U$, $C$, $K$, $\abar$ (as well as $D$ and $\ebar$), we generate $N=1,000$ independent random instances, and run the following algorithms: , , and two versions of  (CR1 and CR2). Some of these runs may have $\longtermengagement\left(\FLseq\right)=0$ (no stable sets exist), especially with higher values of $\ebar_m$.[In the most extreme cases, with $\ebar_m=1$ and $K$ being close to $C-1$, most or all random instances have $\longtermengagement\left(\FLseq\right)=0$. This may be a consequence of our definition of $\ebar$: specifically, since it's defined as the expected distance from a user to a creator, each user will naturally have half of the creators below this threshold in expectation, but she requires to be assigned to all but one of them. Nevertheless, we decided to keep $\ebar$ constant when comparing different values of $K$ and other parameters to keep it as a control variable.] We measure the performance of , CR1 and CR2 algorithms by computing the empirical averages of their approximation ratios in long-term engagement relative to  (on instances that satisfy $\longtermengagement\left(\FLseq\right)>0$).

§.§ Main Observations

Below is a list of key observations that emerge from simulations.
[Increasing $U$]
's performance degrades when $U$ and $\abar$ both increase proportionally while $C$ and $K$ are fixed, subject to $UK=C\abar$ (the “market balance” condition).

[Increasing $C$]
's performance degrades when $C$ increases, while $U$, $K$ and $\abar$ are fixed.

[Increasing $K$]
's performance is poor when the ratio of $K/C$ is high, subject to $UK=C\abar$ (market balance), and degrades when $K$ and $\abar$ increase proportionally while $U$ and $C$ are fixed.

Under conditions in Observations <ref>, <ref> and <ref>, CR2 achieves high approximation ratios, which are usually higher than  and are roughly constant following changes in the respective parameters.

Note that Observation <ref> generalizes Theorem <ref> to non-asymptotic settings, while reducing the dependence on $K>C/2$ and removing the requirement that $D=2$. Observation <ref> generalizes Proposition <ref> to non-asymptotic settings.

§.§ Detailed Results

§.§.§ Increasing U and a (Observation <ref>)

[Approximation ratios of UC, CR1 and CR2 when $U$ and $\abar$ increase proportionally]Approximation ratios of UC, CR1 and CR2 when $U$ and $\abar$ increase proportionally. In all plots, $C=6$, and $K$ increases across the subplots from $1$ (left) to $5$ (right). Within each subplot, $U$ increases exponentially on the $x$-axis, and $\abar = UK/C$. UC, CR1 and CR2 are in blue, red and green respectively, with 95% confidence intervals.

Figure <ref>, which is a duplicate of Figure <ref> in Section <ref>, shows average approximation ratios for test cases where each subplot captures the trend specified in Observation <ref> and Theorem <ref>: both $U$ and $\abar$ increase proportionally while $C=6$ and $K$ remain constant, such that $UK=C\abar$.

In all subplots, the  algorithm shows a drop in performance relative to the  algorithm as $U$ and $\abar$ increase. The decrease is most notable when $K=4$ and $K=5$, both of which satisfy the assumption of $K>C/2$ in Theorem <ref>. However, a smaller decrease can still be observed when $K\leq 3$, which suggests the possibility that the result may still be generally applicable even for smaller values of $K/C$. We also observe that with a greater $\ebar_m$ where user constraints become stricter, 's decrease when $K\leq C/2$ can be more significant.

On the other hand, the CR2 algorithm consistently achieves at least 80% of 's average long-term engagement in all test cases, and its performance is not significantly affected by the increase in $U$ and $\abar$. This is especially true in cases where 's degrade is the most notable.

§.§.§ Increasing C (Observation <ref>)

[Approximation ratios of UC, CR1 and CR2 when $C$ increases]Approximation ratios of UC, CR1 and CR2 when $C$ increases ($x$-axis in each subplot). Across subplots, $K$ increases from $1$ (left) to $4$ (right). All plots satisfy $U=10$ and $\abar = 2K$.

Figure <ref> shows average approximation ratios for test cases where each subplot captures the trend specified in Observation <ref> and Proposition <ref>: only $C$ increases, while $U$, $K$ and $\abar$ remain constant. We set $\abar=2K$, so that market balance is satisfied when $C=5$ (the leftmost point on the $x$-axis), while points further right have markets with disproportionately more creators than users.

The  algorithm sees a rapid decline in performance as $C$ increases, as long as $K>1$. This also suggests that Proposition <ref>'s asymptotic condition $C\rightarrow \infty$ may be unnecessary in practice, as the decrease in 's approximation ratio is already notable even with a small increase in $C$. The CR2 algorithm continues to achieve high and near constant approximation ratios in all cases.

§.§.§ Increasing K and a (Observation <ref>)

[Approximation ratios of UC, CR1 and CR2 when $K$ and $\abar$ increase proportionally]Approximation ratios of UC, CR1 and CR2 when $K$ ($x$-axis in each subplot) and $\abar$ increase proportionally. In all plots, $C=6$. Across subplots, $U$ increases from $12$ (left) to $60$ (right).

Figure <ref> shows average approximation ratios for test cases where each subplot captures the trend specified in Observation <ref>: both $K$ and $\abar$ increase proportionally, while $U$ and $C=6$ remain constant with $UK=C\abar$.

While the  algorithm achieves high approximation ratios for small values of $K$ such as $1$ or $2$, its performance quickly declines for higher values of $K$, and becomes very low when $K=5$. In contrast, the CR2 algorithm sees an improvement as $K$ and $\abar$ increase, which is exactly when  degrades. This suggests that such instances with higher $K$, which are more challenging, are better suited for the creator-centric  algorithms.

Note that in this case, 's approximation ratio drops the most rapidly when $K\geq C/2$, which bears similarity with the condition in Theorem <ref> that $K>C/2$. Such a trend is also observed in other sets of simulations with different parameters; however, $K\geq C/2$ is not the only case where  performs poorly, as we briefly mentioned in Section <ref>.


# Optimal Network Robustness Against Attacks
in Varying Degree Distributions

Masaki Chujyo
Japan Advanced Institute of Science and Technology
Ishikawa, 923-1292 Japan
<EMAIL_ADDRESS>
&Yukio Hayashi
Japan Advanced Institute of Science and Technology
Ishikawa, 923-1292 Japan
&Takehisa Hasegawa
Graduate School of Science and Engineering, Ibaraki University,
Ibaraki, 310-8512 Japan
Corresponding author

###### Abstract

In varying degree distributions, we investigate the optimally robust networks
against targeted attacks to nodes with higher degrees. In considering that a
network tends to have more robustness with a smaller variance of degree
distributions, we clarify the optimal robustness at random regular graphs in
their comprehensive discrete or random perturbations. By comparing robustness
measurements on them, we find that random regular graphs have the optimal
robustness against attacks in varying degree distributions.

##  1 Introduction

At the beginning of this century, it has been found that many real-world
networks commonly have a scale-free structure in which the degree distribution
follows a power-law [1]. Unfortunately, such networks are extremely vulnerable
to targeted removals (attacks) of nodes with higher degrees [2]. However, our
modern society is supported by scale-free networks, such as the Internet,
communication networks, traffic systems, power grids, social networks, supply
chain networks, protein-protein interaction networks, and metabolic networks.
Therefore, overcoming the vulnerability of real-world networks has been an
important issue.

We focus on varying the degree distribution for investigating the robustness
of connectivity. As well-known results, scale-free networks with power-law
degree distributions are more vulnerable to attacks than Erdős-Rényi random
graphs with exponential degree distributions, while scale-free networks are
more tolerant to random node removals (failures) than Erdős-Rényi random
graphs [2]. Recently, it has been shown that random networks with smaller
variances of degree distributions are more robust through numerical
simulations in the range of power-law, exponential, and narrower degree
distributions [3]. The continuously varying degree distributions are generated
by the growing network model [4, 5, 6] and the inverse preferential model [7].
In addition, for discussing the pure effect of degree distributions on the
robustness, the networks are randomized thought configuration models [8, 9].
In a special class of networks with multimodal distributions including power-
law ones, bimodal networks with two kinds of degrees are the most robust for
maximizing the sum of two critical thresholds of whole fragmentations by both
failures and attacks [10]. In other words, the robustness against both
failures and attacks increases, as the variance of degree distribution
decreases. At pinpoints, in comparing the robustness of regular graphs, Erdős-
Rényi random graphs [11], Watts-Strogatz models [12], and Barabási Albert
models [1], it has been numerically shown that regular graphs are the most
robust [13]. Moreover, the degree distribution becomes narrower in maximizing
the robustness index by random rewiring [13]. Although the maximization
changes the degree distribution to trimodal or tetramodal distributions with
three or four degrees, this is not enough to say that regular graph with one
degree is the most robust.

On the other hand, it is found that an onion-like network with positive
degree-degree correlations [14] is the most robust under fixing a degree
distribution [15, 10]. By increasing the degree-degree correlations, some
rewiring methods have been proposed for improving the robustness [16, 17]. In
addition, an incrementally growing method for constructing onion-like networks
is proposed by enhancing interwoven long loops [18, 19]. The robust networks
generated by this growing method have exponential degree distributions [18].
This result also suggest that more homogeneous degree distributions are
crucial to increase the robustness.

Besides the degree-degree correlations, loops on networks have been getting
attention for increasing the robustness [20, 19, 21]. The relation between
loops and the robustness is supported by an asymptotically equivalence of
network decycling and network dismantling [20]. Network decycling or feedback
vertex set (FVS) is a minimum set of nodes that removal makes the network
without loops, while network dismantling is a minimum set of nodes whose
removal makes it a smaller size of connected components. Intuitively, networks
without loops are easily fragmented by any node removals. As the importance of
loops, it has numerically shown that networks with a larger size of FVS have
more robustness against attacks in the incrementally growing onion-like
networks [19]. Furthermore, loop-enhancing rewiring methods by increasing the
size of FVS have been proposed [21]. When the loop-enhancing rewiring is
applied to a network for increasing the robustness, the variance of degree
distributions becomes smaller. It also shows that decreasing of the variance
of degree distribution is strongly related to increasing the robustness.

These previous studies suggest that a network tends to be more robust against
attacks with a smaller variance of degree distribution. Thus, a random regular
graph with the minimum (zero) variance of degree distribution is predicted to
have the optimal robustness. In this paper, we clarify the optimal robustness
in varying degree distributions by comparing the robustness of random regular
graphs and their perturbed ones by comprehensive discrete or random
perturbations.

##  2 Surrounding of random regular graphs

A regular graph consists of all nodes with a constant degree. Thus, the
variance of degree distributions is zero. We compare the robustness in random
regular graphs and the perturbed ones around it. As the surroundings, we
consider two types of networks with discrete and random perturbations. In Sec.
2.1 for discrete perturbations, we introduce bimodal networks with two types
of degrees whose modality is the second minimum to the regular graph with only
one degree. In Sec. 2.2 for random perturbations which include several
modalities of degrees, we introduce modified networks by adding and removing
links to the regular graphs uniformly at random.

###  2.1 Discrete perturbations

As discrete perturbations of a random regular graph, we introduce bimodal
networks with two degrees $d_{1}<d_{2}$ under the average degree $d$. For the
bimodal networks, there are several combinations of degrees $d_{1}$ and
$d_{2}$ in $\Delta d=d_{2}-d_{1}\geq 2$.

For given degrees $d_{1}$ and $d_{2}$ for a bimodal network with $N$ nodes and
the average degree $d$, the number of nodes $N_{1}$ and $N_{2}$ corresponding
to degrees $d_{1}$ and $d_{2}$ are derived as follows. From the total number
of nodes $N$ and links $M$,

$N=N_{1}+N_{2},$ (1) $M=\frac{d\times N}{2}=\frac{d_{1}\times
N_{1}}{2}+\frac{d_{2}\times N_{2}}{2},$ (2)

we obtain

$N_{1}=\frac{d_{2}-d}{\Delta d}N,$ (3) $N_{2}=\frac{d-d_{1}}{\Delta d}N.$ (4)

Since $N_{1}$ and $N_{2}$ must be positive integers, $N$ needs to be divisible
by $\Delta d$. As shown in Table 1, the combinations are
$(d_{1},d_{2})=(d-1,d+\Delta d-1),(d-2,d+\Delta d-2),...,(d-\Delta d+1,d+1)$.
Except for a star structure with $d_{1}=1$ and $d_{2}=N-1$ which is obviously
vulnerable to attacks, Table 1 shows all possible combinations in the ranges
of $2\leq d_{1}\leq d-1$ and $d+1\leq d_{2}\leq N-2$ for constant $N$ and $d$.
Note that these combinations of degrees are comprehensive around a regular
graph. For constructing the bimodal networks, we use a configuration model
according to the degree distribution:

$P(d_{1})=N_{1}/N,$ (5) $P(d_{2})=N_{2}/N.$ (6)

After randomizing them through the configuration model [8, 9], we can discuss
the pure effect of degree distributions on the robustness.

Table 1: Two degrees $d_{1}$ and $d_{2}$, the variance $\sigma^{2}$ of degrees, and the fraction $N_{1}/N$ of nodes with degree $d_{1}$ in bimodal networks with the average degree $d=6$. $\Delta d$ | $d_{1}$ | $d_{2}$ | $\sigma^{2}$ | $N_{1}/N$
---|---|---|---|---
2 | 5 | 7 | 1 | 1/2
3 | 5 | 8 | 2 | 2/3
| 4 | 7 | 2 | 1/3
4 | 5 | 9 | 3 | 3/4
| 4 | 8 | 4 | 2/4
| 3 | 7 | 3 | 1/4
5 | 5 | 10 | 4 | 4/5
| 4 | 9 | 6 | 3/5
| 3 | 8 | 6 | 2/5
| 2 | 7 | 4 | 1/5
| $\vdots$ |  | $\vdots$ |
$\Delta d$ | $d-1=5$ | $d+\Delta d-1$ | $\Delta d-1$ | $(\Delta d-1)/\Delta d$
| $d-2=4$ | $d+\Delta d-2$ | $2(\Delta d-2)$ | $(\Delta d-2)/\Delta d$
| $d-3=3$ | $d+\Delta d-3$ | $3(\Delta d-3)$ | $(\Delta d-3)/\Delta d$
| $d-4=2$ | $d+\Delta d-4$ | $4(\Delta d-4)$ | $(\Delta d-4)/\Delta d$

We can easily calculate the variance of degree distribution of a bimodal
network. From Eqs. (3) and (4), the variance is derived as follows:

$\displaystyle\sigma^{2}$ $\displaystyle=$ $\displaystyle\langle
k^{2}\rangle-\langle k\rangle^{2}$ (7) $\displaystyle=$
$\displaystyle\frac{1}{N}(d_{1}^{2}\times N_{1}+d_{2}^{2}\times N_{2})-d^{2}$
$\displaystyle=$ $\displaystyle\frac{1}{N}\left(d_{1}^{2}\frac{d_{2}-d}{\Delta
d}N+d_{2}^{2}\frac{d-d_{1}}{\Delta d}N\right)-d^{2}$ $\displaystyle=$
$\displaystyle\frac{d_{1}^{2}(d_{2}-d)+d_{2}^{2}(d-d_{1})}{d_{2}-d_{1}}-d^{2}$
$\displaystyle=$ $\displaystyle(d_{2}-d)(d-d_{1}).$

When each of $d_{1}$ or $d_{2}$ is close to $d$, the variance $\sigma^{2}$ is
small. In particular, the minimum variance is $\sigma^{2}=1$ at $d_{1}=d-1$
and $d_{2}=d+1$. As shown in Fig. 1, the variances $\sigma^{2}$ and $\Delta d$
are proportional for a constant $d_{1}$. By substituting $\Delta
d=d_{2}-d_{1}$ into Eq. (7), we obtain

$\displaystyle\sigma^{2}$ $\displaystyle=$ $\displaystyle(d_{2}-d)(d-d_{1})$
(8) $\displaystyle=$ $\displaystyle(d_{1}+\Delta d-d)(d-d_{1})$
$\displaystyle=$ $\displaystyle(d-d_{1})\Delta d-(d-d_{1})^{2}.$

The increasing of the variances $\sigma^{2}$ is remarkable for smaller
$d_{1}$, e.g. green or res lines in Fig. 1. Note that $\Delta d$ is a divisor
of $N$ from Eqs. (3)(4).

Figure 1: Variances $\sigma^{2}$ of degree distributions versus $\Delta d$ in
bimodal networks for $N=1260$ and $d=6$. Green, red, violet, and brown lines
with circle, square, inverted triangle, and diamond points show the results
for $d_{1}=2$, $3$, $4$, and $5$, respectively. Each line is straight, since
$\sigma^{2}$ and $\Delta d$ are proportional for a constant $d_{1}$ in Eq.
(8).

###  2.2 Random perturbations

As random perturbations of regular graphs, we introduce modified networks by
adding and removing links to random regular graphs. Here, $0\leq p\leq 1$ is
the ratio of removed links to the existing links. After removing, for fixing
the average degree $d$, the same number of $Mp$ links are added at randomly
chosen nodes in prohibiting multi-links and self-loops. At $p=0$, all links
are unchanged, while at $p=1$, all links are rewired as Erdős-Rényi random
graphs [11]. For $0<p<1$, we can derive the degree distribution as follow.

$P(k)=\sum_{k_{1}+k_{2}=k}\binom{d}{k_{1}}(1-p)^{k_{1}}p^{d-k_{1}}\frac{\lambda^{k_{2}}}{k_{2}!}e^{-\lambda},$
(9)

where $k_{1}$ and $k_{2}$ are the number of unremoved and added links to a
node, respectively, and $\lambda=2dp$. Fig 2 shows 100 averaged degree
distributions for each $p$. As $p$ increases, the degree distributions become
wider from a delta function $P(k)=\delta_{k,d}$ of the regular graph to
Poisson distribution. Even for $p=0.005$ and $0.01$, the degree distribution
consists of five kinds of degrees, whose modality is much more than the
trimodal or tetramodal distributions as in [13].

Figure 2: Degree distributions of random perturbations to random regular
graphs with $N=10000$ and $d=6$. The degree distributions change from a delta
function of regular graphs ($p=0$) to Poisson distributions ($p=1$).

##  3 Robustness analysis

In this section, we consider two measurements of the robustness index and the
percolation threshold for comparing the robustness against attacks in regular
graphs and perturbed ones. The robustness index [15] is defined as

$R_{\mathrm{TA}}\stackrel{{\scriptstyle\rm{def}}}{{=}}\frac{1}{N}\sum_{q=1}^{N}S(q),$
(10)

where $q$ is the number of removed nodes by attacks, and $S(q)$ is the
fraction of nodes in the largest connected components. As attacks, nodes are
removed one-by-one from the node with the highest degree. Note that the ranges
of $R_{\mathrm{TA}}$ are $[1/N,0.5]$.

The percolation threshold $f_{c}$ is the fraction of remaining nodes (occupied
nodes in percolation theory), where whole networks are fragmented. Below
$f_{c}$, there are no the largest connected components for the network in the
thermodynamic limit ($N\rightarrow\infty$). As $f_{c}$ decreases, the network
becomes more robust, because more nodes need to be removed for fragmentation.
We describe the method to estimate the percolation threshold $f_{c}$ against
attacks by using generating functions for any degree distributions [22, 23].
Remember that $P(k)$ is the degree distributions. Here, we define the excess
degree distribution $Q(k)=(k+1)P(k+1)/\langle k\rangle$, which means that the
probability of reaching a node with $k$ by following a randomly selected link.
We consider the attacks that remove $1-f$ fraction of nodes in order of higher
degrees. Then, $k_{\mathrm{cut}}$ denotes the highest degree in the remaining
nodes, and $\Delta f$ denotes the fraction of removed nodes with degree
$k_{\mathrm{cut}}$. The probability that randomly selected node is not removed
is

$f=\sum_{k=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}P(k)-\Delta
fP(k_{\mathrm{cut}}).$ (11)

The probability that a node by following a randomly selected link is not
removed is

$\hat{f}=\sum_{k=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}Q(k-1)-\Delta
fQ(k_{\mathrm{cut}}-1).$ (12)

Let $\hat{P}(k)$ be the degree distribution of the network remaining after the
attacks, and $\hat{Q}(k)$ be the excess degree distribution. By following [24,
23], we can derive

$\displaystyle\hat{P}(k)=\frac{1}{f}\left[\sum_{k^{\prime}=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}P(k^{\prime})\binom{k^{\prime}}{k}\hat{f}^{k}(1-\hat{f})^{k^{\prime}-k}-\Delta
fP(k_{\mathrm{cut}})\binom{k_{\mathrm{cut}}}{k}\hat{f}^{k}(1-\hat{f})^{k_{\mathrm{cut}}-k}\right],$
(13)
$\displaystyle\hat{Q}(k)=\frac{1}{\hat{f}}\left[\sum_{k^{\prime}=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}Q(k^{\prime})\binom{k^{\prime}}{k}\hat{f}^{k}(1-\hat{f})^{k^{\prime}-k}-\Delta
fQ(k_{\mathrm{cut}})\binom{k_{\mathrm{cut}}-1}{k}\hat{f}^{k}(1-\hat{f})^{k_{\mathrm{cut}}-1-k}\right].$
(14)

We consider the generating functions $F_{0}(x)$ and $F_{1}(x)$ for the
distributions $\hat{P(k)}$ and $\hat{Q(k)}$ after attacks,

$\displaystyle
F_{0}(x)=\sum_{k}\hat{P}(k)x^{k}=\frac{1}{f}\sum_{k^{\prime}=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}P(k^{\prime})(\hat{f}x+1-\hat{f})^{k^{\prime}}-\frac{\Delta
f}{f}P(k_{\mathrm{cut}})(\hat{f}x+1-\hat{f})^{k_{\mathrm{cut}}},$ (15)
$\displaystyle
F_{1}(x)=\sum_{k}\hat{Q}(k)x^{k}=\frac{1}{\hat{f}}\sum_{k^{\prime}=k_{\mathrm{min}}-1}^{k_{\mathrm{cut}}-1}Q(k^{\prime})(\hat{f}x+1-\hat{f})^{k^{\prime}}-\frac{\Delta
f}{\hat{f}}Q(k_{\mathrm{cut}}-1)(\hat{f}x+1-\hat{f})^{k_{\mathrm{cut}}-1}.$
(16)

The fractions of nodes belonging to the largest connected components after
attacks is

$s=f(1-F_{0}(u)),$ (17)

where $u$ is the solution of the self-consistent equation of $u=F_{1}(u)$. We
numerically obtain the fixed point $u$. Here, $s$ is equivalent to $S(q)$ for
$q=1-f$ in Eq. (10). Since the existence of $u<1$ solution is a condition for
the appearance of a largest connected component ($s>0$), the percolation
threshold $f_{c}$ can be obtained under the following conditions,

$\displaystyle F^{\prime}_{1}(1)$ $\displaystyle=$
$\displaystyle\sum_{k^{\prime}=k_{\mathrm{min}}-1}^{k_{\mathrm{cut}}-1}k^{\prime}Q(k^{\prime})$
(18) $\displaystyle=$
$\displaystyle\sum_{k=k_{\mathrm{min}}}^{k_{\mathrm{cut}}}\frac{k(k-1)P(k)}{\langle
k\rangle}-\Delta
f\frac{k_{\mathrm{cut}}({k_{\mathrm{cut}}-1})P({k_{\mathrm{cut}}})}{\langle
k\rangle}=1.$

From Eq. (11), we numerically obtain $f_{c}$ from Eq. 18 with
$k_{\mathrm{cut}}$ which satisfies the condition of Eq. (18). Note that
$f_{c}$ can be only applied on randomized networks like the configuration
model. Here, we apply Eqs. (11-18) for the degree distributions of Eqs. (5, 6,
9) in bimodal networks and randomly perturbed networks from the regular
graphs. random regular graphs and their perturbations.

##  4 Results

We compare these measurements $R_{\mathrm{TA}}$ and $1-f_{c}$ for the
robustness against attacks in random regular graphs and perturbed ones with
$N=6300$ nodes and the average degree $\langle k\rangle=4$ or 6. Note that for
$N=6300$, it is possible to generate regular graphs for $d=4$ and $6$. We use
bimodal networks of all possible combinations of positive integers $d_{1}$ and
$d_{2}$ with $2\leq\Delta d\leq 10$, as shown in Table 1. In addition, we use
modified networks by random perturbations for the ratios of
$p=0.005,0.01,0.1,0.25,0.5,0.75,$ and $1$.

(A) For $\langle k\rangle=4$.

(B) For $\langle k\rangle=6$.

Figure 3: The robustness index $R_{\mathrm{TA}}$ versus the variances
$\sigma^{2}$ of degree distributions. The results for for the average degree
(A) $\langle k\rangle=4$, and (B) $\langle k\rangle=6$. In both figures,
$R_{\mathrm{TA}}$ becomes higher as the variance decreases. In particular, the
random regular graphs (red points) are the most robust.

Figs 3ab show $R_{\mathrm{TA}}$ versus the variance $\sigma^{2}$ of degree
distributions for random regular graphs and perturbed ones with $N=6300$ nodes
and the average degree $\langle k\rangle=4$ or 6. $R_{\mathrm{TA}}$ is
numerically calculated by the Newman-Ziff algorithm [25]. In both Figs 3AB,
$R_{\mathrm{TA}}$ increases as the variance $\sigma^{2}$ decreases in both
discrete and random perturbations (blue triangles and green hexagons). These
results indicate that the smaller variance of the degree distribution tends to
be more robust against attacks. Furthermore, the random regular graphs (red
circles) have the highest robustness than bimodal and modified networks.
Remember that the combinations of degrees for bimodal networks are
comprehensive. Therefore, it is strongly suggested that random regular graphs
have the optimal robustness against attacks.

(A) For $\langle k\rangle=4$.

(B) For $\langle k\rangle=6$.

Figure 4: The percolation thresholds $1-f_{c}$ versus the variances
$\sigma^{2}$ of degree distributions. The results for the average degree (A)
$\langle k\rangle=4$, and (B) $\langle k\rangle=6$. In both figures, $1-f_{c}$
becomes higher as the variance decreases. Random regular graphs (red points)
are the most robust. Note that a higher $1-f_{c}$ means more robust.

For the theoretically estimated percolation threshold $1-f_{c}$, similar
results are obtained for the robustness index $R_{\mathrm{TA}}$. Figures 4ab
show the percolation threshold $1-f_{c}$ versus the variance of degree
distributions for random regular graphs and perturbed ones with $N=6300$ nodes
and the average degree $\langle k\rangle=4$ or 6. In both Figs 4AB, $1-f_{c}$
tends to increase as the variances $\sigma^{2}$ decrease for both discrete and
random perturbations (blue triangles and green hexagons). Furthermore, the
random regular graphs (red circles) have the highest robustness. Thus, random
regular graphs have the optimal robustness against attacks.

In the bimodal networks (blue triangles in Figs 3 or 4), there are similar
values of $R_{\mathrm{TA}}$ or $1-f_{c}$ for different variances $\sigma^{2}$,
e.g. $R_{\mathrm{TA}}$ takes about 0.25 for $\sigma^{2}=2$ and 4 in Fig 4A. To
investigate a relation between the robustness and the variances in bimodal
networks, we show the ratio $S(q)$ of the largest connected components against
attacks. Fig 5 show the ratio $S(q)$ in bimodal networks with $N=6300$ nodes
and the average degree $\langle k\rangle=4$. The inverse triangles show the
analytical results by Eq. (17), while the solid lines show the results by
numerical simulation using the Newman-Ziff algorithm [25]. In Fig 5,
$R_{\mathrm{TA}}$ is the area under the curve with respect to horizontal axis.
Fig 5A for $d_{1}=2$ shows that $R_{\mathrm{TA}}$ decreases as $d_{2}$
increases. On the other hand, Fig 5B for $d_{1}=3$ shows that
$R_{\mathrm{TA}}$ decreases as $d_{2}$ increases, although the decrease of
$R_{\mathrm{TA}}$ becomes smaller for $d_{2}>6$. For example, there is a small
difference between orange ($d_{2}=8$) and blue ($d_{2}=9$) lines. In
particular, in Fig 5B, the lines for $d_{2}>6$ are not smooth and like multi-
step. Such a phenomenon is observed for $d_{1}=3$ close to the average degree
$\langle k\rangle=4$. However, the reason for this is not well understood.
Similar results are obtained for $\langle k\rangle=6$.

(A) For $d_{1}=2$.

(B) For $d_{1}=3$.

Figure 5: The ratio of the largest connected components versus the fraction of
remaining nodes on bimodal networks with $N=6300$ and $\langle k\rangle=4$.
The results are shown for (A) $d_{1}=2$ and (B) $d_{1}=3$.

##  5 Conclusion

In this study, we find optimally robust networks against targeted attacks in
varying degree distributions. In considering that a network tends to be more
robust with the smaller variance of degree distributions, random regular
graphs with the minimum variance are predicted to be optimally robust.
Remember that it is insufficient to determine whether random regular graphs
are optimally robust. We clarify the optimal robustness in varying degree
distributions by comparing the robustness of random regular graphs and their
comprehensive discrete or random perturbations which includes several
modalities of degrees. By comparing the robustness index and percolation
threshold on them, we find that random regular graphs are the highest robust
in all bimodal and modified networks. Our results show that random regular
graphs have the optimal robustness against attacks in varying degree
distributions.

## Acknowledgements

This research is supported in part by JSPS KAKENHI Grant Number JP.21H03425.

## References

  * [1] Albert-László Barabási, Réka Albert, and Hawoong Jeong.  Mean-field theory for scale-free random networks.  Physica A: Statistical Mechanics and its Applications, 272(1):173–187, 1999.
  * [2] Réka Albert, Hawoong Jeong, and Albert-László Barabási.  Error and attack tolerance of complex networks.  Nature, 406(6794):378–382, 2000.
  * [3] Masaki Chujyo and Yukio Hayashi.  Optimal network robustness in continuously changing degree distributions.  In International Conference on Complex Networks and Their Applications. Springer, 2022.
  * [4] Paul L Krapivsky, Sidney Redner, and Francois Leyvraz.  Connectivity of growing random networks.  Physical Review Letters, 85(21):4629–4632, Nov 2000.
  * [5] Paul L Krapivsky and Sidney Redner.  Organization of growing random networks.  Physical Review E, 63(6):066123, May 2001.
  * [6] Paul L Krapivsky and Sidney Redner.  A statistical physics perspective on web growth.  Computer Networks, 39(3):261–276, 2002.
  * [7] Fuxuan Liao and Yukio Hayashi.  Emergence of robust and efficient networks in a family of attachment models.  Physica A: Statistical Mechanics and its Applications, 599:127427, 2022.
  * [8] Duncan S. Callaway, John E. Hopcroft, Jon M. Kleinberg, M. E. J. Newman, and Steven H. Strogatz.  Are randomly grown graphs really random?  Physical Review E, 64(4):041902, Sep 2001.
  * [9] Michele Catanzaro, Marián Boguñá, and Romualdo Pastor-Satorras.  Generation of uncorrelated random scale-free networks.  Physical Review E, 71(2):027103, Feb 2005.
  * [10] Toshihiro Tanizawa, Gerald Paul, Shlomo Havlin, and H. Eugene Stanley.  Optimization of the robustness of multimodal networks.  Physical Review E, 74(1):016125, Jul 2006.
  * [11] Paul Erdős and Alfréd Rényi.  On random graphs i.  Publicationes Mathematicae (Debrecen), 6:290–297, 1959.
  * [12] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  nature, 393(6684):440–442, 1998.
  * [13] Liangliang Ma, Jing Liu, Boping Duan, and Mingxing Zhou.  A theoretical estimation for the optimal network robustness measure r against malicious node attacks.  EPL (Europhysics Letters), 111(2):28003, 2015.
  * [14] Mark E. J. Newman.  Assortative mixing in networks.  Physical Review Letters, 89(20):208701, Oct 2002.
  * [15] Christian M. Schneider, André A. Moreira, José S. Andrade, Shlomo Havlin, and Hans J. Herrmann.  Mitigation of malicious attacks on networks.  Proceedings of the National Academy of Sciences, 108(10):3838–3841, 2011.
  * [16] Ramon Xulvi-Brunet and Igor M Sokolov.  Reshuffling scale-free networks: From random to assortative.  Physical Review E, 70(6):066102, Dec 2004.
  * [17] Zhi-Xi Wu and Petter Holme.  Onion structure and network robustness.  Physical Review E, 84(2):026106, Aug 2011.
  * [18] Yukio Hayashi.  A new design principle of robust onion-like networks self-organized in growth.  Network Science, 6(1):54–70, 2018.
  * [19] Yukio Hayashi and Naoya Uchiyama.  Onion-like networks are both robust and resilient.  Scientific Reports, 8(1):1–13, 2018.
  * [20] Alfredo Braunstein, Luca Dall’Asta, Guilhem Semerjian, and Lenka Zdeborová.  Network dismantling.  Proceedings of the National Academy of Sciences, 113(44):12368–12373, 2016.
  * [21] Masaki Chujyo and Yukio Hayashi.  A loop enhancement strategy for network robustness.  Applied Network Science, 6(1):1–13, 2021.
  * [22] Mark EJ Newman, Steven H Strogatz, and Duncan J Watts.  Random graphs with arbitrary degree distributions and their applications.  Physical review E, 64(2):026118, 2001.
  * [23] Reuven Cohen, Keren Erez, Daniel ben Avraham, and Shlomo Havlin.  Breakdown of the internet under intentional attack.  Phys. Rev. Lett., 86:3682–3685, Apr 2001.
  * [24] Reuven Cohen, Keren Erez, Daniel ben Avraham, and Shlomo Havlin.  Resilience of the internet to random breakdowns.  Phys. Rev. Lett., 85:4626–4628, Nov 2000.
  * [25] M. E. J. Newman and R. M. Ziff.  Fast monte carlo algorithm for site or bond percolation.  Phys. Rev. E, 64:016706, Jun 2001.