# The Wedge Picking Model: A dynamic graph model based on triadic
closure111This manuscript is a full presentation of what has appeared as
“Densest subgraph discovery in evolving graphs” in the sets and partitions
workshop, NeurIPS 2019 & “A theoretical analysis of graph evolution caused by
triadic closure and algorithmic implications” in IEEE BigData 2020.

Sara Ahmadian, Shahrzad Haddadan222Both authors contributed equally to this
paper

###### Abstract

Social networks have become an inseparable part of human life and processing
them in an efficient manner is a top priority in the study of networks. These
networks are highly dynamic and they are growing incessantly. Inspired by the
concept of _triadic closure_ , we propose a probabilistic mechanism to model
the evolution of these dynamic graphs. Although triadic closure is ubiquitous
in social networks and its presence helps forming communities, probabilistic
models encapsulating it have not been studied adequately.

We theoretically analyze our model and show how to bound the growth rate of
some characteristics of the graph, such as degree of vertices. Leveraging our
theoretical results, we develop a scheduling subroutine to process
modifications of the graph in batches. Our scheduling subroutine is then used
to speed up the state-of-the-art algorithms with negligible loss in their
approximation guarantees. We demonstrate the applicability of our method by
applying it to the densest subgraph and tri-densest subgraph discovery
problem.

##  1 Introduction

Structural properties of social network distinguish them from other graphs.
These properties include bounded degeneracy, heavy tailed degree distribution,
high density of triangles. Various generative models have been suggested in
the literature to study or explain these properties. The most celebrated of
these generative models are the preferential attachment model [4], the copying
model [26], or Chung-Lu random graph model [12]. Each of these models explain
some property of social networks but not all of them; see [10] for a
comparative survey. Among all of these models, only a few have encapsulated an
important property of social networks: _triadic closure_ [34, 9, 8].

Put simply, triadic closure is the tendency of a disconnected pair of users
with a large common neighborhood to form connection. German sociologist George
Simmel coined the term in 1908, suggesting that if there is a strong
connection between A and B and there is a strong connection between A and C,
then there must exist a strong or weak connection between B and C.

Triadic closure is a prominent ingredient for formation of modularity in
networks [31] and it has been shown that most of generative models such as
Barabási-Albert model do not generate modularity without additionally
enforcing triadic closure [8]. Thus, deep mathematical understanding of models
explaining triadic closure is crucial. Nonetheless, the generative models
based on triadic closure have not been theoretically analyzed, and little
information about their growth rate or other properties is known.

Among theoretical computer scientists, a new trend of studying social networks
known as “distribution free models” has recently emerged [36]. Such studies
leverage on specific properties of social networks to design tractable
algorithms for expensive and in particular NP-hard problems. In this context
the “c-closure” property was introduced by Fox et al [15], and it sparked
notable research [25, 22, 24]. A c-closed graph is a graph in which any two
vertices $v$ and $u$ having a common neighborhood larger than $c$ are
connected. Problems such as listing all maximal cliques, or computing dense or
sparse subgraphs, which are NP-hard in general are tractable for c-closed
graphs [15, 23]. Distribution free models and in particular c-closure have an
important limitation: they fall short in modeling dynamic graphs which are
more realistic in the context of social networks.

Inspired by Fox et al and subsequent work on c-closed graphs, our goal in this
paper is to introduce a probabilistic dynamic model based on triadic closure,
and analyze it theoretically with the goal of designing algorithms.

In particular, we seek answer to the following questions:

  1. 1.

How does triadic closure explain the evolution of dynamic graphs?

  2. 2.

Can we theoretically analyze the effect of triadic closure on the growth rate
of degree of vertices of a dynamic graph?

  3. 3.

Can we use such bounds to design better algorithms for dynamic graphs (or to
maintain previously calculated solutions)?

We provide answers to the above question by (1) introducing the _wedge picking
model_ , a probabilistic model for dynamic graphs based on triadic closure (2)
presenting a theoretical analysis of the wedge picking model and in particular
the growth rate of its local properties such as the degree of each vertex (3)
after verifying that the wedge picking model explains the evolution of an
input dynamic graph and estimating the parameters of the model in a pre-
processing phase, we use the above theoretical results to design a speed up
subroutine which we call the _rest and run_ strategy. We employ our proposed
method to an important primitive of graph mining: densest subgraph discovery.

The rest and run strategy works as an scheduling subroutine determining
periods of “rest” and “run” for some optimization problems, thus improving
their run time. The idea is to identify pre-calculated intervals for “resting”
while theoretically ensuring that with high probability the quality of
solution will not degrade by much. After the “rest” phase, we read a batch of
updates and start the “run” phase in which we run the original algorithm.

### Related Work

Study of probabilistic models for networks goes back to 1959 when pioneers of
graph algorithms, Erdös and Rényi, introduced their model. Since Erdös–Rényi
model does not explain most of the properties of real networks, other models
like Watts–Strogatz model [43] have been introduced. The Watts–Strogatz model
captures the “six degree of seperation” in real network: despite having low
average degree, most of vertices are reachable from each other via at most six
hops. Their model also captures the existence of communities.

Real world networks have been analyzed vastly with the motivation to identify
properties distinguishing them from regular random networks. Such analysis can
help design of generative models. For instance, Ugander et al. [41] analyzed
social graph of active Facebook users, and reported properties such as: degree
distribution, path length, component size, clustering coefficient, degeneracy,
degree correlation, etc. Various models have been proposed for explaining
different properties of such networks (see, e.g., [10]). Only to explain
degree distribution various models have been suggested which are all based on
the “rich gets richer” phenomenon: Barabási-Albert [44] suggests the
preferential attachment model which generates graphs with power law degree
distribution. Pennock et al. [33] introduced graphs with a similar degree
distribution: the Discrete Gaussian Exponential distribution. Amaral et al [5]
observed exponential cut offs in electric power-grid graph. Among all of these
models, Barabási-Albert model has been used widely and up to today
particularly in the context of social networks. In this model a new vertex
joins the network and it gets connected to each vertex $u$ with probability
proportional to degree of $u$.

Bianconi et al. [8] observed that Barabási-Albert graphs do not contain
modular components like real networks do. They suggested two models to
incorporate triadic closure and thus to create modularity. In the first
(simpler) model, a vertex $u$ joins the network and it gets connected to a
random vertex in the graph. For each of the next edges the end point is chosen
through two rules: w.p. $p$ it is added to a randomly chosen vertex, and w.p.
$1-p$ it is added to a randomly chosen vertex from neighbors of its neighbors.
In the second model, they introduce a _fitness_ factor for vertices. The
probability of choosing end points for new edges will be proportional to the
fitness factor. Bianconi et al’s model generalizes Barabási-Albert’s as
setting $p=0$ and choosing fitness factor equal to degree makes the two models
equivalent.

A similar line of research uses triadic closure for link prediction: Huang et
al [21, 20] study formation of closed triads. Further they examine affects of
formation of the third tie in a triad on the strength of the existing two ties
[19]. They incorporate demographics and network topology for such predictions.
Estrada et al [2] use communicability distance functions to predict triadic
closure. Romero and Kleinberg [35] analyze a _link copying_ regime which is
similar to triadic closure. Despite a long list of similar work [42, 27, 32,
29], none of them presents a theoretical analysis of triadic closure based
solely on graph topology, its affect on rate of degree growth and its possible
algorithmic implications.

We finish this introduction by highlighting our paper’s contribution together
with a road map to read the paper.

### Our Contribution.

  1. 1.

In Section 2, we introduce the wedge picking model which is a probabilistic
generalization of c-closure, tailored to dynamic graphs. We estimate the
parameters of our model in a pre-processing phase. By doing so we are also
able to assert whether the evolution of input graph fits into the wedge
picking model.

  2. 2.

In section 3, we analyze the wedge picking model and bound degree growth (as
well as tri-degree defined as the number of triangles on a vertex) for each
vertex in the network.

  3. 3.

In Section 4, we present our algorithmic contribution which is the
introduction of the rest and run strategy. This strategy can be employed as a
scheduling subroutine to boost the efficiency of other algorithms with
negligible effect on their accuracy.

In Subsection 4.1, we show how to apply the rest and run strategy for
approximating the densest subgraph (and tri-densest subgraph in the appendix).
In particular, we incorporate the rest and run strategy in the algorithm of
[13], and we show the approximation ratio of $4(1+\epsilon)$ for the modified
algorithm.

  4. 4.

In Section 5, we complement our theoretical results by presenting experimental
analysis. Our experimental analysis is twofold: (1) We compare the quality and
the run time of our algorithms in comparison to previous work. We observe that
the rest and run strategy can effectively improve the speed by a factor of
1000 on large data sets while not degrading the quality of the solution. (2)
We run our algorithms on two types of data sets: (a) real-world social graphs
whose evolution is generated by our model, and (b) dynamic real world graphs
of “Facebook wall posts” and “YouTube users” (see Table 2). We compare the run
time and accuracy of algorithms for synthetic and organic evolution and
observe similar results. Thus, we demonstrate the applicability of our model
on real world social graphs.

##  2 The model

In this section, we introduce our model. Let $G_{t}=\langle V,E_{t}\rangle$ be
an undirected dynamic graph with a fixed vertex set $V$ and evolving edge set
$E_{t}$ at time $t$.333For simplicity we assume that $G_{t}$ is undirected but
our results can easily be modified to work for directed graphs. We defer this
discussion to the full version of the paper. The assumption of fixed vertex
set is without loss of generality as we can assume that all the vertices exist
in the graph from the initial state, and those vertices added to the graph in
the course of evolution, initially have degree zero. Therefore, we focus on
how $E_{t}$ evolves through time.

Our model is a probabilistic generalization of c-closure. Consequently for any
disconnected pair of vertices $u$ and $v$ we assume the probability that they
become connected is a function of their common neighborhood denoted by
$d(u,v)$. Since our experimental observations presented in Section 5 show a
linear dependence, we assume this probability is $ad(u,v)+b$, for some $a$ and
$b$ (learned in a pre-processing phase).

Edge removal occurs at a significantly lower rate compared to edge addition in
social graphs. In our model, we choose uniform edge removal for deleting an
edge, i.e., we pick a pair of connected vertices uniformly at random as a
candidate for edge removal. Section 2.1 is devoted to a rigorous presentation
of our model; this presentation has a combinatorial form which is simple and
easy to analyze.

Throughout this paper, we use the following notation: Let $G_{t}=(V,E_{t})$
denote the graph with $n$ vertices at time step $t$, $G_{0}$ denote the
initial graph, and $N_{t}(v)$ the set of neighbors of vertex $v$ at time $t$,
i.e., $N_{t}(v)=\\{u\in V|(u,v)\in E_{t}\\}$. We use $N_{t}(u,v)$ to denote
the common neighborhood of vertices $u$ and $v$ at time $t$, i.e.,
$N_{t}(u,v)=N_{t}(u)\cap N_{t}(v)$. Let $d_{t}(v)$ denote the degree of vertex
$v$ at time $t$ and $d_{t}(u,v)=|N_{t}(u,v)|$. To denote an induced degree,
induced neighborhood or induced common neighborhood in a subgraph
$G^{\prime}$, we mention the subgraph $G^{\prime}$ explicitly and use the
previous notation. We use the notation $\Gamma_{t}(v)$ to denote the number of
wedges with one end point $v$, i.e., the number of paths of length two
starting at $v$, and we use $\Gamma_{t}(V)$ or $\Gamma_{t}$ for short to
denote the total number of wedges.

###  2.1 The wedge picking model

Let $p$, $q$ and $r$ be constants. Throw a fair coin to decide whether to
follow rule (i) or (ii):

  1. (i)

Pick a wedge, a path of length $2$, uniformly at random. If the picked wedge
is open (its endpoints are disconnected), then _close_ it with probability $p$
(place an edge between the endpoints). Note that one can pick a wedge
uniformly at random by picking the midpoint vertex $v$ with probability
proportional to ${{d_{t}(v)}\choose{2}}$, and then choosing the endpoints
uniformly at random from $N_{t}(v)$. Furthermore by picking a wedge uniformly
at random the probability of placing an edge between a disconnected pair of
vertices $u$ and $v$ will be proportional to $d_{t}(u,v)$.

  2. (ii)

Pick a pair of vertices uniformly at random if they are disconnected, connect
them with probability $r$, if they are connected, disconnect them with
probability $q$.

So we can conclude that a disconnected pair $u$ and $v$ gets connected with
probability $0.5(p\frac{d_{t}(u,v)}{\Gamma_{t}}+r{{n}\choose{2}}^{-1})$ which
is linear in $d(u,v)$. Moreover, a connected pair becomes disconnected with
probability $0.5(q\frac{d_{t}(u,v)}{\Gamma_{t}}+q{{n}\choose{2}}^{-1})$.

###  2.2  Parameters of the model

In this section, we explain how we learn whether or not a graph is evolving
through the wedge picking model and if it does how to estimate the parameters
$p$, $q$ and $r$.

_Learning $p$ and $r$. _ In a pre-processing phase, we track edge additions
between time $t$ and $t+\Delta$ where time $t$ is an initial time and
parameter $\Delta$ will be determined later. Let $f(x)$ be the number of
disconnected pairs with $x$ common neighbors in $G_{t}$ that become connected
in $G_{t+\Delta}$, i.e., $f(x)=|\\{(u,v):d_{t}(u,v)=x,(u,v)\in
E_{t+\Delta}\setminus E_{t}\\}|$. For each $x\in\mathbb{Z}_{+}$, we also
calculate $N_{t}(x)=|\\{(u,v);d_{t}(u,v)=x,(u,v)\notin E_{t}\\}|$. Using
discussion in previous section, we know that the probability of edge addition
is linear in $d_{t}(u,v)$; we assume it is $ad_{t}(u,v)+b$. We plot $x$ vs
$\frac{f(x)}{N_{t}(x)}$, i.e., the probability of a pair of vertices with $x$
common neighbors becoming connected. Using linear regression we fit a line
$ax+b$ to this plot and conclude:

$\frac{f(x)}{N_{t}(x)}=ax+b.$ (1)

We use the magnitude of coefficient of determination as a certificate for
guaranteeing a linear relation. For a coefficient of at least444In Algorithm 2
this threshold can be set to any arbitrary value $c$ $0.6$, we can conclude
that the model follows our assumptions. Using the slope and intercept of the
line then we can extract the values of $p$ and $r$ via Bayes’s rule.

######  Theorem 2.1.

If a graph evolves through the wedge picking model with parameters $p$ and
$r$. In Equation 1, we have: $a=p\frac{M}{\Gamma_{t}}$ and
$b=r\frac{M}{{{n}\choose{2}}}$, where $M$ is the probability of an edge being
added to the graph in $[t,t+\Delta]$, i.e.,
$M=\left(p\frac{\Gamma^{o}_{t}}{\Gamma_{t}}+r(1-\frac{|E_{t}|}{{{n}\choose{2}}})\right)/|E_{t+\Delta}\setminus
E_{t}|$ where $\Gamma^{o}_{t}$ is the number of open wedges at time $t$.

###### Proof.

Let $\mathcal{A}$ be the event that an edge is added to the graph any time in
$[t,t+\Delta]$. Using the definition of $M$ and the union bound we will have
$\mathbb{P}({\mathcal{A}})\approx M\cdot|E_{t+\Delta}\setminus E_{t}|$. Let
$\mathcal{B}$ the event that an edge is added to a pair with $x$ common
neighborhood. If the graph follows the wedge picking model, by Bayes rule we
have:

$\begin{array}[]{ll}\mathbb{P}({\mathcal{B}}|{\mathcal{A}})&=\mathbb{P}({\mathcal{A}}|{\mathcal{B}})\mathbb{P}({\mathcal{B}})/\mathbb{P}({\mathcal{A}})\\\
&=pN_{t}(x)\left(\frac{x}{\Gamma_{t}}+r{{{n}\choose{2}}}^{-1}\right)/\mathbb{P}({\mathcal{A}})\\\
&=pN_{t}(d)\left(\frac{x}{\Gamma_{t}}+r{{{n}\choose{2}}}^{-1}\right)/(M\cdot|E_{t+\Delta}\setminus
E_{t}|).\end{array}$

Thus, if we take $\Delta$ so that $N_{t}$ and $\Gamma^{o}_{t}/\Gamma_{t}$
(subsequently $M$) do not change significantly (see the while condition in
Algorithm 2), and using the fact that
$\mathbb{P}({\mathcal{B}}|{\mathcal{A}})=\frac{f(x)}{|E_{t+\Delta}\setminus
E_{t}|}$, we get

$\begin{array}[]{cl}f(x)/N_{t}(x)&=p\frac{M}{\Gamma_{t}}x+r\frac{M}{{{n}\choose{2}}}\end{array}$

∎

_Learning $q$. _ Our experimental analysis on real dynamic graphs suggest a
very low rate of edge deletion compared to edge addition (see Section 5). In
fact, in many of the dynamic graphs we have, edge deletion does not occur at
all! Thus, instead of learning $q$’s value, we suffice to assert if $p/q\geq
n$, which will be useful later on in the analysis of degree and tri-degree
growth (see Lemma 3.1). The proof of the following theorem is straightforward
and deferred to the full version.

######  Theorem 2.2.

For a graph evolving based on the wedge picking model we have:

$p/q\geq\frac{|E_{t+\Delta}\setminus E_{t}|}{|E_{t}\setminus
E_{t+\Delta}|}\cdot\frac{\Gamma_{t}}{\Gamma^{o}_{t}}\cdot\frac{|E_{t}|}{{n\choose
2}}$ (2)

##  3 Theoretical analysis of degree growth

In real social networks, number of edges and open and closed wedges change
rapidly, and keeping track of this change, or calculating them at each time
step can be expensive. In this Section we show how to theoretically bound the
growth rate of degrees in order to avoid expensive bookkeeping.

The rate of evolution of the graph at time $t$ is highly dependent on the
clustering coefficient of $G_{t}$ (defined as the ratio of total number of
open and closed wedges). When the clustering coefficient is low, we expect a
high rate of evolution; meaning not only the number of edges, open and closed
wedges are changing rapidly but also the probabilities of adding or removing
edges are. These rapid changes make design of algorithms a daunting task.
Nevertheless, in the next lemma (Lemma 3.1) we show that these probabilities
do not change significantly in limited time.

Let $\Gamma^{k}_{t}(u)$ be defined as the number of paths of length $k$ at
time $t$ having one end at $u$, and $\Gamma^{k}_{t}(u,v)$ the number of paths
between $u$ and $v$ at time $t$ and of length $k$. For example,
$\Gamma^{1}_{t}(u,v)=1$ if $(u,v)\in E_{t}$ and $0$ otherwise,
$\Gamma^{2}_{t}(u,v)=d_{t}(u,v)$, and $\Gamma^{1}_{t}(u)=d_{t}(u)$. Since
$\Gamma^{2}$ is the most commonly used notation in our paper, we use $\Gamma$
to refer to $\Gamma^{2}$. Note that at any time step, closing or a wedge
residing on a path would decrease the length of the path. Thus,
$\Gamma^{i}_{t+\delta}(u,v)$ will depend on
$\Gamma_{t}^{i+1}(u,v),\dots,\Gamma^{i+\delta}_{t}(u,v)$. Moreover, for an
arbitrary $k$ and any $i<k$ by connecting two paths
$\gamma_{1}\in\Gamma^{i}_{t}(u)$ and $\gamma_{2}\in\Gamma^{k-1-i}_{t}(v)$ we
can create a path of length $k$. We use $d_{max}$ to denote the maximum degree
of the graph $G_{t}$. We formalize the above observations, in the following
lemma:

######  Lemma 3.1.

For any $u,v\in V$ and $\delta\leq e\Gamma_{t}/(2pd_{max})$, $q=o(p/d_{max})$,
and $r\leq(n^{2}/\Gamma_{t})p$ with probability $1-o(1)$ we have:

$\mathbb{E}[d_{t+\delta}(u,v)-d_{t}(u,v)]\leq
4\delta\frac{d_{t}(u)d_{t}(v)}{\Gamma_{t}}.$ (3)

###### Proof.

For simplicity we first assume that we have no edge deletion. We will take
care of the deletions later.

To warm up, consider the probability
$\mathbb{P}\left[d_{t+1}(u,v)-d_{t}(u,v)>0\right]$ there are two ways to add
to $d_{t}(u,v)$: (1) by closing only one wedge placed on a path of length
three between $u$ and $v$, and there are two ways of doing so (rule (i)), (2)
by adding an edge between $w\in N_{t}(v)$ and $u$ or vice versa (rule (ii)).

Thus, $\mathbb{P}\left[(d_{t+1}(u,v)-d_{t}(u,v))>0\right]\leq
2\Gamma^{3}_{t}(u,v)p/\Gamma_{t}+(d_{t}(u)+d_{t}(v))r/n^{2}$, equivalently:

$\mathbb{E}[d_{t+1}(u,v)-d_{t}(u,v)]\leq
2\Gamma^{3}_{t}(u,v)p/\Gamma_{t}+(d_{t}(u)+d_{t}(v))r/n^{2}$.

We now consider the general case of $\delta$ steps:

$\mathbb{E}[d_{t+\delta}(u,v)-d_{t}(u,v)]=\sum_{i=1}^{\delta}\mathbb{E}[d_{t+i}(u,v)-d_{t+i-1}(u,v)]=\sum_{i=1}^{\delta}\mathbb{P}[\text{creating
a wedge at }t+i].$

$w$$u$$v$$u$$v$ Figure 1: After three steps, a path of length 5 between $u$
and $v$ can turn to a wedge between them applying rule (i) (below picture); or
alternatively two disjoint paths can turn to a wedge between $u$ and $v$ by
applying rules (i) and (ii) (top picture). The order of edges being added is:
red, blue, green.

Note that creating a wedge at time $t+j$ is possible by closing wedges
(applying rule (i)) on a path which has length $j+2$ at time $t$. Having rule
(ii) in our hand, we can create new paths of length $j$ at time $t$ by placing
an edge between a path of length $i$ in $\Gamma^{i}_{t}(u)$ and a path of
length $j-1-i$ in $\Gamma^{j-1-i}_{t}(v)$. Thus the original expectation is
bounded by:

$\sum_{i=1}^{\delta}\frac{d_{t+i}(v)+d_{t+i}(u)r}{n^{2}}+2\Gamma^{3}_{t+i}(u,v)\frac{p}{{\Gamma_{t+i}}}.$

We now bound the first and second term of the sum:

$\sum_{i=1}^{\delta}\frac{d_{i}(v)+d_{i}(u)r}{n^{2}}\leq\frac{\delta
r(d_{t}(v)+d_{t}(u))(1+\delta/n)}{n^{2}}$ (4)

$\Gamma^{3}_{t+i}(u,v)\leq\sum_{j=1}^{i}d_{max}^{j}\left(d_{t}(u)d_{t}(v)\frac{p^{j}\kappa(2+j)}{\Gamma_{t}^{j}}+(d_{t}(v)+d_{t}(u))\frac{2r^{j}}{n^{2j}}\right)$
(5)

, where $\kappa(2+j)$ is the number of ways a path of length $2+j$ can be
turned into one wedge by closing $j$ wedges consecutively. And $\Gamma_{t}$ is
the total number of wedges at time $t$.

It is an easy counting problem to see $\kappa(j+2)=(j+1)!$. Note that for any
$t$, $\Gamma_{t}\geq d_{\max}^{2}$, and for each $j$,
$\Gamma_{t}^{2+j}(u,v)\leq d_{t}(u)d_{t}(v)d_{\max}^{j}$, and
$\Gamma_{t}^{j}(u)\leq d_{t}(u)d_{\max}^{j}$ where $d_{\max}$ is maximum
degree at time $t$. Note that
$p^{j}j!/d_{\max}^{j}\leq(p\delta/d_{\max})^{j}$. Under the assumption that
$\delta\leq e\Gamma_{t}/2pd_{max}$ we can simplify Equation 5 to get:

$\begin{array}[]{ll}\sum_{i=1}^{\delta}\Gamma_{t+i}^{3}(u,v)&\leq
d_{t}(u)d_{t}(v)\sum_{i=1}^{\delta}\sum_{j=1}^{i}(j+1)k^{j},\quad k<1/2\\\
&\leq(4\delta)d_{t}(u)d_{t}(v).\end{array}$ (6)

Thus, as long as $r\leq(n^{2}/\Gamma_{t})p$ (consistent with our experiments)
we have:

$\mathbb{E}[(d_{t+\delta}(u,v)-d_{t}(u,v))]\leq\frac{d_{t}(u)d_{t}(v)}{\Gamma_{t}}(4\delta).$
(7)

We now show that our initial assumption is not restrictive us as long as
$q=o(p/d_{max})$. In fact we can show that with probability $1-o(1)$, no edge
deletion will occur in time $\delta\leq ed_{max}/p$:

$\begin{array}[]{ll}\mathbb{P}(\text{at least one edge is
deleted})\leq&\sum_{t=1}^{\delta}q\sum_{u,v}1/n^{2}\\\ \mathbb{P}(\text{at
least one edge is deleted})\leq&\delta p/\omega(d_{max})\leq o(1).\end{array}$

∎

Having Lemma 3.1, for each $v\in V$, we can now bound the rate of its degree
or tri-degree (defined later) growth:

_Degree of a vertex $u\in V$._

Consider and arbitrary vertex $v\in V$, the following lemma bounds the rate of
the growth of $u$’s degree in the wedge picking model:

######  Lemma 3.2.

Let $\delta\leq e\Gamma_{t}/2pd_{max}$ and $q=o(d^{-1}_{max})p$, for any $u\in
V_{t}$:

$\mathbb{E}[(d_{t+\delta}(u)-d_{t}(u))]\leq\delta\left(2p\frac{\Gamma_{t}(u)}{\Gamma_{t}}+r\frac{1}{n}\right).$
(8)

, where $\Gamma_{t}(u)$ is the number of wedges having one endpoint equal to
$v$, i.e. $\Gamma_{t}(u)=\sum_{v\in V}d_{t}(u,v)$.

###### Proof.

Let $|E_{t}|=m_{t}$, we first employ the Cauchy Schwarz inequality to show
that $\Gamma_{t}/m_{t}\geq(1/2)(d_{avg}-1)$: $\Gamma_{t}=\sum_{v\in
V}(d_{t}^{2}(v)-d_{t}(v))/2,\sum_{v\in V}d_{t}^{2}(v)\geq\left(\sum_{v\in
V}d_{t}(v)\right)^{2}/n_{t}$ ; thus, $2\Gamma_{t}+m_{t}\geq m_{t}^{2}/n_{t}$.

$\begin{array}[]{lll}\mathbb{E}[(d_{t+\delta}(u)-d_{t}(u))]&\leq\sum_{i=1}^{\delta}\mathbb{E}[(d_{t+i}(u)-d_{t+i-1}(u))]\\\
&\leq\sum_{i=1}^{\delta}\sum_{u\in
V}d_{t+i-1}(u,v)\frac{p}{\Gamma_{t}}+\frac{\delta\cdot r}{n}.\\\ \end{array}$

Employing Lemma 3.1:

$\begin{array}[]{lll}\sum_{i=1}^{\delta}\sum_{u\in V}&d_{t+i-1}(u,v)\\\
&\leq\sum_{i=1}^{\delta}\sum_{u\in
V}\left(d_{t}(u,v)+\frac{4(i-1)pd(u)d(v)}{\Gamma_{t}}\right)\\\
&\leq\Gamma_{t}(v)\delta+\sum_{i=1}^{\delta}\frac{4(i-1)pd(v)m_{t}}{\Gamma_{t}}.\end{array}$

Having $d_{t}(v)\leq\Gamma_{t}(v)$ and $\frac{2\Gamma_{t}}{m_{t}}\geq
d_{avg}-1$, we get

$\begin{array}[]{lll}\sum_{i=1}^{\delta}\sum_{u\in V}&d_{t+i-1}(u,v)\\\
&\leq(p/\Gamma_{t})\Gamma_{t}(v)\delta(1+(\frac{\delta}{2})(\frac{4pd(v)m_{t}}{\Gamma_{t}\Gamma_{t}(v)}))\\\
&\leq(p/\Gamma_{t})\Gamma_{t}(v)\delta(1+(\frac{\delta}{2})(\frac{2p}{d_{avg}}))\\\
&\leq\frac{\delta\Gamma_{t}(u)p}{\Gamma_{t}}\left(1+\frac{2p\delta}{\Gamma_{t}d_{avg}}\right)\\\
&\leq\frac{\delta\Gamma_{t}(u)p}{\Gamma_{t}}(2),\text{ for
}\delta\leq\Gamma_{t}/d_{\max}p.\end{array}$

∎

_Tri-degree of a vertex $u\in V$._

For each vertex $u$, and time stamp $t$, let tri-degree of $u$ at time $t$,
denoted by $D_{t}(u)$, be the number of triangles having $u$ as a vertex. We
have the following lemma whose proof is similar to proof of Lemma 3.2 and
omitted:

######  Lemma 3.3.

For any $u\in V$ and $\delta\leq ed_{max}/2p$ and $q=o(d^{-1}_{max})p$,

$\mathbb{E}[(D_{t+\delta}(u)-D_{t}(u))]\leq\frac{\delta\zeta^{2}_{t}(v)p}{\Gamma_{t}}\left(1+\frac{8\delta
p}{d_{avg}}+\frac{6\delta^{2}p^{2}}{\Gamma_{t}}\right)+\frac{d^{2}_{t}(v)(\delta+\delta^{2}/n)}{n^{2}}$
(9)

, where $\zeta^{2}_{t}(v)=\sum_{u\in V}(d_{t}(u,v))^{2}.$

######  Remark 3.1.

The growth rate of other notions of degree can be bounded similarly. These
notions have been used in the literature to define various density measures
[39, 16].

##  4 Algorithmic implications: The rest and run strategy

In the dynamic graph literature, algorithms are often designed to update
output solution after every single edge update; this is essential when edge
updates arrive in an arbitrary (or adversarial) manner. Consider an algorithm
designed for dynamic graphs which despite having low amortized cost,
occasionally performs expensive operations in a row. Batching edge updates
improve the run-time of these algorithms significantly. However, when not
designed carefully, batching can harm the accuracy of algorithms.

In this section, we utilize our previous results to devise a speed up
subroutine based on batching for some algorithms without harming their
accuracy. More precisely, for a given graph $G_{t}$, we identify time
$\Delta_{t}$ where a previously calculated solution still serves as a good
approximation for any graph $G_{t^{\prime}}$; $t^{\prime}\in[t,t+\Delta_{t}]$.
Our subroutine declares $[t,t+\Delta_{t}]$ as a “rest” interval. During rest
intervals the algorithm only collects the changes in the graph and does not
perform expensive operations. In the “run” intervals, the algorithm has its
normal performance except since the changes are received in batches it saves
redundant operations; in the experimental section we observe significant speed
up due to this simple trick while maintaining the accuracy compared to the
optimal solution.

Given a problem of finding a subgraph $S$ in $G$ satisfying a certain
property, e.g., the problem of densest subgraph discovery, the question we
seek to answer is:

_Given an approximate solution $S$ for $G_{t}$, what is the largest
$\Delta_{t}$ such that with high probability, for any $t^{\prime}\leq
t+\Delta_{t}$, $S$ is a still “good” approximation for $G_{t^{\prime}}$._

Note that if an algorithm’s functionality is based on the degrees (tri-degree)
of vertices of the input graph (or its degree in other induced subgraphs),
Lemma 3.2 (Lemma 3.3) provides us with a value of $\Delta_{t}$:

Let $C_{t}(v)=2p\frac{\Gamma_{t}(v)}{\Gamma_{t}}+r\frac{1}{n}$, and
$\beta_{t}(1+\epsilon)$ be the change in degrees that the vertices in $S$
afford to undergo while maintaining the quality within $(1+\epsilon)$
precision. We define $\Delta_{t}$ as follows:

$\Delta_{t}\dot{=}\min_{v\in V}\tau_{v},\text{ where
}\tau_{v}\dot{=}\min\left\\{\frac{e\Gamma_{t}}{2pd_{max}},\frac{\beta_{t}(1+\epsilon)}{C_{t}(v)}\right\\}.$
(10)

Employing Lemma 3.2, we conclude that using the above value for $\Delta_{t}$,
for any vertex $u$ (in particular the vertices in solution $S$) and
$\delta\in[t,t+\Delta_{t}]$ we will have:

$\mathbb{E}[d_{\delta}(u)-d_{t}(u)]\leq(1+\epsilon)\beta_{t}.$

We formalize this observation in the next section for finding the densest
subgraph in a dynamic graph. In section 4.2 we show how to generalize these
results for finding tri-densest subgraph with trivial modifications.

###  4.1 The densest subgraph problem

In this section, to demonstrate the applicability of the rest and run
strategy, we apply it to the problem of finding the densest subgraph. We
present a similar algorithm for finding tri-densest subgraph (a subgraph with
maximum density of triangles) in the Section 4.2. We believe that our work
provides initiatives to design of algorithms for finding approximations to the
_$k$ -clique densest subgraph_ problem [38].

Finding maximum cliques in a graph and even approximating it within a
reasonable factor is NP hard [18]. Thus, researchers often define density of a
subgraph as its induced average degree. In the literature, _the densest
subgraph problem_ is discovery of subgraphs with maximum average degree
(formal definition in Equation 11). This problem is polynomially tractable
using flow computations [17], and a greedy algorithm providing a $2$
approximation [11], also known as _peeling_ is used in practice. Peeling is a
key component of most of the state of art algorithms in various massive data
settings. For example: (1) in data streaming model where the network is
processed in passes and the goal is to obtain a solution with minimal number
of passes and low memory Bahmani et al propose an algorithm based on peeling
[6], (2) in the MapReduce model where the data is distributed between
different machines a number of algorithms have been suggested based on peeling
[6, 7, 13] and (3) the dynamic setting in which the graph has an evolving edge
or vertex set, algorithms based on peeling have been shown to be effective [7,
13]. A summary of the results based on peeling is presented in Table 1. It is
important to mention here that peeling is not the only main strategy to find
densest subgraph and in fact several foremost algorithms maintaining sketches
or sparsifiers have been suggested in data streaming and dynamic graph models
[37, 14, 28, 30, 13]. We also remark that we do not aim to beat any of these
algorithms theoretically. Our solution is to boost their runtime in practice
by employing the _rest and run strategy_.

Authors/year | Model | Complexity | Quality | Problem
---|---|---|---|---
Bahmani et al, | Streaming, | #passes: |  | densest
2012 [6] | MR | $\log_{1+\epsilon}n$ | $2(1+\epsilon)$ | subgraph
Epasto et al, | Dynamic, | ACPU |  | densest
2015 [13] | MR | $\log_{1+\epsilon}n$ | $2(1+\epsilon)$ | subgraph
Bhattacharya | Dynamic, | ACPU |  | densest
et al, 2015 [7] | Streaming, MR | $\log_{1+\epsilon}$ | $4(1+\epsilon)$ | subgraph
Tsourakakis, | Dynamic, | #passes: |  | tridensest
2014 [40] | MR | $\log_{1+\epsilon}n$ | $3(1+\epsilon)$ | subgraph
Table 1: A summary of the previous work on densest and tridensest subgraph
discovery based on “peeling”. MR stands for MapReduce and ACPU stands for
amortized cost per update.

Our proposed solution for a faster densest subgraph discovery algorithm is to
equip _peeling_ with the rest and run strategy. We show that while maintaining
$4(1+\epsilon)$ approximation for the densest subgraph problem our algorithm
has significant improvement in its running time compared to its counterparts.

Our algorithm follow the following three steps: (1) We learn the parameters of
the wedge picking model in a pre-processing phase (2) We find rest intervals
after each run of the algorithm (3) we optimise the batch of the updated edges
to feed them into the peeling algorithm.

Let the density of graph $G=(V,E)$, denoted by $\rho(G)$, be the ratio of the
number of edges in $G$ to the number of vertices of $G$, i.e.
$\rho(G)=|E|/|V|$. In the densest subgraph problem, our goal is to find a
subgraph with maximum density. Let $\beta^{*}(G)$ denote the maximum density
among all subgraphs of $G$, and let $densest(G)$ be a subgraph $G$ with
maximum density, so

$\beta^{*}(G)=\max_{G^{\prime}\subseteq
G}\rho(G^{\prime}),~{}~{}densest(G)=\underset{G^{\prime}\subseteq G}{\rm
argmax}~{}\rho(G^{\prime}).$ (11)

In the dynamic graph setting algorithms of Epasto et al [13] and Bhattacharya
et al [7], both based on the peeling strategy, present constant factor
approximation algorithms, with amortized cost $poly(\log n)$ per edge
addition/deletion. Despite having a low amortized cost, the above algorithms
fail to output a solution in reasonable time when the size of a network ($n$)
is huge ($n\simeq 1M$) while the edges are evolving at a high rate; see
Section 5.

In this section, after briefly presenting the peeling strategy, we introduce
our algorithm. In particular, our emphasis is on Epasto et al.’s algorithm
[13] which adopts peeling to dynamic graphs, and proves an amortized cost of
$\log(n)$ per edge update, while maintaining a $2(1+\epsilon)$ approximate
solution. We assume that the reader is familiar with their results and in a
few occasions we rely on their work in our proofs (for more information see
[13]).

_Peeling._ Let $\beta^{*}$ be the optimum density as defined in Equation 11.
Partition the vertices of graph $G=\langle V,E\rangle$ into layers
$S_{0},S_{1},\dots,S_{k}$ as follows to find a subgraph with density at least
$\beta^{*}/2(1+\epsilon)$:

$S_{0}=V$, while $S_{r+1}\neq\emptyset$, derive $S_{r+1}\subseteq S_{r}$ by
removing vertices whose degree in the induced graph $S_{r}$ is less than
$2\beta(1+\epsilon)$.

When the graph is static, a multiplicative $(1+\epsilon)$ approximation of
$\beta^{*}$ can be approximated by iterating over all $\log_{1+\epsilon}(n)$
values. For the dynamic case Epasto et al. suggest maintaining the following
invariant if possible, and if not possible rebuilding the layers by iterating
over all the $\log_{1+\epsilon}(n)$ values for $\beta$ as in the static case:

Invariant: For a given density $\beta$, parameter $\epsilon$, and current
graph $G_{t}=(V_{t},E)$, the nodes of the graph are organized in layers
$S_{0},S_{1},\cdots,S_{k}$ for $k=\lceil\log_{1+\epsilon}{n}\rceil$, where
$S_{0}=V_{t}$, $S_{r+1}\subseteq S_{r}$ is obtained from removing vertices
with degree less than $2\beta(1+\epsilon)$ from $S_{r}$, and
$S_{k}=\emptyset$.

0: threshold $c$ , A series of edge updates:
$\\{\langle(u,v)_{t_{i}},{\chi}_{t_{i}}\rangle\\}_{i=0}^{\infty}$, where
$(u,v)_{t_{i}}$s are pairs of vertices where the update takes place at time
$t_{i}$ and $\chi_{t_{i}}$ is either addition or removal of an edge.

0: Layers $S_{0},S_{1},S_{2},\dots,S_{l}$,

At time $t_{0}$: Run Epasto et all algorithm and find
$S_{1},S_{2},\dots,S_{l}$.

At time $t_{0}$, run Algorithm 2 and find $p$, $q$, $r$ and $\mathcal{R}$.

if ${\mathcal{R}}\geq c$ then

continue

repeat

having $p,q$ and $r$, find $\Delta_{t}$

while $t_{i}\leq t_{0}+\Delta_{t}$ do

Update the graph and do nothing, let $U$ be the set of updated vertices

Push all the vertices in $U$ in the stack and run algorithm of Epasto et al.
to maintain $S_{0},S_{1},S_{2},\dots,S_{l}$.

$t_{0}=t_{0}+\Delta_{t}$.

until $\infty$

Algorithm 1 Rest and run densest sub graph.

0: An initial graph $G_{0}$, a series of edge updates:
$\\{\langle(u,v)_{t_{i}},{\chi}_{t_{i}}\rangle\\}_{i=0}^{\infty}$, where
$(u,v)_{t_{i}}$s are pairs of vertices where the update takes place at time
$t_{i}$ and $\chi_{t_{i}}$ is either addition or removal of an edge.

0: $p,q,r$ (as defined in Section 2.1), and linear regression’s coefficient of
determination.

$t\leftarrow t_{0}$.

for each $0\leq x\leq n$, let $f(x)=0$ and $f^{\prime}(x)=0$.

$A\leftarrow 0,D\leftarrow 0$ respectively the number of added/deleted edges.

while
$\frac{\Gamma^{o}_{t}}{\Gamma_{t}}\in[\frac{1}{1+\epsilon},1+\epsilon]\frac{\Gamma^{o}_{0}}{\Gamma_{0}}$,
$\forall x:N_{t}(x)\in[\frac{1}{1+\epsilon},1+\epsilon]N_{0}(x),t\leq|E_{0}|$
do

$x=d_{t}(u,v)$

update $f(x),A,D$

Update $\Gamma_{t}^{o}$, $\Gamma_{t}$, and $N_{t}$

$t\leftarrow t+1$

$a,b\leftarrow$ applying linear regression to $f(x)/N_{0}(x)=ax+b$.

Using Theorems 2.1 and 2.2 find $p,r$, $q$, and the coefficient of
determination $\cal R$.

return $p,q,r,{\cal R}$

Algorithm 2 Learning Phase.

_Our Algorithm: rest and run + Peeling_.

The learning phase of our algorithm which was explained in full detail in
Section 2.2 is presented as Algorithm 2. The rest and run intervals are found
in the UpdatePeeling, Algorithm 1. The correctness of Algorithm 1 algorithm
can be easily concluded from correctness of Epasto et al’s algorithm [13] and
the following lemma:

######  Lemma 4.1.

For an arbitrary vertex $v\in V$, let $d^{\prime}(v)$ be degree of $v$ in
layer $S_{l}(v)$ at time $t+\tau(v)$. For $\beta_{O}\geq c\log(n)$ for
constant $c>1$ with probability $1-o(1)$ for all vertices $v$ in $G\setminus
S_{l}$, we have:

$d^{\prime}(v)\leq 4(1+\epsilon)\beta_{O}.$ (12)

###### Proof.

For each $v$ consider a sequence of random variables $X_{1},X_{2},\dots
X_{\tau(v)}$, $X_{i}$ indicating degree incrementation of $v$ at time $t+i$.
Note that using the values of $\tau$ defined in Equation 10 we have
$\mathbb{E}[d_{t+\tau(v)}(v)-d_{t}(v)]\leq\beta(1+\epsilon)$. Applying the
Chernoff bound we have: $\mathbb{P}\left[d_{t+\tau(v)}(v)-d_{t}(v)\geq
2\beta(1+\epsilon)\right]\leq e^{-(1+\epsilon)\beta}\leq\omega(1/n)$. Summing
over all vertices in $G\setminus S_{l}$ and using the union bound we obtain:

$\displaystyle\mathbb{P}\left[\exists v\in G\setminus
S_{l};~{}d_{t+\tau(v)}(v)-d_{t}(v)\geq 2\beta(1+\epsilon)\right]$
$\displaystyle\leq(n-\log(n))\omega(1/n)=o(1).$

∎

The following remark is concluded from Theorem [13] and Lemma 4.1:

_Remark 1._ Algorithm 1 maintains a $4(1+\epsilon)$ approximation to the
densest subgraph problem. And if $A$ is the total number of edges added to the
graph in between any two consequent calls of Algorithm 1 and $U$ is the total
number of affected vertices, then since any batch of edges that are added to a
single vertex in the graph are processed only once, this will cause the
runtime of our algorithm to drop by a ratio of $\nicefrac{{A}}{{U}}$ compared
to that of Epasto et al [13].

In the next section, using Lemma 3.3 we employ the rest and run strategy to
find tri-densest subgraphs (subgraphs with maximum average of tri-degree)
within $5(1+\epsilon)$ approximation factor.

###  4.2 Finding Tri-densest Subgraph

Algorithms for densest subgraph may output subgraphs with small clustering
coefficient and large diameter. Hence studying other similar problems have
been suggested in the literature [39, 38, 40]: one example is searching for
subgraphs which have maximal density of triangles i.e. discovery of _tri-
densest subgraphs_. Note that a subgraph with a higher density of triangles
has a higher clustering coefficient and is a better representative of triadic
closure.

We now proceed to present out solution to this problem in the wedge picking
model:

Let the tri-density of a graph $G=(V,E)$, denoted by $\xi(G)$, be the ratio of
the number of triangles in $G$ to the number of vertices of $G$, i.e.
$\xi(G)=|W^{c}(G^{\prime})|/3|V^{\prime}|$, where $W^{c}(G^{\prime})$ is its
number of closed wedges (Note that each triangle counts as three closed
wedges). In the tridensest subgraph problem, our goal is to find a subgraph
with maximum tridensity. Let $\alpha_{O}(G)$ denote the maximum tridensity
among all subgraphs of $G$, and let $tridensest(G)$ be a subgraph with maximum
density, so

$\alpha_{O}(G)=\max_{G^{\prime}\subseteq
G}\xi(G^{\prime}),~{}~{}tridensest(G)=\underset{G^{\prime}\subseteq G}{\rm
argmax}~{}\xi(G^{\prime}).$

The problem has a $3(1+\epsilon)$ solution when updates are adversarial:
maintain peeling layers by removing vertices with tridegree less than
$3(1+\epsilon)\alpha$ consecutively [40]. Following the strategy of rest and
run, at each time $t$ we run the algorithm $UpdateTriPeeling$ of [40],
calculate $\Delta_{t}$. Then, we wait until $t+\Delta_{t}$ for the next call
to $UpdateTriPeeling$.

0: Layers $S_{0},S_{1},S_{2},\dots,S_{l}$ , $T$, most recent reading time $t$.

0: $5(1+\epsilon)$ approximation to densest subgraph, most recent reading time
$t^{\prime}$

Let $\Delta_{t}=\min_{v}\\{\tau_{v}\in T\\}$;

Read $\Delta$ edge updates:
$U=\\{(u_{1},v_{1}),(u_{2},v_{2}),\dots,(u_{\Delta_{t}},v_{\Delta_{t}})\\}$;

$E=E\cup U$

$G_{t+\Delta_{t}}=\langle V,E\rangle$

Update $N=\\{N(v)\\}_{v\in V}$ and $T=\\{\tau(v)\\}_{v\in V}$ correspondingly;

$UpdateTriPeeling(G_{t+\Delta_{t}},U)$;

return $S_{l}$, $t^{\prime}$

Algorithm 3 Update (tri-Densest).

The following Theorem proves the correctness of Algorithm 3, and its proof is
identical to proof of Lemma 4.1 and thus omitted.

######  Theorem 4.1.

In the wedge picking model, and for $\alpha_{O}\geq c\log(n)$; $c>1$ a
constant, there is an algorithm which maintains a $5(1+\epsilon)$
approximation of tridensest subgraph problem with probability $1-o(1)$ and low
amortized cost.

##  5 Experiments

###  5.1 Asserting the validity of wedge picking model assumptions

In order to assert whether or not the probability of adding an edge between
any pair of disconnected vertices is linear with respect to the size of their
common neighborhood, we run algorithm 2 the graphs of Table 2. Plotting
$f(d)/n(d)$ over $d$, and running linear regression, we observe two main
general behaviours for these graphs: (a) coefficient of determination is
large. i.e. higher than $0.6$; see e.g. Figure 2a. (b) coefficient of
determination is reasonable. i.e. between $0.2$ and $0.5$; see e.g. Figure 2b.
For most of the graphs with coefficient of determination between $0.2$ and
$0.5$, the plot shows an interesting branching behaviour: the dependence is
linear but it is in fact more that one line; see e.g. Figure 2b.

In both of the above cases we conclude linearity.

(a) dataset: Digg Friends, Slope: 0.01, intercept: 0.02, coefficient of
determination: 0.66. The high value of the coefficient of determination
certifies linear relation.

(b) dataset: Facebook wall posts, Slope: 0.0004, intercept: .005, coefficient
of determination: 0.36. Despite low coefficient of determination, we conclude
linearity since we can observe two separate linear behaviors.

Figure 2: Plot of $f(d)/n(d)$ over $d$ as defined in Section 2.2. The green
line shows the result of linear regression.

###  5.2 The densest subgraph algorithm in real dynamic graphs

In this section, our goal is to demonstrate the applicability of the rest and
run strategy, in particular when it is applied to the densest subgraph
problem. Thus, we compare the run time and accuracy of Algorithm 1 and [13] on
the data sets presented in Table 2. We note that all the networks of Table 4
are not dynamic and not helpful for this section. We will later use them to
generate synthetic data (Section 5.3). Besides, these datasets only evolve
through edge addition, thus we set $q=0$ and we extract $p$ and $r$ through
learning these parameters by running Algorithm 2.

data set | $n$ | $|E_{t_{0}}|$ | $d_{avg}$ | $d_{max}$ | $\Delta_{t_{0}}$ | $\Gamma_{0}$ | $\beta_{t_{0}}$
---|---|---|---|---|---|---|---
Facebook (WOSN) | 63,731 | 481327 | 25.640 | 1,098 | 1758 | 33044752 | 91.268
Digg friends | 279,630 | 1,731,653 | 12.385 | 12,204 | 5276 | 97367436 | 57.34
YouTube | 3,223,589 | 9,375,374 | 5.8167 | 91,751 | 39021 | 1245457386 | 33.987
Table 2: We used the above dynamic datasets from Koblenz dataset collection in
our experiments of Sections 5.2 and 5.3

_Accuracy._ Figure 3 shows the result of running Algorithm 1 on Digg friends
dataset. We observe that algorithm tracks the density outputted by [13]
closely, thus in practice the rest and run strategy does not harm accuracy of
the original algorithm.

Figure 3: Comparison of accuracy of our algorithm against [13] on Digg Friends
dataset. The $x$ axis is the number of rest and runs and the $y$ axis is the
density output by each algorithm.

_Run time._ In Table 3, we present the runtime of the algorithm for all
datasets in Table 2. The runtimes demonstrate that the rest and run strategy
is highly effective in reducing when employed on huge graphs. In particular
when the original algorithm does not terminate in reasonable time; see e.g.
the row corresponding to YouTube.

data set | Our running time | [13]
---|---|---
Facebook (WOSN) | 4s | 12m
Digg Friends | 20s | 1m
YouTube | 46s | +8h
Table 3: Runtime comparison on real dynamic data sets. The $x$ axis is the
number of rest and runs and the $y$ axis is the density output by each
algorithm.

###  5.3 The densest subgraph algorithm in synthetically generated data

In this section, our goal is to study the efficiency and accuracy of Algorithm
1 in an ideal scenario when the graph’s evolution is perfectly consistent with
the assumptions of our model,i.e., we have perfect linearity. To achieve this,
we take $r,q=0.001,p=0.75$. We generate the edge sequence separately and then
we run dense graph detection algorithm; doing so we achieve two goals (1) the
time spent on the edge sequence generation has no affect in our algorithm
runtime and (2) our comparison is based on the same benchmark for our
algorithm and the algorithms we compare against.

In subsection 5.3.1 we assess the quality of approximation by comparing the
density returned by our algorithm to the optimal density found by a linear
program (LP) solver. We use an open source LP solver for our experiments. In
Subsection 5.3.2, we switch to larger networks, having vertex set of order ten
thousand to a million, to compare the quality and run time of our algorithm to
[13].

Data Description. The datasets are collected from [1] and [3], and are listed
in Table 4 and 2. We pre-process these datasets and remove duplicate edges and
self loops, so for some data sets the number of edges in our input is slightly
smaller than those presented in the original sources. For dynamic graphs, we
sort them according to their time-stamps in our pre-processing. A more
detailed description of the data sets is presented in Appendix.

####  5.3.1 Small datasets: A comparison of accuracy against optimal solution

We evaluate the quality of our solution by comparing it to the the optimal
answer. To obtain the maximum density, we solve the linear programming (LP)
formulated by Charikar et al. [11]. In Figure 4, we present the two data sets
for which we observed the largest gap between the outcomes of the two
algorithms (ours and the LP). Note that the gap is always less than 1.15 after
40 rounds of rest-and-run.

Figure 4: Quality comparison against OPT [11] on data sets: CA-CondMat (left), email-Eu-core (right). The $x$ axis is the number of rest and runs and the $y$ axis is the density output by each algorithm. data set | $n$ | $|E_{t_{0}}|$ | $d_{avg}$ | $d_{max}$ | $\Delta_{t_{0}}$ | $\Gamma_{0}$ | $\beta_{t_{0}}$
---|---|---|---|---|---|---|---
email-Eu-core | 986 | 16,064 | 32 | 345 | 626 | 1,183,216 | 26.86
CA-GrQc | 5241 | 14,484 | 5 | 81 | 147 | 229,867 | 19.56
CA-CondMat | 23,133 | 93,439 | 8 | 279 | 506 | 1,967,650 | 12.5
soc-Epinions | 75,879 | 405740 | 10 | 3044 | 5517 | 74,201,120 | 59.06
twitter | 81,306 | 1,342,296 | 33 | 3383 | 6131 | 230,093,274 | 50.07
dblp | 317,080 | 1,049,866 | 6 | 343 | 622 | 21,780,889 | 48.60
Amazon products | 334,863 | 925,872 | 5 | 549 | 995 | 9,752,186 | 2.76
soc-pokec-relationships | 1,632,803 | 22,301,964 | 27 | 14584 | 26919 | 2,086,073,558 | 32.68
Table 4: We use the above real world graphs which can be found in [1].

####  5.3.2 Big datasets: Runtime and quality assessment on large data sets

We compare the efficiency of our algorithm to [13], which has amortized cost
of a few microseconds per update.

In order to make our comparison more accurate, we feed the same sequence of
updates to our algorithm and the algorithm of [13] for 100 rounds of rest and
run. The only difference between our algorithm and algorithm of [13] is that
we apply the changes after $\Delta_{t}$ updates at once to the graph and run
$UpdatePeeling$. In contrast, [13] calls $UpdatePeeling$ after any single
update. We observe that the negligible theoretical gap between the accuracy of
our algorithm vs [13] vanishes in practice, i.e., in our experiments often
both solutions have the same quality. In fact, as all of our plots
demonstrate, the ratio of our algorithm’s output and the output of [13] is
always at most $1.65$; see Figure 4.

Foremost, we observe a remarkable progress in the runtime of our algorithm. As
we had expected, large values of $\Delta_{t}$s boost the total running time of
our algorithm to the level that it outperforms algorithms of [13] by factor of
1000. The result of our comparison is presented in Table 5.

Figure 5: Quality comparison against [13] on CA-GrQc (left) and email-Eu-core (right) data sets. The $x$ axis is the number of rest and runs and the $y$ axis is the density output by each algorithm. data set | Our running time | [13]
---|---|---
dblp | 3.43s | 32m
Amazon products | 6s | 48m41s
soc-Epinions | 12.4s | 4h23m12s
twitter | 13.52s | 7h4m55s
soc-pokec-relationships | 2m 18s | +24h
Table 5: Runtime comparison on larger data sets.

##  6 Acknowledgement

Shahrzad Haddadan was supported by a Google Focused Research Award, SIR Grant
RBSI14Q743, and NSF Award CCF-174074. The authors are thankful to Flavio
Chierichetti for several helpful conversations about this paper.

## References

  * [1] Konect (the koblenz network collection).  http://konect.uni-koblenz.de/networks.
  * [2] Predicting triadic closure in networks using communicability distance functions.  SIAM J. Appl. Math., 75(4):1725–1744.
  * [3] Stanford Large Network Dataset Collection.  https://snap.stanford.edu/data/.  [Online; accessed 23-May-2109].
  * [4] R. A. Albert-László Barabási.  Emergence of scaling in random networks.  Science, 286:509–512, 1999.
  * [5] S. A. B. E. M. AMARAL, L. A. N. and H. E. STANLEY.  Classes of small-world networks.  Proceedings of the National Academy of Sciences, 97, 21:11149–11152, 2000.
  * [6] B. Bahmani, R. Kumar, and S. Vassilvitskii.  Densest subgraph in streaming and mapreduce.  Proc. VLDB Endow., 5(5):454–465, Jan. 2012.
  * [7] S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. Tsourakakis.  Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams.  In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 173–182, New York, NY, USA, 2015. ACM.
  * [8] G. Bianconi, R. K. Darst, J. Iacovacci, and S. Fortunato.  Triadic closure as a basic generating mechanism of the structure of complex networks.  Technical Report arXiv:1407.1664, Jul 2014.  Comments: 11 pages, 14 figures.
  * [9] J. C. Brunson.  Triadic analysis of affiliation networks.  Network Science, 3:480–508, 2015.
  * [10] D. Chakrabarti and C. Faloutsos.  Graph mining: Laws, generators, and algorithms.  ACM Comput. Surv., 38(1), June 2006.
  * [11] M. Charikar.  Greedy approximation algorithms for finding dense components in a graph.  In Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX ’00, pages 84–95, Berlin, Heidelberg, 2000. Springer-Verlag.
  * [12] F. Chung and L. Lu.  Connected components in random graphs with given expected degree sequences.  Annals of Combinatorics, 6:125–145, 11 2002.
  * [13] A. Epasto, S. Lattanzi, and M. Sozio.  Efficient densest subgraph computation in evolving graphs.  In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 300–310, Republic and Canton of Geneva, Switzerland, 2015. International World Wide Web Conferences Steering Committee.
  * [14] H. Esfandiari, M. T. Hajiaghayi, and D. P. Woodruff.  Brief announcement: Applications of uniform sampling: Densest subgraph and beyond.  ArXiv, abs/1506.04505, 2015.
  * [15] J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein.  Finding Cliques in Social Networks: A New Distribution-Free Model.  In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, pages 55:1–55:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
  * [16] A. Gionis and C. E. Tsourakakis.  Dense subgraph discovery: Kdd 2015 tutorial.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 2313–2314, New York, NY, USA, 2015. ACM.
  * [17] A. V. Goldberg.  Finding a maximum density subgraph.  Technical report, Berkeley, CA, USA, 1984.
  * [18] J. Hastad.  Clique is hard to approximate within.  In Acta Mathematica, pages 627–636, 1996.
  * [19] H. Huang, Y. Dong, J. Tang, H. Yang, N. V. Chawla, and X. Fu.  Will triadic closure strengthen ties in social networks?  ACM Trans. Knowl. Discov. Data, 12(3), Jan. 2018.
  * [20] H. Huang, J. Tang, L. Liu, J. Luo, and X. Fu.  Triadic closure pattern analysis and prediction in social networks.  IEEE Transactions on Knowledge and Data Engineering, 27(12):3374–3389, 2015.
  * [21] H. Huang, J. Tang, S. Wu, L. Liu, and X. fu.  Mining triadic closure patterns in social networks.  WWW ’14 Companion, page 499–504, New York, NY, USA, 2014. Association for Computing Machinery.
  * [22] E. Husic and T. Roughgarden.  Fpt algorithms for finding dense subgraphs in $c$-closed graphs, 2020\.
  * [23] T. Koana, C. Komusiewicz, and F. Sommer.  Computing dense and sparse subgraphs of weakly closed graphs, 2020.
  * [24] T. Koana, C. Komusiewicz, and F. Sommer.  Exploiting $\mathbf{c}$-closure in kernelization algorithms for graph problems, 2020.
  * [25] T. Koana and A. Nichterlein.  Detecting and enumerating small induced subgraphs in $c$-closed graphs, 2020.
  * [26] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal.  Stochastic models for the web graph.  In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS ’00, pages 57–, Washington, DC, USA, 2000. IEEE Computer Society.
  * [27] T. Lou, J. Tang, J. Hopcroft, Z. Fang, and X. Ding.  Learning to predict reciprocity and triadic closure in social networks.  ACM Transactions on Knowledge Discovery from Data (TKDD), 7, 07 2013\.
  * [28] A. Mcgregor, D. Tench, S. Vorotnikova, and H. T. Vu.  Densest subgraph in dynamic graph streams.  In MFCS, 2015.
  * [29] I. S. K. N. C. D. A. U. Milo R, Shen-Orr S.  Network motifs: simple building blocks of complex networks.  Science, 2002.
  * [30] M. Mitzenmacher, J. W. Pachocki, R. Peng, C. E. Tsourakakis, and S. C. Xu.  Scalable large near-clique detection in large-scale networks via sampling.  In KDD, 2015.
  * [31] M. E. J. Newman.  Modularity and community structure in networks,.  pages 8577–8582, 2006.
  * [32] T. Opsahl.  Triadic closure in two-mode networks: Redefining the global and local clustering coefficients.
  * [33] F. G. W. L. S. G. E. J. pennock, D. M. and C. L. Giles.  Winners don’t take all: Characterizing the competition for links on the web.  Proceedings of the National Academy of Sciences, 99, 8:5207–5211, 2002.
  * [34] G. Robins, P. Pattison, and P. Wang.  Closure, connectivity and degree distributions: Exponential random graph (p*) models for directed social networks.  Social Networks, 31:105–117, 2009.
  * [35] D. M. Romero and J. Kleinberg.  The directed closure process in hybrid social-information networks, with an analysis of link formation on twitter.  ArXiv, abs/1003.2469, 2010.
  * [36] T. Roughgarden and C. Seshadhri.  Distribution-free models of social networks, 2020.
  * [37] S. Sawlani and J. Wang.  Near-optimal fully dynamic densest subgraph.  ArXiv, abs/1907.03037, 2019.
  * [38] C. Tsourakakis.  The k-clique densest subgraph problem.  In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 1122–1132, Republic and Canton of Geneva, Switzerland, 2015. International World Wide Web Conferences Steering Committee.
  * [39] C. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. Tsiarli.  Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees.  In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, pages 104–112, New York, NY, USA, 2013. ACM.
  * [40] C. E. Tsourakakis.  A novel approach to finding near-cliques: The triangle-densest subgraph problem, 2014.
  * [41] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow.  The anatomy of the facebook social graph.  ArXiv, abs/1111.4503, 2011.
  * [42] B. X. X. F. e. a. Wang, W.  From triadic closure to conference closure: the role of academic conferences in promoting scientific collaborations.  Scientometrics, 2017.
  * [43] D. Watts and S. Strogatz.  dynamics of small-world networks.  volume 393:440–442, 1998.
  * [44] S.-H. Yook, H. Jeong, and A.-L. Barabási.  Modeling the internet’s large-scale topology.  Proceedings of the National Academy of Sciences of the United States of America, 99(21):13382–13386, 2002.

###  .1 Dataset description

Here we provide information on the data sets used in our experiments. This
information is copied from pages on [3] describing the data set for
completeness.

Email-Eu-core network The network was generated using email data from a large
European research institution. The data set has been anonymized. There is an
edge $(u,v)$ in the network if person $u$ sent person $v$ at least one email.
The e-mails only represent communication between institution members (the
core), and the dataset does not contain incoming messages from or outgoing
messages to the rest of the world.

Collaboration networks We have two networks from collaboration network
datasets on [3]: CA-GrQc (General Relativity and Quantum Cosmology) and CA-
CondMat(General Relativity and Quantum Cosmology). These networks are from
e-print arXiv on the related field. If an author $i$ co-authored a paper with
author $j$, the graph contains a undirected edge from $i$ to $j$. If the paper
is co-authored by k authors this generates a completely connected (sub)graph
on $k$ nodes.

Epinions social network This is a who-trust-whom online social network of a a
general consumer review site Epinions.com. Members of the site can decide
whether to ”trust” each other. All the trust relationships interact and form
the Web of Trust which is then combined with review ratings to determine which
reviews are shown to the user.

Twitter This dataset consists of ’circles’ (or ’lists’) from Twitter. Twitter
data was crawled from public sources.

DBLP collaboration network The DBLP computer science bibliography provides a
comprehensive list of research papers in computer science. A co-authorship
network is constructed by connecting two authors if they publish at least one
paper together.

Amazon product co-purchasing network Network was collected by crawling Amazon
website. It is based on "Customers Who Bought This Item Also Bought" feature
of the Amazon website. If a product $i$ is frequently co-purchased with
product $j$, the graph contains an undirected edge from $i$ to $j$.

Pokec social network Pokec is the most popular on-line social network in
Slovakia. The popularity of network has not changed even after the coming of
Facebook. Pokec has been provided for more than 10 years and connects more
than 1.6 million people.

###  .2 Missing proofs

In this section, we present the missing proofs from the main body.

###### Proof of Lemma 3.3.

$\begin{array}[]{lll}\mathbb{E}[(D_{t+\delta}(u)-D_{t}(u))]\leq\\\
\sum_{i=1}^{\delta}\mathbb{E}[(D_{t+i}(u)-D_{t+i-1}(u))]\leq\\\
\sum_{i=1}^{\delta}\sum_{u\in V}(p_{u,v}(t+i-1))d_{t+i-1}(u,v)\leq\\\
\sum_{i=1}^{\delta}\sum_{u\in V}(d_{t+i-1}(u,v))^{2}p/K_{t}\\\ \\\ \text{~{}
Thus:}\\\ \mathbb{E}[(D_{t+\delta}(u)-D_{t}(u))]\leq\\\
(p/K_{t})\sum_{i=1}^{\delta}\sum_{u\in
V}\left(d_{t}(u,v)+\frac{4(i-1)pd(u)d(v)}{K_{t}}\right)^{2}\leq\\\
(p/K_{t})\sum_{i=1}^{\delta}\sum_{u\in
V}\left(d_{t}(u,v)^{2}+\frac{16(i-1)^{2}p^{2}d^{2}(u)d^{2}(v)}{K^{2}_{t}}+\right.\\\
\hskip 56.9055pt\left.\frac{8(i-1)pd(u)d(v)d_{t}(u,v)}{K_{t}}\right)\leq\\\
(p/K_{t})\sum_{i=1}^{\delta}\sum_{u\in
V}\left(d_{t}(u,v)^{2}+\frac{16(i-1)^{2}p^{2}d^{2}(u)d^{2}(v)}{K^{2}_{t}}+\right.\\\
\hskip 56.9055pt\left.\frac{8(i-1)pd(u)d(v)d_{t}(u,v)}{K_{t}}\right)\leq\\\
(p/K_{t})\sum_{i=1}^{\delta}\left(\zeta^{2}_{t}(v)+\frac{32(i-1)^{2}p^{2}d^{2}(v)K_{t}}{K^{2}_{t}}+\frac{8(i-1)pm_{t}d^{2}(v)}{K_{t}}\right)\leq\\\
(p/K_{t})\zeta^{2}_{t}(v)\left(1+\frac{32\delta^{3}p^{2}d^{2}(v)}{6K_{t}\zeta^{2}_{t}(v)}+\frac{4\delta^{2}pm_{t}d^{2}(v)}{K_{t}\zeta^{2}_{t}(v)}\right)\leq\\\
(p/K_{t})\zeta^{2}_{t}(v)\delta(1+\frac{8\delta
p}{d_{avg}}+\frac{6\delta^{2}p^{2}}{K_{t}}).\end{array}$

∎


# Minimal $L^{p}$-Solutions to Singular
Sublinear Elliptic Problems

Aye Chan May  School of Integrated Science and Innovation, Sirindhorn
International Institute of Technology, Thammasat University, Thailand
<EMAIL_ADDRESS>and  Adisak Seesanea  School of Integrated Science
and Innovation, Sirindhorn International Institute of Technology, Thammasat
University, Thailand<EMAIL_ADDRESS>
###### Abstract.

We solve the existence problem for the minimal positive solutions $u\in
L^{p}(\Omega,dx)$ to the Dirichlet problems for sublinear elliptic equations
of the form

$\begin{cases}\mathcal{L}u=\sigma u^{q}+\mu\qquad\quad\text{in}\quad\Omega,\\\
\liminf\limits_{x\rightarrow y}u(x)=0\qquad
y\in\partial_{\infty}\Omega,\end{cases}$

where $0<q<1$ and $\mathcal{L}u:=-\text{div}(\mathcal{A}(x)\nabla u)$ is a
linear uniformly elliptic operator with bounded measurable coefficients. The
coefficient $\sigma$ and data $\mu$ are nonnegative Radon measures on an
arbitrary domain $\Omega\subset\mathbb{R}^{n}$ with a positive Green function
associated with $\mathcal{L}$. Our techniques are based on the use of sharp
Green potential pointwise estimates, weighted norm inqualities, and norm
estimates in terms of generalized energy.

###### Key words and phrases:

sublinear elliptic equation, measure data, divergence form operator, Green
function

###### 2020 Mathematics Subject Classification:

Primary 35J61; Secondary 31B10, 42B37.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Function Spaces
    2. 2.2 Potentials
  3. 3 Construction of minimal $L^{p}$-solutions

##  1\. Introduction

Let $\Omega$ be a nonempty open connected set in $\mathbb{R}^{n}$ ($n\geq 3$)
which possesses a positive Green function $G$, and $\mathcal{M}^{+}(\Omega)$
denotes the class of all nonnegative Radon measures in $\Omega.$

We consider the Dirichlet problem

(1.1) $\begin{cases}\mathcal{L}u=\sigma u^{q}+\mu,\quad u\geq
0\quad\text{in}\quad\Omega,\\\ \liminf\limits_{x\rightarrow y}u(x)=0,\quad
y\in\partial_{\infty}\Omega\end{cases}$

in the sublinear case $0<q<1$ where $\sigma,\mu\in\mathcal{M}^{+}(\Omega)$.

Here $\mathcal{L}u:=-\text{div}(\mathcal{A}(x)\nabla u)$ with bounded
measurable coefficients is assumed to be uniformly elliptic, i.e.,
$\mathcal{A}:\Omega\to\mathbb{R}^{n\times n}$ is a real symmetric matrix-
valued function and there exists positive constants $m\leq M$ so that

$m|\xi|^{2}\leq\mathcal{A}(x)\xi\cdot\xi\leq M|\xi|^{2}$

for almost every $x\in\Omega$ and for every $\xi\in\mathbb{R}^{n}.$

In this paper, a solution $u$ to the problem (1.1) will be understood in the
sense that $u$ is an $\mathcal{A}$-superharmonic function on $\Omega$ such
that $u\in L^{q}_{loc}(\Omega,d\sigma)$ with $u\geq 0\;d\sigma$-a.e., and
satisfies the corresponding integral equations

(1.2) $u=\mathbf{G}(u^{q}d\sigma)+\mathbf{G}\mu\quad\text{in}\;\;\Omega.$

Here, the Green potential of a measure $\sigma\in\mathcal{M}^{+}(\Omega),$ is
defined by

$\mathbf{G}\sigma=\int_{\Omega}G(x,y)d\sigma(y),\quad x\in\Omega$

where a function $G:\Omega\times\Omega\to(0,\infty]$ called a positive Green
function associated with $\mathcal{L}$ in $\Omega.$

In the classical case $\mathcal{L}:=-\Delta$, these sublinear equations are
closely related to the study of porous medium equations, and were studied by
Brezis and Kamin [4] under the assumption of the bounded domain. The reader
can also see such a sublinear problem under various assumptions, for instance,
[1, 2, 5, 8, 9, 10, 11, 13], and the literature cited there.

There are many of the existing solutions theories to elliptic equations (1.1)
involving measures. For instance, Véron [14], considered problem (1.1) with
different boundary conditions: homogeneous Dirichlet boundary conditions
($u=0$ on $\partial\Omega$) and measure boundary conditions ($u=\mu$ on
$\partial\Omega$ where $\mu$ is Radon measure) under a smooth bounded domain
$\Omega.$

The homogeneous case ($\mu=0$) of problem (1.1) was investigated by Seesanea
and Verbitsky [11]. Nevertheless, when it comes to the case $\mu\geq 0$, the
relation between $\sigma$ and $\mu$ seems to be nontrivial in the scale of
Lebesgue space.

Furthermore, in [13], the author introduced the bilateral pointwise estimates
in terms of the intrinsic nonlinear potentials which can be utilized to obtain
the existence of a positive solution $u\in L^{p}(\Omega,dx)$ to (1.1).
Unfortunately, the definition of intrinsic nonlinear potential is defined in
terms of the best localized constant of related sublinaer weighted norm
inequality, which make it difficult to be verified.

In this present paper, we aims to provide a simple approach to overcome the
difficulties in [11] and deduce useful sufficient conditions on measures
$\sigma$ and $\mu$ for the existence of the positive minimal
$\mathcal{A}$-superharmonic solution $u\in L^{p}(\Omega,dx)$ to (1.1).

Our main results read as follows.

######  Theorem 1.1.

Let $\sigma,\mu\in\mathcal{M^{+}}(\Omega)$ such that $(\sigma,\mu)\neq(0,0)$,
$0<q<1$ and $G$ be a positive Green function associated with $\mathcal{L}$ in
$\Omega\subset\mathbb{R}^{n},n\geq 3$. Suppose also that
$\frac{n}{n-2}<p<\infty$,

(1.3) $\mathbf{G}\sigma\in L^{\frac{\gamma+q}{1-q}}(\Omega,d\sigma)$

and

(1.4) $\mathbf{G}\mu\in L^{\gamma}(\Omega,d\mu),$

with $\gamma=\frac{p(n-2)-n}{n}.$ Then there exists a positive minimal
$\mathcal{A}$-superharmonic solution $u\in L^{p}(\Omega,dx)$ to (1.1).

A sufficient condition for (1.3) and (1.4) with $\gamma=\frac{p(n-2)-n}{n}$ is
given by

(1.5) $\sigma\in L^{s_{1}}(\Omega,dx),\quad s_{1}=\frac{np}{n(1-q)+2p}$

and

(1.6) $\mu\in L^{s_{2}}(\Omega,dx),\quad s_{2}=\frac{np}{n+2p}$

where $\frac{n}{n-2}<p<\infty.$ Therefore, the following corollary can be
simply deduced from Theorem 1.1.

######  Corollary 1.2.

Under the assumptions of Theorem 1.1, if conditions (1.5) and (1.6) are
fulfilled, then there exists a positive minimal $\mathcal{A}$-superharmonic
solution $u\in L^{p}(\Omega,dx)$ to (1.1).

Observe that Corollary 1.2 was done by Boccardo and Orsina [3], with a
different proof, when $\Omega$ is a bounded domain in $\mathbb{R}^{n}$.

Organization of the paper

In Section 2, we organize some definitions and well-known research that are
relevant to our problem. In Section 3, we prove an estimate for $p$-th
integrability of potentials in terms of generalized Dirichlet energy and the
existence result of the problem by applying the previous estimate. Moreover,
we provide a sufficient condition for the existence of a positive solution to
(1.1).

Notation

We use the following notation in this paper. Let $\Omega$ be a connected open
subset in $\mathbb{R}^{n}$.

  * •

$D$:= a relatively compact open subset of $\Omega$.

  * •

$\mathcal{H}_{\mathcal{A}}(D)$:= the set of all continuous
$\mathcal{A}$-harmonic functions in $D.$

  * •

$\mathcal{C}_{0}^{\infty}(\Omega)$:= the set of all smooth compactly supported
functions on $\Omega$.

  * •

$\mathcal{M}^{+}(\Omega)$:= the set of all nonnegative Radon measures on
$\Omega$.

  * •

$L^{p}(\Omega,d\mu)$:= the $L^{p}$ space with respect to Radon measure
$\mu\in\mathcal{M}^{+}(\Omega).$

  * •

$L^{p}(\Omega,dx)$:= the $L^{p}$ space with respect to Lebesgue measure.

##  2\. Preliminaries

Thoughout, let $\Omega$ be a domain (connected open set) in $\mathbb{R}^{n}$.

###  2.1. Function Spaces

######  Definition 2.1.

For $1\leq p<\infty$ and $\mu\in\mathcal{M}^{+}(\Omega),$ we denote by
$L^{p}(\Omega,d\mu)$ the space of all real-valued measurable functions $f$ on
$\Omega$ such that

$\|f\|_{L^{p}(\Omega,d\mu)}=\big{(}\int_{\Omega}|f(x)|^{p}d\mu(x)\big{)}^{\frac{1}{p}}<\infty.$

######  Definition 2.2.

A function $u\in W^{1,2}_{loc}(\Omega)$ is said to be $\mathcal{A}$-harmonic
if $u$ satisfies the equation

$\mathcal{L}u=0\quad\text{in}\quad{\Omega}$

in the distributional sense, i.e.,

$\int_{\Omega}\mathcal{A}(x,\nabla u(x))\cdot\nabla\phi
dx=0,\quad\forall\phi\in\mathcal{C}^{\infty}_{0}(\Omega).$

The set of $\mathcal{A}$-harmonic functions on $\Omega$ is denoted by
$\mathcal{H}_{\mathcal{A}}(\Omega)$. Every $\mathcal{A}$-harmonic function $u$
has a continuous representative which coincides with $u$ a.e. see[7, Theorem
3.70].

######  Definition 2.3.

A function $u:\Omega\to(-\infty,+\infty]$ is $\mathcal{A}$-superharmonic if
$u$ is lower semicontinuous in $\Omega,$ $u\not\equiv+\infty$ in each
component of $\Omega,$ and for each $D\Subset\Omega$ and
$h\in\mathcal{C}(\bar{D})\cap\mathcal{H}_{\mathcal{A}}(D)$, the inequality
$u\geq h$ on $\partial D$ implies $u\geq h$ in $D.$

Let $u$ be an $\mathcal{A}$-superharmonic function in $\Omega.$ Then there
exists a unique measure $\omega\in\mathcal{M}^{+}(\Omega)$ such that

$\mathcal{L}u=\omega\quad\text{in}\quad\Omega$

in the distributional sense, i.e.,

$\int_{\Omega}\mathcal{A}(x,\nabla
u(x))\cdot\nabla\phi\;dx=\int_{\Omega}\phi\;d\omega,\quad\forall\phi\in\mathcal{C}^{\infty}_{0}(\Omega).$

The measure $\omega$ is called the Riesz measure associated with $u,$ see [7,
Theorem 21.2].

###  2.2. Potentials

Let $\gamma>0$ and $\omega\in\mathcal{M}^{+}(\Omega),$ and let $G$ be a
positive Green function associated with $\mathcal{L}$ on $\Omega.$ The
generalized Green energy, introduced in [9], of a mesure
$\omega\in\mathcal{M}^{+}{\Omega}$ is given by

$\mathcal{E}_{\gamma}[\omega]:=\int_{\Omega}(\mathbf{G}\omega)^{\gamma}d\omega.$

The first theorem gives an auxiliary fact that will be used in the proof of
the main lemma. The complete proof can be seen in [9, Lemma 3.3].

######  Theorem 2.4 (See [9]).

Let $0<\gamma<1$ and $\mu\in\mathcal{M^{+}}(\Omega)$. Suppose $G$ is a
positive Green function associated with $\mathcal{L}$ on $\Omega$. Suppose
$u:\mathbf{G}\mu\not\equiv\infty.$ Then $w:=u^{\gamma}$ is a positive
$\mathcal{A}$-superharmonic function on $\Omega,$ and $w=\mathbf{G}\omega,$
where $\omega\in\mathcal{M}^{+}(\Omega)$ is the Riesz measure of $w$.
Moreover,

$\mathcal{E}_{\gamma}[\mu]<+\infty\quad\text{if and only
if}\quad\mathcal{E}_{1}[\omega]<+\infty$

The next theorem provides sharp lower pointwise estimates for supersolutions
to sublinear elliptic equations due to Grigor’yan and Verbitsky, [6, Theorem
1.3].

######  Theorem 2.5 ( See [6]).

Let $0<q<1$ and $\sigma\in\mathcal{M^{+}}(\Omega)$. Suppose $G$ is a positive
Green function associated with $\mathcal{L}$ on $\Omega$. If $u\in
L^{q}_{loc}(\Omega,d\sigma)$ is a positive supersolution to the sublinear
integral equation

(2.1) $u\geq\mathbf{G}(u^{q}d\sigma),\quad x\in\Omega,$

then

(2.2)
$u(x)\geq(1-q)^{\frac{1}{1-q}}\big{[}\mathbf{G}\sigma(x)\big{]}^{\frac{1}{1-q}},\quad
x\in\Omega.$

We use the following pointwise iterated inequalities to derive the Green
potential estimate, see [6, Lemma 2.5].

######  Theorem 2.6 (See [6]).

Let $\sigma\in\mathcal{M^{+}}(\Omega)$ with $\sigma\not\equiv 0$, and let $G$
be the positive Green function associated with $\mathcal{L}$ on $\Omega.$ Then
the following estimates hold.
(i) If $t\geq 1,$ then

(2.3) $(\mathbf{G}\sigma)^{t}(x)\leq
t\mathbf{G}((\mathbf{G}\sigma)^{t-1}d\sigma)(x),\quad x\in\Omega.$

(ii) If $0<t\leq 1,$ then

(2.4) $(\mathbf{G}\sigma)^{t}(x)\geq
t\mathbf{G}((\mathbf{G}\sigma)^{t-1}d\sigma)(x),\quad x\in\Omega.$

The argument of finding a solution depends on the following weighted norm
inequalities of the $(s,r)$-type in the case where $0<r<s$ and $1<s<\infty,$
for operators $\mathbf{G}$:

(2.5) $\|\mathbf{G}(fd\sigma)\|_{L^{r}(\Omega,d\sigma)}\leq
c\|f\|_{L^{s}(\Omega,d\sigma)},\quad f\in L^{s}(\Omega,d\sigma),$

where $c$ is a positive constant independent of $f,$ for an arbitrary measure
$\sigma\in\mathcal{M^{+}}(\Omega),$ under certain assumptions on $G,$ see [12,
Theorem 1.1].

######  Theorem 2.7 (See [12]).

Let $\sigma\in\mathcal{M^{+}}(\Omega)$ with $\sigma\not\equiv 0,$ and let $G$
be the positive Green function associated with $\mathcal{L}$ on $\Omega.$
(i)If $1<s<\infty$ and $0<r<s,$ then the weighted norm inequality (2.5) is
fulfilled if and only if

(2.6) $\mathbf{G}\sigma\in L^{\frac{sr}{s-r}}(\Omega,d\sigma).$

(ii)If $0<q<1$ and $0<\gamma<\infty,$ then there exists a positive
(super)solution $u\in L^{\gamma+q}(\Omega,d\sigma)$ to sublinear integral
equation (2.1) if and only if the weighted norm inequality (2.5) is fulfilled
with $r=\gamma+q$ and $s=\frac{\gamma+q}{q},$ i.e.,

(2.7) $\|\mathbf{G}(fd\sigma)\|_{L^{\gamma+q}(\Omega,d\sigma)}\leq
c\|f\|_{L^{\frac{\gamma+q}{q}}(\Omega,d\sigma)},\quad f\in
L^{\frac{\gamma+q}{q}}(\Omega,d\sigma),$

or equivalently,

(2.8) $\mathbf{G}\sigma\in L^{\frac{\gamma+q}{1-q}}(\Omega,d\sigma).$

The next theorem gives the existence of a positive solution $u\in
L^{\gamma+q}(\Omega,d\sigma)(\gamma>0)$ to the integral equation (1.2) in the
sublinear case, which is claimed by Seesanea and Verbitsky, see [9, Theorem
4.2].

######  Theorem 2.8 (See [9]).

Let $0<q<1,0<\gamma<\infty$ and $\sigma,\mu\in\mathcal{M^{+}}(\Omega)$ with
$\sigma,\mu\not\equiv 0.$ Suppose $G$ is a positive quasi-symmetric lower
semicontinuous kernel on $\Omega\times\Omega,$ which satisfies the WMP. If
(1.3) and

(2.9) $\mathbf{G}\mu\in L^{\gamma+q}(\Omega,d\sigma)$

hold, then there exists a positive (minimal) solution $u\in
L^{\gamma+q}(\Omega,d\sigma)$ to (1.2). The converse statement is valid
without the quasi-symmetry assumption on $G.$

The following lemma was stated in [9, Lemma 4.3]. We can control the
interaction between the measure coefficient and measure data by applying the
following lemma.

######  Lemma 2.9 (See [9]).

Let $0<q<1,0<\gamma<\infty,$ and $\sigma,\mu\in\mathcal{M^{+}}(\Omega).$
Suppose $G$ is a positive Green function associated with $\mathcal{L}$ on
$\Omega.$ Then conditions (1.3) and (1.4) imply (2.9).

The next results are essential lemmas to prove positive solutions to (1.1)
when $\mu=0.$ The complete proofs of the following two lemmas can be found in
[11, Lemma 4.1 and Lemma 4.2].

######  Lemma 2.10 (See [11]).

Let $0<q<1,$ and let $\sigma\in\mathcal{M}^{+}(\Omega)$ with $\sigma\not\equiv
0.$ Suppose $G$ is a positive Green function associated with $\mathcal{L}$ on
$\Omega.$ Suppose that $\frac{n}{n-2}<p<\infty$ and the condition

(2.10) $\mathbf{G}\sigma\in L^{\frac{p}{1-q}}(\Omega,dx)$

is valid. Then

$\|\mathbf{G}(gd\sigma)\|_{L^{p}(\Omega,dx)}\leq
c\|\mathbf{G}\sigma\|^{\frac{1}{s^{\prime}}}_{L^{\frac{p}{1-q}}(\Omega,dx)}\|f\|_{L^{s}(\Omega,d\sigma)},\quad
f\in L^{s}(\Omega,d\sigma),$

where $c$ is a positive constant independent of $f$ and $q$ and
$s=\frac{p(n-2)-n(1-q)}{nq}.$

######  Lemma 2.11 (See [11]).

Let $0<q<1,$ and let $\sigma\in\mathcal{M}^{+}(\Omega)$ with $\sigma\not\equiv
0.$ Suppose $G$ is a positive Green function associated with $\mathcal{L}$ on
$\Omega$. If $\frac{n}{n-2}<p<\infty,$ then (1.3) with
$\gamma=\frac{p(n-2)-n}{n}$ implies (2.10). In fact,

$\|\mathbf{G}\sigma\|_{L^{\frac{p}{1-q}}(\Omega,dx)}\leq\tilde{C}\big{\|}\mathbf{G}\sigma\big{\|}_{L^{\frac{\gamma+q}{1-q}}(\Omega,d\sigma)}^{\frac{\gamma+q}{\gamma+1}}$

where $\tilde{C}$ is a positive constant depending on $\gamma$ and $q$.

##  3\. Construction of minimal $L^{p}$-solutions

In this section, we prove our main result stated Theorem 1.1 and its
consequence in Corollary 1.2.

The following lemma is one of the key ingredients in our approach.

######  Lemma 3.1.

Let $0<\gamma<\infty$ and $0<q<1.$ Suppose $G$ is a positive Green function
associated with $\mathcal{L}$ in $\Omega\subset\mathbb{R}^{n},n\geq 3$. Let
$\mu\in\mathcal{M}^{+}(\Omega)$ such that $\mathbf{G}\mu\not\equiv\infty.$ If
$\omega\in\mathcal{M}^{+}(\Omega)$ is a Riesz measure of the
$\mathcal{A}$-superharmonic function $(\mathbf{G}\mu)^{1-q},$ then

$\mathcal{E}_{\frac{\gamma+q}{1-q}}[\omega]\leq C\mathcal{E}_{\gamma}[\mu]$

where $C$ is a positive constant depending on $\gamma$ and $q.$

###### Proof.

We have $w:=(\mathbf{G}\mu)^{1-q}$ is a positive $\mathcal{A}$-superharmonic
function in $\Omega$, and $w:=\mathbf{G}\omega$ where
$\omega\in\mathcal{M}^{+}(\Omega)$ is a Riesz measure of $w.$ Consider two
cases as follows:

  * •

Case:$\gamma+q>1$.

Applying the iterated inequality (2.3) with $t=\gamma+q$, together with
Fubini’s theorem and Hölder’s inequality with the exponents
$\frac{\gamma}{\gamma+q-1}$ and $\frac{\gamma}{1-q},$ we obtain

$\displaystyle\mathcal{E}_{\frac{\gamma+q}{1-q}}[\omega]=\int_{\Omega}(\mathbf{G}\omega)^{\frac{\gamma+q}{1-q}}d\omega$
$\displaystyle=\int_{\Omega}(\mathbf{G}\mu)^{\gamma+q}d\omega$
$\displaystyle\leq
C\int_{\Omega}\mathbf{G}((\mathbf{G}\mu)^{\gamma+q-1}d\mu)d\omega$
$\displaystyle\leq
C\Big{(}\int_{\Omega}(\mathbf{G}\mu)^{\gamma}d\mu\Big{)}^{\frac{\gamma+q-1}{\gamma}}\Big{(}\int_{\Omega}(\mathbf{G}\omega)^{\frac{\gamma}{1-q}}d\mu\Big{)}^{\frac{1-q}{\gamma}}$
$\displaystyle=C\int_{\Omega}(\mathbf{G}\mu)^{\gamma}d\mu$
$\displaystyle=C\mathcal{E}_{\gamma}[\mu]$

  * •

Case:$\gamma+q\leq 1$.

Write

$\int_{\Omega}(\mathbf{G}\mu)^{\gamma+q}d\omega=\int_{\Omega}(\mathbf{G}\mu)^{\gamma+q}F^{a-1}F^{1-a}d\omega,$

where $a=\gamma+q$ and $F$ is a positive $\omega$-measurable function to be
determined later. Applying Hölder’s inequality with the exponents
$\frac{1}{a}$ and $\frac{1}{1-a}$, we get

$\displaystyle\mathcal{E}_{\frac{\gamma+q}{1-q}}[\omega]=\int_{\Omega}(\mathbf{G}\omega)^{\frac{\gamma+q}{1-q}}d\omega$
$\displaystyle=\int_{\Omega}(\mathbf{G}\mu)^{\gamma+q}F^{a-1}F^{1-a}d\omega$
$\displaystyle\leq\Big{(}\int_{\Omega}(\mathbf{G}\mu)^{\frac{\gamma+q}{a}}F^{\frac{a-1}{a}}d\omega\Big{)}^{a}\Big{(}\int_{\Omega}Fd\omega\Big{)}^{1-a}$

Setting $F=(\mathbf{G}\omega)^{\frac{\gamma+q}{1-q}}$.

(3.1)
$\Big{(}\mathcal{E}_{\frac{\gamma+q}{1-q}}[\omega]\Big{)}^{\gamma+q}\leq\Big{(}\int_{\Omega}(\mathbf{G}\mu)\big{(}\mathbf{G}\omega\big{)}^{(\frac{\gamma+q}{1-q})(\frac{\gamma+q-1}{\gamma+q})}d\omega\Big{)}^{\gamma+q}$

The right-hand side of (3.1) is estimated by using Fubini’s theorem, followed
by inequality (2.4) with $t=\frac{\gamma}{1-q}$

$\displaystyle\mathcal{E}_{\frac{\gamma+q}{1-q}}[\omega]\leq\int_{\Omega}\mathbf{G}(\big{(}\mathbf{G}\omega\big{)}^{\frac{\gamma+q-1}{1-q}}d\omega)d\mu$
$\displaystyle\leq C\int_{\Omega}(\mathbf{G}\omega)^{\frac{\gamma}{1-q}}d\mu$
$\displaystyle=C\int_{\Omega}(\mathbf{G}\mu)^{\gamma}d\mu$
$\displaystyle=\mathcal{E}_{\gamma}[\mu].$

This completes the proof of the lemma. ∎

The following lemma gives Green potentials norm estimates in terms of
generalized energy.

######  Lemma 3.2.

Let $G$ be a positive Green function associated with $\mathcal{L}$ in
$\Omega\subset\mathbb{R}^{n}$. Let $\mu\in\mathcal{M}^{+}(\Omega)$ such that
$\mathbf{G}\mu\not\equiv\infty.$ Then, for $0<\gamma<\infty,$
$\mathbf{G}\mu\in L^{\gamma}(\Omega,d\mu)$ implies $\mathbf{G}\mu\in
L^{p}(\Omega,dx)$, i.e.,

$\|\mathbf{G}\mu\|_{L^{p}(\Omega,dx)}\leq
c\Big{(}\mathcal{E}_{\gamma}[\mu]\Big{)}^{\frac{1}{\gamma+1}}$

where $p=\frac{n(1+\gamma)}{n-2}$ and $c$ is a positive constant depending on
$\gamma$.

###### Proof.

Notice that $w:=(\mathbf{G}\mu)^{1-q}$ with $0<q<1$ is a positive
$\mathcal{A}$-superharmonic function on $\Omega$ since
$\mathbf{G}\mu\not\equiv+\infty,$ and $w:=\mathbf{G}\omega,$ where
$\omega\in\mathcal{M}^{+}(\Omega)$ is the Riesz measure of $w,$ see [9].

Applying the Lemma 3.1 together with Lemma 2.11, we get the desired estimate,

$\|\mathbf{G}\mu\|_{L^{p}(\Omega,dx)}=\big{\|}\mathbf{G}\omega\big{\|}^{\frac{1}{1-q}}_{L^{\frac{p}{1-q}}(\Omega,dx)}\leq\tilde{C}\big{\|}\mathbf{G}\omega\big{\|}^{\frac{\gamma+q}{(\gamma+1)(1-q)}}_{L^{\frac{\gamma+q}{1-q}}(\Omega,d\omega)}\leq\tilde{C}C\big{\|}\mathbf{G}\mu\big{\|}_{L^{\gamma}(\Omega,d\mu)}^{\frac{\gamma}{\gamma+1}}.$

where $\tilde{C}$ and $C$ are constants in Lemma 2.11 and Lemma 3.1
respectively. ∎

We are now ready to prove the main theorem of this work.

###### Proof of Theorem 1.1.

Suppose that (1.3) and (1.4) hold for $\gamma=\frac{p(n-2)-n}{n}.$ The
condition (2.9) is satisfied by Lemma 2.9. As a result, according to Theorem
2.8, the integral equation

$u=\mathbf{G}(u^{q}d\sigma)+\mathbf{G}\mu\quad\text{in}\quad\Omega$

has a positive solution $u\in L^{\gamma+q}(\Omega,d\sigma).$ In order to get
solution $u\in L^{p}(\Omega,dx),$ we combine Lemma 2.10, Lemma 2.11 and Lemma
3.2. Then, we find that

$\displaystyle\|u\|_{L^{p}(\Omega,dx)}$
$\displaystyle\leq\|\mathbf{G}(u^{q}d\sigma)\|_{L^{p}(\Omega,dx)}+\|\mathbf{G}\mu\|_{L^{p}(\Omega,dx)}$
$\displaystyle\leq
C\|\mathbf{G}\sigma\|_{L^{\frac{\gamma+q}{1-q}}(\Omega,d\sigma)}\;\|u^{q}\|_{L^{\frac{\gamma+q}{q}}(\mathbb{R}^{n},\,d\sigma)}+c\Big{(}\int_{\Omega}(\mathbf{G}\mu)^{\gamma}\,d\mu\Big{)}^{\frac{1}{\gamma+1}}$
$\displaystyle=C\|u\|^{q}_{L^{\gamma+q}(\Omega,\,d\sigma)}<+\infty.$

This shows that there exists a positive solution $u\in L^{p}(\Omega,dx)$ to
(1.1) ∎

We finish this paper by providing a proof of Corollary 1.2. The following
proof is mainly influenced by Seesanea and Verbitsky [9] and by Boccardo and
Orsina [3].

###### Proof of Corollary 1.2.

Setting $\gamma=\frac{p(n-2)-n}{n}$. Then $s_{1}=\frac{np}{n(1-q)+2p}>1$. By
Hölder inequality,

(3.2)
$\int_{\Omega}\big{(}\mathbf{G}\sigma\big{)}^{\frac{\gamma+q}{1-q}}d\sigma\leq\big{\|}\mathbf{G}\sigma\big{\|}^{\frac{\gamma+q}{1-q}}_{L^{(\frac{\gamma+q}{1-q})s^{\prime}_{1}}(\Omega,dx)}\|\sigma\|_{L^{s_{1}}(\Omega,dx)},$

where $s^{\prime}_{1}=\frac{np}{p(n-2)-n(1-q)}$ is the conjugate of $s_{1}$.
We see that

$\frac{1}{s_{1}}+\frac{1}{\big{(}\frac{\gamma+q}{1-q}\big{)}s^{\prime}_{1}}=\frac{2}{n}.$

Appealing to Hardy-Littlewood-Sobolev inequality,

(3.3)
$\begin{split}\big{\|}\mathbf{G}\sigma\big{\|}_{L^{\big{(}\frac{\gamma+q}{1-q}\big{)}s^{\prime}_{1}}(\Omega,dx)}\lesssim\big{\|}\mathbf{G}\tilde{\sigma}\big{\|}_{L^{\big{(}\frac{\gamma+q}{1-q}\big{)}s^{\prime}_{1}}(\mathbb{R}^{n},dx)}&\lesssim\|\tilde{\sigma}\|_{L^{s_{1}}(\mathbb{R}^{n},dx)}\\\
&=\|\sigma\|_{L^{s_{1}}(\Omega,dx)}.\end{split}$

Here, $\tilde{\sigma}$ is the zero extension of $\sigma$ to $\mathbb{R}^{n}$.
Thus, by (3.2) and (3.3),

$\big{\|}\mathbf{G}\sigma\big{\|}_{L^{\frac{\gamma+q}{1-q}}(\Omega,d\sigma)}\leq\Big{(}\big{\|}\sigma\big{\|}^{\frac{\gamma+q}{1-q}+1}_{L^{s_{1}}(\Omega,dx)}\Big{)}^{\frac{1-q}{\gamma+q}}=\big{\|}\sigma\big{\|}^{\frac{\gamma+1}{\gamma+q}}_{L^{s_{1}}(\Omega,dx)}<+\infty$

Hence, (1.3) is valid. Similarly, we note that $s_{2}=\frac{np}{n+2p}>1$. By
Hölder inequality,

(3.4)
$\int_{\Omega}(\mathbf{G}\mu)^{\gamma}d\mu\leq\|\mathbf{G}\mu\|^{\gamma}_{L^{\gamma
s^{\prime}_{2}}(\Omega,dx)}\|\mu\|_{L^{s_{2}}(\Omega,dx)}$

where $s^{\prime}_{2}=\frac{s_{2}}{s_{2}-1}$. We see that

$\frac{1}{s_{2}}+\frac{1}{\gamma s^{\prime}_{2}}=\frac{2}{n}.$

Taking Hardy-Littlewood-Sobolev inequality,

(3.5) $\|\mathbf{G}\mu\|_{L^{\gamma
s^{\prime}_{2}}(\Omega,dx)}\lesssim\|\mathbf{G}\tilde{\mu}\|_{L^{\gamma
s^{\prime}_{2}}(\mathbb{R}^{n},dx)}\lesssim\|\tilde{\mu}\|_{L^{s_{2}}(\mathbb{R}^{n},dx)}=\|\mu\|_{L^{s_{2}}(\Omega,dx)},$

where $\tilde{\mu}$ is the zero extension of $\mu$ to $\mathbb{R}^{n}$. Thus,
by (3.4) and (3.5),

$\|\mathbf{G}\mu\|_{L^{\gamma}(\Omega,d\mu)}\leq\big{(}\|\mu\|^{\gamma+1}_{L^{\gamma}(\Omega,dx)}\big{)}^{\frac{1}{\gamma}}<+\infty.$

Therefore, (1.4) is fulfilled. Consequently, Theorem 1.1 yields the existence
of the minimal positive solution $u\in L^{p}(\Omega,dx)$ to (1.1). ∎

## Acknowledgments

This study was supported by Thammasat University Research Fund, Contract No.
TUFT 52/2566. A.C.M. gratefully acknowledges financial support from the
Excellent Foreign Student (EFS) scholarship, Sirindhorn International
Institute of Technology (SIIT), Thammasat University.

## References

  * [1] P. Bénilan and H. Brezis.  Nonlinear problems related to the Thomas-Fermi equation.  J. Evol. Equ., 3(4):673–770, 2003.
  * [2] P. Benilan, H. Brézis, and M. G. Crandall.  A semilinear equation in $L^{1}(\mathbb{R}^{N})$.  Ann. Sc. Norm. Super. Pisa, Cl. Sci., IV. Ser., 2:523–555, 1975\.
  * [3] L. Boccardo and L. Orsina.  Sublinear equations in $L^{s}$.  Houston J. Math., 20(1):99–114, 1994.
  * [4] H. Brézis and S. Kamin.  Sublinear elliptic equations in $\mathbb{R}{}^{n}$.  Manuscr. Math., 74(1):87–106, 1992.
  * [5] D. Cao and I. Verbitsky.  Nonlinear elliptic equations and intrinsic potentials of Wolff type.  J. Funct. Anal., 272(1):112–165, 2017.
  * [6] A. Grigor’yan and I. Verbitsky.  Pointwise estimates of solutions to nonlinear equations for nonlocal operators.  Ann. Sc. Norm. Super. Pisa, Cl. Sci. (5), 20(2):721–750, 2020.
  * [7] T. Kilpeläinen, J. Heinonen, and O. Martio.  Nonlinear Potential Theory of Degenerate Elliptic Equations.  01 2006.
  * [8] S. Quinn and I. E. Verbitsky.  A sublinear version of Schur’s lemma and elliptic PDE.  Anal. PDE, 11(2):439–466, 2018.
  * [9] A. Seesanea and I. E. Verbitsky.  Solutions to sublinear elliptic equations with finite generalized energy.  Calc. Var. Partial Differ. Equ., 58(1):21, 2019.  Id/No 6.
  * [10] A. Seesanea and I. E. Verbitsky.  Finite energy solutions to inhomogeneous nonlinear elliptic equations with sub-natural growth terms.  Adv. Calc. Var., 13(1):53–74, 2020.
  * [11] A. Seesanea and I. E. Verbitsky.  Solutions in Lebesgue spaces to nonlinear elliptic equations with subnatural growth terms.  St. Petersbg. Math. J., 31(3):557–572, 2020.
  * [12] I. E. Verbitsky.  Sublinear equations and Schur’s test for integral operators.  In 50 years with Hardy spaces. A tribute to Victor Havin, pages 467–484. Cham: Birkhäuser, 2018.
  * [13] I. E. Verbitsky.  Global pointwise estimates of positive solutions to sublinear equations.  St. Petersbg. Math. J., 34(3):531–556, 2023.
  * [14] L. Véron.  Elliptic equations involving measures.  In Handbook of differential equations: Stationary partial differential equations. Vol. I., pages 593–712. Amsterdam: Elsevier/North-Holland, 2004.