Fitzpatrick function for generalized monotone operators

Mohammad Hossein Alizadeh∗111e-mail<EMAIL_ADDRESS>

∗Department of Mathematics, Institute for Advanced Studies in Basic Sciences
(IASBS), P.O. Box 45195-1159, Zanjan, Iran

Abstract. We define the Fitzpatrick function of a $\sigma$-monotone operator
in a way similar to the original definition given by Fitzpatrick. We show that
some well-known properties of Fitzpatrick function remain valid for the larger
class of premonotone operators. Also, we find some conditions under which the
Fitzpatrick function of a $\sigma$-monotone operator is proper, and give some
results in Hilbert spaces.

Keywords: Fitzpatrick function; maximal monotone operator; generalized
monotone operator

Mathematics Subject Classification : 47H05, 49J53, 47H04.

##  1 Introduction

The literature on monotone and generalized monotone operators is quite
extensive. These notions have been found appropriate in various branches of
mathematics such as operator theory, PDE, SDE, differentiability theory of
convex functions and nonlinear functional analysis.

The notion of pre-monotone operators for the finite-dimensional case is
introduced in [11]. The class of pre-monotone operators includes many
important classes of operators such as monotone and $\varepsilon$-monotone
operators but also contains many more: for example, if $T$ is monotone and $R$
is globally bounded, then $T+R$ is premonotone. In Banach spaces, some basic
properties of pre-monotone operators such as local boundedness, generalization
of the L. Vesely theorem are studied in [3]. Also in [1] some results on the
sum and difference of the $\sigma$-monotone operators, and relations between
the $\sigma$-monotonicity and $\sigma$-convexity, are investigated.

The Fitzpatrick function of a monotone operator was introduced in [12] by
Fitzpatrick. Around 13 years later, a convex representation (Fitzpatrick
function) of maximal monotone operators was rediscovered by Martinez-Legaz and
Théra [13]. Burachik and Svaiter [8] also rediscovered Fitzpatrick functions
and studied the whole family of lower semicontinuous and convex functions
associated with a given maximal monotone operator. The Fitzpatrick function
makes a bridge between the results on convex functions and results on maximal
monotone operators ( see [4, 5, 6, 14] and the references therein). The
Fitzpatrick function was also used for deterministic and stochastic
differential equations driven by multivalued maximal monotone operators [15].
Recently, Fitzpatrick functions (or “Fitzpatrick transforms”) were proved to
be a valuable tool in the study of monotone bifunctions (see [2], [7] and
[10]). Moreover, very recently a generalization of the strong Fitzpatrick
inequality is studied in [9].

In this paper we introduce the Fitzpatrick function of a $\sigma$-monotone
operator and we investigate some properties of this function. We hope that the
Fitzpatrick function will be a tool for linking maximal $\sigma$-monotone
theory to convex analysis and add to their lure.

The rest of the paper is organized as follows: The next section contains some
notation, and facts on $\sigma$-monotone operators, and Fitzpatrick function.
In Section 3 after defining the Fitzpatrick function of a $\sigma$-monotone
operator, we show that for a $\sigma$-monotone operator, the inequality
$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\left\langle
x^{\ast},x\right\rangle$ holds for all $\left(x,x^{\ast}\right)\in X\times
X^{\ast}$ and we have the equality if
$\left(x,x^{\ast}\right)\in\operatorname*{gr}T$ and $\sigma\left(x\right)=0.$
Also we find some conditions under which $\mathcal{F}_{T}$ is proper . In
Section 4 we provide some kind of surjectivity results on Hilbert spaces. We
conclude the paper by presenting some examples and a related remark.

##  2 Preliminaries

Suppose that $X$ is a real Banach space, with topological dual space
$X^{\ast}$. We will denote the duality pairing by
$\left\langle\cdot,\cdot\right\rangle$. Given an operator $T:X\rightarrow
2^{X^{\ast}}$, its domain is $D\left(T\right)=\left\\{x\in
X:T\left(x\right)\neq\emptyset\right\\},$ its range

$R\left(T\right)=\left\\{x^{\ast}\in X^{\ast}:\exists x\in X\text{ s.t.
}x^{\ast}\in T\left(x\right)\right\\}$

and its graph $\operatorname{gr}T:=\left\\{\left(x,x^{\ast}\right)\in X\times
X^{\ast}:x^{\ast}\in T\left(x\right)\right\\}.$

Recall that $T$ is said to be monotone if for every $x,y\in D\left(T\right),\
x^{\ast}\in T\left(x\right)$ and $y^{\ast}\in T\left(y\right)$,

$\langle x^{\ast}-y^{\ast},\ x-y\rangle\geq 0,$

and $T$ is said to be maximal monotone if its graph is not properly included
in any other monotone graph.

For a monotone operator $T$, its Fitzpatrick function introduced in [12] is
defined by

$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\sup\left\\{\left\langle
x^{\ast},y\right\rangle+\left\langle
y^{\ast},x-y\right\rangle:\left(y,y^{\ast}\right)\in\operatorname{gr}T\right\\}.$

It is a lower semicontinuous (lsc from now on) and convex function.

###### Proposition 1

[12] For a maximal monotone operator $T:X\rightarrow 2^{X^{\ast}}$ one has

$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\left\langle
x^{\ast},x\right\rangle\quad\forall\left(x,x^{\ast}\right)\in X\times
X^{\ast},$

and the equality holds if and only if
$\left(x,x^{\ast}\right)\in\operatorname{gr}T.$

###### Definition 2

(i) Given an operator $T:X\rightarrow 2^{X^{\ast}}$ and a map
$\sigma:D\left(T\right)\rightarrow\mathbb{R}_{+}$, $T$ is said to be
$\sigma$_-monotone_ if for every $x,y\in D(T),\ x^{\ast}\in T\left(x\right)$
and $y^{\ast}\in T\left(y\right)$,

$\langle x^{\ast}-y^{\ast},\
x-y\rangle\geq-\min\\{\sigma(x),\sigma(y)\\}\|x-y\|.$ (1)

(ii) An operator $T$ is called _pre-monotone_ if it is $\sigma$-monotone for
some $\sigma:D\left(T\right)\rightarrow\mathbb{R}_{+}$.

(iii) A $\sigma$-monotone operator $T$ is called _maximal_ $\sigma$_-monotone_
, if for every operator $T^{\prime}$ which is $\sigma^{\prime}$-monotone with
$\operatorname*{gr}T\subseteq\operatorname*{gr}T^{\prime}$ and
$\sigma^{\prime}$ an extension of $\sigma$, one has $T=T^{\prime}$.

As for the monotone case, each $\sigma$-monotone operator has a maximal
$\sigma$-monotone extension [11].

###### Definition 3

Let $A$ be a subset of $X$. Given a mapping
$\sigma:A\rightarrow\mathbb{R}_{+}$, two pairs $(x,x^{\ast}),(y,y^{\ast})\in
A\times X^{\ast}$ are $\sigma$-monotonically related if

$\langle
x^{\ast}-y^{\ast},x-y\rangle\geq-\min\\{\sigma(x),\sigma(y)\\}\|x-y\|.$

An equivalent condition for maximal $\sigma$-monotonicity, which we use in
Section 3, is stated next:

###### Proposition 4

[3] The $\sigma$-monotone operator $T:X\rightarrow 2^{X^{\ast}}$ is maximal
$\sigma$-monotone if and only if, for every point $(x_{0},x_{0}^{\ast})\in
X\times X^{\ast}$ and every extension $\sigma^{\prime}$ of $\sigma$ to
$D\left(T\right)\cup\left\\{x_{0}\right\\}$ such that $(x_{0},x_{0}^{\ast})$
is $\sigma$-monotonically related to all pairs
$(y,y^{\ast})\in\operatorname{gr}(T)$, we have
$(x_{0},x_{0}^{\ast})\in\operatorname{gr}(T)$.

The paper [11] contains some examples of maximal $\sigma$-monotone operators.

##  3 The Fitzpatrick function of $\sigma$-monotone operators

The definition we use for the Fitzpatrick function is exactly the same as for
monotone operators:

###### Definition 5

Let $X$ be a Banach space and $T:X\rightarrow 2^{X^{\ast}}$ be a
$\sigma$-monotone operator. The _Fitzpatrick function_ associated with $T$ is
the function $\mathcal{F}_{T}:X\times
X^{\ast}\rightarrow\mathbb{R}\cup\left\\{+\infty\right\\}$ defined by

$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\sup_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left(\left\langle
x^{\ast},y\right\rangle+\left\langle y^{\ast},x\right\rangle-\left\langle
y^{\ast},y\right\rangle\right).$

$\mathcal{F}_{T}$ is norm$\times$weak∗\- lsc and convex on $X\times X^{\ast}$.

We need the following lemma for proving Theorem 7.

###### Lemma 6

Suppose that $T$ is maximal $\sigma$-monotone for some
$\sigma:D\left(T\right)\rightarrow\mathbb{R}_{+}$. Then for all
$\left(x,x^{\ast}\right)\in X\times X^{\ast}$ we have

$\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle\leq 0.$ (2)

Proof. We consider two cases: If $(x,x^{\ast})\in\operatorname*{gr}T$, then
obviously

$\inf_{(y,y^{\ast})\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle\leq\left\langle
x^{\ast}-x^{\ast},x-x\right\rangle=0.$

If $\left(x,x^{\ast}\right)\notin\operatorname*{gr}T$, then we will show that

$\inf_{(y,y^{\ast})\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle<0.$ (3)

Indeed, if on the contrary (3) does not hold, then for all
$(y,y^{\ast})\in\operatorname*{gr}T$,

$\left\langle y^{\ast}-x^{\ast},y-x\right\rangle\geq 0.$

Consequently, for any extension $\sigma^{\prime}$ of $\sigma$ on
$D(T)\cup\\{x\\}$ and every $(y,y^{\ast})\in\operatorname*{gr}T$,

$\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle\geq-\min\\{\sigma^{\prime}(x),\sigma^{\prime}(y)\\}\left\|x-y\right\|.$

By Proposition 4 this implies that
$\left(x,x^{\ast}\right)\in\operatorname*{gr}T$, a contradiction. Thus (3)
holds. So (2) holds in all cases.

###### Theorem 7

Suppose that $T:X\rightarrow 2^{X^{\ast}}$ is a maximal $\sigma$-monotone
operator. Then

$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\left\langle
x^{\ast},x\right\rangle\qquad\forall\left(x,x^{\ast}\right)\in X\times
X^{\ast}.$ (4)

If $\left(x,x^{\ast}\right)\notin\operatorname*{gr}T$, then we have strict
inequality in (4). If $\left(x,x^{\ast}\right)\in\operatorname*{gr}T$ and
$\sigma\left(x\right)=0,$ then the equality holds.

Proof. Let $\left(x,x^{\ast}\right)\in X\times X^{\ast}.$ It can be easily
verified

$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle
x^{\ast},x\right\rangle-\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle.$ (5)

According to (2) we have
$\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle\leq 0.$ Thus
$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\left\langle
x^{\ast},x\right\rangle.$ Let
$\left(x,x^{\ast}\right)\notin\operatorname*{gr}T$, and assume in
contradiction that $\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle
x^{\ast},x\right\rangle.$ From (5) we get
$\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle=0$. But according to (3) it is not
possible. Now, suppose that $x^{\ast}\in T\left(x\right)$ and
$\sigma\left(x\right)=0.$ Then for each
$\left(y,y^{\ast}\right)\in\operatorname*{gr}T$

$\langle x^{\ast}-y^{\ast},\
x-y\rangle\geq-\min\\{\sigma(x),\sigma(y)\\}\|x-y\|=0.$

Therefore $\left\langle x^{\ast},y\right\rangle+\left\langle
y^{\ast},x\right\rangle-\left\langle y^{\ast},y\right\rangle\leq\left\langle
x^{\ast},x\right\rangle$. By taking the supremum over all
$\left(y,y^{\ast}\right)\in\operatorname*{gr}T$ we get
$\mathcal{F}_{T}\left(x,x^{\ast}\right)\leq\left\langle
x^{\ast},x\right\rangle$ and so
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle x^{\ast},x\right\rangle.$

###### Remark 8

  * •

Note that if $\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle
x^{\ast},x\right\rangle$, then indeed
$\left(x,x^{\ast}\right)\in\operatorname*{gr}T$ because when
$\left(x,x^{\ast}\right)\notin\operatorname*{gr}T$ by Theorem 7 we would have
strict inequality.

  * •

Note that

$\displaystyle x^{\ast}$ $\displaystyle\in
T\left(x\right)\Leftrightarrow\langle x^{\ast}-y^{\ast},\
x-y\rangle\geq-\min\\{\sigma(x),\sigma(y)\\}\|x-y\|\text{
}\forall\left(y,y^{\ast}\right)\in\operatorname*{gr}T$
$\displaystyle\Leftrightarrow\left\langle
x^{\ast},x\right\rangle+\min\\{\sigma(x),\sigma(y)\\}\|x-y\|$
$\displaystyle\geq\left\langle x^{\ast},y\right\rangle+\left\langle
y^{\ast},x\right\rangle-\left\langle
y^{\ast},y\right\rangle\quad\forall\left(y,y^{\ast}\right)\in\operatorname*{gr}T$
$\displaystyle\Leftrightarrow\left\langle x^{\ast},x\right\rangle+\sup_{y\in
D\left(T\right)}\\{\min\\{\sigma(x),\sigma(y)\\}\|x-y\|\\}$
$\displaystyle\geq\sup_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left(\left\langle
x^{\ast},y\right\rangle+\left\langle y^{\ast},x\right\rangle-\left\langle
y^{\ast},y\right\rangle\right)$ $\displaystyle\Leftrightarrow\left\langle
x^{\ast},x\right\rangle+\sup_{y\in
D\left(T\right)}\\{\min\\{\sigma(x),\sigma(y)\\}\|x-y\|\\}\geq\mathcal{F}_{T}\left(x,x^{\ast}\right).$

  * •

One can easily check that if $T$ and $S$ are $\sigma$-monotone operators and
$S$ is an extension of $T$ i.e.,
$\operatorname{gr}T\subseteq\operatorname{gr}S$, then
$\mathcal{F}_{T}\leq\mathcal{F}_{S}.$

Notice that in some cases the Fitzpatrick function can be $+\infty$ on
$X\times X^{\ast}$ as the following example shows.

###### Example 9

Suppose that $X$ is a Hilbert space and $T:X\rightarrow 2^{X}$ is an operator.
Assume that $D\left(T\right)$ contains a ray $L=\mathbb{R}z$ ($z\neq 0$) such
that for each $y\in L$, $\\{0,y_{0}^{\ast}\\}\subseteq T(y)$ where
$y_{0}^{\ast}$ is a fixed element, not identically zero on $L$. Then
$\mathcal{F}_{T}$ can not be proper.

Proof. Let $\left(x,x^{\ast}\right)\in X\times X^{\ast}$. First we suppose
that $x^{\ast}\neq 0$ on $L.$ Then $\left\langle x^{\ast},z\right\rangle\neq
0,$ and we can assume without loss of generality that $\left\langle
x^{\ast},z\right\rangle>0.$ Then take $y^{\ast}=0,$

$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\sup_{y\in L}\left\langle
x^{\ast},y\right\rangle\geq\lim_{n\rightarrow\infty}\left\langle
x^{\ast},nz\right\rangle=+\infty.$

If $x^{\ast}=0,$ then

$\displaystyle\mathcal{F}_{T}\left(x,x^{\ast}\right)$
$\displaystyle=\sup_{\left(y,y^{\ast}\right)\in\operatorname{gr}T}\left(\left\langle
y^{\ast},x-y\right\rangle\right)$ $\displaystyle\geq\left\langle
y_{0}^{\ast},x\right\rangle-\inf_{y\in L}\left\langle
y_{0}^{\ast},y\right\rangle.$

Again without loss of generality we may assume $\left\langle
y_{0}^{\ast},z\right\rangle$ is negative and then get $\inf_{y\in
L}\left\langle y_{0}^{\ast},y\right\rangle=-\infty.$Thus we conclude that
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=+\infty.$

According to the above example if the graph of a maximal $\sigma$-monotone
operator contains the lines $L\times\left\\{0^{\ast}\right\\}$ and
$L\times\left\\{y_{0}^{\ast}\right\\}$ and $y_{0}^{\ast}\neq 0$ on $L$, then
the Fitzpatrick function can be everywhere $+\infty.$ Indeed, take
$T:\mathbb{R}\rightarrow 2^{\mathbb{R}}$ to be defined by $T(x)=[0,1]\,$for
all $x\in\mathbb{R}$. One can see that this operator is $\sigma$-monotone with
$\sigma(x)=1$ for all $x$. In fact, it is maximal $\sigma$-monotone and
$\mathcal{F}_{T}\equiv+\infty$.

According to the Theorem 7 if $T$ is maximal $\sigma$-monotone, $(x,x^{\ast})$
in $\operatorname{gr}T$ and $\sigma(x)=0$, then
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle x^{\ast},x\right\rangle$
and so $\mathcal{F}_{T}\left(x,x^{\ast}\right)<\infty$.

Recall that [3], given an operator $T:X\rightarrow 2^{X^{\ast}}$, we define
the function
$\sigma_{T}:D\left(T\right)\rightarrow\mathbb{R}_{+}\cup\\{+\infty\\}$ by

$\sigma_{T}(x)=\inf\\{a\in\mathbb{R}_{+}:\left\langle
x^{\ast}-y^{\ast},x-y\right\rangle\geq-a\left\|x-y\right\|,\forall(y,y^{\ast})\in\operatorname*{gr}T,x^{\ast}\in
T(x)\\}.$ (6)

The following proposition shows that if the equality holds in Theorem 7 for
all $x^{\ast}\in T\left(x\right)$, then $\sigma_{T}\left(x\right)=0.$

###### Proposition 10

Suppose that $T:X\rightarrow 2^{X^{\ast}}$ is $\sigma$-monotone. Let $x\in X$
and for each $x^{\ast}\in T\left(x\right),$
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle x^{\ast},x\right\rangle,$
then $\sigma_{T}\left(x\right)=0.$

In particular, if $T$ is a single-valued $\sigma$-monotone, and $\
\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle x^{\ast},x\right\rangle,$
then $\sigma_{T}\left(x\right)=0.$

Proof. For every $x^{\ast}\in T(x)$ we have$\
\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\langle x^{\ast},x\right\rangle.$
Thus

$\left\langle x^{\ast},y\right\rangle+\left\langle
y^{\ast},x\right\rangle-\left\langle y,y^{\ast}\right\rangle\leq\left\langle
x^{\ast},x\right\rangle\qquad\forall\left(y,y^{\ast}\right)\in\operatorname{gr}T,x^{\ast}\in
T\left(x\right),$

Therefore

$0\leq\left\langle
x^{\ast}-y^{\ast},x-y\right\rangle\qquad\forall\left(y,y^{\ast}\right)\in\operatorname{gr}T,x^{\ast}\in
T\left(x\right).$ (7)

From (6) and (7) we get $\sigma_{T}\left(x\right)=0.$

According to the above proposition, for a maximal $\sigma$-monotone operator
$T$ if $\sigma_{T}\left(x\right)\neq 0,$ then
$\mathcal{F}_{T}\left(x,x^{\ast}\right)>\left\langle x^{\ast},x\right\rangle.$

In the following proposition, we find a sufficient condition, for finiteness
of the Fitzpatrick function.

###### Proposition 11

Suppose that $T:X\rightarrow 2^{X^{\ast}}$ is $\sigma$-monotone and set

$M:=\left\\{\left(x,x^{\ast}\right)\in\operatorname{gr}T:\sup_{y\in
D\left(T\right)}\left\\{\min\left\\{\sigma\left(x\right),\sigma\left(y\right)\right\\}\left\|x-y\right\|\right\\}<\infty\right\\}.$

Then $\operatorname*{co}M\subseteq D\left(\mathcal{F}_{T}\right).$

Proof. Assume that $\left(x,x^{\ast}\right)\in M.$ According to Remark 8 part
II, we have $\ \mathcal{F}_{T}\left(x,x^{\ast}\right)<\infty.$ Thus $M\subset
D\left(\mathcal{F}_{T}\right)$. On the other hand $\mathcal{F}_{T}$ is convex
so $D\left(\mathcal{F}_{T}\right)$ is also convex and so
$\operatorname*{co}M\subseteq D\left(\mathcal{F}_{T}\right).$

##  4 Some results on Hilbert spaces

From now on, $X$ is a Hilbert space.

###### Proposition 12

Assume that $T:X\rightarrow 2^{X}$ is $\sigma$-monotone. Suppose that
$R\left(I+T\right)=X.$ If $(y,y^{\ast})\in X\times X$ is
$\sigma$-monotonically related to $\operatorname{gr}T$, then there exists
$\left(x,x^{\ast}\right)\in\operatorname{gr}T,$ such that

$||x^{\ast}-y^{\ast}||=||x-y||\leq\sigma\left(x\right).$

Moreover, if $\sigma\left(x\right)=0,$ then
$(y,y^{\ast})\in\operatorname{gr}T$.

Proof. By assumption $R\left(I+T\right)=X,$ so we can find $x\in X$ such that
$y+y^{\ast}\in\left(I+T\right)\left(x\right)$. This means that there exists
$\left(x,x^{\ast}\right)\in\operatorname{gr}T$ such that
$y+y^{\ast}=x+x^{\ast}.$ From here we get

$y-x=x^{\ast}-y^{\ast}.$ (8)

On the other hand, $(y,y^{\ast})\in X\times X$ is $\sigma$-monotonically
related to $\operatorname{gr}T$. Thus

$-\sigma(x)\|x-y\|\leq\langle x^{\ast}-y^{\ast},x-y\rangle.$ (9)

From (8) and (9) we infer that

$-\sigma(x)\|x-y\|\leq-\langle x-y,x-y\rangle=-||x-y||^{2}.$

Therefore $||x-y||\leq\sigma\left(x\right).$

Now if $\sigma\left(x\right)=0,$ then form the above inequality and (8) we
conclude that $x=y$ and $x^{\ast}=y^{\ast}.$ Thus
$\left(y,y^{\ast}\right)\in\operatorname{gr}T$.

###### Corollary 13

Assume that $T:X\rightarrow 2^{X}$ is monotone. If $R\left(I+T\right)=X$, then
$T$ is maximal monotone.

For the proof of following fact, see [4, Corollary 15.17].

Fact 1: Suppose that $f:X\rightarrow\mathbb{R}\cup\left\\{+\infty\right\\}$ is
proper, convex, and lower semicontinuous. If
$f\left(\cdot\right)+\frac{1}{2}\left|\left|\cdot\right|\right|^{2}\geq 0,$
then there exists $x^{\ast}\in X$ such that

$f\left(x\right)+\frac{1}{2}\left|\left|x\right|\right|^{2}\geq\frac{1}{2}\left|\left|x+x^{\ast}\right|\right|^{2}.\qquad\forall
x\in X$

###### Proposition 14

Suppose that $T:X\rightarrow 2^{X}$ is maximal $\sigma$-monotone. Then there
exists $\left(z,z^{\ast}\right)\in X\times X$ such that

$\langle
x^{\ast}-z^{\ast},x-z\rangle\geq\frac{1}{2}||z+z^{\ast}||^{2}+\inf_{\left(y,y^{\ast}\right)\in\operatorname{gr}T}\left\langle
x^{\ast}-y^{\ast},\ x-y\right\rangle.\qquad\forall\left(x,x^{\ast}\right)\in
X\times X$

Proof. Let$\ T$ be a maximal $\sigma$-monotone operator. Then by Theorem 7

$\mathcal{F}_{T}\left(x,x^{\ast}\right)\geq\left\langle
x^{\ast},x\right\rangle\qquad\forall\left(x,x^{\ast}\right)\in X\times X.$

We equip $X\times X$ with the usual inner product
$\left\langle(x,y),(x^{\prime},y^{\prime})\right\rangle=\left\langle
x,x^{\prime}\right\rangle+\left\langle y,y^{\prime}\right\rangle$. Then for
each $\left(x,x^{\ast}\right)\in X\times X$

$\displaystyle\mathcal{F}_{T}\left(x,x^{\ast}\right)+\frac{1}{2}\left|\left|\left(x,x^{\ast}\right)\right|\right|^{2}$
$\displaystyle\geq\left\langle
x^{\ast},x\right\rangle+\frac{1}{2}\left|\left|\left(x,x^{\ast}\right)\right|\right|^{2}$
$\displaystyle=\frac{1}{2}\left|\left|x+x^{\ast}\right|\right|^{2}\geq 0.$

Since $\mathcal{F}_{T}:X\times
X\rightarrow\mathbb{R}\cup\left\\{+\infty\right\\}$ is proper, convex, and
lower semicontinuous, by using Fact 1 we find $\left(z^{\ast},z\right)\in
X\times X$ such that for each $\left(x,x^{\ast}\right)\in X\times X$ we have

$\displaystyle\mathcal{F}_{T}\left(x,x^{\ast}\right)+\frac{1}{2}\left|\left|\left(x,x^{\ast}\right)\right|\right|^{2}$
$\displaystyle\geq\frac{1}{2}\left|\left|\left(x,x^{\ast}\right)+\left(z^{\ast},z\right)\right|\right|^{2}$
$\displaystyle=\frac{1}{2}\left(||\left(x,x^{\ast}\right)||^{2}+||\left(z^{\ast},z\right)||^{2}+2\left\langle\left(x,x^{\ast}\right),\left(z^{\ast},z\right)\right\rangle\right).$

Now using (5), we get

$\left\langle
x^{\ast},x\right\rangle-\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle\geq\frac{1}{2}||\left(z^{\ast},z\right)||^{2}+\left\langle
z^{\ast},x\right\rangle+\left\langle x^{\ast},z\right\rangle.$

Therefore

$\left\langle x^{\ast},x\right\rangle-\left\langle
z^{\ast},x\right\rangle-\left\langle
x^{\ast},z\right\rangle\geq\inf_{\left(y,y^{\ast}\right)\in\operatorname*{gr}T}\left\langle
y^{\ast}-x^{\ast},y-x\right\rangle+\frac{1}{2}||\left(z^{\ast},z\right)||^{2}.$

By adding $\left\langle z^{\ast},z\right\rangle$ in the two sides of the above
inequality we obtain the desired inequality.

We conclude the paper by presenting two examples related to the Fitzpatrick
function of a pre-monotone operator.

###### Example 15

Consider the triangular function $T:\mathbb{R}\rightarrow\mathbb{R}$ defined
by $T\left(x\right):=\max\left\\{1-|x|,0\right\\}.$ Clearly $T$ is not
monotone but it is pre-monotone by Proposition 3.4 in [11]. Then
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\iota_{\left\\{0^{\ast}\right\\}}+\frac{1}{4}\left(x+1\right)^{2}$
where $\iota_{C}$ is the indicator function of $C.$

Proof. Fix $\left(x,x^{\ast}\right)\in\mathbb{R}\times\mathbb{R},$ by
definition

$\displaystyle\mathcal{F}_{T}\left(x,x^{\ast}\right)$
$\displaystyle=\sup\left\\{x^{\ast}y+y^{\ast}x-yy^{\ast}:\left(y,y^{\ast}\right)\in\operatorname{gr}T\right\\}$
$\displaystyle=\sup_{y\in\mathbb{R}}\left\\{x^{\ast}y+T\left(y\right)x-yT\left(y\right)\right\\}.$

Set $h\left(y\right)=x^{\ast}y+xT\left(y\right)-yT\left(y\right).$

1) If $|y|\geq 1,$ then $T\left(y\right)=0$ and so
$h\left(y\right)=x^{\ast}y$. Therefore

$\sup_{|y|\geq 1}h\left(y\right)=\left\\{\begin{array}[c]{cc}0&\text{if
}x^{\ast}=0,\\\ +\infty&\text{if }x^{\ast}\neq 0.\end{array}\right.$

2) If $y\in[0,1],$ then $T\left(y\right)=1-y$ and
$h\left(y\right)=x^{\ast}y+\left(x-y\right)\left(1-y\right)$. Thus
$\sup_{y\in\left[0,1\right]}h\left(y\right)=\max\left\\{x,x^{\ast}\right\\}.$

3) If $y\in[-1,0],$ then $T\left(y\right)=1+y$ and
$h\left(y\right)=x+\left(x^{\ast}+x-1\right)y-y^{2}$. We get
$\sup_{y\in\left[-1,0\right]}h\left(y\right)=\frac{1}{4}\left(\left(x+1\right)^{2}-x^{\ast}\right).$

Finally we have
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\left\\{\begin{array}[c]{cc}+\infty&\text{if
}x^{\ast}\neq 0,\\\ \frac{1}{4}\left(x+1\right)^{2}&\text{if
}x^{\ast}=0.\end{array}\right.$ In other words
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\iota_{\left\\{0^{\ast}\right\\}}+\frac{1}{4}\left(x+1\right)^{2}.$

###### Example 16

(Normal function) Suppose $X$ is $\mathbb{R}$ and let
$T\left(x\right)=\frac{1}{1+x^{2}}.$ Then $T$ is not monotone but it is
$\sigma$-monotone (for $\sigma=1).$ Moreover,
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\iota_{\left\\{0^{\ast}\right\\}}+\frac{1}{2\left(\sqrt{x^{2}+1}-x\right)}.$

Proof. Fix $\left(x,x^{\ast}\right)\in\mathbb{R}\times\mathbb{R}$. The
Fitzpatrick function of $T$ is

$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\sup_{y\in\mathbb{R}}\left\\{x^{\ast}y+T\left(y\right)x-yT\left(y\right)\right\\}.$

We define $h\left(y\right):=x^{\ast}y+\left(x-y\right)\frac{1}{1+y^{2}}.$ It
is easy to see that if $x^{\ast}\neq 0,$ then
$\sup_{y\in\mathbb{R}}h\left(y\right)=+\infty.$ Now for $x^{\ast}=0,$ a direct
calculation shows that the maximum is attend at $x-\sqrt{x^{2}+1}$ and so
$\sup_{y\in\mathbb{R}}h\left(y\right)=\frac{1}{2\left(\sqrt{x^{2}+1}-x\right)}.$Thus
we conclude that
$\mathcal{F}_{T}\left(x,x^{\ast}\right)=\sup_{y\in\mathbb{R}}h\left(y\right)=\left\\{\begin{array}[c]{cc}+\infty&\text{if
}x^{\ast}\neq 0,\\\ \frac{1}{2\left(\sqrt{x^{2}+1}-x\right)}&\text{if
}x^{\ast}=0.\end{array}\right.$

###### Acknowledgement 17

It is my great pleasure to thanks Professor Hadjisavvas for insightful
comments and various helpful discussions which led to considerable
improvements throughout the earlier draft of this manuscript. Also, I would
like to thank Professor Martinez-Legaz who motivated me to study the subject
of this paper.

## References

  * [1] M. H. Alizadeh and M. Roohi, _Some results on pre-monotone operators_ , accepted.
  * [2] M. H. Alizadeh and Hadjisavvas, _On the Fitzpatrick transform of a monotone bifunction_ , Optimization 62 (2013) 693–701.
  * [3] M. H. Alizadeh, N. Hadjisavvas and M. Roohi, _Local boundedness properties for generalized monotone operators_ , J. Convex Anal. 19 (2012) 49–61.
  * [4] H. H. Bauschke and P. L. Combettes, _Convex Analysis and Monotone Operator Theory in Hilbert Spaces,_ Springer (2011).
  * [5] H. H. Bauschke, D. A., McLaren and H. S. Sendov, _Fitzpatrick functions: Inequalities, examples and remarks on a problem of S. Fitzpatrick_ , J. Convex Anal. 13 (2006) 499-523.
  * [6] J. M. Borwein, _Fifty years of maximal monotonicity_. Optim. Lett. 4 (2010) 473–490.
  * [7] R.I. Bot and S.-M. Grad, _Approaching the maximal monotonicity of bifunctions via representative functions_. J. Convex Anal. 19 (2012) 713–724.
  * [8] R. S. Burachik and B. F. Svaiter, _Maximal monotone operators, convex functions and a special family of enlargements_ , Set-Valued Anal., 10(4) (2002) 297–316.
  * [9] L. M. Elias and J.-E. Martinez-Legaz, _A generalization of the strong Fitzpatrick inequality,_ Optimization, doi. 10.1080/02331934.2016.1179738 (2016).
  * [10] A. N. Iusem, _On the maximal monotonicity of diagonal subdifferential operators_. J. Convex Anal. 18 (2011) 489–503.
  * [11] A. N. Iusem, G. Kassay and W. Sosa, _An existence result for equilibrium problems with some surjectivity consequences_ , J. Convex Anal. 16 (2009) 807–826.
  * [12] S. Fitzpatrick, _Representing monotone operators by convex functions,_ in: Functional Analysis and Optimization, Workshop and Mini-conference, Canberra, Australia 1988, pp. 59–65, Proc. Center Math. Anal. Australian Nat. Univ. 20 (1988).
  * [13] G.-E. Martinez-Legaz and M. Thera, _A convex representation of maximal monotone operators_ , J. Nonlinear Convex Anal., 2() (2001) 243–247.
  * [14] J.-P. Penot and C. Zalinescu, _Some problems about the representation of monotone operators by convex functions_ , ANZIAM J. 47 (2005) 1-20.
  * [15] A. Rascanu and E. Rotenstein, _The Fitzpatrick Function – A Bridge between Convex Analysis and Multivalued Stochastic Differential Equations_. J. Convex Anal., 18 (2011) 105-138.


# Joint Slot and Power Optimization for Grant Free Random Access with Unknown
and Heterogeneous Device Activity

Alix Jeannerot  INSA Lyon, Inria, CITI, UR3720
69621 Villeurbanne, France
<EMAIL_ADDRESS>Malcolm Egan  Inria, INSA Lyon, CITI, UR3720
69621 Villeurbanne, France
<EMAIL_ADDRESS>Jean-Marie Gorce  INSA Lyon, Inria, CITI, UR3720
69621 Villeurbanne, France
<EMAIL_ADDRESS>
###### Abstract

Grant Free Random Access (GFRA) is a popular protocol in the Internet of
Things (IoT) to reduce the control signaling. GFRA is a framed protocol where
each frame is split into two parts: device identification; and data
transmission part which can be viewed as a form of Frame Slotted ALOHA (FSA).
A common assumption in FSA is device homogeneity; that is the probability that
a device seeks to transmit data in a particular frame is common for all
devices and independent of the other devices. Recent work has investigated the
possibility of tuning the FSA protocol to the statistics of the network by
changing the probability for a particular device to access a particular slot.
However, power control with a successive interference cancellation (SIC)
receiver has not yet been considered to further increase the performance of
the tuned FSA protocols. In this paper, we propose algorithms to jointly
optimize both the slot selection and the transmit power of the devices to
minimize the outage of the devices in the network. We show via a simulation
study that our algorithms can outperform baselines (including slotted ALOHA)
in terms of expected number of devices transmitting without outage and in term
of transmit power.

###### Index Terms:

ALOHA, resource allocation, power control, stochastic optimization

##  I Introduction

The selection of transmit resources with limited coordination between devices
and with the base station is a key problem in wireless multiple access
networks which lead to a family of protocols known as ALOHA. Slotted ALOHA [1]
protocols and most of its variants such as framed slotted ALOHA (FSA) [2],
coded slotted ALOHA (CSA) [3], irregular repetition slotted ALOHA (IRSA) [4],
assume that the network is homogeneous, meaning that devices are independent
and equally likely to transmit data. However within the context of modern
communication networks like Internet of Things or event-driven communication,
the probability that a device is active in a specific frame is likely to vary
from device to device.

A key question is whether exploiting knowledge of device heterogeneity can
improve resource utilization. To this end, new variants of Frame Slotted ALOHA
have been proposed, where the probability that a particular device chooses a
particular slot is not uniform but is optimized as a function of the
statistics of the network. In [5, 6], stochastic resource selection is
optimized based on the joint probability of activity of the devices.
Optimization is based on heuristics in [5] and by solving a quadratic program
in [6]. However both approaches require the knowledge at the base station of
the activity probability of the devices in the network. To relax this
assumption, the work in [7, 8] proposed to sequentially optimize the
stochastic resource allocation based only on the devices active in each frame,
achieved via projected stochastic gradient descent. Finally, in [9, 10], the
impact of imperfect estimation of device activity (e.g., via device
identification algorithms [11]) on the optimization is studied as well as
method to mitigate the effect of activity estimation errors.

Collisions arising from multiple devices utilizing the same resources in
Slotted ALOHA is a limiting factor when seeking to increase the density of the
network. To this end, it is common to assume that the base station is able to
exploit successive interference cancellation (SIC). In SIC, the data of each
device is sequentially decoded, and subtracted from the received signal in
order to increase the SINR of the devices that are yet to be decoded. SIC was
used in [8, 7] to take advantage of the different channel conditions to
further reduce the contention in network. However the power was assumed to be
the same for all the devices. To further exploit the SIC receiver, it is
desirable to also tune the power at which the devices transmit in addition to
the slot they transmit in. As such, power control can be exploited in a
similar manner as power domain non orthogonal multiple access (PD-NOMA) [12].

In this paper, we propose an algorithm in the context of NB-IoT networks [13]
to jointly optimize two different types of resources: the temporal slot
(orthogonal) and the transmit power (non-orthogonal). Our contributions are as
follows:

  1. (i)

we propose an algorithm to jointly optimize the slot selection and the
transmit power of devices to minimize the outage probability of the devices,
with a SIC receiver at the base station. In contrast, existing work [7, 8]
exploiting SIC assumes constant power levels.

  2. (ii)

We propose an additional algorithm to adapt power control resulting from the
algorithm in (i), leading to further reductions of the power consumption
without reducing throughput performance. This algorithm is run after the
algorithm in (i) has completed, allowing to minimize the transmit power when
the network runs.

  3. (iii)

We show via a simulation study that our algorithms can exploit heterogeneous
activity, leading either to improvements in throughput performance or
reductions in energy consumption.

In section II we present our system model, in section III we define the
objective function, in section IV we introduce the optimization method and
finally we show simulation results in section V.

##  II System model

Consider a network consisting of a single base station with $N_{r}$ antennas
and $N$ devices. In NB-IoT, uplink communications occur over a single carrier
that is shared by the devices. Devices are assumed to be synchronized and the
time is split into frames, each consisting of $K$ slots. Each frames consists
of two parts: device identification and data transmission. During the device
identification part, all devices that seek to transmit data send their unique
identifier (pilot) at same time. Data transmission consists of $K$ slots,
active devices can transmit data on only one slot per frame. Each slot is
further divided into $L$ symbols.

###  II-A Activity model

In each frame only a subset of the $N$ devices is active. The probability that
a particular device $i$ is active in a frame is $p_{i}$ and let
$X_{i}\in\\{0,1\\}$, the state of the device (respectively inactive or
active), $X_{i}\sim\mathrm{Ber(p_{i})}$. We define
$\mathbf{X}\in\\{0,1\\}^{N}$ the vector of active devices and
$\mathbf{p}=[p_{1}\ldots p_{N}]$ the vector of activity probabilities,
$\mathbf{X}\sim p_{\mathbf{X}}$, where $p_{\mathbf{X}}$ is
$\mathrm{Ber}(\mathbf{p})$; without loss of generality, we assume devices are
sorted in terms of activity: $p_{1}\leq\ldots\leq p_{N}$. As such, devices are
mutually independent with different marginals:

$\displaystyle
p_{\mathbf{X}}(\mathbf{x})=\prod_{i=1}^{N}p_{i}^{x_{i}}(1-p_{i})^{1-x_{i}},.$
(1)

The activity vector $\mathbf{X}^{t}$ in frame $t$ is independent of the other
frames; i.e., $\mathbf{X}^{t}$ is independent of $\mathbf{X}^{t^{\prime}}$
$\forall t\neq t^{\prime}$. We consider the following assumptions:

  1. (i)

the base station does not have knowledge of the parameter $\mathbf{p}$ of the
activity distribution,

  2. (ii)

we assume that, during the pilot phase, the base station detects without error
the active devices (e.g using receiver like [11]) and thus has access to
sample $\mathbf{X}^{t}$.

###  II-B Slot selection

In contrast to standard approaches that utilize FSA to perform the slot
selection, we follow the line of work [5, 6, 8, 7, 9, 10] that perform the
slot selection according to a slot allocation matrix
$\mathbf{A}\in\mathbb{R}_{+}^{N\times K}$. Each element of $\mathbf{A}$
represents the probability that a device selects a particular slot when it is
active. More precisely: $a_{i,k}=\mathrm{Pr}\text{(device $i$ selects slot $k$
$|$ $X_{i}=1$)}$. In other words, matrix $\mathbf{A}$ must satisfy the
constraint $\mathcal{H}=\\{\mathbf{A}\in\mathbb{R}^{N\times
K}_{+}:\sum_{k=1}^{K}A_{ik}=1,~{}i=1,\ldots,N\\}$. Note that in the standard
FSA protocol, the allocation matrix is the constant matrix
$\mathbf{A}_{\mathrm{ALOHA,ij}}=\frac{1}{K}$

###  II-C Transmit power

The transmit power of the devices is
$\mathbf{P}=[P_{1},\ldots,P_{N}]\in\mathbb{R}_{+}^{N}$. The transmit power of
each individual device is constrained by $P_{\min,i}\leq P_{i}\leq P_{\max}$,
where $0<P_{\min,i}\leq P_{\max}$, $P_{\min,i}$ should be defined to be large
enough to ensure reliable reception if no devices, other than device $i$, are
transmitting, and $P_{\max}$ is a value that depends on the standard or other
regulations. The choice of the transmit power is independent of the slot.

###  II-D Channel model and receiver

We assume that devices are equipped with a single transmit antenna and that
the base station is equipped with $N_{r}$ receive antennas. The channel
between the devices and the base station is modeled by block Rayleigh fading
with additive white Gaussian noise. During a slot, devices send a fixed number
of symbols $L$. In the slot $s$ of frame $t$, assuming there are $N_{a,s}$
active devices, the received signal $\mathbf{Y}^{t}_{s}\in\mathbb{C}^{L\times
N_{r}}$ is:

$\displaystyle\mathbf{Y}^{t}_{s}$
$\displaystyle=\sqrt{\mathrm{diag}(\mathbf{P})}\mathbf{D}^{t}(\mathbf{H}^{t})^{\dagger}+\mathbf{W}^{t},$
(2)

where $\mathrm{diag}(\mathbf{P})$ represents the $N_{a,s}\times N_{a,s}$
diagonal matrix of device’s transmit power,
$\mathbf{D}^{t}=[(\mathbf{d}_{i}^{t})^{\dagger},\ldots,(\mathbf{d}_{N_{a,s}}^{t})^{\dagger}]\in\mathbb{C}^{L\times
N_{a,s}}$ with $\mathbb{E}[\|\mathbf{d}_{i}\|^{2}]=1$ and represents the data
symbols sent by the active devices,
$\mathbf{H}^{t}=[(\mathbf{h}_{i}^{t})^{\dagger},\ldots,(\mathbf{h}_{N_{a,s}}^{t})^{\dagger}]\in\mathbb{C}^{N_{r}\times
N_{a,s}}$ is the channel gain matrix, assuming the channel is constant
throughout over frame $t$, and $\mathbf{W}^{t}\in\mathbb{C}^{L\times N_{r}}$
is circularly Gaussian noise $\sim\mathcal{CN}(0,I\sigma^{2})$.

In this work, perfect channel state information at the receiver (CSIR) is
assumed and a MRC spatial filter is utilized to maximize the SINR of the
devices. The signal associated to device $i$ is (superscript $t$ is dropped to
ease the notation):

$\displaystyle\hat{\mathbf{y}}_{i}=\mathbf{Y}\frac{\mathbf{h}_{i}}{\|\mathbf{h}_{i}\|^{2}}=\sqrt{P_{i}}\mathbf{d}_{i}+\sum_{j\neq
i}\sqrt{P_{j}}\mathbf{d}_{j}\frac{\mathbf{h}_{j}^{\dagger}\mathbf{h}_{i}}{\|\mathbf{h}_{i}\|^{2}}+\hat{\mathbf{w}}_{i}.$

Where $\hat{\mathbf{y}}_{i}\in\mathbb{C}^{L}$ is the received the
approximation of $\mathbf{d}_{i}$, and
$\hat{\mathbf{w}}\sim\mathcal{CN}\left(0,\mathrm{diag}\left(\frac{1}{\|\mathbf{h_{i}}\|^{2}}\right)\sigma^{2}\right)$.

For a subset of devices $\mathcal{S}\subset\\{1,\ldots N\\}$ ordered in
decreasing received power, and a given power vector $\mathbf{P}$, we can
express the SINR of the first device $S(1)$ in the set $\mathcal{S}$ under the
noise and the interference of the other devices of $\mathcal{S}$:

$\displaystyle\mathrm{SINR}(\mathcal{S},\mathbf{P})=\frac{P_{\mathcal{S}(1)}}{\frac{\sigma^{2}}{\|\mathbf{h}_{\mathcal{S}(1)}\|^{2}}+\sum_{i=2}^{|\mathcal{S}|}\left(\frac{|\mathbf{h}_{\mathcal{S}(i)}^{\dagger}\mathbf{h}_{\mathcal{S}(1)}|}{\|\mathbf{h}_{\mathcal{S}(1)}\|^{2}}\right)^{2}P_{\mathcal{S}(i)}}.$
(3)

We assume that the data of $\mathcal{S}(1)$ can be decoded if
$\mathrm{SINR}(\mathcal{S},\mathbf{P})>\gamma;~{}\gamma>0$. An outage arises
when $\mathrm{SINR}(\mathcal{S},\mathbf{P})\leq\gamma$. We further assume that
the receiver performs successive interference cancellation (SIC): if
$\mathrm{SINR}(\mathcal{S},\mathbf{P})>\gamma$ the receiver can proceed to
compute $\mathrm{SINR}(\mathcal{S}\setminus{\mathcal{S}(1)},\mathbf{P})$,
otherwise all devices in $\mathcal{S}$ are considered outed of the network.

##  III Objective

In this paper, we are interested in maximizing the number of devices that
transmit without an outage [8]. More precisely we aim to maximize the expected
number of devices for which the MRC receiver combined with the SIC decoder
will lead to a SINR that is sufficient to be able to recover its sent signal.
This objective is defined as an expectation over the activity distribution of
the device $p_{\mathbf{X}}$ defined in (1):

$\displaystyle T(\mathbf{A,P})$ $\displaystyle=\mathbb{E}_{\mathbf{X}\sim
p_{\mathbf{X}}}[T(\mathbf{A,P;X})]$ (4) $\displaystyle T(\mathbf{A,P;X})$
$\displaystyle=\sum_{k=1}^{K}{\sum\limits_{\mathcal{S}\in\mathcal{P}(N)}{{Q_{k}}}}(\mathbf{A},\mathcal{S}\mid{\mathbf{X}})\mathrm{SIC}(\mathcal{S},\mathbf{P}),$
(5)

where $\mathcal{P}(N)$ represents the power set of $\\{1,\ldots,N\\}$,

$\displaystyle{Q_{k}}(\mathbf{A},\mathcal{S}\mid{\mathbf{X}})$
$\displaystyle=\prod\limits_{i\in\mathcal{S}}{{X_{i}}}{A_{ik}}\prod\limits_{j\in{\mathcal{S}^{c}}}{\left({1-{X_{j}}{A_{jk}}}\right)},$
(6)

represent the probability that all devices in a subset of the devices are
choosing a particular slot while the other devices chose another slot, and:

$\displaystyle\mathrm{SIC}(\mathcal{S},\mathbf{P})=\sum_{l=1}^{|\mathcal{S}|-1}\mathbbm{1}\left\\{\mathrm{SINR}(\mathcal{S},\mathbf{P})>\gamma\right\\}$
$\displaystyle~{}~{}~{}~{}~{}\cdot\prod_{m=1}^{l}\mathbbm{1}\left\\{\mathrm{SINR}(\mathcal{S}\setminus\\{\mathcal{S}(1),\ldots,\mathcal{S}(m)\\},\mathbf{P})>\gamma\right\\},$
(7)

represents the number of devices within a set of device $\mathcal{S}$ that
have a sufficient SINR to be decoded under a SIC decoder. We assume that, all
sets $\mathcal{S}\in\mathcal{P}(N)$, are sorted in terms of decreasing
received power. Note that if a device $\mathcal{S}(i)$ cannot be decoded then
all subsequent devices $\mathcal{S}(j),~{}i<j$, also cannot be decoded.

To allow for a fair comparison of the performance under different network
statistics, we define the normalized expected number of devices that transmit
without outage:

$\displaystyle T^{N}(\mathbf{A,P})$
$\displaystyle=\frac{\mathbb{E}_{\mathbf{X}\sim
p_{\mathbf{X}}}[T_{1}(\mathbf{A,P;X})]}{\sum_{i=1}^{N}p_{i}}.$ (8)

##  IV Proposed Algorithms

###  IV-A Slot and power optimization

Optimization of $\mathbf{A}$ and $\mathbf{P}$ in (4) is performed in an
sequential manner using stochastic optimization based on the vector of active
devices $\mathbf{X}^{t}$ of each frame $t$. The optimization problem is
written as follows:

$\displaystyle\mathbf{A}^{\star},\mathbf{P}^{\star}$
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}\mathbf{A}\in\mathbb{R}^{N\times
K}_{+},\\\ \mathbf{P}\in\mathbb{R}^{N}\end{subarray}}T_{1}(\mathbf{A,P})$ (9)
$\displaystyle\text{s.t.:~{}}P_{\mathrm{min},i}\leq P_{i}\leq
P_{\mathrm{max}},~{}\forall i\in\\{1\ldots N\\}$
$\displaystyle\sum_{j}A_{i,j=1},~{}\forall i\in\\{1\ldots N\\}.$

Note that problem (9) is non convex, due to the nature of (6). Note also that
the objective in (9) is non-differentiable, due to the indicator function in
(7), to circumvent the latter issue, we propose to approximate the indicator
with a properly scaled sigmoid function centered on $\gamma$:

$\displaystyle\widetilde{\mathrm{SIC}}(\mathcal{S},\mathbf{P})=\sum_{l=1}^{|\mathcal{S}|-1}\sigma_{f}\left(b\mathrm{SINR}(\mathcal{S},\mathbf{P})-\gamma\right)$
$\displaystyle~{}~{}~{}~{}\cdot\prod_{m=1}^{l}\sigma_{f}\left(b\mathrm{SINR}\left(\mathcal{S}\setminus\\{\mathcal{S}(1),\ldots,\mathcal{S}(m)\\},\mathbf{P}\right)-\gamma\right),$
(10)

where $\sigma_{f}(x)=\frac{1}{1-e^{-x}}$ is the sigmoid function and b is a
sharpness parameter. Let:

$\displaystyle\tilde{T}(\mathbf{A,P;X})$
$\displaystyle=\sum_{k=1}^{K}{\sum\limits_{\mathcal{S}\in\mathcal{P}(N)}{{Q_{k}}}}(\mathbf{A},\mathcal{S}\mid{\mathbf{X}})\widetilde{\mathrm{SIC}}(\mathcal{S},\mathbf{P}).$
(11)

In each frame, by detecting active devices, we obtain a sample
$\mathbf{X}^{t}\sim p_{\mathbf{X}}$ yielding
$\tilde{T}(\mathbf{A}^{t},\mathbf{P}^{t};\mathbf{X}^{t})$. Considering that
the two optimization variables $\mathbf{A}$ and $\mathbf{P}$ have different
impact and that the activity of the devices is heterogeneous, we use ADAGRAD
[14]. The optimization algorithm is detailed in Alg. 1, where ADAGRAD is as
implemented in the Pytorch package [15] and where the operator
$\Pi_{[}\mathcal{H}]\\{\cdot\\}$ represent the projection on the constraint
set of the parameters.

1 Choose initial allocation matrix $\mathbf{A}^{1}$ initial power allocation
$\mathbf{P}^{1}$, and step-size sequence $\\{\mu^{t}\\}$

2 $t\leftarrow 1$.

3 while  _not converged_ do

4 Detect active devices to obtain $\mathbf{X}^{t}$

5
$(\mathbf{A}^{t+1},\mathbf{P}^{t+1})\leftarrow$ADAGRAD$(\mu^{t},(\mathbf{A}^{t},\mathbf{P}^{t}),\tilde{T}(\mathbf{A}^{t},\mathbf{P}^{t};\mathbf{X}^{t}))$

6 $\mathbf{A}^{t+1}\leftarrow\Pi_{\mathcal{H}}[\mathbf{A}^{t+1}]$

7 $\mathbf{P}^{t+1}\leftarrow\Pi_{[P_{\min,i},P_{\max}]}[\mathbf{P}^{t+1}]$

8

9 end while

missingfnum@algorithm1Algorithm 1 Optimization of $\mathbf{A}$ and
$\mathbf{P}$ to solve (9).

###  IV-B Power Reduction

For a fixed allocation matrix $\mathbf{A}$ and a given objective value, there
are several power vectors that achieve this value. Hence, after (9) is solved
via Alg. 1, we seek to minimize the transmit power of all the devices without
decreasing the objective. A way to achieve this is, for all sets $\mathcal{S}$
for which $\mathrm{SINR}(\mathcal{S},\mathbf{P})>\gamma$,to find the smallest
transmit power vector that will lead to a SINR that is just above the
threshold $\gamma$. Then for all devices the maximum value over all the
minimal transmit power is taken. This process, described in Alg. 2, is
repeated until the resulting power vector cannot be reduced further.

1

2Function  _power_cleanup(_$\mathcal{S},\mathbf{P},\mathbf{h}$_)_

$sinr,I=SINR(\mathcal{S},\mathbf{P},\mathbf{h})$;

// I is the denominator of (3)

3 if  _$sinr >\gamma$_ then

// Find min power for $\mathcal{S}$(1)

$p_{\mathrm{min}}=(\gamma*I)/(|h[1]|)^{2}+\epsilon$;

// $\epsilon>0$

4

5 if  _order of SIC decoding is changed_ then

6 $p_{min}=$ min value that do not change the order

7 end if

8 return $p_{min}$

9 end if

10 else

// Iterate the other combination of devices and take the max

11 $\mathbf{P}_{\mathrm{temp}}=[0,\ldots,0]$

12 for  _$i=2;~{}i\leq|\mathcal{S}|;~{}i++$_ do

13 $\mathcal{S}_{\mathrm{next}}=\mathcal{S}\setminus\\{\mathcal{S}(i)\\}$

14
$\mathbf{P}_{\mathrm{temp}}[i]=\textnormal{{power\\_cleanup}}(\mathcal{S}_{\mathrm{next}},\mathbf{P}_{\mathrm{temp}},\mathbf{h})$

15 end for

16 return $\max(\mathbf{P}_{\mathrm{temp}})$

17 end if

18

19

20$\mathbf{P}_{\mathrm{cleaned}}=[0,\ldots,0]$

21for  _$k=0;~{}k <K;~{}k++$_ do

$\mathcal{S}=\text{indices where}(A[:,k]>0)$;

// Devices transmitting in k

$\mathcal{S}$=sort($\mathcal{S}$, $\mathbf{P}$);

// By decreasing power

22

23 $P_{k}=\textnormal{{power\\_cleanup}}(\mathbf{P},g,\mathcal{S})$

24
$P_{\mathrm{cleaned}}[\mathcal{S}(1)]=\max(P_{\mathrm{cleaned}}[\mathcal{S}(1)],P_{k})$

25 for  _$i=2;~{}i\leq|\mathcal{S}|;~{}i++$_ do

26 $\mathcal{S}\leftarrow\mathcal{S}\setminus\\{\mathcal{S}(i-1)\\}$

27 $P_{k}=\textnormal{{power\\_cleanup}}(\mathcal{S},\mathbf{P},g)$

28
$P_{\mathrm{cleaned}}[\mathcal{S}(1)]=\max(P_{\mathrm{cleaned}}[\mathcal{S}(1)],P_{k})$

29 end for

30

31 end for

return $P_{\mathrm{cleaned}}$

missingfnum@algorithm2Algorithm 2 Reducing the power

##  V Numerical results

###  V-A Methods and Baselines

####  V-A1 Independent activity

We evaluate the performance of a slot and a power allocation optimized with
Alg.1. Three methods are considered:

  1. (i)

Optimization with Alg. 1 only.

  2. (ii)

Optimization with Alg. 1 followed by power reduction algorithm Alg. 2.

  3. (iii)

Optimization with Alg. 1 with $\ell^{1}$ regularization: the objective
optimized is
$\widetilde{T}(\mathbf{A}^{t}\mathbf{P}^{t})+\lambda\|\mathbf{P^{t}}\|_{1}$,
with $\lambda=0.001$.

####  V-A2 ALOHA with structured power levels

The devices are choosing their transmit slot uniformly at random (according to
the ALOHA matrix)
$\mathbf{A}_{\mathrm{ALOHA},~{}ij}=\frac{1}{K},~{}\forall{i,j}$. To cover a
sufficient power diversity, a worst case scenario for the definition of the
power levels is as follows:

  1. (i)

set the first level $P_{l1}=\max_{i}P_{\min,i}$ to ensure that the device with
the worst channel condition can transmit,

  2. (ii)

define power levels of order $j$ as $P_{lj}=2^{j}P_{l1}$, $\forall~{}j$ such
that $P_{lj}\leq P_{\max}$.

Devices choose their transmit slots according to $\mathbf{A}_{\mathrm{ALOHA}}$
and the transmit power vector is
$\mathbf{P}=[P_{l1},\ldots,P_{lj},P_{l1}\ldots]$ (power levels are assigned
cyclically among devices).

####  V-A3 Greedy allocation

When the activity probability is known at the BS, a greedy allocation can be
considered. It ensures that devices the most active can be decoded by
assigning them either orthogonal slots or different transmit power levels at
the expense of the least active devices that share a single slot and a single
power level. The greedy allocation places the least probable devices in the
same slot at transmit power $P_{lj}$, and then by orthogonally grouping blocks
of $K$ devices on $K$ slots at the lower power levels. Matrix
$\mathbf{A_{\mathrm{greedy}}}$ can be represented using blocks of diagonal
matrices $I_{k}$ of size $K$. The allocation gives:

$\begin{split}\mathbf{A}_{\mathrm{greedy}}=\begin{bmatrix}1&0&\dots&0\\\
&\vdots&\\\ 1&0&\dots&0\\\ &I_{k}&\\\ &\vdots&\\\
&I_{k}&\end{bmatrix}\end{split},~{}\begin{split}\mathbf{P}_{\mathrm{greedy}}=\begin{bmatrix}P_{lj}\\\
\vdots\\\ P_{lj}\\\ P_{lj}\\\ \vdots\\\ P_{l1}\end{bmatrix}\end{split}$

###  V-B Simulation setup

We consider a network consisting of $N$ devices and $K$ slots. In each frame,
devices are either active or inactive, independently of the other devices and
of the frame number, according to a Bernouilli law of parameter
$\mathbf{p}=[p_{1}\ldots p_{N}]$. In each frame $t$ the base station has only
access to a sample $\mathbf{X}^{t}\sim\mathrm{Ber}(\mathbf{p})$. The channels
are assumed to be fixed during all the simulation,
$\mathbf{H}^{t}=\mathbf{H},~{}\forall t$. We consider a Rayleigh fading model
where the channel between device $i$ and antenna $l$ of the base station is
$h_{i,l}\sim\mathcal{CN}(0,1)$. The base station is equipped with $N_{r}=2$
receive antennas.

We consider 4 different scenarios covering different number of slots, devices
and activity probabilities.

  1. 1.

$N=5$, $K=2$, $\mathbf{p}=[.08,.12,.33,.35,.38]$

  2. 2.

$N=5$, $K=2$, $\mathbf{p}=[.22,.38,.41,.70,.88]$

  3. 3.

$N=8$, $K=3$, $\mathbf{p}=[.10,.12,.37,.41,.41,.41,.42,.45]$

  4. 4.

$N=8$, $K=3$, $\mathbf{p}=[.36,.38,.39,.46,.54,.64,.68,.83]$

Alg. 1 is run for 100000 frames with $\mu^{t}=0.01~{}\forall t$, the initial
allocation matrix $\mathbf{A}^{1}$ is random and the initial power allocation
is $\mathbf{P}^{1}=[P_{\min,1},\ldots,P_{\min,N}]$, $P_{\max}$ is 6, and the
number of power level used by the baselines is 2. The sharpness parameter in
(10) is $b=10$.

###  V-C Results

Figure 1: Resulting objective $T^{N}(\mathbf{A,P})$ for the different method
in the each scenarios.

Our simulations compare the resulting expected number of devices able to
transmit without outage and the expected transmit power of devices in the
network. The first bar in dark blue represent the performance obtained by the
initial $\mathbf{A}^{1}$ and $\mathbf{X}^{1}$. In Fig.1, our methods (red,
green and purple, resp. 2nd, 3rd and 4th bar) are able to find a power and a
slot allocation that allows to increase by up to 150% the objective
$T^{N}(\mathbf{A},\mathbf{P})$ (in scenario 4) compared to the baseline
considered (orange and light blue, resp. 5th and 6th bar). Alg. 1 with
regularization (purple) has similar performance as Alg. 1 (red) and Alg. 1
with Alg. 2 (green) except for scenario 1 where there is a significant
performance degradation compared to the other algorithms. We see also that
performing the power reduction algorithm does not reduce the performance and
might even lead to a small increase, as seen for scenario 3. Fig. 2 shows the
average transmit power of the different methods. We first see that the
initialization has the smallest average power as it was initialized to the
minimal transmit power of each device. The transmit power of Alg. 1 (red) is
always the highest because there is no mechanism to try to limit the transmit
power, in contrast with the green and purple bars. The average transmit power
of Alg. 1 with Alg. 2 is always smaller than Alg. 2 with $\ell^{1}$
regularization and is also smaller than the baselines. Thus the method using
Alg. 1 with Alg. 2 yields a slot and power allocations that avoids undecodable
collisions with a transmit power that is smaller than the baselines.

Figure 2: Average power ($\mathbb{E}_{\mathbf{X}}[\mathbf{P}^{T}\mathbf{X}]$)
used.

##  VI Conclusion

To fully exploit the capability of a SIC-enabled base station, controlling the
transmit power of the devices as well as with their transmit slot is
important. In this paper, we proposed algorithms for jointly optimizing both
slot and power allocations for all devices of the network. This increases the
performance of the network, measured by the expected number of devices that
transmit without outage. We presented a second method aimed at minimizing the
transmit power of the devices without decreasing the throughput performances.
Our simulations show that our algorithm can significantly outperform existing
ALOHA-based algorithms in terms of both throughput and power consumption.

## References

  * [1] L. G. Roberts, “ALOHA packet system with and without slots and capture,” _ACM SIGCOMM Computer Communication Review_ , vol. 5, no. 2, pp. 28–42, Apr. 1975.
  * [2] J. Wieselthier, A. Ephremides, and L. Michaels, “An exact analysis and performance evaluation of framed ALOHA with capture,” _IEEE Transactions on Communications_ , vol. 37, no. 2, pp. 125–137, Feb. 1989.
  * [3] E. Paolini, G. Liva, and M. Chiani, “Coded Slotted ALOHA: A Graph-Based Method for Uncoordinated Multiple Access,” _IEEE Transactions on Information Theory_ , vol. 61, no. 12, pp. 6815–6832, Dec. 2015.
  * [4] G. Liva, “Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHA,” _IEEE Transactions on Communications_ , vol. 59, no. 2, pp. 477–487, Feb. 2011.
  * [5] A. E. Kalor, O. A. Hanna, and P. Popovski, “Random Access Schemes in Wireless Systems with Correlated User Activity,” in _2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. Kalamata: IEEE, Jun. 2018, pp. 1–5.
  * [6] P. Raghuwanshi, O. L. A. López, P. Popovski, and M. Latva-aho, “Channel Scheduling for IoT Access with Spatial Correlation,” _IEEE Communications Letters_ , pp. 1–1, 2024.
  * [7] C. Zheng, M. Egan, L. Clavier, A. E. Kalor, and P. Popovski, “Stochastic Resource Optimization of Random Access for Transmitters With Correlated Activation,” _IEEE Communications Letters_ , vol. 25, no. 9, pp. 3055–3059, Sep. 2021.
  * [8] ——, “Stochastic Resource Allocation for Outage Minimization in Random Access with Correlated Activation,” in _2022 IEEE Wireless Communications and Networking Conference (WCNC)_. Austin, TX, USA: IEEE, Apr. 2022, pp. 1635–1640.
  * [9] A. Jeannerot, M. Egan, L. Chetot, and J.-M. Gorce, “Mitigating User Identification Errors in Resource Optimization for Grant-Free Random Access,” in _2023 IEEE 97th Vehicular Technology Conference (VTC2023-Spring)_ , Jun. 2023, pp. 1–6.
  * [10] A. Jeannerot, M. Egan, and J.-M. Gorce, “Exploiting Device Heterogeneity in Grant-Free Random Access: A Data-Driven Approach,” _IEEE Transactions on Vehicular Technology_ , pp. 1–11, 2024.
  * [11] L. Chetot, M. Egan, and J.-M. Gorce, “Joint Identification and Channel Estimation for Fault Detection in Industrial IoT With Correlated Sensors,” _IEEE Access_ , vol. 9, pp. 116 692–116 701, 2021.
  * [12] M. Mounir, M. B. El_Mashade, and A. Mohamed Aboshosha, “On The Selection of Power Allocation Strategy in Power Domain Non-Orthogonal Multiple Access (PD-NOMA) for 6G and Beyond,” _Transactions on Emerging Telecommunications Technologies_ , vol. 33, no. 6, p. e4289, 2022.
  * [13] A. Hoglund, X. Lin, O. Liberg, A. Behravan, E. A. Yavuz, M. Van Der Zee, Y. Sui, T. Tirronen, A. Ratilainen, and D. Eriksson, “Overview of 3GPP Release 14 Enhanced NB-IoT,” _IEEE Network_ , vol. 31, no. 6, pp. 16–22, Nov. 2017.
  * [14] J. Duchi, E. Hazan, and Y. Singer, “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization,” _Journal of Machine Learning Research_ , p. 39, 2011.
  * [15] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “PyTorch: An Imperative Style, High-Performance Deep Learning Library,” in _Advances in Neural Information Processing Systems 32_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 8024–8035.


# Detecting communities via edge Random Walk Centrality

Ashwat Jain
Wadham College, University of Oxford, United Kingdom
<EMAIL_ADDRESS>
&P. Manimaran
School of Physics, University of Hyderabad, India
<EMAIL_ADDRESS>

###### Abstract

Herein we present a novel approach of identifying community structures in
complex networks. We propose the usage of the Random Walk Centrality (RWC),
first introduced by Noh and Rieger [Phys. Rev. Lett. 92.11 (2004): 118701]. We
adapt this node centrality metric to an edge centrality metric by applying it
to the line graph of a given network. A crucial feature of our algorithm is
the needlessness of recalculating the centrality metric after each step, in
contrast to most community detection algorithms. We test our algorithm on a
wide variety of standard networks, and compare them with pre-existing
algorithms. As a predictive application, we analyze the Indian Railway network
for robustness and connectedness, and propose edges which would make the
system even sturdier.

##  1 Introduction

Networks are ubiquitous - any interaction between members of a set may be
represented so. The set may consist of humans (interactions then could take
forms such as co-authoring a scientific paper [18], following on social
networking sites [29], starring in the same movie [14], friendship [9],
internet connections [32], etc.), animals [17, 21] (in which case the
interactions could be being part of the same pack/group, being preyed
on/preying on each other, sharing a habitat with each other), inanimate
objects like railway stations [13] (with two stations being called interacting
if a train stops at them both), or any other entity. The members of the set
are represented as ’nodes’ or ’vertices’ and the interactions between them as
’edges’. The resulting structure is what would be called a ’graph’ or a
’network’.

In addition to being extensively applicable to the fields of applied
mathematics and statistical physics [33, 4, 8], networks yield themselves as
an excellent tool for analysis and modelling of interactions in the real
world. They possess several interesting properties. One particular feature
found in most networks is the presence of tightly-clustered subsets of nodes,
called ’communities’ [10]. While there is no universally agreed-upon
definition of a community [31], it may be intuitively understood as a subset
of the node set which consists of nodes which interact more amongst themselves
than with those outside the community.

Communities can tell us a lot about the network: if there exists a natural
division amongst members, if members have a common choice, or even if they act
collectively. Detection of community structure thus becomes an endeavor worth
pursuing, and over the years we have seen many pioneering works [22, 25, 24,
27, 19, 11] on the subject.

Broad classification of community structure division algorithms is that into
agglomerative and divisive clustering methods. In the former, we start with an
unconnected set of nodes and progressively add links between them until a
satisfactory community structure is reached. In the latter, we start with the
original (connected) network and iteratively remove edges such that the
remainder depicts communities.

It is evident that the usage of both agglomerative and divisive clustering
methods requires the selection of an edge to add and remove respectively. The
question then arises: given a network, how should one choose an edge for the
application of clustering methods? The answer lies in centrality metrics -
measures of how important a component of the graph is. The component may be an
edge or a vertex, and in this case, we would like an edge centrality metric.
We require a procedure to assign a value to each edge of a graph, and then we
shall be able to choose the most/least important edge to remove/add during our
clustering.

Numerous centrality metrics exist. A long (and possibly extensible) list may
be found at [2]. Several centrality metrics have previously been used to
approach the problem of community structure detection. Consider, for example,
Information Centrality [6], a metric based on the efficiency of information
transfer over a network - and used for community structure identification in
[12]. Another metric, the Resistance Distance, was used in [38] (originally
introduced in [15]), which considered each edge as a fixed resistor and used
the effective resistance between two nodes as a distance metric on the graph.
In contrast, [35] uses the same notion of electrical circuits, but defines
distance based on the voltage difference between nodes. Several ’betweenness’
metrics (namely Shortest Path, Random Walk and Current Flow) were introduced
and used by [26]. Another paper [7] uses a different random-walk based metric,
called the diffusion distance: "The diffusion distance between two nodes is
small if random walkers starting at these two nodes are likely to be at the
same location at time t". Similarly, another notion of distance (i.e., a
metric) is defined in [30] by claiming that random walks on a network get
’trapped’ in communities. Many more methods, including several based on random
walks may be found in the review article [10].

A useful tool to interrelate node and edge centralities is that of a line
graph. Given any network, an alternate and equivalent network can be
constructed with nodes of the new network representing edges of the old one,
and two nodes of the new network have an edge connecting them if the
corresponding two edges of the original network share a node. In essence, we
’invert’ the nodes and edges. It is evident that the two networks are
equivalent and either can be retrieved from the other (See Whitney’s Line
Graph Theorem, [34]). Also evident, but perhaps slightly less so, is that the
node centrality of the original network is the same as the corresponding edge
centrality of the line graph (and vice-versa).

The metric we propose in this paper is the edge Random Walk Centrality (RWC)
[28]. It "quantifies how central a node is, regarding its potential to receive
information randomly diffusing over the network". In terms of the line graph,
this translates to the fact that an edge with higher RWC is likely to receive
information before another. The choice of metric for community structure
detection may be justified by highlighting the impact of communities on
information spread. Tightly-knit communities will have information spread to
them faster than loosely-connected nodes. Below, we reproduce the calculations
as given in [28] for the value of the RWC. Note that the RWC calculated is for
the nodes of the given network. However, we shall apply this to the line
graphs derived from the networks under our consideration, thus transforming
the metric into the edge RWC.

### Random Walk Centrality

We consider the adjacency matrix $\mathbf{A}$ of a finite, undirected network.
We define $K$ as the degree distribution vector, i.e.,
$K_{i}=\Sigma_{j}\mathbf{A}_{ij}$ and the total degree of the graph,
$N=\Sigma_{i}K_{i}$. As in equation 1 of reference [28], we have the
probability of a random walker starting from node $i$ to be at node $j$ after
a time $t$ to be:

$P_{ij,t+1}=\sum_{k}\frac{A_{kj}}{K_{k}}P_{ik,t}$ (1)

However, this is subject to the initial condition $P_{ij,0}=\delta_{ij}$,
representing the fact that at $t=0$, the signals are all at their starting
positions. By inspection, (1) also gives

$P_{ij,t}K_{i}=P_{ji,t}K_{j}$ (2)

And hence, the infinite time limit (corresponding to the stationary
probability distribution $P_{i}^{\infty}$ is simply equal to

$P_{i}^{\infty}=\frac{K_{i}}{N}$ (3)

The characteristic relaxation time $\tau_{i}$ of the node $i$ is given by the
expression

$\tau_{i}=\sum_{t=0}^{\infty}(P_{ii,t}-P_{i}^{\infty})$ (4)

And finally, we can write the RWC $C_{i}$ of node i as

$C_{i}=\frac{P_{i}^{\infty}}{\tau_{i}}$ (5)

We thus have a centrality metric for the nodes of a given graph. When applied
to the line graph of the graph under consideration, it will yield the edge
RWC. This is what we shall use in our agglomerative clustering algorithm.

Figure 1: (a) The dendrogram obtained by using Ward’s linkage on an artificial
network consisting of 4 communities of 16 nodes each. The largest links are
those which connect distinct communities. (b) The dendrogram for Lusseau’s
Dolphin network, clearly showing a pathological peak in modularity very low in
the dendrogram - with only 9 links having been added.

Using the RWC on the line graph for community detection differs from classical
random-walk based algorithms in two respects. First, most works define their
metrics with respect to nodes [10], while it is more favorable to use edges.
Using edges to identify community structure is motivated by the fact that a
’community’ is defined much better in terms of connections (i.e., edges)
rather than members (nodes). While a rigorous definition of ’community’ is
lacking, most modern works agree that a division into communities is good if
the "proportion of edges inside the communities is high compared to the
proportion of edges between them"[30]. To the same end, the measure for
evaluating the quality of community division is the _modularity_ , described
and first introduced in [26]

Consider a division of the network into $p$ communities, and define a square,
symmetric matrix e of the same size. $e_{ab}$ will denote the fraction of
edges that run from community $a$ to community $b$. The modularity is then
given by

$Q=\operatorname{Tr}\textbf{e}-||\textbf{e}^{2}||$ (6)

where $||\textbf{M}||$ gives the sum of all elements of the matrix M. This is
exactly what we require: the trace gives the fraction of intra-community
edges, while the element sum gives the inter-community edges.

Second, although line graphs have previously been used to find overlapping
community structures (see [36]), using them in this applicative scenario
provides a unique advantage - it allows us to investigate directly the edges
of the graph using methods well-tested for nodes. The RWC "quantifies how
central a node is located regarding its potential to receive information
randomly diffusing over the network"[28]. Applying this on the line graph
gives us a measure of how central an _edge_ is with respect to information
travelling across the network.

This paper is organized as follows: In Section II, we expand on the
implementation of our algorithm and discuss other computational aspects. In
Section III, we present the results of our algorithm when applied to some
standard networks and compare them to previous results. Finally, in Section
IV, we showcase an application of our algorithm to the Indian Railway network.

Network | Ideal communities | Algorithm | Communities | Correctly classified nodes | Max modularity
---|---|---|---|---
Football | 12 | RWC | 11 | 99.14% | 0.13
GN | 13 * | 97.41% | ?
Karate | 2 | RWC | 2 | 91.18% | 0.35
GN | 5 | 70.59% ** | 0.4
Les Miserables | ? | RWC | 4 | - | 0.4
GN | 11 | - | 0.54
Dolphin | 2 | RWC | 2 | 90.00% | 0.1
GN | 5 | N.A ^ | 0.52 ^
Collaboration | ? | RWC | 10 | - | 0.07
GN | 13 | - | 0.72 ^^
Table 1: Comparison of the RWC algorithm and the Girvan Newman algorithm with
the ideal (expected) community structure of several real-world networks. The
ideal split for _Les Misérables_ and Collaboration networks is unknown. The
max modularity is undefined for the ideal split.
∗Not considering Independent school singleton communities
∗∗Considering split at the global modularity maximum
^Girvan and Newman [26] used the [20] dataset, while we used the [21] dataset
^^Different datasets were used

##  2 Implementation

We now present our hierarchical (agglomerative) clustering algorithm. Given a
graph $G$ with $n$ vertices and $m$ edges, perform the following.
Preparatory steps:

  1. 1.

Construct the line graph $G_{1}$ (which will consist of $m$ vertices and
$\sum_{i=1}^{n}d_{i}^{2}-m$ edges, where $d_{i}$ is the degree of vertex $i$).

  2. 2.

Calculate the RWC of all the nodes of $G_{1}$, by (5) and assign these values
as weights to the corresponding edges of $G$

  3. 3.

Define an $n\times n$ distance matrix $R$, such that the entry
$R_{ij}$($=R_{ji}$) corresponds to the sum of weights of edges that lie in the
(weighted) shortest path from node $i$ to node $j$. This distance matrix then
represents the pairwise distance between all nodes of $G$

We now have a forest of nodes (singleton clusters). Iterative steps:

  1. 1.

Merge the two closest clusters, and replace them with a new cluster

  2. 2.

Recalculate distances to all other clusters

These steps are repeated until there is only one cluster left. This
hierarchical clustering now gives us a dendrogram, which can be analyzed to
find the optimal community structure. Concluding steps:

  1. 1.

Plot modularity (6) against the height at which the dendrogram is cut off for
a given range (see below)

  2. 2.

Obtain the community structure by cutting the dendrogram at the point where
modularity reaches its maximum

The ’distance’ between clusters (as used above) may be defined in several
different ways [23]. These are known as linkage methods, and we believe that
using Ward’s linkage is the most appropriate. This defines the distance
between clusters as increase in the (ESS) error sum of squares. The sum of
squares is defined in the usual way, the sum of squared distances of all nodes
from their cluster mean. In our analysis on artificially generated networks
(Fig. 1a), we found that Ward’s linkage will give a large distance between
clusters if merging them leads to a community structure that is much less
pronounced. We thus argue that the optimal community structure will be
obtained by cutting the dendrogram at some point of the longest link (i.e., by
removing edges which have the largest distance by Ward’s linkage). Now there
may exist many other links which exist between the endpoints of this longest
link. To determine which of these gives us the optimal cutoff, we use the
modularity.

Calculating modularity in this truncated domain has two advantages: One, it
significantly reduces computation time as the number of points at which
modularity must be calculated is lower. Second, in some networks (for example
the American Football network and Dolphin network (Fig. 1b)) we obtain a sharp
and narrow spike in modularity at the very beginning of clustering. There are
a lot of edges with very similar RWC scores, and in this densely populated
stratum of the dendrogram the modularity achieves a peak value with most nodes
still remaining singleton communities. Calculating modularity only in the
truncated region serves to avoid this pathological peak.

However, if the maximum of the modularity is obtained at one of the endpoints
of the truncated region, we further calculate the modularity for the next few
links on that side, until we reach a local maximum of modularity. This ensures
that the truncation does not leave out modularity maxima which are in the same
neighborhood.

The calculation of the RWC runs in time $\mathcal{O}(n^{3})$ for a graph of n
nodes. However, since we run the algorithm on the line graph, the complete
clustering algorithm takes time $\mathcal{O}(m^{3})$, where $m$ is the number
of edges in the original network.

This method of community detection offers a unique advantage over traditional
methods - it eliminates the need of recalculation of the centrality metric at
every step. Once the RWC has been calculated for the network, and the distance
matrix defined, we no longer need to recalculate the RWC for the new network.
The results are comparable to (and in certain cases, even better) than
conventional community detection algorithms. The order of standard algorithms
like Girvan and Newman’s shortest path betweenness algorithm [26] is
$\mathcal{O}(n^{3})$, while ours is $\mathcal{O}(m^{3})$, which is the same
for sparse graphs. In the next section, we demonstrate this by applying our
algorithm to a wide range of standard and well-tested networks.

##  3 Preliminary tests

We test our method on graphs whose community structure has been established
very firmly. This includes one computer-generated class of graphs and five
real world networks: the American College Football network [3], Zachary’s
Karate Club network [37], the Bottlenose Dolphin network [21], the Les
Misérables character network [16] and the Network Science coauthorship network
[27]. Our results are summarized in Table 1

Figure 2: The dendrograms obtained along with the modularity plot in the
truncated region, and the corresponding division into communities. (a) shows
the split of Zachary’s Karate network into 2 communities while (b) shows the
split of Lusseau’s Dolphin network into 2 groups

###  3.1 Artificial network

Figure 3: The comparison of accuracies of the RWC and Girvan-Newman
algorithms. Each point is an average of up to 10 graphs

We created networks with 64 nodes divided into 4 communities of 16 each. The
average degree of a node for connection within its community,
$z_{\text{in}}=6$ and we varied the out degree $z_{\text{out}}$ from 0.5 to
5.5, in increments of 0.5. The accuracy of the community division can be found
in Fig. 3. While it seems to produce worse results than the Girvan-Newman
algorithm for the out-degree range 3 to 7, it appears to perform better at the
higher end of the spectrum. This depicts usability in cases where the out
degree and in degree are equal and the community structure is very convoluted.

###  3.2 American College Football network

Figure 4: The dendrogram for the split of the American 2000 NCAA Division I-A
football season. The conference divisions match extremely well with the true
conferences, with the exception of Texas Tech. Independents are mostly placed
together, except for Notre Dame, Navy and Lousiana Lafayette.

This network depicts the various American Football college conferences that
happened in the USA in 2000. There were a total of 116 schools participating
in 12 conferences [3]. Each node represents a school and each edge represents
a game between those two schools. Naturally, the conferences then form
communities, and we apply our method to this network.

The results are excellent - only one node (Texas Tech) is misclassified. In
addition, all the I-A Independent schools occur together in our dendrogram
(with the exception of Louisiana Lafayette, Notre Dame and Navy).

Figure 5: The map showing the split of members of the study of Zachary’s
Karate club. Node 1 is the administrator of the club, while node 33 is the
instructor.

Figure 6: The community map of _Les Misérables_

###  3.3 Zachary’s Karate Club network

This is a well-studied network in community detection. Conventional clustering
algorithms like the Girvan-Newman usually divide it into two, three or four
communities. The ’ideal’ community division seems to be that into two groups
(stemming from the fact that the club members aligned either with the club’s
administrator or the instructor after the fission of the club). The RWC
algorithm yields a split into 2 groups: very close to the ideal split, and
very similar to that of Girvan and Newman [26] and the actual split [37], with
the only difference being the classifications of the nodes at the boundary of
the two ideal communities (note that all the three ’misclassified’ nodes, 9,
10, and 31 have an equal number of connections to both the ideal communities).

###  3.4 Les Misérables character network

Victor Hugo’s _Les Misérables_ presents an ensemble of characters. These
characters can be put into a network, with edges representing simultaneous
appearance of characters in particular scenes. Different splits have been
proposed by various authors ([26, 5]). However, they all share a common
characteristic: Valjean and his adversary Javert form the hubs of two of the
largest communities, and the same is observed in the split given by the RWC
algorithm (Fig. 6).

###  3.5 Bottlenose Dolphin network

Figure 7: The community map of the Bottlenose Dolphins network (left) and the
Network Science Collaboration network (right).

A study of 62 bottlenose dolphins was conducted by [21] over seven years. We
ran our algorithm on the graph presented in [21], and the resulting community
structure we found is shown in Fig. 7a. In the original paper, the authors
identify 3 groups of dolphins. Out of those, one group is claimed to be an
artefact (stemming from the low observation frequency of some individuals).
This artefact is absent in our network, indicating that it is better than
conventional clustering methods. The other two groups match very well to the
groups found by our algorithm. The individuals at the boundary of the two
groups seem to be placed into the wrong group. However, [26] says that the
very formation of the two communities occurred because of the temporary
disappearance of the individuals at the boundary. In this light, the
classification of these individuals doesn’t seem as dubious.

###  3.6 Network Science coauthorship network

This network represents the collaboration between physicists who researched
networks, taken from [27]. The obtained community structure is shown in Fig.
7. The number of authors is too large for their names to be included, but the
division corresponds very well to instiutional affiliations and geographic
locations of the authors.

##  4 Indian Railway network

The Indian Railway Network is one of the most expansive in the world, with
about 68,000 km (42000 mi) of track length as of 2022. The graph nodes here
have been chosen to correspond with the Divisional Headquarters of the
Railways, numbering 70 (Data source: [1]). The edges correspond to _adjacent_
stops that a train makes (i.e., node pairs that are not connected do not imply
that there is no train between them, only that there is no direct train
between them). We desire that such large networks upon which people rely be
well-connected. Below, we list certain characteristics that are expected to be
seen in such a well-connected network.

Figure 8: Our results of the analysis of the Indian Railway Network. (a) shows
the dendrogram, accompanied by a very flat modularity graph. (b) shows the map
of the railway division headquarters, accurate to geographical positions.
Three communities are seen, though they are not apparent except for the color
assigned to the nodes. (c) shows the distribution of shortest path lengths of
the network, clearly showing a single peak.

  * •

Ideally, a well-connected (sparse) network should have a low number of
communities (i.e., the whole graph should be as close to a single community as
possible). A high number of communities would mean that nodes lying in
different communities are not very well-connected.

  * •

We do not expect any single link to be very important individually, and this
would reflect as a rather flat modularity graph. It would depict the
sturdiness of the network to dysfunctional links, which could happen due to a
large variety of causes - technical breakdowns, maintenance works, terrorist
attacks, traffic overload, etc. A well-connected network must be resilient to
these situations to maintain steady flow of traffic and smooth functioning.

  * •

A sparse, well-connected network should have a small variance in link
importance: all the edges should have approximately equal scores of any given
centrality metric. A link which is much too important (or unimportant) would
mean a high (low) traffic along it, making it particularly crucial (useless)
to the network.

  * •

It is also reasonable to expect the node density to be fairly uniform over the
network. Large fluctuations in concentration of nodes would give rise to
community structures, which would not be an expected characteristic of a well-
connected network.

  * •

Finally, well-connected sparse networks can be expected to show the small-
world effect: that the average shortest path between two nodes be much smaller
than the size of the network. In popular literature, this shortest path length
is found to be near about 6 in most real-world networks, fancily deemed ’six
degrees of separation’. If a network is split distinctly into communities, we
can expect the shortest path length distribution to show multiple peaks (with
the first and largest peak corresponding to node pairs lying in the same
community). Higher the number of peaks, the worse is the well-connectedness of
the network.

When we apply our community detection algorithm to the Indian Railway Network,
these characteristics are exactly what we see.

  * •

There appear to be only three communities, roughly corresponding to
geographically accurate partitions of the country (Fig. 8b), with the North
and West clubbed together, the East as a community and the South as another.

  * •

The modularity graph (Fig. 8a) is also nearly constant (in the truncated
region), highlighting the resistance of the network to a train that is
temporarily not functioning and the presence of alternate routes that are only
slightly longer.

  * •

The lowest stratum of the dendrogram (Fig. 8a) shows link lengths being very
close together (i.e., at the same height).

  * •

The node density (Fig. 8b) is not uniform, but given the population density,
the node density is found to be in good accordance with it. This reflects the
efficient distribution of traffic over nodes, fulfilling the utilitarian well-
connected condition.

  * •

Lastly, the shortest path length distribution of the Indian Railway Network
(Fig. 8c) shows one single peak.

Indeed, to make this network even sturdier and more uniform than it already
is, we suggest adding more edges (i.e., trains) between nodes lying at the
boundary of the three communities (direct trains like Raipur to
Waltair/Vijayawada/Guntur/Hyderabad/Secunderabad, Jhansi to
Jabalpur/Nagpur/Lucknow, Bhusawal to Karwar/Solapur/Hubli, etc.). Adding these
trains also causes the RWC values of the new edges to fall in the same range
as the other edges, and no changes in the number of peaks in the shortest path
length distribution (with, of course, no change in node density).

##  5 Conclusion

We presented an agglomerative hierarchical algorithm using Noh and Rieger’s
[28] Random Walk Centrality as a metric to identify community structure in
complex networks. Our approach is unique in three ways. First, the usage of
line graphs to find edge centrality gives us the advantage of directly
investigating edge connections (which are arguably more fundamental than node
linkages in term of community structures). Second, the calculation of RWC only
once in the process allows us to run in time $\mathcal{O}(m^{3})$ for a graph
with $m$ edges. Third, we evaluated the modularity only for the dendrogram
stratum defined by the largest edge, when drawn using Ward’s Linkage method.
This helps reduce computation time without impacting community detection (in
fact, it helps surpass pathological peaks in modularity which can sometimes
occur when very few edges have been added during clustering). We then tested
our algorithm on several standard networks and obtained excellent results.
Finally, we demonstrated an application of the algorithm to the Indian Railway
Network and checked whether it was well-connected.

## Acknowledgements

The author PM would like to thank the Department of Science and Technology,
Government of India, (DST-MATRICS GoI Project No. SERB/F/506/2019-2020 Dated
15th May 2019) for their financial support

## References

  * [1] https://dataspace.mobi/dataset/indian-railways-data/resource/7d9f8457-9f2b-4aa4-a79a-d91d5280a332.
  * [2] https://www.centiserver.org/centrality/.
  * [3] https://www.sports-reference.com/cfb/years/2000-standings.html.
  * [4] Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  Reviews of modern physics, 74(1):47, 2002.
  * [5] James P Bagrow and Erik M Bollt.  Local method for detecting communities.  Physical Review E, 72(4):046108, 2005.
  * [6] Ulrik Brandes and Daniel Fleischer.  Centrality measures based on current flow.  In Volker Diekert and Bruno Durand, editors, STACS 2005, pages 533–544, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [7] Ronald R Coifman and Stéphane Lafon.  Diffusion maps.  Applied and computational harmonic analysis, 21(1):5–30, 2006.
  * [8] Sergei N Dorogovtsev and José FF Mendes.  Evolution of networks: From biological nets to the Internet and WWW.  Oxford university press, 2003.
  * [9] Nathan Eagle, Alex Pentland, and David Lazer.  Inferring friendship network structure by using mobile phone data.  Proceedings of the national academy of sciences, 106(36):15274–15278, 2009.
  * [10] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75–174, 2010.
  * [11] Santo Fortunato and Claudio Castellano.  Community structure in graphs, 2007.
  * [12] Santo Fortunato, Vito Latora, and Massimo Marchiori.  Method to find community structures based on information centrality.  Phys. Rev. E, 70:056104, Nov 2004.
  * [13] Saptarshi Ghosh, Avishek Banerjee, Naveen Sharma, Sanket Agarwal, Niloy Ganguly, Saurav Bhattacharya, and Animesh Mukherjee.  Statistical analysis of the indian railway network: A complex network approach.  Acta Physica Polonica B Proceedings Supplement, 4(2):123–138, 2011\.
  * [14] Bruce W Herr, Weimao Ke, Elisha Hardy, and Katy Borner.  Movies and actors: Mapping the internet movie database.  In 2007 11th International Conference Information Visualization (IV’07), pages 465–469. IEEE, 2007.
  * [15] D. J. Klein and M. Randić.  Resistance distance.  Journal of Mathematical Chemistry, 12(1):81–95, Dec 1993.
  * [16] Donald E Knuth.  The Stanford GraphBase: a platform for combinatorial computing.  ACM, 1993.
  * [17] Jens Krause, David Lusseau, and Richard James.  Animal social networks: an introduction.  Behavioral Ecology and Sociobiology, 63(7):967–973, 2009.
  * [18] Sameer Kumar.  Co-authorship networks: a review of the literature.  Aslib Journal of Information Management, 2015.
  * [19] E. A. Leicht and M. E. J. Newman.  Community structure in directed networks.  Phys. Rev. Lett., 100:118703, Mar 2008.
  * [20] David Lusseau.  The emergent properties of a dolphin social network.  Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(suppl_2):S186–S188, 2003.
  * [21] David Lusseau, Karsten Schneider, Oliver J Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson.  The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations.  Behavioral Ecology and Sociobiology, 54(4):396–405, 2003.
  * [22] M.Girvan and M.E.J. Newman.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002.
  * [23] Fionn Murtagh and Pedro Contreras.  Algorithms for hierarchical clustering: an overview.  Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86–97, 2012.
  * [24] M. E. J. Newman.  Detecting community structure in networks.  The European Physical Journal B, 38(2):321–330, Mar 2004.
  * [25] M. E. J. Newman.  Fast algorithm for detecting community structure in networks.  Phys. Rev. E, 69:066133, Jun 2004.
  * [26] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Phys. Rev. E, 69:026113, Feb 2004.
  * [27] M.E.J. Newman.  Modularity and community structure in networks.  Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006.
  * [28] Jae Dong Noh and Heiko Rieger.  Random walks on complex networks.  Phys. Rev. Lett., 92:118701, Mar 2004.
  * [29] Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos.  Community detection in social media.  Data mining and knowledge discovery, 24(3):515–554, 2012.
  * [30] Pascal Pons and Matthieu Latapy.  Computing communities in large networks using random walks.  In pInar Yolum, Tunga Güngör, Fikret Gürgen, and Can Özturan, editors, Computer and Information Sciences - ISCIS 2005, pages 284–293, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [31] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi.  Defining and identifying communities in networks.  Proceedings of the national academy of sciences, 101(9):2658–2663, 2004.
  * [32] Erzsébet Ravasz and Albert-László Barabási.  Hierarchical organization in complex networks.  Physical review E, 67(2):026112, 2003.
  * [33] Steven H Strogatz.  Exploring complex networks.  nature, 410(6825):268–276, 2001.
  * [34] Hassler Whitney.  Congruent graphs and the connectivity of graphs.  American Journal of Mathematics, 54:61–79, 1932.
  * [35] F. Wu and B. A. Huberman.  Finding communities in linear time: a physics approach.  The European Physical Journal B, 38(2):331–338, Mar 2004.
  * [36] Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski.  Overlapping community detection in networks: The state-of-the-art and comparative study.  ACM Comput. Surv., 45(4), aug 2013.
  * [37] Wayne W Zachary.  An information flow model for conflict and fission in small groups.  Journal of anthropological research, 33(4):452–473, 1977.
  * [38] Teng Zhang and Changjiang Bu.  Detecting community structure in complex networks via resistance distance.  Physica A: Statistical Mechanics and its Applications, 526:120782, 2019.