# Densest Diverse Subgraphs:
How to Plan a Successful Cocktail Party with Diversity

Atsushi Miyauchi<EMAIL_ADDRESS>0000-0002-6033-6433 CENTAI
InstituteTurinItaly ,  Tianyi Chen<EMAIL_ADDRESS>Boston UniversityBostonMAUSA
,  Konstantinos Sotiropoulos<EMAIL_ADDRESS>Boston UniversityBostonMAUSA and
Charalampos E. Tsourakakis<EMAIL_ADDRESS>Boston UniversityBostonMAUSA

(2023)

###### Abstract.

Dense subgraph discovery methods are routinely used in a variety of
applications including the identification of a team of skilled individuals for
collaboration from a social network. However, when the network’s node set is
associated with a sensitive attribute such as race, gender, religion, or
political opinion, the lack of diversity can lead to lawsuits.

In this work, we focus on the problem of finding a densest diverse subgraph in
a graph whose nodes have different attribute values/types that we refer to as
colors. We propose two novel formulations motivated by different realistic
scenarios. Our first formulation, called the _densest diverse subgraph
problem_ (DDSP), guarantees that no color represents more than some fraction
of the nodes in the output subgraph, which generalizes the state-of-the-art
due to Anagnostopoulos et al. (CIKM 2020). By varying the fraction we can
range the diversity constraint and interpolate from a diverse dense subgraph
where all colors have to be equally represented to an unconstrained dense
subgraph. We design a scalable $\Omega(1/\sqrt{n})$-approximation algorithm,
where $n$ is the number of nodes. Our second formulation is motivated by the
setting where any specified color should not be overlooked. We propose the
_densest at-least- $\vec{k}$-subgraph problem_ (Dal$\vec{k}$S), a novel
generalization of the classic Dal$k$S, where instead of a single value $k$, we
have a vector $\bm{k}$ of cardinality demands with one coordinate per color
class. We design a $1/3$-approximation algorithm using linear programming
together with an acceleration technique. Computational experiments using
synthetic and real-world datasets demonstrate that our proposed algorithms are
effective in extracting dense diverse clusters.

social network analysis, densest subgraph problem, diversity, fairness,
approximation algorithms

††journalyear: 2023††copyright: acmlicensed††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††price: 15.00††doi: 10.1145/3580305.3599306††isbn:
979-8-4007-0103-0/23/08††ccs: Theory of computation Graph algorithms
analysis††ccs: Theory of computation Approximation algorithms analysis

##  1\. Introduction

Dense subgraph discovery (DSD) is a fundamental graph-mining primitive,
routinely used to mine social, financial, and biological networks among others
(Gionis and Tsourakakis, 2015). Applications include team formation (Gajewar
and Das Sarma, 2012; Rangapuram et al., 2013), detecting correlated genes
(Tsourakakis et al., 2013), community and spam link farm detection in the Web
graph (Gibson et al., 2005; Dourisboure et al., 2007), finding experts in
crowdsourcing systems (Kawase et al., 2019), spotting money laundering in
financial networks (Li et al., 2020; Starnini et al., 2021; Chen and
Tsourakakis, 2022), assessing the statistical significance of motifs (Chen et
al., 2022), and modeling real-world networks (Chanpuriya et al., 2021). See
the tutorial (Gionis and Tsourakakis, 2015) for an extensive list of related
applications.

Among various DSD formulations, the densest subgraph problem (DSP) stands out
for various reasons (Lanciano et al., 2023). For a given undirected graph
$G=(V,E)$ with $n=|V|$ nodes and $m=|E|$ edges, DSP is solvable in polynomial
time using maximum flow (Goldberg, 1984; Picard and Queyranne, 1982) or linear
programming (LP) (Charikar, 2000) and can be approximated within a factor of 2
using a greedy algorithm (Kortsarz and Peleg, 1994; Charikar, 2000), and more
recently solved near-optimally by an iterative greedy algorithm over the input
(Chekuri et al., 2022; Boob et al., 2020). Furthermore, DSP is solvable on
massive graphs using distributed and streaming implementations (Bahmani et
al., 2012) and admits useful variants, e.g., (Kawase and Miyauchi, 2018;
Kuroki et al., 2020; Tsourakakis, 2015; Veldt et al., 2021).

In numerous real-world settings, we have extra information about the nodes.
For example, in a graph database we may know each individual’s gender and
race. On the Twitter follow network, there exist methods to infer from tweets
whether a node is positive, neutral, or negative towards a controversial topic
(De et al., 2016). On brain networks neurons can play different functional
roles (Adami et al., 2011; Matejek et al., 2022). Consider also the problem of
organizing a cocktail party (Sozio and Gionis, 2010) with diversity
constraints as follows:

> A number of computer scientists aim to organize a cocktail party to
> celebrate Turing’s legacy. They believe that the success of the event will
> be higher if they invite computer scientists who have collaborated in the
> past but also who span different research areas. Whom should they invite?

We will refer to the set of different attribute values/types of nodes as
_colors_. The aforementioned settings motivate the problem of finding a
_densest diverse subgraph_ , namely a subset of nodes that induce many edges,
but also are diverse in terms of colors. We will be referring to the concept
of diversity as _fairness_ when the attribute concerns sensitive information
such as gender, race, or religion. Applying a DSD method does not guarantee
that the extracted densest subgraph will be diverse. Actually on a variety of
real data, we observe that this is the typical case, i.e., the densest
subgraph often exhibits strong homophily. Suppose the output of such a method
is used to select a group of individuals in a social network. In that case, it
will not be representative of the different races/religions/opinions that may
co-exist in the network. This can be especially harmful in the context of
selecting teams using dense subgraphs (Rangapuram et al., 2013), recommending
material to social media users that is not balanced in terms of opinions and
hence increasing polarization (Musco et al., 2018) or even leading to lawsuits
(Graber, 2020). In such cases, it becomes of paramount importance to have
algorithms that can extract a cluster with diversity guarantees.

With the exception of a recent paper by Anagnostopoulos et al.
(Anagnostopoulos et al., 2020), very little attention has been given to dense
diverse subgraph extraction, despite the extensive research on the DSP and its
applications (Lanciano et al., 2023). Although Anagnostopoulos et al.
(Anagnostopoulos et al., 2020) have made progress, there are still many
unanswered questions. For example, the methods they propose exclusively focus
on scenarios involving two colors and strive to achieve the complete fairness
in the output. Furthermore, their spectral approach offers theoretical
guarantees, but these guarantees are contingent upon restrictive conditions
for the spectrum of the input graph that are computationally burdensome to
verify. Additionally, they offer heuristics for scenarios involving more than
two colors, but without any assurances regarding their quality.

###  1.1. Our Contributions

We introduce two novel formulations for finding a densest diverse subgraph.
The first one is called the _densest diverse subgraph problem_ (DDSP), and the
second one is called the _densest at-least- $\vec{k}$-subgraph problem_
(Dal$\vec{k}$S). Informally, the first problem aims to offer diversity
guarantees that concern the relative sizes of the color classes, while the
second guarantees in terms of absolute counts.

Let $C$ be the set of colors. Our first formulation guarantees the diversity
of the output in the sense that it is not dominated by any single color. To
this end, the formulation introduces a parameter $\alpha\in[1/|C|,1]$ that
determines the maximum portion of any color in the output solution. It should
be noted that our formulation is a substantial generalization of the _fair
densest subgraph problem_ introduced by Anagnostopoulos et al.
(Anagnostopoulos et al., 2020), enabling us to deal with non-binary attributes
and to freely adjust the degree of diversity. Interestingly, from a theory
perspective, our formulation contains two important variants of DSP, the
densest at-least-$k$-subgraph problem (Dal$k$S) and the densest at-
most-$k$-subgraph problem (Dam$k$S), as special cases, cf. Sections 2 and 3.1
for details.

On the other hand, our second formulation guarantees the diversity of the
output in the sense that it does not overlook any specified color. In
particular, consider a graph where $|C|$ is a very small constant and the
minority colors appear only in a handful of nodes. Instead of imposing
relative constraints on the sizes through ratios, we impose absolute
constraints on the cardinalities of the nodes from each color. Specifically,
the formulation requires the output to contain at least a given number of
representatives from each color. The formulation is a novel generalization of
Dal$k$S, where instead of just demanding $k$ nodes in the output, we have a
vector $\bm{k}$ of demands from each color, i.e., they are lower bounds on how
many nodes we have to include from each possible color.

As both formulations are NP-hard, we design polynomial-time approximation
algorithms: For the first problem, we provide an approximation algorithm for
the case where $V$ is already diverse (i.e., $V$ is a feasible solution for
the problem). Our algorithm has an approximation ratio of
$\gamma\cdot\max\left\\{\frac{1}{\lceil 1/\alpha\rceil},\,\frac{1}{\alpha
n}\right\\}$, where $\gamma$ is the best approximation ratio known for Dal$k$S
(currently equal to $1/2$ (Khuller and Saha, 2009)). By simple calculation, we
observe that the above approximation ratio leads to an approximation ratio of
$\Omega(1/\sqrt{n})$, irrespective of any parameter other than the number of
nodes. Moreover, we can also see that the approximation ratio is lower bounded
by $1/|C|$, meaning that the algorithm attains a constant-factor approximation
for the case of $|C|=O(1)$ and is a generalization of the $1/2$-approximation
algorithm for the fair densest subgraph problem by Anagnostopoulos et al.
(Anagnostopoulos et al., 2020). Our algorithm is based on an approximation
algorithm for Dal$k$S with a carefully selected value of $k$, together with a
simple postprocessing. The primary factor determining the time complexity of
our algorithm is the time complexity of the approximation algorithm used for
Dal$k$S.

For the second problem, we devise a $1/3$-approximation algorithm, which runs
in polynomial time for constant $|C|$. In the design and analysis of our
algorithm, we generalize the existing $1/2$-approximation algorithm for
Dal$k$S and its approximation ratio analysis. As shown later, we can get a
$1/4$-approximate solution directly using the $1/2$-approximation algorithm
for Dal$k$S. Our effort improves the approximation ratio from $1/4$ to $1/3$,
by sacrificing some degree of scalability. We also present an acceleration
technique for the proposed algorithm with the aid of the well-known greedy
peeling algorithm (Charikar, 2000). The running time of our original algorithm
is $O((n/|C|)^{|C|}T_{\text{LP}})$, where $T_{\text{LP}}$ is the time required
to solve an LP used in the algorithm, while the accelerated version runs in
$O(|C|(n/|C|)^{|C|-1}T_{\text{LP}})$. In the case where $|C|$ is a small
constant, the reduction of the running time due to the acceleration is
drastic.

We evaluate our algorithms on real-life attributed datasets, including social
networks with gender and profession attributes. We compare against
Anagnostopoulos et al. (Anagnostopoulos et al., 2020), but we also develop a
novel baseline that uses node embeddings (Perozzi et al., 2014; Qiu et al.,
2018; Chanpuriya et al., 2020) combined with advances in scalable fair
clustering of points (Backurs et al., 2019). The algorithms we propose have
the capability to extract dense and diverse subgraphs. We demonstrate that
real-world networks contain dense subgraphs that exhibit significant
homophily, emphasizing the importance of employing our tools in scenarios
where diversity or fairness is essential.

##  2\. Related work

DSP and its variations. Given an undirected graph $G=(V,E)$, we define for any
non-empty subset of nodes $S\subseteq V$ the (degree) density
$d(S)=|E(S)|/|S|$, where $E(S)=\\{\\{u,v\\}\in E\mid u,v\in S\\}$. The DSP
aims to maximize the degree density over all possible subsets. Notice that the
degree density is just half of the average degree of an induced subgraph. The
DSP is polynomial-time solvable using $O(\log n)$ max-flow computations
(Goldberg, 1984; Picard and Queyranne, 1982), $O(1)$ number of flows using
parametric maximum flow (Gallo et al., 1989), or LP (Charikar, 2000). There
also exists a linear-time $1/2$-approximation algorithm that greedily removes
a node of the smallest degree, and reports the maximum degree density seen
among these subsets (Kortsarz and Nutov, 2005; Charikar, 2000). This kind of
algorithm is often called the greedy peeling algorithm. Recently, Boob et al.
(Boob et al., 2020) proposed Greedy++, an iterative peeling algorithm that
generalizes the above and converges to a near-optimal solution extremely fast
without the use of flows. Very recently, Chekuri et al. (Chekuri et al., 2022)
analyzed the performance of Greedy++, and showed that its algorithmic idea
could be generalized to general fractional supermodular maximization.

DSP has a lot of problem variants (Lanciano et al., 2023). Unlike the original
DSP, its size-restricted variants are known to be NP-hard. Indeed, the densest
$k$-subgraph problem (D$k$S) that asks for the densest subgraph with exactly
$k$ nodes, is not only NP-hard, but also hard to approximate, with the best-
known approximation ratio being $\Omega(1/n^{1/4+\epsilon})$ for any
$\epsilon>0$ (Bhaskara et al., 2010). This approximability result is far off
from the best-known hardness result that assumes the Exponential Time
Hypothesis (ETH). If ETH holds, then D$k$S cannot be approximated within a
ratio of $n^{1/(\log\log n)^{c}}$ for some $c>0$. Another size-restricted
variant, Dam$k$S, aims to maximize the degree density over all subsets of
nodes $S$ such that $|S|\leq k$ (Andersen and Chellapilla, 2009). It is known
that $\alpha$-approximation to Dam$k$S leads to $\alpha/4$-approximation to
D$k$S (Khuller and Saha, 2009).

Closest to this work lies Dal$k$S, which imposes the cardinality constraint
$|S|\geq k$ (Andersen and Chellapilla, 2009). The problem is also known to be
NP-hard (Khuller and Saha, 2009). Andersen and Chellapilla (Andersen and
Chellapilla, 2009) designed a $1/3$-approximation algorithm that runs in
linear time, using greedy peeling. Khuller and Saha (Khuller and Saha, 2009)
designed two different approximation algorithms, that both achieve
$1/2$-approximation using either a small number of flows, or by solving an LP
(Khuller and Saha, 2009).

Fair densest subgraph problem. Despite the large amount of research on DSD,
the problem of finding a densest diverse subgraph has not received attention
with the single exception of Anagnostopoulos et al. (Anagnostopoulos et al.,
2020) who introduced the fair densest subgraph problem for two colors.
Assuming the graph is fair to begin with, i.e., the two colors are equally
represented in $V$, they demand equal representation of each category in the
output. For this case, they proposed a greedy $1/2$-approximation algorithm
and a spectral approach. The spectral approach comes with guarantees only in
limited cases (e.g., all degrees being almost equal), which are not typical on
real data that tend to have a skewed degree distribution. This algorithm can
be extended to the case of $|C|>2$, but without quality guarantees. Finally,
the authors studied the hardness of the problem and showed that their
formulation is at least as hard as Dam$k$S: Any $\alpha$-approximation to
their formulation leads to $\alpha$-approximation to Dam$k$S.

Fairness and algorithms. While DSD with diversity is not yet well studied,
fair clustering of clouds of points has received much attention from the data
mining community. Chierichetti et al. (Chierichetti et al., 2017) initiated
the problem of finding balanced clusters in a cloud of points, namely clusters
where two groups are equally represented. They proposed a method called
fairlet decomposition, that decomposes a dataset into minimal sets that
satisfy fair representation, called fairlets. Afterwards, typical machine
learning algorithms, like $k$-median, can be used to obtain fair clusters.
Backurs et al. (Backurs et al., 2019) provided a scalable algorithm for the
fairlet decomposition. Later work has extended the problem of finding fair
clusters to the case of correlation clustering (Ahmadian et al., 2020b) and
hierarchical clustering (Ahmadian et al., 2020a).

##  3\. Problem statements

In this section, we formally introduce our optimization problems. Let
$G=(V,E)$ be an undirected graph with $n=|V|$ nodes and $m=|E|$ edges. Let $C$
be a set of colors. Without loss of generality $|C|\leq n$. Let $\ell\colon
V\rightarrow C$ be the coloring function that assigns a color to each node.
Given the above as input, we aim to find a densest diverse subgraph. We
mathematically formalize the notion of diversity in two ways found in Sections
3.1 and 3.2, respectively.

###  3.1. Densest Diverse Subgraph Problem (DDSP)

Our first notion aims to ensure that no single color dominates the rest.
Specifically, for $S\subseteq V$, we denote by $c_{\text{max}}(S)$ the maximum
number of nodes in $S$ that receive the same color, i.e.,
$c_{\mathrm{max}}(S)=\max_{c\in C}|\\{v\in S\mid\ell(v)=c\\}|$. We also denote
by $\alpha(S)$ the maximum fraction of monochromatic nodes in $S$, i.e.,
$\alpha(S)=c_{\mathrm{max}}(S)/|S|$. Our problem can be formulated as follows:

###### Problem 1 (DDSP).

Given an undirected graph $G=(V,E)$, $\ell\colon V\rightarrow C$, and
$\alpha\in[1/|C|,1]$, find a subset of nodes $S\subseteq V$ that maximizes the
degree density $d(S)$ subject to the constraint $\alpha(S)\leq\alpha$.

This problem is a major generalization of the fair densest subgraph problem
introduced by Anagnostopoulos et al. (Anagnostopoulos et al., 2020), which is
obtained for the special values $|C|=2$ and $\alpha=1/2$. As the fair densest
subgraph problem is NP-hard (Anagnostopoulos et al., 2020), Problem 1 is also
NP-hard. Clearly when $\alpha=1$ we are oblivious to diversity and obtain
(polynomial-time solvable) DSP. More interestingly, Problem 1 contains two
totally different optimization problems, Dal$k$S and Dam$k$S, as special
cases:

###### Proposition 1.

There exist polynomial-time reductions from Dal$k$S and Dam$k$S to Problem 1.

###### Proof.

The reductions are obtained by appropriately setting the number of colors and
the parameter $\alpha$. For Dal$k$S, it suffices to construct the instance of
Problem 1 by coloring the nodes with $n$ distinct colors and setting $\alpha$
to be $1/k$. For Dam$k$S, it suffices to construct the instance of Problem 1
by coloring the nodes with the single color and adding $k$ isolated nodes
(i.e., dummy nodes) with another color, and setting $\alpha=1/2$. ∎

###  3.2. Densest At-Least-$\vec{k}$-Subgraph (Dal$\vec{k}$S)

Our second formulation diversifies the output by ensuring that it does not
overlook any specified color. To this end, the formulation requires the output
to contain at least a given number of representatives from each color. For
$S\subseteq V$ and $c\in C$, let $S_{c}=\\{v\in S\mid\ell(v)=c\\}$. Our
problem formulation is as follows:

###### Problem 2 (Dal$\vec{k}$S).

Given an undirected graph $G=(V,E)$, $\ell\colon V\rightarrow C$, and
$\bm{k}=(k_{c})_{c\in C}\in\mathbb{Z}_{\geq 0}^{|C|}$, find a subset of nodes
$S\subseteq V$ that maximizes the degree density $d(S)$ subject to
$|S_{c}|\geq k_{c}$ for any $c\in C$.

Obviously the above problem is a generalization of Dal$k$S. Thus, the problem
is NP-hard. If $\bm{k}=\bm{0}$, the problem is reduced to the original DSP;
therefore, throughout the paper, we assume that $k_{c}\geq 1$ for some $c\in
C$. As mentioned in the introduction, we can easily get a $1/4$-approximation
algorithm for the problem:

###### Proposition 2.

For Problem 2, there exists a polynomial-time $1/4$-approximation algorithm.

###### Proof.

Let $G=(V,E)$, $\ell\colon V\rightarrow C$, $\bm{k}=(k_{c})_{c\in
C}\in\mathbb{Z}_{\geq 0}^{|C|}$ be an instance of Problem 2, and OPT the
optimal value of the instance. To get a feasible solution for Problem 2, we
have to take at least $k_{c}$ nodes for every color $c\in C$; therefore,
Dal$k$S with $k=\|\bm{k}\|_{1}=\sum_{c\in C}k_{c}$ on $G$ is a relaxation of
Problem 2 on $G$. Let $S\subseteq V$ be an $\alpha$-approximate solution for
Dal$k$S with $k=\|\bm{k}\|_{1}$. As Dal$k$S with $k=\|\bm{k}\|_{1}$ is a
relaxation of Problem 2, we have $d(S)\geq\alpha\cdot\text{OPT}$. Note that
$S$ is not necessarily feasible for Problem 2, but we can make it feasible by
adding at most $k_{c}$ nodes for every color $c\in C$, resulting in adding at
most $\|\bm{k}\|_{1}\leq|S|$ nodes in total. Letting $S’\subseteq V$ be the
resulting subset, we have
$d(S’)=\frac{|E(S’)|}{|S’|}\geq\frac{|E(S)|}{|S’|}\geq\frac{1}{2}\cdot
d(S)\geq\frac{\alpha}{2}\cdot\text{OPT}$, meaning that $S’$ is an
$\alpha/2$-approximate solution for Problem 2. As mentioned above, there is a
polynomial-time $1/2$-approximation algorithm for Dal$k$S (Khuller and Saha,
2009). Therefore, we can set $\alpha=1/2$ and have a polynomial-time
$1/4$-approximation algorithm for Problem 2. ∎

##  4\. Algorithm for Problem 1

In this section, we design a polynomial-time
$\Omega(1/\sqrt{n})$-approximation algorithm for Problem 1. A subset of nodes
$S\subseteq V$ is said to be diverse if $\alpha(S)\leq\alpha$ holds. In what
follows, we assume that $V$ is diverse, i.e., $\alpha(V)\leq\alpha$.

###  4.1. The Proposed Algorithm

Our algorithm first computes a constant-factor approximate solution (say
$\gamma$-approximate solution) to Dal$k$S on $G$ with $k=\lceil
1/\alpha\rceil$. For example, we can use a $1/2$-approximation algorithm using
LP (Khuller and Saha, 2009) or a $1/3$-approximation algorithm using greedy
peeling (Andersen and Chellapilla, 2009). Then, the algorithm makes the
solution feasible by adding an arbitrary node with a color of the lowest
participation iteratively (Procedure 1). For reference, the entire procedure
of our algorithm is summarized in Algorithm 2.

The time complexity of Algorithm 2 is dominated by the algorithm we use for
Dal$k$S. Even if we consider the objective value in Procedure 1, it still
depends on the choice of the approximation algorithm for Dal$k$S. If we employ
a $1/2$-approximation algorithm using LP, the time complexity of Algorithm 2
is dominated by that required for solving the LP. If we use a
$1/3$-approximation algorithm using greedy peeling, Algorithm 2 can be
implemented to run in $O(m+n\log n)$ time, by handling the nodes outside $S$
using a Fibonacci heap for each color with key values being degrees to $S$.

1 while  _$\alpha(S) >\alpha$_ do

2 Find $v_{\mathrm{min}}\in V\setminus S$ that satisfies
$\ell(v_{\mathrm{min}})\in\mathop{\rm argmin}_{c\in C}|S_{c}|$;

/* In practice consider also the objective value. */

3 $S\leftarrow S\cup\\{v_{\mathrm{min}}\\}$;

4

5return $S$;

Procedure 1 $\mathsf{Diversify}(S)$

Input : $G=(V,E)$, $\ell\colon V\rightarrow C$, $\alpha\in[1/|C|,1]$

Output : $S\subseteq V$

1 $S\leftarrow$ $\gamma$-approximate solution to Dal$k$S on $G$ with $k=\lceil
1/\alpha\rceil$;

/* See (Khuller and Saha, 2009) and (Andersen and Chellapilla, 2009) for the
algorithms achieving $\gamma=1/2$ and $\gamma=1/3$, respectively. */

2 return $\mathsf{Diversify}(S)$;

Algorithm 2 $\Omega(1/\sqrt{n})$-approximation algorithm

###  4.2. Analysis

We analyze the approximation ratio of Algorithm 2. We have the following key
lemma:

###### Lemma 0.

Assume that $\alpha(V)\leq\alpha$ holds. Then, for any $S\subseteq V$ with
$|S|\geq\lceil 1/\alpha\rceil$, it holds that
$|\mathsf{Diversify}(S)|\leq\min\\{\lceil 1/\alpha\rceil,\alpha n\\}\cdot|S|$.

###### Proof.

We first prove that
$c_{\mathrm{max}}(S)=c_{\mathrm{max}}(\mathsf{Diversify}(S))$ holds. As
$S\subseteq\mathsf{Diversify}(S)$, we have $c_{\mathrm{max}}(S)\leq
c_{\mathrm{max}}(\mathsf{Diversify}(S))$. Therefore, it suffices to show
$c_{\mathrm{max}}(S)\geq c_{\mathrm{max}}(\mathsf{Diversify}(S))$. For
$S\subseteq V$ and $c\in C$, we denote by $f(S,c)$ the fraction of the nodes
in $S$ that receive the color $c$, i.e., $f(S,c)=|S_{c}|/|S|$. Let us focus on
an arbitrary iteration of Procedure 1 and let $S’\subseteq V$ be the subset
kept at the beginning of the iteration. Then there exists $c\in C$ that
satisfies the condition $f(S’,c)<\alpha$. Suppose, for contradiction, that
there exist no such colors. Then, for any color $c\in C$, we have
$f(S’,c)\geq\alpha$. Moreover, as $S’$ is not yet feasible, we see that there
exists $c’\in C$ that satisfies $f(S’,c’)>\alpha$. Therefore, we have

$\displaystyle 1=\sum_{c\in C}f(S’,c)$ $\displaystyle=f(S’,c’)+\sum_{c\in
C\setminus\\{c’\\}}f(S’,c)$ $\displaystyle>\alpha+(|C|-1)\alpha=|C|\alpha\geq
1,$

a contradiction. From the above, recalling the greedy rule of Procedure 1, we
see that Procedure 1 only adds the nodes with the colors $c\in C$ that satisfy
$f(S’,c)<\alpha$. To increase $c_{\text{max}}$ in this iteration, Procedure 1
needs to add a node with a color $c\in C$ that satisfies $f(S’,c)>\alpha$, but
it does not happen. As we fixed an iteration arbitrarily, $c_{\text{max}}$
does not increase throughout Procedure 1. Therefore, we have
$c_{\text{max}}(S)\geq c_{\text{max}}(\textsf{Diversify}(S))$.

Assume that in some iteration, which produces $S^{\prime\prime}\subseteq V$,
of Procedure 1, $|S^{\prime\prime}|=\lceil|S|/\alpha\rceil$ holds. Then we
have

$\displaystyle\alpha(S^{\prime\prime})=\frac{c_{\mathrm{max}}(S^{\prime\prime})}{|S^{\prime\prime}|}=\frac{c_{\mathrm{max}}(S)}{\lceil|S|/\alpha\rceil}\leq\alpha\cdot\frac{c_{\mathrm{max}}(S)}{|S|}\leq\alpha,$

where the second equality follows from
$c_{\mathrm{max}}(S)=c_{\mathrm{max}}(\mathsf{Diversify}(S))$. This means that
the algorithm terminates at or before this iteration. Therefore, we have
$|\mathsf{Diversify}(S)|\leq\lceil|S|/\alpha\rceil$.

Similarly, assume that in some iteration, which produces
$S^{\prime\prime}\subseteq V$, of Procedure 1,
$|S^{\prime\prime}|=c_{\mathrm{max}}(S)|S|$ holds. Then we have

$\displaystyle\alpha(S^{\prime\prime})=\frac{c_{\mathrm{max}}(S^{\prime\prime})}{|S^{\prime\prime}|}=\frac{c_{\mathrm{max}}(S)}{c_{\mathrm{max}}(S)|S|}=\frac{1}{|S|}\leq\frac{1}{\lceil
1/\alpha\rceil}\leq\alpha,$

where the first inequality follows from the assumption of the lemma. This
means that the algorithm terminates at or before this iteration. Therefore, we
have $|\mathsf{Diversify}(S)|\leq c_{\mathrm{max}}(S)|S|$.

From the above, we see that

$\displaystyle|\mathsf{Diversify}(S)|$
$\displaystyle\leq\min\\{\lceil|S|/\alpha\rceil,c_{\mathrm{max}}(S)|S|\\}$
$\displaystyle\leq\min\\{\lceil 1/\alpha\rceil,c_{\mathrm{max}}(V)\\}\cdot|S|$
$\displaystyle\leq\min\\{\lceil 1/\alpha\rceil,\alpha n\\}\cdot|S|,$

which completes the proof. ∎

Using the above lemma, we can prove the following:

###### Theorem 2.

Algorithm 2 is a $\left(\gamma\cdot\max\left\\{\frac{1}{\lceil
1/\alpha\rceil},\,\frac{1}{\alpha n}\right\\}\right)$-approximation algorithm
for Problem 1 when $\alpha(V)\leq\alpha$ holds. Here $\gamma$ is the
approximation ratio of the algorithm for Dal$k$S used in Algorithm 2.

###### Proof.

Let $\mathsf{OPT}$ be the optimal value of Problem 1. Let $S\subseteq V$ be a
constant-factor approximate solution (say $\gamma$-approximate solution) for
Dal$k$S on $G$ with $k=\lceil 1/\alpha\rceil$. Note that Dal$k$S with
$k=\lceil 1/\alpha\rceil$ is a relaxation of Problem 1, because even if we
pick the nodes, all of which have different colors, we need at least $k=\lceil
1/\alpha\rceil$ nodes to satisfy the diversity constraint. Thus, we have
$d(S)=\frac{|E(S)|}{|S|}\geq\gamma\cdot\mathsf{OPT}$. The output of the
algorithm is $\mathsf{Diversify}(S)$ whose objective value can be evaluated as
follows:

$\displaystyle d(\mathsf{Diversify}(S))$
$\displaystyle=\frac{|E(\mathsf{Diversify}(S))|}{|\mathsf{Diversify}(S)|}$
$\displaystyle\geq\frac{|E(S)|}{\min\\{\lceil 1/\alpha\rceil,\alpha
n\\}\cdot|S|}$ $\displaystyle\geq\gamma\cdot\max\left\\{\frac{1}{\lceil
1/\alpha\rceil},\,\frac{1}{\alpha n}\right\\}\cdot\mathsf{OPT},$

where the first inequality follows from Lemma 1. ∎

It should be emphasized that the approximation ratio of Algorithm 2 is lower
bounded by $1/|C|$, meaning that the algorithm is a constant-factor
approximation algorithm for the case of $|C|=O(1)$. In fact, we see that
$\frac{1}{\lceil 1/\alpha\rceil}\geq\frac{1}{\lceil|C|\rceil}=\frac{1}{|C|}$.
Therefore, Algorithm 2 can be seen as a generalization of the
$1/2$-approximation algorithm for the fair densest subgraph problem by
Anagnostopoulos et al. (Anagnostopoulos et al., 2020).

Moreover, the above analysis leads to an approximation ratio that is
independent of any parameter other than $n$:

###### Corollary 0.

Algorithm 2 is an $\Omega(1/\sqrt{n})$-approximation algorithm for Problem 1
when $\alpha(V)\leq\alpha$ holds.

###### Proof.

We can lower bound the approximation ratio given in Theorem 2 as follows:

$\displaystyle\gamma\cdot\max\left\\{\frac{1}{\lceil
1/\alpha\rceil},\,\frac{1}{\alpha
n}\right\\}\geq\gamma\cdot\sqrt{\frac{1}{\lceil
1/\alpha\rceil}\cdot\frac{1}{\alpha
n}}=\Omega\left(\frac{1}{\sqrt{n}}\right).$

∎

##  5\. Algorithm for Problem 2

In this section, we design a polynomial-time $1/3$-approximation algorithm for
Problem 2 with $|C|=O(1)$. Using a sophisticated LP, we can improve the
approximation ratio of $1/4$ given in Proposition 2. Recall that
$\bm{k}=(k_{c})_{c\in C}\in\mathbb{Z}_{\geq 0}^{|C|}$ is the input lower-bound
vector.

###  5.1. The Proposed Algorithm

Let $\bm{p}=(p_{c})_{c\in C}\in\mathbb{Z}_{\geq 0}^{|C|}$ be a vector that
satisfies $\bm{p}\geq\bm{k}$. We consider the following LP:

$\displaystyle\mathrm{LP}(\bm{p})\colon\ \ $ $\displaystyle\mathrm{maximize}$
$\displaystyle\sum_{e\in E}x_{e}$ $\displaystyle\mathrm{subject\ to}$
$\displaystyle x_{e}\leq y_{u},\ x_{e}\leq y_{v}$ $\displaystyle\forall
e=\\{u,v\\}\in E,$ $\displaystyle\sum_{v\in
V_{c}}y_{v}=\frac{p_{c}}{\|\bm{p}\|_{1}}$ $\displaystyle\forall c\in C,$
$\displaystyle y_{v}\leq\frac{1}{\|\bm{p}\|_{1}}$ $\displaystyle\forall v\in
V,$ $\displaystyle x_{e},y_{v}\geq 0$ $\displaystyle\forall e\in E,\,\forall
v\in V.$

Note that this is a major generalization of the LP used in the
$1/2$-approximation algorithm for Dal$k$S (Khuller and Saha, 2009). The LP for
Dal$k$S is parameterized by a single value, while our LP is parameterized by
multiple values (i.e., a vector $\bm{p}$). This modification is essential to
address the generalization caused by Dal$\vec{k}$S.

Let $(\bm{x}^{*},\bm{y}^{*})$ be an optimal solution to $\mathrm{LP}(\bm{p})$
for $\bm{p}$. For $(\bm{x}^{*},\bm{y}^{*})$ and $r\geq 0$, we define
$S(r)=\\{v\in V\mid y^{*}_{v}\geq r\\}$. Now we are ready to present our
algorithm. For each $\bm{p}\in\mathbb{Z}_{\geq 0}^{|C|}$ such that
$\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$, the algorithm conducts the following
procedure: It first solves $\mathrm{LP}(\bm{p})$ to obtain an optimal solution
$(\bm{x}^{*},\bm{y}^{*})$. Then using the solution, the algorithm enumerates
all possible $S(r)$’s by setting $r\in\\{y^{*}_{v}\mid v\in V\\}\cup\\{0\\}$
each, makes them feasible by adding nodes with appropriate colors using
Procedure 3, and takes the best subset among them, as a candidate for
$\bm{p}$. After the above iterations, the algorithm finally outputs the best
subset among all candidates for $\bm{p}$ with
$\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$. The entire procedure is summarized
in Algorithm 4.

1 for  _each $c\in C$_ do

2 if  _$|S_{c}| <k_{c}$_ then

3 Take arbitrary $v\in V_{c}\setminus S_{c}$;

/* In practice consider also the objective value. */

4 $S\leftarrow S\cup\\{v\\}$;

5

6

7return $S$;

Procedure 3 $\textsf{Make\\_it\\_feasible}(S)$

Input : $G=(V,E)$, $\ell\colon V\rightarrow C$, $\bm{k}=(k_{c})_{c\in
C}\in\mathbb{Z}_{\geq 0}^{|C|}$

Output : $S\subseteq V$

1 for  _each $\bm{p}$ such that $\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$_ do

2 Solve $\mathrm{LP}(\bm{p})$ to obtain an optimal solution
$(\bm{x}^{*},\bm{y}^{*})$;

3 Construct
$\textsf{Candidates}(\bm{p})\coloneqq\\{\textsf{Make\\_it\\_feasible}(S(r))\mid
r\in\\{y^{*}_{v}\mid v\in V\\}\cup\\{0\\}\\}$;

4 Take $\textsf{Best}(\bm{p})\in\mathop{\rm argmax}\\{d(S)\mid
S\in\textsf{Candidates}(\bm{p})\\}$;

5

6return $\mathop{\rm argmax}\\{d(S)\mid
S\in\\{\textsf{Best}(\bm{p})\mid\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}\\}\\}$;

Algorithm 4 $1/3$-approximation algorithm for Problem 2

###  5.2. Analysis

We first give a lower bound on the optimal value of $\mathrm{LP}(\bm{p})$.

###### Lemma 0.

For any $S\subseteq V$ such that $|S_{c}|=p_{c}$ for every $c\in C$, there
exists a feasible solution of $\,\mathrm{LP}(\bm{p})$ whose objective function
value is greater than or equal to $d(S)$.

###### Proof.

Construct a solution $(\bm{x},\bm{y})$ of $\mathrm{LP}(\bm{p})$ as follows:

$\displaystyle x_{e}=\begin{cases}1/\|\bm{p}\|_{1}&\text{if }e\in E(S),\\\
0&\text{otherwise},\end{cases}\qquad
y_{v}=\begin{cases}1/\|\bm{p}\|_{1}&\text{if }v\in S,\\\
0&\text{otherwise}.\end{cases}$

Then we can see that $(\bm{x},\bm{y})$ is feasible for $\mathrm{LP}(\bm{p})$.
In fact, $\sum_{v\in V_{c}}y_{v}=\sum_{v\in
S_{c}}y_{v}=\frac{p_{c}}{\|\bm{p}\|_{1}}$. The objective function value of
$(\bm{x},\bm{y})$ is $\sum_{e\in E}x_{e}=\sum_{e\in
E(S)}x_{e}=\frac{|E(S)|}{\|\bm{p}\|_{1}}=d(S).$ Thus, we have the lemma. ∎

For $S\subseteq V$, let $C_{\mathrm{sat}}(S)=\\{c\in C\mid|S_{c}|\geq
k_{c}\\}$, i.e., the set of colors for which the constraint is satisfied by
$S$. We can prove the following key lemma (see Appendix A for the proof):

###### Lemma 0.

Let $S^{*}\subseteq V$ be an optimal solution to Problem 2. For each $c\in C$,
let $p^{*}_{c}=|S^{*}_{c}|$. Let $(\bm{x}^{*},\bm{y}^{*})$ be an optimal
solution to $\mathrm{LP}(\bm{p}^{*})$ and $\lambda$ its objective value. Then
there exists $S\in\\{S(r)\mid r\in\\{y^{*}_{v}\mid v\in V\\}\cup\\{0\\}\\}$
that satisfies (exactly) one of the following:

  1. (1)

$d(S)\geq\lambda/3$ and $C_{\mathrm{sat}}(S)=C$;

  2. (2)

$\displaystyle\frac{|E(S)|}{\sum_{c\in C_{\mathrm{sat}}(S)}|S_{c}|+\sum_{c\in
C\setminus C_{\mathrm{sat}}(S)}k_{c}}\geq\lambda/3$ and
$C_{\mathrm{sat}}(S)\neq\emptyset\neq C\setminus C_{\mathrm{sat}}(S)$;

  3. (3)

$|E(S)|\geq|E(S^{*})|/3$ and $C_{\mathrm{sat}}(S)=\emptyset$.

Based on the above lemma, we prove the following:

###### Theorem 3.

Algorithm 4 is a $1/3$-approximation algorithm for Problem 2 and runs in
$O((n/|C|)^{|C|}T_{\mathrm{LP}})$ time, where $T_{\mathrm{LP}}$ is the time
complexity required to solve the LP.

###### Proof.

As the time complexity analysis is straightforward, we show the approximation
ratio of $1/3$. Let $S^{*}\subseteq V$ be an optimal solution to Problem 2 and
for each $c\in C$, let $p^{*}_{c}=|S^{*}_{c}|$. Looking at Lemma 2, we see
that when the algorithm solves $\mathrm{LP}(\bm{p}^{*})$, one of the possible
$S(r)$’s itself is just the subset of nodes $S\subseteq V$ whose existence is
guaranteed in Lemma 2. Then it is easy to see that
$\textsf{Make\\_it\\_feasible}(S)$ is a $1/3$-approximate solution. Therefore,
$\textsf{Best}(\bm{p}^{*})$ is also a $1/3$-approximate solution. Noticing
that the algorithm outputs the best of $\textsf{Best}(\bm{p})$’s for all
possible $\bm{p}$ with $\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$ (containing
$\bm{p^{*}}$), we are done. ∎

Here we mention a simple acceleration technique for Algorithm 4. As shown in
Lemma 1, $\text{LP}(\bm{p}^{*})$ with $p^{*}_{c}=|S^{*}_{c}|$ has the optimal
value greater than or equal to $d(S^{*})$. Therefore, if we solve
$\text{LP}(\bm{p})$ for some $\bm{p}$ and its optimal value is less than the
density of the current best feasible solution, the LP must not be
$\text{LP}(\bm{p}^{*})$ and thus we can skip the procedure to be applied to
its optimal solution (i.e., Lines 3 and 4). In the next section, we present an
additional acceleration technique that can reduce the number of LPs to solve.

###  5.3. Acceleration via Greedy Peeling

Our acceleration technique for Algorithm 4 is based on greedy peeling.
Algorithm 5 is a straightforward application of greedy peeling to Problem 2,
where for $S\subseteq V$ and $v\in S$, $\text{deg}_{S}(v)$ denotes the degree
of $v$ in $G[S]=(S,E(S))$.

Input : $G=(V,E)$, $\ell\colon V\rightarrow C$, $\bm{k}=(k_{c})_{c\in
C}\in\mathbb{Z}_{\geq 0}^{|C|}$

Output : $S\subseteq V$

1 $S^{(n)}\leftarrow V$, $i\leftarrow n$;

2 while  _$|S^{(i)}_{c}| >k_{c}\ $ for every $c\in C$ with $k_{c}\geq 1$_ do

3 $v_{\text{min}}\leftarrow\mathop{\rm argmin}_{v\in
S^{(i)}}\mathrm{deg}_{S^{(i)}}(v)$;

4 $S^{(i-1)}\leftarrow S^{(i)}\setminus\\{v_{\text{min}}\\}$, $i\leftarrow
i-1$;

5

6return $\mathop{\rm argmax}\\{d(S)\mid S\in\\{S^{(n)},\dots,S^{(i)}\\}\\}$;

Algorithm 5 Greedy peeling algorithm for Problem 2

This algorithm achieves an approximation ratio of $1/2$ in a very specific
case as follows:

###### Lemma 0.

Assume that there exists an optimal solution $S^{*}\subseteq V$ that satisfies
$|S^{*}_{c}|>k_{c}$ for every $c\in C$ with $k_{c}\geq 1$. Then Algorithm 5
outputs a $1/2$-approximate solution for Problem 2.

###### Proof.

It is easy to see that for any $v\in S^{*}$, $S^{*}\setminus\\{v\\}$ is a
feasible solution for Problem 2. Therefore, we have that for any $v\in S^{*}$,

$\displaystyle d(S^{*})\geq d(S^{*}\setminus\\{v\\}).$

Transforming the above inequality, we have that for any $v\in S^{*}$,

(1) $\displaystyle\mathrm{deg}_{S^{*}}(v)\geq d(S^{*}).$

Let $v^{*}$ be the node that is contained in $S^{*}$ and removed first by the
algorithm. Note that the existence of such a node is guaranteed due to the
assumption of the lemma and the design of the algorithm. Let
$S^{\prime}\subseteq V$ be the subset of nodes kept just before the removal of
$v^{*}$. Obviously $S^{*}\subseteq S^{\prime}$ and thus $S^{\prime}$ is a
feasible solution of Problem 2. We can evaluate the density of $S^{\prime}$ as
follows:

$\displaystyle d(S^{\prime})$ $\displaystyle=\frac{\frac{1}{2}\sum_{v\in
S^{\prime}}\mathrm{deg}_{S^{\prime}}(v)}{|S^{\prime}|}\geq\frac{1}{2}\mathrm{deg}_{S^{*}}(v^{*})\geq\frac{1}{2}d(S^{*}),$

where the first inequality follows from the greedy choice of $v^{*}$ and the
relation $S^{\prime}\supseteq S^{*}$, and the second inequality follows from
inequality (1). Noticing that $S^{\prime}$ is one of the output candidates of
the algorithm, we have the lemma. ∎

Finally, our accelerated algorithm is described in Algorithm 6.

Input : $G=(V,E)$, $\ell\colon V\rightarrow C$, $\bm{k}=(k_{c})_{c\in
C}\in\mathbb{Z}_{\geq 0}^{|C|}$

Output : $S\subseteq V$

1 Run Algorithm 5 and obtain its output $S_{\text{peel}}$;

2 Run Algorithm 4 after replacing “$\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$”
by “$\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in C}$ with $p_{c}=k_{c}$ for some $c\in
C$ with $k_{c}\geq 1$” in Lines 1 and 5, and obtain its output
$S_{\text{LP}}$;

3 return $\mathop{\rm argmax}\\{d(S)\mid
S\in\\{S_{\text{peel}},S_{\text{LP}}\\}\\}$;

Algorithm 6 Accelerated $1/3$-approximation algorithm for Problem 2

###### Theorem 5.

Algorithm 6 is a $1/3$-approximation algorithm for Problem 2 and runs in
$O(|C|(n/|C|)^{|C|-1}T_{\mathrm{LP}})$ time, where $T_{\mathrm{LP}}$ is the
time complexity required to solve the LP.

###### Proof.

The time complexity analysis is again trivial. Hence, in what follows, we
guarantee the approximation ratio. If there exists an optimal solution
$S^{*}\subseteq V$ that satisfies $|S^{*}_{c}|>k_{c}$ for every $c\in C$ with
$k_{c}\geq 1$, then the output $S_{\text{peel}}$ of Algorithm 5 is a
$1/2$-approximate solution; thus, we are done. Otherwise there exists an
optimal solution $S^{*}\subseteq V$ that satisfies $|S^{*}_{c}|=k_{c}$ for
some $c\in C$ with $k_{c}\geq 1$. The modified version of Algorithm 4 used in
Algorithm 6 skips some $\bm{p}$’s with $\bm{k}\leq\bm{p}\leq(|V_{c}|)_{c\in
C}$ but still tests $\bm{p}^{*}$ with $p^{*}_{c}=|S^{*}_{c}|$ for any $c\in
C$. Therefore, the analysis similar to that for Algorithm 4 still works and we
see that $S_{\text{LP}}$ is a $1/3$-approximate solution. Therefore, we have
the theorem. ∎

##  6\. Experimental Evaluation

In this section, we evaluate our proposed algorithms using a variety of
synthetic and real-world networks.

###  6.1. Experimental Setup

Table 1. Dataset statistics summary.

Dataset | $|C|$ | $n$ | $m$ | $\alpha(V)$
---|---|---|---|---
Amazon Product | $2$ | 3.3K $\pm 4.7K$ | 24.7K $\pm 47.3K$ | 0.68 $\pm 0.12$
Facebook100 |  $2$ or $4$ | 10.7K $\pm 8.4K$ | 399K $\pm 315K$ | 0.48 $\pm 0.09$
GitHub Developers | $2$ | 37,700 | 289,003 | 0.74
LastFM Asia | $18$ | 7,624 | 27,806 | 0.20
Deezer Europe | $2$ | 28,281 | 92,752 | 0.56
DBLP | $6$ | 25,176 | 151,670 | 0.32

Datasets. We use two collections of datasets and four single-graph datasets,
with attributes for the nodes in the graphs. Table 1 summarizes the statistics
of the following datasets, where for the first two datasets, we put the
average values with the standard deviations.

  * •

Amazon Product Metadata \- 299 graphs (Ni et al., 2019). This consists of a
collection of 299 graphs, each with 2 colors, as curated by Anagnostopoulos et
al. (Anagnostopoulos et al., 2020). Classes are product categories, while
edges indicate that products were co-purchased.

  * •

Facebook100 \- 100 graphs (Traud et al., 2012). This contains 100 anonymized
networks of the Facebook social network from universities across the United
States. Nodes have demographic attributes, like profession (faculty/student),
gender (male/female), the year they joined the university, etc. For our
purpose, we also create $2^{2}=4$ categories that combine profession and
gender. The largest graph in terms of $m$ has 1,382,325 edges.

  * •

GitHub Developers (Rozemberczki et al., 2021). Nodes are developers in GitHub
who have starred at least 10 repositories, and edges are mutual follower
relationships between them. The attribute is whether the user is a web or a
machine learning developer.

  * •

LastFM Asia Social Network (Rozemberczki and Sarkar, 2020). Nodes are LastFM
users from Asian countries and edges are mutual follower relationships between
them. The attribute is the location of a user.

  * •

Deezer Europe Social Network (Rozemberczki and Sarkar, 2020). Nodes are Deezer
users from European countries and edges are mutual follower relationships
between them. The attribute is the gender of a user.

  * •

DBLP Co-Authorship. We also create a dataset from the DBLP database. We create
a graph from authors of papers published in major conferences in $6$ areas
(Theory, Data Management, Data Mining, Learning, Networking, and Image & Video
Processing) between 2003 and 2022. Nodes are authors with attributes being the
area (s)he has most publications. Edges indicate that the two authors have
collaborated at least once. See Appendix B.1 for details.

Figure 1. The diversity of the entire graph and the top-4 densest subgraphs of
the first two datasets in Table 1. The first figure is for the Amazon Product
dataset ($|C|=2$), while the latter three figures are for the Facebook100
dataset (left: Profession and Gender ($|C|=4$), middle: Profession ($|C|=2$),
right: Gender ($|C|=2$)). Note that $\alpha(S)=1/|C|$ means the complete
diversity of $S$.

Baselines. For Problem 1, we employ the following baselines, including a novel
baseline we devise using node embeddings (Qiu et al., 2018):

  * •

DSP. The (unconstrained) densest subgraph. Specifically, we use Greedy++ by
Boob et al. (Boob et al., 2020) for 5 iterations, which in practice finds an
optimal solution to DSP in very few iterations. For $S\subseteq V$, we define
the normalized density as its density divided by the optimal value to DSP.

  * •

PS and FPS. The spectral algorithms by Anagnostopoulos et al. (Anagnostopoulos
et al., 2020) that split the entries of the largest eigenvector of the
adjacency matrix (PS) and “fairified” adjacency matrix (FPS), based on their
color, and sort them in a similar spirit with spectral clustering.

  * •

Embedding+Fair Clustering. We design a novel baseline that first embeds the
graph using the node embedding method NetMF (Qiu et al., 2018) and then
clusters the nodes using the fair $k$-means implementation of Backurs et al.
(Backurs et al., 2019) for various values of $k$. We compute the density of
each fair cluster for each value of $k$, and output the maximum among all.

For Problem 2, we run the following two baselines:

  * •

IP. We implement an exact algorithm using integer programming and test its
scalability. See Appendix B.2 for details.

  * •

Prop2. We also implement the $1/4$-approximation algorithm introduced in
Proposition 2. To solve Dal$k$S, we use the $1/2$-approximation algorithm
based on LP with a greedy peeling acceleration (Khuller and Saha, 2009).

Machine specs and code. The experiments are performed on a single machine,
with Intel i7-10850H CPU @ 2.70GHz and 32GB of main memory. We use C++ for all
experiments. Linear programming and integer programming are implemented with
SciPy and solved with HiGHS (Huangfu and Hall, 2015). The code and datasets
are available online.111https://github.com/tsourakakis-lab/densest-diverse-
subgraphs

###  6.2. Evaluation of Algorithm 2 (for Problem 1)

Preliminary experiments. Although we have created a reliable algorithmic
toolbox for dense diverse clusters, we must assess their practical
effectiveness. Specifically, when examining the densest subgraph or the
top-$k$ densest subgraphs with sensitive attributes, do we observe diversity
in the subgraphs? The answer is generally no, as observed in the vast majority
of cases. This trend can result in unfair solutions, particularly in the
context of sensitive attributes.

In Figure 1 we present the statistics of the entire graph and the top-4
densest subgraphs of the Amazon Product and Facebook100 datasets from Table 1,
using standard box plots. As can be seen, the densest subgraphs tend to be not
diverse. Especially for the Amazon Product dataset (leftmost figure), the
densest subgraph most of the times is nearly monochromatic. This phenomenon is
not restricted to the densest subgraph but also found for the top-4 densest
subgraphs, implying that strong homophily is a key factor behind dense
clusters. We observe a similar trend for the Facebook100 dataset (the latter
three figures). Even if we restrict our attention to the specific attribute we
consider, profession or gender, we see that again they are not represented
equally in the densest subgraph. These findings motivate the study of Problem
1, where we can control the extent to which a specific color dominates the
subgraph returned by an algorithm.

Solution quality of algorithms. We compare Algorithm 2 with the baseline
algorithms with respect to the density and diversity of the returned
subgraphs, using the six datasets of Table 1. We run Algorithm 2 by varying
the value of $\alpha$. Note that when $\alpha(V)>\alpha$, Algorithm 2 may fail
to find a feasible solution. In that case, we resort to iteratively peeling a
node with the minimum degree from $S$ with the most dominant color, until we
obtain a feasible solution, or conclude that none exists. PS and FPS by
Anagnostopoulos et. al. (Anagnostopoulos et al., 2020) return by definition
completely-balanced subgraphs, thus corresponding to the solutions of Problem
1 for a value of $\alpha=1/|C|$.

Our results are depicted in Figure 2 for the two collections of datasets,
Amazon Product and Facebook100. As these two datasets consist of a number of
graphs, we present the average values with the standard deviations. We see
that Algorithm 2 outperforms the baselines. Let us first focus on the case of
$\alpha=1/|C|$. Algorithm 2 returns a better solution than that of PS and FPS
for the Amazon Product dataset, while PS and FPS are comparable to Algorithm 2
for the Facebook100 dataset. We observe similar trends for the single graph
datasets, as seen in Figure 3. More precisely, when $\alpha=1/|C|$, Algorithm
2 performs better than PS and FPS in $3$ out of $4$ cases. Moreover, we see
that by varying the parameter $\alpha$, we can adjust the trade-off between
getting a subgraph as dense as possible (when we let $\alpha$ approach the
diversity of the densest subgraph in the graph), or sacrifice density with the
aim of getting more diverse subgraphs (completely balanced when we set
$\alpha=1/|C|$).

Figure 2. Performance of algorithms for the Amazon Products and Facebook100
datasets.

Figure 3. Performance of algorithms for the single-graph datasets.

(Poor) performance of Embedding+Fair Clustering. Here we use a random sample
of $35$ graphs from the Facebook100 dataset due to the cost of producing
embeddings for each graph, as we did not notice significant changes after
including more datasets in terms of results. We also use only gender as our
attribute (as fair clustering methods allow only two colors), while we range
$k$ in $k$-means from 2 to 32 and report the best result. In Figure 4, we see
the results of this baseline in terms of the diversity of the clusters we get,
as well their density. We see that simply performing $k$-means on the embedded
graph results in clusters that are highly unbalanced. On the other hand, fair
$k$-means allows us to get fair clusters by design (Figure 4 (left)), but the
corresponding subgraph is not as dense as the output by Algorithm 2 (Figure 4
(right)). Notice that for the attribute we consider in this case, the ratio of
the two colors in the graph is only slightly different from that of the
densest subgraph (see the rightmost of Figure 1). Hence, Algorithm 2 finds
subgraphs almost as dense as the densest.

Running time of algorithms. In Figure 5 (left) we report the runtime of
algorithms on the Amazon Product dataset. We employed this dataset because the
sizes of the graphs (in terms of $n$ and $m$) vary substantially so that we
can easily see how the running time of algorithms grows. We see that all of
them scale (almost) linearly with the number of edges; in particular, the
result for Algorithm 2 is consistent with the theoretical analysis in Section
4.1. Note that for Algorithm 2, we report the runtime for the most difficult
case, when $\alpha=0.5$; hence the subgraphs need to be completely balanced.
As we relax the diversity constraint, the runtime drops significantly as
evident on the synthetic graphs, as shown in Figure 5 (right). The synthetic
graph we employed resembles the stochastic block model paradigm. We
constructed a graph with 5 clusters of 40,000 nodes each, with higher intra-
connectivity within clusters, than inter-connectivity across clusters. Most
importantly, one of the clusters has a much higher density than the rest.
Hence, the densest subgraph consists of 40,000 nodes. Initially, we assign
nodes to one of five colors uniformly at random. Hence, the (original) densest
subgraph is already diverse. Therefore, Algorithm 2 does not need to invoke
Procedure 1. Thus, relaxing the diversity constraint has no impact in this
case (blue dotted line). On the other hand, if we assign a unique color to
each cluster, then the densest subgraph becomes monochromatic and in order to
have a diverse representation we need to involve the whole graph to our
solution, resulting in a longer runtime that gets decreased as we relax the
diversity constraint (solid orange line). Finally we remark that on the
Facebook100 dataset Algorithm 2 runs in 3s for $\alpha=0.5$ and 11s for
$\alpha=0.25$ even on the aforementioned largest graph with more than one
million edges.

Figure 4. Diversity and normalized density of subgraphs obtained using
Embedding+Fair Clustering (together with its unfair variant), and Algorithm 2.

Figure 5. Left: Runtime as a function of the number of edges for all
algorithms. Right: Runtime of Algorithm 2 as a function of the diversity
parameter $\alpha$.

###  6.3. Evaluation of Algorithm 6 (for Problem 2)

We empirically study the accuracy and efficiency of Algorithm 6 to understand
its practical performance. We apply our algorithm and the baseline Prop2 on a
part of the Amazon Product dataset, consisting of the graphs with at most
1,000 nodes and 5,000 edges. For each color $c\in C$, we set the lower bound
as $k_{c}=|V_{c}|/2$. We also calculate the optimal solutions using IP and
report the empirical approximation ratios of Algorithm 6 and Prop2.

The results are shown in Figure 6. In Figure 6 (left) we observe that in most
graphs the solutions returned by Algorithm 6 are optimal or near-optimal, with
empirical approximation ratios consistently higher than $0.95$. This means
that our proposed algorithm is of high accuracy in practice, despite the
theoretical approximation guarantee being $1/3$. The baseline Prop2 returns
solutions with empirical approximation ratios greater than $0.8$ but the
performance is worse than that of ours. In Figure 6 (right) we show the
running times of all algorithms applied. As expected, Prop2 is the fastest as
it solves only one LP. Algorithm 6 can scale to graphs in two colors with
thousands of nodes, and it is faster than IP in general. Although from the
figure the scalability of Algorithm 6 looks not much better than that of IP,
we wish to remark that there are 7 graphs for which Algorithm 6 runs more than
10 times faster than IP. In the extreme example, where $n=30$ and $m=381$,
Algorithm 6 runs in 0.58s, while IP consumes 242.2s, meaning that Algorithm 6
runs more than 400 times faster than IP. We further discuss the scalability of
Algorithm 6 particularly with respect to $|C|$ in Appendix B.3.

Figure 6. Empirical approximation ratios and running times of Algorithm 6 and
baselines on the Amazon Product dataset with at most 1,000 nodes and 5,000
edges.

##  7\. Conclusions

In this work, we have focused on the problem of finding a densest diverse
subgraph. We proposed novel formulations and approximation algorithms for two
different notions of diversity. We performed various experiments on synthetic
and real-world datasets, verifying that the densest subgraphs tend to be
driven by homophily and that our tools provide the state-of-the-art methods.

Our work makes significant progress towards DSD with diversity and opens up
several interesting problems. Can we improve the
$\Omega(1/\sqrt{n})$-approximation for Problem 1 (in the case of $V$ being
diverse)? Can we design a better algorithm for Problem 2, in terms of both the
approximation ratio and the runtime? Investigating the hardness of
approximation is also an interesting direction.

## References

  * (1)
  * Adami et al. (2011) Christoph Adami, Jifeng Qian, Matthew Rupp, and Arend Hintze. 2011\.  Information content of colored motifs in complex networks.  _Artif. Life_ 17, 4 (2011), 375–390.
  * Ahmadian et al. (2020a) Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. 2020a.  Fair hierarchical clustering. In _NeurIPS ’20_. 21050–21060.
  * Ahmadian et al. (2020b) Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. 2020b.  Fair correlation clustering. In _AISTATS ’20_. 4195–4205.
  * Anagnostopoulos et al. (2020) Aris Anagnostopoulos, Luca Becchetti, Adriano Fazzone, Cristina Menghini, and Chris Schwiegelshohn. 2020\.  Spectral relaxations and fair densest subgraphs. In _CIKM ’20_. 35–44.
  * Andersen and Chellapilla (2009) Reid Andersen and Kumar Chellapilla. 2009.  Finding dense subgraphs with size bounds. In _WAW ’09_. 25–37.
  * Backurs et al. (2019) Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. 2019\.  Scalable fair clustering. In _ICML ’19_. 405–413.
  * Bahmani et al. (2012) Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012\.  Densest subgraph in streaming and MapReduce. In _VLDB ’12_. 454–465.
  * Bhaskara et al. (2010) Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. 2010\.  Detecting high log-densities: An ${O}(n^{1/4})$ approximation for densest $k$-subgraph. In _STOC ’10_. 201–210.
  * Boob et al. (2020) Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020.  Flowless: Extracting densest subgraphs without flow computations. In _TheWebConf ’20_. 573–583.
  * Chanpuriya et al. (2020) Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. 2020\.  Node embeddings and exact low-rank representations of complex networks. In _NeurIPS ’20_. 13185–13198.
  * Chanpuriya et al. (2021) Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. 2021\.  On the power of edge independent graph models. In _NeurIPS ’21_. 24418–24429.
  * Charikar (2000) Moses Charikar. 2000\.  Greedy approximation algorithms for finding dense components in a graph. In _APPROX ’00_. 84–95.
  * Chekuri et al. (2022) Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022\.  Densest subgraph: Supermodularity, iterative peeling, and flow. In _SODA ’22_. 1531–1555.
  * Chen et al. (2022) Tianyi Chen, Brian Matejek, Michael Mitzenmacher, and Charalampos E. Tsourakakis. 2022\.  Algorithmic tools for understanding the motif structure of networks. In _ECML PKDD ’22_. 3–19.
  * Chen and Tsourakakis (2022) Tianyi Chen and Charalampos Tsourakakis. 2022.  AntiBenford subgraphs: Unsupervised anomaly detection in financial networks. In _KDD ’22_. 2762–2770.
  * Chierichetti et al. (2017) Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. 2017.  Fair clustering through fairlets. In _NIPS ’17_. 5029–5037.
  * De et al. (2016) Abir De, Isabel Valera, Niloy Ganguly, Sourangshu Bhattacharya, and Manuel Gomez-Rodriguez. 2016\.  Learning and forecasting opinion dynamics in social networks. In _NIPS ’16_. 397–405.
  * Dourisboure et al. (2007) Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. 2007\.  Extraction and classification of dense communities in the web. In _WWW ’07_. 461–470.
  * Gajewar and Das Sarma (2012) Amita Gajewar and Atish Das Sarma. 2012.  Multi-skill collaborative teams based on densest subgraphs. In _SDM ’12_. 165–176.
  * Gallo et al. (1989) Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan. 1989\.  A fast parametric maximum flow algorithm and applications.  _SIAM J. Comput._ 18, 1 (1989), 30–55.
  * Gibson et al. (2005) David Gibson, Ravi Kumar, and Andrew Tomkins. 2005.  Discovering large dense subgraphs in massive graphs. In _VLDB ’05_. 721–732.
  * Gionis and Tsourakakis (2015) Aristides Gionis and Charalampos E. Tsourakakis. 2015\.  Dense subgraph discovery: KDD 2015 Tutorial. In _KDD ’15_. 2313–2314.
  * Goldberg (1984) Andrew V. Goldberg. 1984\.  _Finding a maximum density subgraph_.  University of California Berkeley.
  * Graber (2020) Julie Graber. 2020\.  Companies Hit With Lawsuits for Lack of Diversity at the Top.  https://www.linkedin.com/pulse/companies-hit-lawsuits-lack-diversity-top-julie-graber/.
  * Huangfu and Hall (2015) Qi Huangfu and Julian Hall. 2015.  Parallelizing the dual revised simplex method.  _Math. Program. Comput._ 10 (2015), 119–142.
  * Kawase et al. (2019) Yasushi Kawase, Yuko Kuroki, and Atsushi Miyauchi. 2019\.  Graph mining meets crowdsourcing: Extracting experts for answer aggregation. In _IJCAI ’19_. 1272–1279.
  * Kawase and Miyauchi (2018) Yasushi Kawase and Atsushi Miyauchi. 2018.  The densest subgraph problem with a convex/concave size function.  _Algorithmica_ 80, 12 (2018), 3461–3480.
  * Khuller and Saha (2009) Samir Khuller and Barna Saha. 2009.  On finding dense subgraphs. In _ICALP ’09_. 597–608.
  * Kortsarz and Nutov (2005) Guy Kortsarz and Zeev Nutov. 2005.  Approximating $k$-node connected subgraphs via critical graphs.  _SIAM J. Comput._ 35, 1 (2005), 247–257.
  * Kortsarz and Peleg (1994) Guy Kortsarz and David Peleg. 1994.  Generating sparse 2-spanners.  _J. Algorithms_ 17, 2 (1994), 222–236.
  * Kuroki et al. (2020) Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. 2020.  Online dense subgraph discovery via blurred-graph feedback. In _ICML ’20_. 5522–5532.
  * Lanciano et al. (2023) Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2023.  A survey on the densest subgraph problem and its variants.  _arXiv preprint arXiv:2303.14467_ (2023).
  * Li et al. (2020) Xiangfeng Li, Shenghua Liu, Zifeng Li, Xiaotian Han, Chuan Shi, Bryan Hooi, He Huang, and Xueqi Cheng. 2020\.  FlowScope: Spotting money laundering based on graphs. In _AAAI ’20_. 4731–4738.
  * Matejek et al. (2022) Brian Matejek, Donglai Wei, Tianyi Chen, Charalampos E. Tsourakakis, Michael Mitzenmacher, and Hanspeter Pfister. 2022.  Edge-colored directed subgraph enumeration on the connectome.  _Sci. Rep._ 12, 1 (2022), 11349.
  * Musco et al. (2018) Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. 2018\.  Minimizing polarization and disagreement in social networks. In _TheWebConf ’18_. 369–378.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In _EMNLP-IJCNLP ’19_. 188–197.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _KDD ’14_. 701–710.
  * Picard and Queyranne (1982) Jean-Claude Picard and Maurice Queyranne. 1982.  A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory.  _Networks_ 12, 2 (1982), 141–159.
  * Qiu et al. (2018) Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018\.  Network embedding as matrix factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In _WSDM ’18_. 459–467.
  * Rangapuram et al. (2013) Syama Sundar Rangapuram, Thomas Bühler, and Matthias Hein. 2013\.  Towards realistic team formation in social networks based on densest subgraphs. In _WWW ’13_. 1077–1088.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021.  Multi-scale attributed node embedding.  _J. Complex Netw._ 9, 2 (2021), 1–22.
  * Rozemberczki and Sarkar (2020) Benedek Rozemberczki and Rik Sarkar. 2020.  Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In _CIKM ’20_. 1325–1334.
  * Sozio and Gionis (2010) Mauro Sozio and Aristides Gionis. 2010.  The community-search problem and how to plan a successful cocktail party. In _KDD ’10_. 939–948.
  * Starnini et al. (2021) Michele Starnini, Charalampos E. Tsourakakis, Maryam Zamanipour, André Panisson, Walter Allasia, Marco Fornasiero, Laura Li Puma, Valeria Ricci, Silvia Ronchiadin, Angela Ugrinoska, Marco Varetto, and Dario Moncalvo. 2021.  Smurf-based anti-money laundering in time-evolving transaction networks. In _ECML PKDD ’21_.
  * Traud et al. (2012) Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. 2012\.  Social structure of Facebook networks.  _Physica A_ 391, 16 (2012), 4165–4180.
  * Tsourakakis (2015) Charalampos E. Tsourakakis. 2015\.  The k-clique densest subgraph problem. In _WWW ’15_. 1122–1132.
  * Tsourakakis et al. (2013) Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. 2013\.  Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In _KDD ’13_. 104–112.
  * Veldt et al. (2021) Nate Veldt, Austin R. Benson, and Jon Kleinberg. 2021\.  The generalized mean densest subgraph problem. In _KDD ’21_. 1604–1614.

##  Appendix A Proof of Lemma 2

First we consider the case where $y_{c}\geq 1$ for every $c\in C$. Let $a$ be
the maximum number that satisfies $C_{\mathrm{sat}}(S(a))=C$. Let $b$ be the
infimum of the numbers $b$ that satisfy $C_{\mathrm{sat}}(S(b))=\emptyset$.
Let $y^{*}_{\mathrm{max}}=\max_{v\in V}y^{*}_{v}$. Note that $0\leq a\leq
b\leq y^{*}_{\mathrm{max}}$ hold.

To prove the lemma, it suffices to show that (at least) one of the following
cases occurs:

Case (i):

There exists some $r^{\prime}\leq a$ such that
$d(S(r^{\prime}))\geq\frac{\lambda}{3}$;

Case (ii):

There exists some $a<r^{\prime}\leq b$ such that
$\displaystyle\frac{|E(S(r^{\prime}))|}{\sum_{c\in
C_{\mathrm{sat}}(S(r^{\prime}))}|S(r^{\prime})_{c}|+\sum_{c\in C\setminus
C_{\mathrm{sat}}(S(r^{\prime}))}k_{c}}\geq\lambda/3$;

Case (iii):

There exists some $r^{\prime}>b$ such that
$|E(S(r^{\prime}))|\geq\frac{|E(S^{*})|}{3}$.

To show that, suppose that none of the above cases occurs. We define indicator
functions $Z_{v}(r)\colon[0,y^{*}_{\mathrm{max}}]\rightarrow\\{0,1\\}$ for
$v\in V$ and $Z_{e}(r)\colon[0,y^{*}_{\mathrm{max}}]\rightarrow\\{0,1\\}$ for
$e=\\{u,v\\}\in E$ as follows:

$\displaystyle Z_{v}(r)=\begin{cases}1&\text{if }r\leq y^{*}_{v},\\\
0&\text{otherwise},\end{cases}\quad Z_{e}(r)=\begin{cases}1&\text{if
}r\leq\min\\{y^{*}_{u},y^{*}_{v}\\},\\\ 0&\text{otherwise}.\end{cases}$

Since Case (i) does not hold, for any $r^{\prime}\leq a$, we have
$d(S(r^{\prime}))=\frac{|E(S(r^{\prime}))|}{|S(r^{\prime})|}<\frac{\lambda}{3}$.
Thus, we have

$\displaystyle\int_{0}^{a}|E(S(r))|\,\mathrm{d}r$
$\displaystyle<\frac{\lambda}{3}\int_{0}^{a}|S(r)|\,\mathrm{d}r$
$\displaystyle=\frac{\lambda}{3}\int_{0}^{a}\sum_{v\in
V}Z_{v}(r)\,\mathrm{d}r=\frac{\lambda}{3}\sum_{v\in
V}\int_{0}^{a}Z_{v}(r)\,\mathrm{d}r.$

Since Case (ii) does not occur, for any $a<r^{\prime}\leq b$, we have
$|E(S(r^{\prime}))|<\frac{\lambda}{3}\left(\sum_{c\in
C_{\mathrm{sat}}(S(r^{\prime}))}|S(r^{\prime})_{c}|+\sum_{c\in C\setminus
C_{\mathrm{sat}}(S(r^{\prime}))}k_{c}\right)$. Hence, we have

$\displaystyle\int_{a}^{b}|E(S(r))|\,\mathrm{d}r<\frac{\lambda}{3}\int_{a}^{b}\left(\sum_{c\in
C_{\mathrm{sat}}(S(r))}|S(r)_{c}|+\sum_{c\in C\setminus
C_{\mathrm{sat}}(S(r))}k_{c}\right)\,\mathrm{d}r.$

Now we see that

$\displaystyle\int_{a}^{b}\sum_{c\in
C_{\mathrm{sat}}(S(r))}|S(r)_{c}|\,\mathrm{d}r\leq\int_{a}^{b}\sum_{c\in
C}|S(r)_{c}|\,\mathrm{d}r$ $\displaystyle=\int_{a}^{b}\sum_{c\in C}\sum_{v\in
V_{c}}Z_{v}(r)\,\mathrm{d}r=\sum_{c\in C}\sum_{v\in
V_{c}}\int_{a}^{b}Z_{v}(r)\,\mathrm{d}r$ $\displaystyle=\sum_{v\in
V}\int_{a}^{b}Z_{v}(r)\,\mathrm{d}r$

and

$\displaystyle\int_{a}^{b}\sum_{c\in C\setminus
C_{\mathrm{sat}}(S(r))}k_{c}\,\mathrm{d}r\leq\int_{a}^{b}\sum_{c\in
C}p^{*}_{c}\,\mathrm{d}r\leq\|\bm{p}^{*}\|_{1}\cdot y^{*}_{\mathrm{max}}\leq
1.$

Therefore, we have

$\displaystyle\int_{a}^{b}|E(S(r))|\,\mathrm{d}r<\frac{\lambda}{3}\left(\sum_{v\in
V}\int_{a}^{b}Z_{v}(r)\,\mathrm{d}r+1\right).$

Since Case (iii) does not hold, for any $r^{\prime}>b$, we have
$|E(S(r^{\prime}))|<\frac{|E(S^{*})|}{3}$. Thus, we have

$\displaystyle\int_{b}^{y^{*}_{\mathrm{max}}}|E(S(r))|\,\mathrm{d}r$
$\displaystyle<\frac{|E(S^{*})|}{3}\int_{b}^{y^{*}_{\mathrm{max}}}\,\mathrm{d}r$
$\displaystyle\leq\frac{|E(S^{*})|}{3}y^{*}_{\mathrm{max}}\leq\frac{1}{3}\frac{|E(S^{*})|}{\|\bm{p}^{*}\|_{1}}\leq\frac{\lambda}{3},$

where the last inequality follows from Lemma 1. Thus, we have

$\displaystyle\int_{0}^{y^{*}_{\mathrm{max}}}|E(S(r))|\,\mathrm{d}r$
$\displaystyle=\int_{0}^{a}|E(S(r))|\,\mathrm{d}r+\int_{a}^{b}|E(S(r))|\,\mathrm{d}r+\int_{b}^{y^{*}_{\mathrm{max}}}|E(S(r))|\,\mathrm{d}r$
$\displaystyle<\frac{\lambda}{3}\left(\sum_{v\in
V}\int_{0}^{a}Z_{v}(r)\,\mathrm{d}r+\left(\sum_{v\in
V}\int_{a}^{b}Z_{v}(r)\,\mathrm{d}r+1\right)+1\right)$
$\displaystyle\leq\frac{\lambda}{3}\left(\sum_{v\in
V}y^{*}_{v}+2\right)=\frac{\lambda}{3}\left(\sum_{c\in C}\sum_{v\in
V_{c}}y^{*}_{v}+2\right)=\lambda.$

On the other hand, by a simple calculation, we have

$\displaystyle\int_{0}^{y^{*}_{\mathrm{max}}}|E(S(r))|\,\mathrm{d}r=\int_{0}^{y^{*}_{\mathrm{max}}}\sum_{e\in
E}Z_{e}(r)\,\mathrm{d}r$ $\displaystyle=\sum_{e\in
E}\int_{0}^{y^{*}_{\mathrm{max}}}Z_{e}(r)\,\mathrm{d}r=\sum_{e\in
E}\min\\{y^{*}_{u},y^{*}_{v}\\}\geq\sum_{e\in E}x^{*}_{e}=\lambda,$

which contradicts to the above inequality.

Next we consider the case where $y_{c}=0$ for some $c\in C$. Defining $a$,
$b$, and $y^{*}_{\mathrm{max}}$ in the same way, we have $0\leq a\leq
y^{*}_{\mathrm{max}}<b=\infty$. It suffices to show that (at least) one of the
following cases occurs:

Case (i):

There exists some $r^{\prime}\leq a$ such that
$d(S(r^{\prime}))\geq\frac{\lambda}{3}$;

Case (ii):

There exists some $a<r^{\prime}\leq y^{*}_{\mathrm{max}}$ such that
$\displaystyle\frac{|E(S(r^{\prime}))|}{\sum_{c\in
C_{\mathrm{sat}}(S(r^{\prime}))}|S(r^{\prime})_{c}|+\sum_{c\in C\setminus
C_{\mathrm{sat}}(S(r^{\prime}))}k_{c}}\geq\lambda/3$.

The proof is similar to the above and thus omitted. ∎

##  Appendix B Supplementary Material for Experiments

###  B.1. DBLP Co-Authorship Dataset

We create this dataset from all authors that have published at least 3 papers
in the following conferences between 2003 and 2022:

  * •

Theory:  COLT, FOCS, ICALP, SODA, STOC

  * •

Data Management:  CIDR, ICDE, PODS, SIGMOD, VLDB

  * •

Data Mining:  CIKM, ICDM, KDD, WSDM, WWW

  * •

Learning:  AAAI, ICLR, ICML, NeurIPS

  * •

Networking:  ICC, IMC, INFOCOM, MOBICOM, SIGCOMM

  * •

Image & Video Processing:  CVPR, ECCV, ICCV

###  B.2. IP for Problem 2

Let us introduce a $0$–$1$ variable $x_{e}$ for each $e\in E$ and $0$–$1$
variable $y_{v}$ for each $v\in V$. Then for each
$k_{\text{guess}}\in\\{\|\bm{k}\|_{1},\dots,n\\}$, we construct the following
(mixed) integer linear programming problem:

maximize $\displaystyle\sum_{e\in E}x_{e}/k_{\text{guess}}$ subject to
$\displaystyle\sum_{v\in V}y_{v}=k_{\text{guess}},$ $\displaystyle\sum_{v\in
V_{c}}y_{v}\geq k_{c}$ $\displaystyle\forall c\in C,$ $\displaystyle x_{e}\leq
y_{u},\ x_{e}\leq y_{v}$ $\displaystyle\forall e=\\{u,v\\}\in E,$
$\displaystyle 0\leq x_{e}\leq 1$ $\displaystyle\forall e\in E,$
$\displaystyle y_{v}\in\\{0,1\\}$ $\displaystyle\forall v\in V.$

It is easy to see that this problem is equivalent to Problem 2 with size
constraint $|S|=k_{\text{guess}}$. Note that the $0$–$1$ constraints for
$x_{e}$’s are relaxed because they are redundant.

The baseline IP computes an optimal solution to Problem 2 as follows: Solve
the above integer programming problem for all
$k_{\text{guess}}\in\\{\|\bm{k}\|_{1},\dots,n\\}$ and return a solution with
the maximum density value.

###  B.3. Scalability of Algorithm 6 on Synthetic Data

We run Algorithm 6 on a set of Erdős-Rényi graphs with size $n$ ranged in
$\\{18,54,90,126\\}$, edge probability $p=5/n$, and the number of colors $|C|$
ranged in $\\{2,3,6\\}$. Nodes are evenly split into colors, and the lower
bound is set as $k_{c}=\left\lfloor\frac{n}{2|C|}\right\rfloor$ for each $c\in
C$. Random graphs are sampled ten times for each setting, and the averaged
running times are reported in Figure 7. When we have only two colors,
Algorithm 6 can scale up to a thousand nodes as shown in the main text.
However, the algorithm becomes rather inefficient as the graph size goes
beyond that or the number of colors increases.

Figure 7. Running time of Algorithm 6.


# Development of sieve of Eratosthenes and sieve of Sundaram’s proof

Ahmed Diab

###### Abstract

We make two algorithms that generate all prime numbers up to a given limit,
they are a development of sieve of Eratosthenes algorithm, we use two formulas
to achieve this development, where all the multiples of prime number 2 are
eliminated in the first formula, and all the multiples of prime numbers 2 and
3 are eliminated in the second formula.

Using the first algorithm we proof sieve of Sundaram’s algorithm, then we
improve it to be more efficient prime generating algorithm.

We will show the difference in performance between all the algorithms we will
make and sieve of Eratosthenes algorithm in terms of run time.

†† e-mail<EMAIL_ADDRESS>†† _Mathematics Subject
Classification (2020):_ 11N35

##  1 Introduction

Sieve of Eratosthenes algorithm (SOE) is a well known algorithm that generates
all prime numbers up to a given limit $N$, it contains some rules that control
the elimination process of the multiples of prime numbers see [3, 4, 5, 6, 7],
two of these rules are

  1. 1.

$N_{f}=R^{2}$ (1.1)

Where $N_{f}$ is the first uncommon multiple of prime number $R$ with prime
numbers smaller than $R$, which will be the first multiple to be eliminated.

  2. 2.

$R_{l}=\left\lfloor\sqrt{N}\right\rfloor$ (1.2)

Where $R_{l}$ is the last prime number whose multiples will be eliminated.

Using equations (3.2) and (3.4) in reference [2] and SOE algorithm we will
develop two algorithms that generate all prime numbers up to a given limit
$N$.

We use the advantage of equation (3.2) in reference [2] which is

$2n+1=p$ (1.3)

Where all multiples of 2 are eliminated, so we will set our rules to eliminate
the orders of the multiples of prime numbers greater that 2 from $n$, then the
remaining values of $n$ will be entered to equation (1.3) to get its
corresponding prime numbers.

We will use the first produced algorithm as a proof to Sieve of Sundaram’s
algorithm [1] ,then we will develop it using the property of the exact match
of the mathematical concepts between these two algorithms.

Then we will use equation (3.4) in reference [2] to make the second
development to SOE algorithm, this is the formula

$2\left\lfloor\frac{3n_{1}+1}{2}\right\rfloor+1=p$ (1.4)

Where all multiples of 2 and 3 are eliminated, we will set some rules to
eliminate the orders of the multiples of prime numbers greater than 3 from
$n_{1}$ .

##  2 First development of SOE (D1SOE)

In this developed algorithm we eliminate the corresponding $n$ of the
multiples of prime numbers greater than 2 from $n$ \- in equation (1.3) - up
to a certain limit $n_{m}$, where

$n_{m}=\left\lfloor\frac{N-1}{2}\right\rfloor$ (2.1)

We take the floor to the right hand-side of equation (2.1) because we are
interested in the integer value of $n_{m}$.

To obtain the order of the first uncommon multiple of a prime number with
prime numbers smaller we substitute by ($N_{f}=2m+1$) and ($R=2z+1$) in
equation (1.1)

$2m+1=(2z+1)^{2}$

$2m+1=4z^{2}+4z+1$

$m=2(z^{2}+z)$ (2.2)

$m$: Is the order of the first multiple we will eliminate.

$z$: Is the order of the prime number whose multiples we want to eliminate.

In this case the multiples of prime numbers are equidistant numbers,
consequently their orders too see [2], in order to eliminate the multiples of
prime numbers we need to know the difference between the orders of any two
successive multiples, we can get the multiples of any number by multiplying
this number by the integer numbers, but in this case we will multiply it by
the odd numbers because the multiples of 2 are already eliminated, so for $p$
prime number, the multiples of $p$ are $((1*p),(3*p),(5*p),(7*p),...)$.

using first two successive multiples which are $(1p)$ and $(3p)$ then
substituting by each one in the inverse of equation (1.3) then subtracting the
corresponding $n$ of $(1p)$ from the corresponding $n$ of $(3p)$ we obtain

$\frac{3p-1}{2}-\frac{p-1}{2}=d$

$\therefore p=d$ (2.3)

$d$: The difference between the orders of any two successive multiples of a
prime number $p$.

We will eliminate all the numbers starting from $m$ with $d$ steps to $n_{m}$
which are the orders of the multiples of prime number $p$.

The order of the last prime number its multiples should be eliminated will be
derived from equation (1.2) -without the floor- by substituting by

  * •

$R_{l}=2k+1$

  * •

$N=2q+1$

equation (1.2) will be

$k=\frac{\sqrt{2q+1}}{2}-\frac{1}{2}$ (2.4)

We will take the floor to the right hand-side of equation (2.4) because we are
interested in the integer value of $k$

$k=\left\lfloor\frac{\sqrt{2q+1}}{2}-\frac{1}{2}\right\rfloor$ (2.5)

$k$: The order of the number whose first prime number smaller than it is the
last prime number whose multiples we want to eliminate.

$q$: The order of the limit which we want to generate all prime numbers up to.

After eliminating all the orders of prime numbers starting from 3 to the first
prime number smaller than $k$ from $n$ we substitute by the remaining values
of $n$ in equation (1.3) to obtain all prime numbers in the interval
$\left[3,N\right]$.

Following a c++ code representation for D1SOE algorithm.

    #include <iostream>
    #include <cstdlib>
    #include<cmath>
    using namespace std;
    int D1SOE(int n_m) {
    Ψint n = 0, m = 0, ArrayLim = 0;
    Ψcout << "\n2 ";
    Ψ// adding 1 to n_m because the array starts from order 0
    ΨArrayLim = n_m + 1;
    Ψbool* array = new bool[ArrayLim];
    Ψ// Initializing the array with false values
    Ψfor (int i = 0; i < ArrayLim; i++)
    ΨΨarray[i] = false;
    Ψ// The mean elimination theorem
    Ψfor (n = 1; n <= int((sqrt(((2 * n_m) + 1) / 4.0)) - 0.5); n++)
    Ψ{if (array[n] != 0)
    ΨΨΨcontinue;
    ΨΨfor (m = (2 * ((n * n) + n)); m <= n_m; m += ((2 * n) + 1))
    ΨΨ{array[m] = true;}}
    Ψ// Printing for loop
    Ψfor (int n = 1; n < ArrayLim; n++)
    ΨΨif (!array[n])
    ΨΨΨcout << (2 * n) + 1 << " ";
    Ψreturn 0;}
    // Driver program to test above
    int main() {
    Ψint n_m, N = 0;
    Ψcout << "\n Enter limit : ";
    Ψcin >> N;
    Ψn_m = ((N - 1) / 2);
    ΨD1SOE(n_m);
    Ψreturn 0;}

##  3 Proof and development of sieve of Sundaram (DSOS)

let $i,j\in\mathbb{N},\ 1\leq i\leq j$

$i+j+2ij=y$ (3.1)

Sieve of Sundaram’s algorithm [1] eliminates all the values of $y$ from the
integer numbers up to a limit $l$ where $y\leq l$.

We can write equation (3.1) as follows

$i+(2i+1)j=y$ (3.2)

Let

$u=2i+1$ (3.3)

Condition $i\leq j$ will control the starting point of $y$, which is the value
of $y$ when $i=j$.

substituting by $i=j$ in equation (3.2)

$i+(2i+1)i=y$

$2(i^{2}+i)=y$ (3.4)

Equation (3.4) is the same as equation (2.2) which also determines the
starting point of the elimination process.

The end point of the elimination process is $y\leq l$ where $l$ by the
definition of sieve of Sundaram is the integer value of

$l=\frac{N-1}{2}$

which could be written as

$l=\left\lfloor\frac{N-1}{2}\right\rfloor$ (3.5)

$N$: Is the limit which we want to generate all the prime numbers up to.

Equation (3.5) is the same as equation (2.1) which determines the end point of
the elimination process, this condition will control the last value of $j$.
Starting from ($2(i^{2}+i)$) to $l$ with $u$ steps represented by the term
($u*j$) in equation (3.2) this algorithm is nearly the same as D1SOE
algorithm.
Substitutes by the remaining integer values in an equation the same as
equation (1.3) prime numbers are obtained.

The differences between D1SOE algorithm and Sundaram’s algorithm is

  1. 1.

In equation (3.1) $i$ takes all integer values from 1 to $l$, in D1SOE it
takes only the values of the orders of prime numbers.

  2. 2.

In Sundaram’s algorithm the limit of $i$ is defined by equation (3.5), where
D1SOE uses equation (2.5).

Using equation (2.5) this is the limit of $i$ should be used

$k^{\prime}=\left\lfloor\frac{\sqrt{2q^{\prime}+1}}{2}-1\right\rfloor$ (3.6)

where
$k^{\prime}$: Is the order of -the corresponding $n$ of- the limit of $i$.

$q^{\prime}$: Is the order of -the corresponding $n$ of- $N$.

Changing these conditions in Sundaram’s algorithm it will be exactly the same
as D1SOE algorithm.

Following a c++ code representation for DSOS algorithm.

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    int DSOS(int n)
    {   int i = 0, ArrayLim = 0, j = 0, n_m = 0;
        n_m = (n - 1) / 2;
           cout << 2 << " ";
        // adding 1 to n_m because the array starts from order 0
        ArrayLim = n_m + 1;
        bool* array = new bool[ArrayLim];
        // Initializing the array with false values
        for (i = 0; i < ArrayLim; i++)
            array[i] = false;
        // The mean elimination theorem
        for (i = 1; i<=int((sqrt(((2 * n_m) + 1) / 4.0)) - 0.5); i++)
        {   if (array[i] != 0)
                continue;
            for (j = i; (i + j + 2 * i * j) <= n_m; j++)
                array[i + j + 2 * i * j] = true; }
          // Printing for loop
          for (i = 1; i <= n_m; i++)
            if (array[i] == false)
                cout << 2 * i + 1 << " ";
        return 0;}
    // Driver program to test above
    int main(void)
    {   int n = 0;
        cout << "\n Enter limit : ";
        cin >> n;
        DSOS(n);
        return 0;}

##  4 Second development of SOE algorithm (D2SOE)

In this algorithm we eliminate the orders of the multiples of prime numbers
greater than 2 and 3 from $n_{1}$ in equation (1.4).

Using ISEF from reference [2] the inverse of equation (1.4) will be

$n_{1}=\left\lceil\frac{((\frac{p-1}{2})*2)-1}{3}\right\rceil$

$n_{1}=\left\lceil\frac{p-2}{3}\right\rceil$ (4.1)

The limit of $n_{1}$ is

$n_{1m}=\left\lceil\frac{N-2}{3}\right\rceil$ (4.2)

$N$: The limit which we want to generate all the prime numbers up to.
$n_{1m}$: The order of $N$.

The order of the first multiple we want to eliminate will be calculated by
substituting by

  * •

$\left\lfloor\frac{3g+1}{2}\right\rfloor=m$

  * •

$\left\lfloor\frac{3b+1}{2}\right\rfloor=z$

in equation (2.2)

$\left\lfloor\frac{3g+1}{2}\right\rfloor=2(\left\lfloor\frac{3b+1}{2}\right\rfloor^{2}+\left\lfloor\frac{3b+1}{2}\right\rfloor)$

Using ISEF from reference [2]

$g=\left\lceil\frac{4(\left\lfloor\frac{3b+1}{2}\right\rfloor^{2}+\left\lfloor\frac{3b+1}{2}\right\rfloor)-1}{3}\right\rceil$
(4.3)

$g$: The order of the first multiple will be eliminated.
$b$: The order of the prime number whose multiples we want to eliminate.

The multiples of the prime numbers in equation (1.4) are divided into two
sequences see [2], and $g$ can equal any number from these two sequences.

The multiples of a prime number $p$ in equation (1.4) are ($p$, $5p$, $7p$,
$11p$,…) which are the integer numbers without the multiples of 2 and 3
multiplied by prime number $p$. The first sequence is ($p$, $7p$, $13p$, …),
and the second sequence is ($5p$, $11p$, $17p$, …).

We need to know the following information to be able to eliminate the
multiples of the prime numbers in this case

  1. 1.

The difference between the orders of any two successive multiples in any
sequence of these two sequences, let it be $f_{1}$.

$f_{1}=\left\lceil\frac{7p-2}{3}\right\rceil-\left\lceil\frac{p-2}{3}\right\rceil$
(4.4)

Using computer programming the following relation is true for $p$ equals the
integers from 1 to $10^{10}$

$2p=\left\lceil\frac{7p-2}{3}\right\rceil-\left\lceil\frac{p-2}{3}\right\rceil$
(4.5)

We assume that this relation is true for $p$ equals all integers upto
infinity.

  2. 2.

The difference between the orders of the first (or the second or the third,
…etc) numbers in both sequence, let it be $f_{2}$.

$f_{2}=\left\lceil\frac{5p-2}{3}\right\rceil-\left\lceil\frac{p-2}{3}\right\rceil$
(4.6)

  3. 3.

The difference between the order of the first number in the second sequence
and the order of the second number in the first sequence, let it be $f_{3}$.

$f_{3}=\left\lceil\frac{7p-2}{3}\right\rceil-\left\lceil\frac{5p-2}{3}\right\rceil$
(4.7)

  4. 4.

Whether $g$ belongs to the first or the second sequence, the second sequence
could be represented by $(3x-1)$ where $x$ is an integer, so by adding 1 to
$g$ and then dividing it by 3 we can know that it belongs to the second
sequence if the result is an integer, if the result is not an integer then it
belongs to the first sequence, while the first sequence could be represented
by $(3x+1)$.

After calculating $g$ we will determine whether $g$ belongs to the first or
the second sequence, Then we will eliminate this sequence by adding $f_{1}$ to
$g$ then we will eliminate the result then we will repeat adding $f_{1}$ to
the last result and eliminate the resultant number, our limit will be
$n_{1m}$.

After eliminating the sequence which $g$ belongs to we will eliminate the
other sequence by the same method but starting from ($g+f_{3}$) if $g$ belongs
to the second sequence, and from (($g+f_{2}$) or ($g-f_{3}$)) if $g$ belongs
to the first sequence.

The order of the last prime number its multiples should be eliminated will be
derived from equation (2.4) by substituting by

  * •

$\left\lfloor\frac{3h+1}{2}\right\rfloor=k$

  * •

$\left\lfloor\frac{3e+1}{2}\right\rfloor=q$

Equation (2.4) will be

$\left\lfloor\frac{3h+1}{2}\right\rfloor=\frac{\sqrt{2\left\lfloor\frac{3e+1}{2}\right\rfloor+1}}{2}-\frac{1}{2}$
(4.8)

using ISEF

$h=\left\lceil\frac{\sqrt{2\left\lfloor\frac{3e+1}{2}\right\rfloor+1}-2}{3}\right\rceil$
(4.9)

where
$h$: The order -corresponding $n_{1}$\- of the number whose first prime number
smaller than it is the last prime number whose multiples we want to eliminate.
$e$: The order -corresponding $n_{1}$\- of the limit which we want to generate
all prime numbers up to.

After eliminating the orders of the multiples of prime numbers from $n_{1}$ we
will substitute by the remaining $n_{1}$ in equation (1.4) to obtain prime
numbers.

Following a c++ code representation for D2SOE algorithm.

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    int D2SOE(int n1_m) {
    Ψint n1 = 0, g = 0, z = 0, p = 0,f1=0,f3=0;
    Ψcout << "\n2 3 ";
    Ψbool* array = new bool[n1_m];
    Ψ// Initialising the D2SOE array with false values
    Ψfor (int i = 0; i < n1_m; i++)
    ΨΨarray[i] = false;
    Ψ// The mean elimination theorem
    Ψfor (n1=1;n1<=ceil((sqrt(2*floor((3*n1_m+1)/2.0)+1)-2)/3.0);n1++)
    Ψ{ if (array[n1] != 0)
    ΨΨΨcontinue;
    ΨΨz = ((3 * n1 + 1) / 2.0);
    ΨΨp = ((2 * z) + 1);
    ΨΨf1 = (ceil(((7*p)-2) / 3.0) - ceil((p - 2) / 3.0));
    ΨΨf3 = (ceil(((7*p)-2) / 3.0) - ceil(((5 * p) - 2) / 3.0));
    ΨΨfor (g = ceil(((4*((z*z) + z)) - 1) / 3.0); g < n1_m;g+=f1)
    ΨΨ{ array[g] = true; }
    ΨΨif ((p +1) % 3 == 0) {
    ΨΨΨfor (g = ceil(((4*((z*z) + z)) - 1) / 3.0) + f3; g < n1_m;g+=f1)
    ΨΨΨ{ array[g] = true; } }
    ΨΨelse {
    ΨΨΨfor (g = ceil(((4*((z*z) + z)) - 1) / 3.0) - f3; g<n1_m;g+=f1)
    ΨΨΨ{ array[g] = true; }}}
    Ψ// printing for loop
    Ψ for (int n1 = 1; n1 < n1_m; n1++)
    ΨΨif (!array[n1]) {
    ΨΨΨz = (((3 * n1) + 1) / 2.0);
    ΨΨΨcout << (2 * z) + 1 << " "; }
    Ψreturn 0; }
    // driver program to test above
    int main() {
    Ψint n1_m, N = 0;
    Ψcout << "\n Enter limit : ";
    Ψcin >> N;
    Ψn1_m = ceil((N - 2) / 3.0);
    ΨD2SOE(n1_m);
    Ψreturn 0; }

##  5 Implementation results

To know in general the speed difference between these algorithms we use the
same coding concept for all algorithms and the same device under the same
circumstances, the results are listed in the next table, where this table
shows the run time in microseconds for each algorithm required to generate all
the prime numbers from 1 to the limit $N$.

$N$ | SOE | D1SOE | D2SOE | DSOS
---|---|---|---|---
$10^{3}$ | 10 | 10 | 10 | 9
$10^{4}$ | 92 | 53 | 32 | 54
$10^{5}$ | 978 | 472 | 263 | 450
$10^{6}$ | 12793 | 6021 | 3492 | 5812
$10^{7}$ | 190523 | 88483 | 53848 | 86673
$10^{8}$ | 2160761 | 1045056 | 741409 | 1038911
$10^{9}$ | 24837596 | 12143628 | 8471540 | 12008482
$2*10^{9}$ | ….. | 25136075 | 17953830 | 25208467

D2SOE is the fastest algorithm then D1SOE then DSOS with almost the same speed
as D1SOE, then the last and the slowest one is SOE algorithm.

##  6 conclusion

Using sieve of Eratosthenes algorithm and two of my prime numbers formulas we
was able to make two developments to sieve of Eratosthenes algorithm, the
first one we used a formula where all the multiples of 2 are eliminated and we
derived all the required formulas to accomplish the elimination of the
multiples of the prime numbers, and the generation of all the prime numbers up
to a gives limit see 2, and we used this algorithm to proof sieve of
Sundaram’s algorithm by showing the exact match between these two algorithms,
then we used this match to improve sieve of Sundaram see section 3.

In the second algorithm we used a formula where all the multiples of the prime
numbers 2 and 3 are eliminated, and derived the required formulas for the
elimination process see section 4.

Finally we showed the run time differences between our developed algorithms
and sieve of Eratosthenes algorithm see section 5.

## References

  * [1] V Ramaswami Aiyar.  Sundaram’s sieve for prime numbers.  The Mathematics Student, 2(2):73, 1934.
  * [2] Ahmed Diab.  Sequence elimination function and the formulas of prime numbers.  Far East Journal of Mathematical Education, 21:7–21, 2021.
  * [3] ROY DUBISCH.  The sieve of eratosthenes.  The Arithmetic Teacher, 18(4):236–237, 1971.
  * [4] R. A. Fisher.  The sieve of eratosthenes.  The Mathematical Gazette, 14(204):564–566, 1929.
  * [5] Samuel Horsley.  Ko$\sigma$ kinon epato$\sigma$ $\theta$ enoy $\sigma$. or, the sieve of eratosthenes. being an account of his method of finding all the prime numbers, by the rev. samuel horsley, frs.  Philosophical Transactions (1683-1775), 62:327–347, 1772.
  * [6] Melissa e O’neill.  The genuine sieve of eratosthenes.  Journal of Functional Programming, 19(1):95, 2009.
  * [7] Jonathan Sorenson.  An introduction to prime number sieves.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1990.


# Number of unique Edge-magic total labelings on Path $P_{n}$

Mukkai S. Krishnamoorthy
Rensselaer Polytechnic Institute, Troy, NY
Allen Lavoie
Washington University, St. Louis, MO
Ali Dasdan,
Hypergrowth, San Fransico Bay Area, CA
Bharath Santosh
Rennselaer Polytechnic Institute, Troy, NY

###### Abstract

Edge-magic total labeling was introduced by [2]. The number of edge-magic
solutions for cycles have been explored in [1]. This sequence is mentioned in
On Line Encyclopedia of Integer Sequences (OEIS) [3]. In this short note, we
enumerate the number of unique edge-magic total labelings on Path $P_{n}$

##  1 Introduction

Edge-magic labeling (EMTL) has been studied in the past with an application
towards communication networks. Given a simple undirected graph $G=(V,E)$, let
$\lambda$ be a mapping from the numbers $1,2,\cdots,|V|+|E|$ to the vertices
and edges of graph G, such that each element has an unique label. The weight
of an edge is obtained as the sum of the labels of that edge and its two end
vertices. An edge-magic total labeling is labeling in which the weight of
every edge is the same. The weight of the each edge is said to be a magic
constant. Figure 1 illustrates an example for a path of length 5 with a magic
constant of 16.

Figure 1: Path of length 5

Paper by Wallis et al [4] describes existence of edge-magic total labeling of
many types of graphs including $P_{n}$. The aim of this note is to enumerate
unique edge-magic total labeling of Path $P_{n}$.

##  2 Main Results

Our results are summarized in the following Table.

Path Length | Number of Solutions
---|---
0 | 1
1 | 3
2 | 12
3 | 28
4 | 48
5 | 240
6 | 944
7 | 5344
8 | 23408
9 | 133808
10 | 751008
11 | 5222768
12 | 37898776
13 | 292271304
Table 1: Number of Edge-Magic Total Labels.

As far as we have seen this series 1,3,12,28,48,240,944,5344,23408 does not
appear in OEIS.

###  2.1 Method and Program

We started with a simple python program to obtain all edge-magic solutions of
paths of lengths 2 to 17. Paths of length 2 means that there will be three
vertices and 2 edges, a total of 5 graph elements.

    import itertools
    for j in range(5,27,2):
        x = range(1,j+1)
        sum2 = 0
        for a in itertools.permutations(x):
            x = list(a)
            sum1 = x[0]+x[1]+x[2]
            d = 1
            for i in range(2,j-2,2):
                if (sum1== x[i]+x[i+1]+x[i+2]):
                    d = 1
                else:
                    d = 0
                    break
            if (d==1):
                if (a[0]<a[j-1]):
                    #print x, sum1
                    sum2 = sum2+1
        print j, "\t", sum2

This program generated one permutation at a time, and checked for whether the
assignment leads to an edge-magic labeling.

However it is too slow and we could not compute past the path length of 7. We
further optimized our python code and utilized the bounds on magic sum, $k$,
similar to the one used in the paper[1]. Let $f(r)=\frac{r\times(r+1)}{2}$

$\frac{f(2\times n+1)+f(n-1)}{n}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
k\leavevmode\nobreak\ \leq\frac{2\times f(2\times n+1)-f(n+2)}{n}$

With this improvement and a shortcircuit optimization, we are able to get up
to a path length of 13. All our code is located in the following github
location https://github.com/allenlavoie/path-counting .

We will like to point the total number of edge-magic solutions for paths form
a strict (albeit weak) upper bound for total number of edge-magic solutions
for cycles of the same length.

## References

  * [1] A. Baker and J. Sawada, ”Magic Labelings on Cycles and Wheels,” Lecture Notes in Computer Science 5165 Combinatorial Optimization and Applications. Second International Conference, COCOA 2008. pp. 361-373
  * [2] R. D.Godbold and P.J.. Slater, ”All cycles are edge-magic,” Bulletin of the ICA vol. 22 (1998) pp. 93-97.
  * [3] _On Line Encyclopedia of Integer Sequences, Seq A 145692_ http://oeis.org/A145692
  * [4] W. D. Wallis et. al, ”Edge-magic total labelings,” Australasian Journal of Combinatorics vol. 22, 2000. pp.177-190