# A non commutative generalization BL-rings

Surdive Atamewoue Tsafack1,2, Arnaud Fobasso Tchinda2, Yuming Feng1,3,,
Selestin Ndjeya4
$1.$ Key Laboratory of Intelligent Information Processing and Control,
Chongqing Three Gorges University, Wanzhou, Chongqing, 404100, China
$2.$ Department of Mathematics, University of Yaounde 1, Cameroon
$3.$ Chongqing Engineering Research Center of Internet of Things and
Intelligent Control Technology ,
Chongqing Three Gorges University, Wanzhou, Chongqing, 404100, China
$4.$ Department of Mathematics, Higher Teacher Training College, University of
Yaounde 1
Cameroun
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author,
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The purpose of this work is to extend the study of the commutative rings whose
lattice of ideals can be a structure of BL-algebra as carry out by Heubo et al
in 2018, to non commutative rings appointed in the work as pseudo BL-rings. We
study and characterize rings whose ideals form a pseudo BL-algebra, we
describe them in terms of their subdirectly irreductible factors. We obtain
that these are (up to isomorphism) to a subring of a direct sums of unitary
special primary rings and discrete valuation ring.

Keywords: BL-rings, pseudo-BL algebras, pseudo BL-ring, BL-algebras,
multiplication ring.

AMS Mathematics Subject Classification(2010): 03B50, 06D99.

##  1 Introduction

It is well known that the algebraic study of classical logic proceeds via
Boolean algebras [1]. For the infinite valued logic of Łukasiewicz, the
algebraic analogues of Boolean algebras are the MV-algebras. It is also well
known that Boolean algebras can be subsumed within the theory of rings. From
their inception there was the question of whether or not the same is true of
MV-algebras. In 2009 Belluce and Di Nola wrote an article on commutative rings
whose ideals form an MV-algebra [1], in that work they introduced and gave
some properties of a class of commutative rings whose lattice of ideals form
an MV-algebra, which they called Łukasiewicz rings. An important non-
commutative generalization of MV-algebra, known as pseudo MV-algebra was
introduced by Georgescu and Iorgulescu [5]. The natural question that arises
is what happens if one drops the commutativity assumption on Łukasiewicz
rings. The answer of that question has been the goal of Kadji, Lele and Nganou
in their work A non-commutative generalization of Łukasiewicz rings [7] where
they study and characterize all rings whose ideals form a pseudo MV-algebra,
which they called generalized Łukasiewicz rings, this was in 2016. Since the
class of BL-algebras contains the MV-algebras, from then in 2018, Heubo et al.
[8] initiated the study of commutative rings whose lattice of ideals can be
equipped with a structure of BL-algebra. Recall that BL-algebras where
introduced by Peter Hájek in 1998 as algebraic structures for his Basic Logic
to formalize many-valued logics (in short MV logics) induced by continuous
$t$-norms on the real unit interval [0,1] and the were generalized to pseudo
BL-algebras by Di Nola, Georgescu and Iorgulescu [3].
In the idea to continuous the investigation of classes of rings for which the
residuated lattice $A(R)$ of their ideals is an algebra of a well-known
subvariety of residuated lattices, in this work we generalize the notion of
commutative BL-ring to non commutative case, whom is call in the present
pseudo BL-ring.
The paper is organized as follows. In section 2, we introduce and recall some
definitions and preliminaries results that will be useful in the paper. In
section 3, we introduce and study the main properties of pseudo BL-ring, also
their connections with some class of non commutative rings. In section 4, we
prove that this class is closed under finite direct products, arbitrary direct
sums and homomorphic images. Furthermore, a description of subdirectly
irreducible pseudo BL-rings is obtain.

##  2 General Preliminaries

We recall here definitions and properties that are useful throughout the
article.

###### Definition 2.1

([6]) A BL-algebra is a structure $(A,\vee,\wedge,\odot,0,1)$ such that

(1) $(A,\vee,\wedge,0,1)$ is a bounded lattice,

(2) $(A,\odot,1)$ is an abelian monoid, that is, $\odot$ is commutative,
associative and $x\odot 1=1\odot x=x$,

(3) the following conditions hold for all $x,y,z\in A$,

(BL-1) $x\odot y\leq z$ iff $x\leq y\rightarrow z$ (residuation),

(BL-2) $x\wedge y=x\odot(x\rightarrow y)$ (divisibility),

(BL-3) $(x\rightarrow y)\vee(y\rightarrow x)=1$ (prelinearity).

An MV-algebra is a BL-algebra $A$ satisfying the double negation law:
$x^{\ast\ast}=x$, for all $x\in A$, where $x^{\ast}=x\rightarrow 0$.

Given any BL-algebra $A$, $MV(A):=\\{x^{\ast}~{}|~{}x\in A\\}$ is an MV-
algebra, and is indeed the largest BL-subalgebra of $A$ satisfying the double
negation. This MV-algebra is called the MV-center of $A$.
We recall that a BL-algebra $A$ is an MV-algebra iff $(x^{\ast})^{\ast}=x$ for
any $x\in A$.

###### Definition 2.2

([5]) A pseudo MV-algebra is a structure
$(A,\odot,\oplus,(^{\ast}),(^{-}),0,1)$ of type (2, 2, 1, 1, 0, 0), such that
the following axioms are satisfied for all $x,y,z\in A$,

(1) $x\odot(y\odot z)=(x\odot y)\odot z$,

(2) $x\odot 1=1\odot x=x$,

(3) $x\odot 0=0\odot x=0$,

(4) $0^{\ast}=1$, $0^{-}=1$,

(5) $(x^{-}\odot y^{-})^{\ast}=(x^{\ast}\odot y^{\ast})^{-}$,

(6) $x\odot(x^{-}\oplus y)=y\odot(y^{-}\oplus x)=(x\oplus y^{\ast})\odot
y=(y\oplus x^{\ast})\odot x$,

(7) $x\oplus(x^{\ast}\odot y)=(x\odot y^{\ast})\oplus y$,

(8) $(x^{\ast})^{-}=x$, where $y\oplus x:=(x^{\ast}\odot
y^{\ast})^{-}=(x^{\ast}\odot y^{\ast})^{-}$.

###### Definition 2.3

([3]) A pseudo BL-algebra is a structure
$\mathcal{A}=(A,\vee,\wedge,\odot,\rightarrow,\rightsquigarrow,0,1)$ of type
(2, 2, 2, 2, 2, 0, 0) which satisfies the following axioms, for all $x,y,z\in
A$,

(1) $(A,\vee,\wedge,0,1)$ is a bounded lattice,

(2) $(A,\odot,1)$ is a monoid, that is, $\odot$ is associative and $x\odot
1=1\odot x=x$,

(3) $x\odot y\leq z$ iff $x\leq y\rightarrow z$ iff $y\leq x\rightsquigarrow
z$,

(4) $x\wedge y=(x\rightarrow y)\odot x=x\odot(x\rightsquigarrow y)$,

(v) $(x\rightarrow y)\vee(y\rightarrow x)=(x\rightsquigarrow
y)\vee(y\rightsquigarrow x)=1$.

A ring $R$ is said to be generated by idempotents, if for every $x\in R$,
there exists an idempotent element $e\in R$ (that is $e^{2}=e$) such that
$e\cdot x=x\cdot e=x$. There are a residuated lattice form by the two-sided
ideals of the ring $R$, this lattice is define by

$A(R):=\langle
Id(R),\wedge,\vee,\otimes,\rightarrow,\rightsquigarrow,\\{0\\},R\rangle,$

where

$I\wedge J=I\cap J,~{}I\vee J=I+J,~{}I\otimes J=I\cdot J,$ $I\rightarrow
J:=\\{x\in R|~{}xI\subseteq J\\},~{}I\rightsquigarrow J:=\\{x\in
R|~{}Ix\subseteq J\\}.$

Note that $I^{\ast}:=\\{x\in R~{}|~{}xI=\\{0\\}\\}$ is simply the right
annihilator of $I$ in $R$ and $I^{-}:=\\{x\in R~{}|~{}Ix=\\{0\\}\\}$ is simply
the left annihilator of $I$ in $R$, where $I$ is an ideal of $R$. Given a ring
$R$, recall that an ideal $I$ of $R$ is called an annihilator ideal (resp. a
dense ideal) if $I=J^{\ast}$ and $I=K^{-}$ for some ideals $J$, $K$ of $R$
(resp. $I^{\ast}=I^{-}=\\{0\\}$).

$AN^{\ast}(R):=\\{I^{\ast}~{}|~{}I\in A(R)\\}$ and
$AN^{-}(R):=\\{I^{-}~{}|~{}I\in A(R)\\}$ denote the sets of left and right
annihilator ideals of $R$.

$D^{\ast}(R):=\\{I\in A(R)~{}|~{}I^{\ast}=\\{0\\}\\}$ and $D^{-}(R):=\\{I\in
A(R)~{}|~{}I^{-}=\\{0\\}\\}$ denote the sets of left and right dense ideals of
$R$.

###### Definition 2.4

([11]) A ring $R$ is called a multiplication ring, if for every ideals $I$,
$J$ of $R$ such that $I\subseteq J$, there exist ideals $K$, $K^{\prime}$ such
that $I=J\cdot K=K^{\prime}\cdot J$.

##  3 Pseudo BL-rings

We start this section by the introduction of the notion of pseudo BL-rings
which shall be non commutative rings for which the lattices of ideals are fit
out with pseudo BL-algebra structures. The main properties of these rings are
examine and their we settle some connections of these rings to other known
classes of rings.

###### Definition 3.1

A ring $R$ generated by idempotents is called a pseudo BL-ring if it
satisfies,

PBLR-1

$I\cap J=I\cdot(I\rightsquigarrow J)=(I\rightarrow J)\cdot I,$

PBLR-2

$(I\rightarrow J)+(J\rightarrow I)=(I\rightsquigarrow J)+(J\rightsquigarrow
I)=R,$

for all ideals $I$, $J$ of $R$.

###### Lemma 3.2

Let $I$ and $J$ be two ideals of a ring $R$. Then

(1) $I\rightarrow J=I\rightarrow(I\cap J)$ and $I\rightsquigarrow
J=I\rightsquigarrow(I\cap J)$.

(2) $(I+J)\rightarrow J=I\rightarrow J$ and $(I+J)\rightarrow I=J\rightarrow
I$.

Proof. These are easily derived from the definitions and the operations
involved.

###### Lemma 3.3

Let $I$ and $J$ be two ideals of a ring $R$. Then $(I\rightarrow J)\cdot
I\subseteq I\cap J$ and $I\cdot(I\rightsquigarrow J)\subseteq I\cap J$.

Proof. Let $x\in(I\rightarrow J)\cdot I$, then
$x=\displaystyle{\sum_{i=1}^{n}a_{i}b_{i}}$ with $a_{i}\in I\rightarrow J$,
$b_{i}\in I$ and $n\in\mathbb{N}$. When using definition of ideal and the
definition of $I\rightarrow J$, we have that $x\in I$ and $x\in J$. Therefore
$x\in I\cap J$ and $(I\rightarrow J)\cdot I\subseteq I\cap J$.
Let $y\in I\cdot(I\rightsquigarrow J)$, then
$y=\displaystyle{\sum_{i=1}^{n}a_{i}b_{i}}$ with $a_{i}\in I$, $b_{i}\in
I\rightsquigarrow J$ and $n\in\mathbb{N}$. When using definition of ideal and
the definition of $I\rightsquigarrow J$, we have that $y\in I$ and $y\in J$.
Therefore $y\in I\cap J$ and $I\cdot(I\rightsquigarrow J)\subseteq I\cap J$.

The following proposition give some axioms equivalent to PBLR-1 and PBLR-2.

###### Proposition 3.4

Let $R$ be a pseudo BL-ring. For all ideals $I$, $J$, $K$ of $R$, the
following hold,

(1) PBLR-1 iff $I\cap J\subseteq(I\rightarrow J)\cdot I$ and $I\cap J\subseteq
I\cdot(I\rightsquigarrow J)$.
(2) PBLR-2 iff $(I\cap J)\rightarrow K=(I\rightarrow K)+(J\rightarrow K)$ iff
$(I\cap J)\rightsquigarrow K=(I\rightsquigarrow K)+(J\rightsquigarrow K)$.
(3) PBLR-2 iff $I\rightarrow(J+K)=(I\rightarrow J)+(I\rightarrow K)$ iff
$I\rightsquigarrow(J+K)=(I\rightsquigarrow J)+(I\rightsquigarrow K)$.

Proof. (1) By using Lemma 3.3.

(2) Assume that $(I\cap J)\rightarrow K=(I\rightarrow K)+(J\rightarrow K)$.
Let’s take $K=I\cap J$, then $(I\cap J)\rightarrow(I\cap
J)=(I\rightarrow(I\cap J))+(J\rightarrow(I\cap J))$. Since $(I\cap
J)\rightarrow(I\cap J)=R$, $I\rightarrow(I\cap J)=I\rightarrow J$ and
$J\rightarrow(I\cap J)=J\rightarrow I$ by Lemma 3.2, then $R=(I\rightarrow
J)+(J\rightarrow I)$.
Assume now that $R=(I\rightarrow J)+(J\rightarrow I)$.

Let $x\in(I\cap J)\rightarrow K$, then $x$ can be write as $x=x\cdot i+x\cdot
j$, with $i\in I$, $j\in J$, and $i+j=1$ (1 is an idempotent). Thus, $x\cdot
j\in I\rightarrow K$ and $x\cdot i\in J\rightarrow K$. Therefore $(I\cap
J)\rightarrow K\subseteq(I\rightarrow K)+(J\rightarrow K)$.

Let $z\in(I\rightarrow K)+(J\rightarrow K)$, then $z=x+y$ with $x\in
I\rightarrow K$ and $y\in J\rightarrow K$, that is $xI\subseteq K$ and
$yJ\subseteq K$. Thus $x(I\cap J)\subseteq K$ and $y(I\cap J)\subseteq K$,
which allow to obtain $z(I\cap J)=(x+y)(I\cap J)\subseteq K$.

Therefore $(I\rightarrow K)+(J\rightarrow K)\subseteq(I\cap J)\rightarrow K$.

Using the same previous method with $"\rightsquigarrow"$ it is straightforward
that PBLR-2 iff $(I\cap J)\rightsquigarrow K=(I\rightsquigarrow
K)+(J\rightsquigarrow K)$.

(3) Assume that PBLR-2 is true, then for ideals $J$ and $K$ of $R$, we have
$J\rightarrow K+K\rightarrow J=R$. Let $y\in I\rightarrow(J+K)$, then $y\in
R$. This means that $y$ can be write as $y=y\cdot j+y\dot{k}$, with $j\in J$
and $k\in K$, such that $j+k=1$ (1 is an idempotent). Since $y\cdot j\in
I\rightarrow J$ and $y\cdot k\in I\rightarrow K$, then
$I\rightarrow(J+K)\subseteq(I\rightarrow J)+(I\rightarrow K)$.

Let $x\in(I\rightarrow J)+(I\rightarrow K)$, then $x=a+b$ with $a\in
I\rightarrow J$ and $b\in I\rightarrow K$. Thus $aI\subseteq J$ and
$bI\subseteq K$, so $aI+bI\subseteq J+K$. Therefore $xI\subseteq J+K$, and
$I\rightarrow(J+K)\supseteq(I\rightarrow J)+(I\rightarrow K)$.

Conversely, assume now that $I\rightarrow(J+K)=(I\rightarrow J)+(I\rightarrow
K)$. Set $I=J+K$, then by Lemma 3.2, we have $J\rightarrow K+K\rightarrow J=R$
for all ideals $J,K$ of $R$. Thus PBLR-2 holds.

Using the same previous method with $"\rightsquigarrow"$ it is straightforward
that PBLR-2 iff $I\rightsquigarrow(J+K)=(I\rightsquigarrow
J)+(I\rightsquigarrow K)$.

###### Remark 3.5

Let $R$ be a commutative ring. If $I\rightarrow J=I\rightsquigarrow J$, then
$R$ is a BL-ring.

By Definitions 3.1 and 2.4, we have the following results that give a
characterization of the pseudo BL-rings.

###### Proposition 3.6

Let $R$ be a ring. $R$ satisfies $PBLR-1$ if and only if it is a
multiplication ring.

Proof. Let $R$ be a ring. Assume that $R$ satisfies $PBLR-1$, then $I\cap
J=I\cdot(I\rightsquigarrow J)=(I\rightarrow J)\cdot I$. Let $I$ and $J$ be two
ideals of $R$ such that $I\subseteq J$. We found two ideals $K$ and
$K^{\prime}$ of $R$, such that $I=J\cdot K=K^{\prime}\cdot J$.

By $PBLR-1$, $I=I\cap J=J\cdot(J\rightsquigarrow I)=(J\rightarrow I)\cdot J$.
Then took $K=J\rightsquigarrow I$ and $K^{\prime}=J\rightarrow I$.

Conversely, assume that $R$ is a multiplication ring and let $I$, $J$ be
ideals of $R$. Since $I\cap J\subseteq J$, there exist two ideals $K$ and
$K^{\prime}$ of $R$ such that $I\cap J=J\cdot K=K^{\prime}\cdot J$. Hence
$J\cdot K\subseteq I$, $K^{\prime}\cdot J\subseteq I$ and it follows that
$K\subseteq J\rightsquigarrow I$ and $K^{\prime}\subseteq J\rightarrow I$.

Thus $I\cap J\subseteq J\cdot(J\rightsquigarrow I)$ and $I\cap
J\subseteq(J\rightarrow I)\cdot I$. Therefore, $PBLR-1$ holds.

###### Proposition 3.7

Let $R$ be a ring. Then the following are equivalent,

(1) $R$ is a pseudo BL-ring.

(2) $A(R)$ is a pseudo BL-algebra.

Proof. Assume that $R$ is a pseudo BL-ring. Then PBLR-1 and PBLR-2 hold.

By the definition of $A(R)$, $(A(R);\wedge,\vee,\\{0\\},R)$ is a bounded
lattice and $(A(R);\otimes,R)$ is an associative monoid.

Let $I$, $J$ and $K$ be ideals of $R$, then $I\otimes J\subseteq K$
$\Leftrightarrow$ $I\subseteq J\rightarrow K$ $\Leftrightarrow$ $J\subseteq
I\rightsquigarrow K$. Since PBLR-1 and PBLR-2 hold, then prelinearity and
divisibility hold. Thus $A(R)$ is a pseudo BL-algebra.

Conversely assume that $A(R)$ is a pseudo BL-algebra.

Since for all $x,y$ in $R$, $x\wedge y=(x\rightarrow y)\cdot
x=x\cdot(x\rightsquigarrow y)$ and $(x\rightarrow y)\vee(y\rightarrow
x)=(x\rightsquigarrow y)\vee(y\rightsquigarrow x)=1$, then PBLR-1 and PBLR-2
hold. Therefore by Proposition 3.6, $R$ is a multiplication ring, so generated
by idempotents.

Thus $R$ is a pseudo BL-ring.

We know that if $R$ is a ring and $M_{n}(R)$ the ring of $n\times n$ matrices
over $R$, then any ideal $\mathcal{I}$ of $M_{n}(R)$ has the form $M_{n}(I)$
for a uniquely determined ideal $I$ of $R$ [9].

###### Lemma 3.8

If $R$ is a multiplicative ring, then $M_{n}(R)$ is a multiplicative ring.

Proof. Let $M_{n}(I)$ and $M_{n}(J)$ two ideals of $M_{n}(R)$ such that
$M_{n}(I)\subseteq M_{n}(J)$, with $I,J$ two ideals of $R$.

It is easily verify that $M_{n}(I)\subseteq M_{n}(J)$ if and only if
$I\subseteq J$. Since $R$ is a multiplicative ring, then there exist $K$ and
$K^{\prime}$ two ideals of $R$, such that $I=J\cdot K=K^{\prime}\cdot J$ which
allow to say that $M_{n}(I)=M_{n}(J)\cdot M_{n}(K)=M_{n}(K^{\prime})\cdot
M_{n}(J)$. Thus $M_{n}(R)$ is a multiplicative ring.

###### Lemma 3.9

If $R$ is a multiplicative ring, then $M_{n}(R)$ satisfies PBLR-1.

Proof. Let $R$ be a multiplicative ring, then by using Lemma 3.8 and
Proposition 3.6, we have that PBLR-1 holds for $M_{n}(R)$.

###### Lemma 3.10

Let $I$ and $J$ be two ideals of a ring $R$, then

(1) $M_{n}(I+J)=M_{n}(I)+M_{n}(J)$.

(2) $M_{n}(I\rightarrow J)=M_{n}(I)\rightarrow M_{n}(J)$ and
$M_{n}(I\rightsquigarrow J)=M_{n}(I)\rightsquigarrow M_{n}(J)$.

Proof. Straightforward, just use the definition of the operations involved.

###### Example 3.11

Let $R$ be a Notherian multiplicative ring, then $M_{n}(R)$ is a pseudo BL-
ring.
Let $R$ be a discrete valuation ring or a Łukasiewicz ring, then $M_{n}(R)$ is
a pseudo BL-ring.

Now given a ring $R$ and a proper ideal $I$ of R, let’s consider the ring
$R/I$. An ideal of $R/I$ is a set $J/I=\\{x/I~{}|~{}x\in J\\}$, where $J$ is
an ideal of $R$ and $I\subseteq J$. We also define the left annihilator(
respectively the right annihilator) of an ideal $I$ by $I^{\ast}=\\{x\in
R~{}|~{}xI=\\{0\\}\\}=\\{x\rightarrow 0~{}|~{}x\in I\\}$ (respectively
$I^{-}=\\{x\in R~{}|~{}Ix=\\{0\\}\\}=\\{x\rightsquigarrow 0~{}|~{}x\in I\\}$).

###### Lemma 3.12

Let $I$ ,$J$ and $K$ be ideals of a ring $R$, such that $I\subseteq J$ and
$I\subseteq K$. Then,

(1) $(J/I)^{\ast}=(J\rightarrow I)/I$ and $(J/I)^{-}=(J\rightsquigarrow I)/I$.

(2) $(J/I)\rightarrow(K/I)=(J\rightarrow K)/I$ and
$(J/I)\rightsquigarrow(K/I)=(J\rightsquigarrow K)/I$

Proof. (1) Let $x/I\in(J/I)^{\ast}$, then for all $a/I$ with $a\in J$, $xa\in
I$. This means that $xJ\subseteq I$. Thus $x/I\in(J\rightarrow I)/I$.

Therefore $(J/I)^{\ast}\subseteq(J\rightarrow I)/I$.

Conversely let $y/I\in(J\rightarrow I)/I$, then for any $a/I\in J/I$, $ya\in
I$ because, $yJ\subseteq I$ by the definition of $y/I\in(J\rightarrow I)/I$.
This means that $y/I(J/I)=I$. Therefore $(J/I)^{\ast}\supseteq(J\rightarrow
I)/I$.
To show that $(J/I)^{-}=(J\rightsquigarrow I)/I$ holds, we just have to use
same idea as in $(J/I)^{\ast}=(J\rightarrow I)/I$.

(2) Let $y/I\in(J\rightarrow K)/I$, then $yJ\subseteq K$. This implies that
$(xJ)/I\subseteq K/I$ which is $(y/I)\cdot(J/I)\subseteq K/I$. Thus
$(J\rightarrow K)/I\subseteq(J/I)\rightarrow(K/I)$.
Conversely let $x/I\in(J/I)\rightarrow(K/I)$, then for all $a\in J$ $xa\in K$,
which implies that $x/I\in(J\rightarrow K)/I$. Therefore
$(J/I)\rightarrow(K/I)\subseteq(J\rightarrow K)/I$.
With the same idea as for $(J/I)\rightarrow(K/I)=(J\rightarrow K)/I$, we show
that $(J/I)\rightsquigarrow(K/I)=(J\rightsquigarrow K)/I$.

It is possible to observe if the property PBLR-2 in a ring $R$ by observing
his quotient by a proper ideal. This is the main purpose of the following
propositions.

###### Proposition 3.13

Let $I$ and $J$ be two ideals of a ring $R$. If the ring $R$ satisfies PBLR-2,
then $I\cap J=\\{0\\}$ implies that $I^{\ast}+J^{\ast}=R$ and $I^{-}+J^{-}=R$.

Proof. Assume that $I\cap J=\\{0\\}$.

PBLR-2 holds means that $I\rightarrow J+J\rightarrow I=R$ and
$I\rightsquigarrow J+J\rightsquigarrow I=R$. then $I^{\ast}+J^{\ast}=R$ and
$I^{-}+J^{-}=R$ by using Lemma 3.2, definitions and operations involved.

We denote PBLR-3: $I\cap J=\\{0\\}$ implies that $I^{\ast}+J^{\ast}=R$ and
$I^{-}+J^{-}=R$.

###### Proposition 3.14

A ring $R$ satisfies PBLR-2 if and only if every quotient of $R$ by an ideal
satisfies PBLR-3.

Proof. Let $I$ be an ideal of the ring $R$ which satisfies PBLR-2. Let $J,K$
two ideals of $R$ such that $I\subseteq J$, $J\subseteq K$ and
$(J/I)\cap(K/I)=I$. It is clear that $J\cap K=I$. Since
$(J/I)^{-}+(K/I)^{-}=(J\rightarrow I)/I+(K\rightarrow I)/I=(J\rightarrow(J\cap
K))/I+(K\rightarrow(J\cap K))/I=((J\rightarrow K)+(K\rightarrow J))/I=R/I$ (by
using Lemmas 3.2, 3.12). In the same way, $(J/I)^{\ast}+(K/I)^{\ast}=R/I$.
Thus, PBLR-3 holds for $R/I$.
Conversely, suppose that in every factor of $R$, PBLR-3 holds. Let $I$, $J$ be
ideals of $R$, then $R/(I\cap J)$ satisfies PBLR-3. Clearly $(I/(I\cap
J))\cap(J/(I\cap J))=(I\cap J)$, then $(I/(I\cap J))^{-}+(J/(I\cap
J))^{-}=R/(I\cap J)$ and $(I/(I\cap J))^{\ast}+(J/(I\cap J))^{\ast}=R/(I\cap
J)$ (by using Lemma 3.12). That is $(I\rightsquigarrow J)/(I\cap
J)+(J\rightsquigarrow I)/(I\cap J)=(I\rightarrow J)/(I\cap J)+(J\rightarrow
I)/(I\cap J)=R/(I\cap J)$. Thus, $((I\rightarrow J)+(J\rightarrow I))/(I\cap
J)=((I\rightsquigarrow J)+(J\rightsquigarrow I))/(I\cap J)=R/(I\cap J)$ that
implies $(I\rightarrow J)+(J\rightarrow I)=R$ and $(I\rightsquigarrow
J)+(J\rightsquigarrow I)=R$. Finally $R$ satisfies PBLR-2, which conclude the
proof.

###### Proposition 3.15

Every quotient of a multiplication rings is a multiplication ring.

Proof. Let $R$ be a multiplication ring and $K$ an ideal of $R$. Let $I/K$ and
$J/K$ be two ideals of $R/K$ such that $I/K\subseteq J/K$, then $I\subseteq
J$. Hence, there exist ideals $T$ and $T^{\prime}$ of $R$ (because $R$ is a
multiplication ring) such that $I=J\cdot T=T^{\prime}\cdot J$. Thus
$I/K=(J\cdot T)/K=(T^{\prime}\cdot J)/K$ and $I/K=J/K\cdot
T/K=T^{\prime}/K\cdot J/K$. Therefore, $R/K$ is a multiplication ring.

###### Proposition 3.16

Let $R$ be a multiplication ring such that the quotient ring satisfies PBLR-3,
then $R$ satisfies PBLR-3.

Proof. Let $R$ ba a multiplication ring, then the quotient is a multiplication
ring (by Proposition 3.15). Since the quotient of $R$ satisfies PBLR-3 then,
then the ring $R$ satisfies PBLR-2 (by Proposition 3.14). We use the
Proposition 3.13 to conclude that PBLR-3 hlods for the ring $R$.

###### Corollary 3.16.1

Every multiplication ring satisfies PBLR-2 if and only if every multiplication
ring satisfies PBLR-3.

###### Corollary 3.16.2

Any quotient of a pseudo BL-ring by a proper ideal is again a pseudo BL-ring.

###### Definition 3.17

([9]) A ring $R$ is called a prime ring if the null ideal $(O)$ is a prime
ring.

###### Proposition 3.18

Prime ideals of pseudo BL-rings are maximal.

Proof. Let $I$, $J$ be two ideals of a pseudo BL-ring $R$, such that $I$ is a
prime ideal and $I\subseteq J\subseteq R$ (with $I\neq J$). Since $I$ is
prime, it is known that $R/I$ is a prime ring, so
$(J/I)^{\ast}=(J/I)^{-}=0/I$.

Since $R/I$ is a pseudo BL-ring (by Corollary 3.16.2),
$(J/I)=((J/I)^{\ast})^{\ast}=((J/I)^{-})^{-}=(0/I)^{\ast}=(0/I)^{-}=R/P$. Thus
$J=R$ and $I$ is a maximal ideal of $R$.

###### Proposition 3.19

Let $R$ be a pseudo BL-ring and $I$ an ideal of $R$ such that $I\cap
I^{\ast}=\\{0\\}$ and $I\cap I^{-}=\\{0\\}$. Then $I$ is a pseudo BL-ring.

Proof. It is well known that an ideal is a subring, thus $Id(I)\subseteq
Id(R)$ because

$\left\\{\begin{array}[]{ll}I\cap I^{\ast}=\\{0\\}&\hbox{}\\\ I\cap
I^{-}=\\{0\\}&\hbox{}\end{array}\right.$

imply that,

$\left\\{\begin{array}[]{ll}I+I^{\ast}=I\vee I^{\ast}=R&\hbox{}\\\
I+I^{-}=I\vee I^{-}=R&\hbox{}\end{array}\right.$

Since $R$ is generated by idempotents, for any $x\in I$, there are
$e,e^{\prime}\in R$, (right and left idempotents) $m_{1},m_{3}\in I$ and
$m_{2}\in I^{\ast}$, $m_{4}\in I^{-}$ such that

$ex=x,\ e^{\prime}x=x$

and

$\left\\{\begin{array}[]{ll}m_{1}+m_{2}=e&\hbox{}\\\
m_{3}+m_{4}=e^{\prime}&\hbox{}\end{array}\right.$

Then

$\left\\{\begin{array}[]{ll}m_{1}e+m_{2}e=e^{2}=e=m_{1}+m_{2}\Rightarrow
m_{1}-m_{1}e=m_{2}e-m_{2}\in I\cap I^{\ast}=\\{0\\}&\\\
e^{\prime}m_{3}+e^{\prime}m_{4}=(e^{\prime})^{2}=e^{\prime}=m_{3}+m_{4}\Rightarrow
m_{3}-e^{\prime}m_{3}=e^{\prime}m_{4}-m_{4}\in I\cap
I^{-}=\\{0\\}&\end{array}\right.$

It follow that

$\left\\{\begin{array}[]{ll}m_{1}=m_{1}e,~{}m_{2}e=m_{2},&\\\
e^{\prime}m_{3}=m_{3},~{}e^{\prime}m_{4}=m_{4},&\end{array}\right.$

$x=m_{1}x$, $x=xm_{3}$, $(m_{1})^{2}=m_{1}$, $(m_{3})^{2}=m_{3}$ since
$m_{2}\in M^{\ast}$, $m_{4}\in I^{-}$. Thus $m_{1}$ and $m_{3}$ are
idempotents in $I$, and $I$ is generated by idempotents.

Since $Id(M)\subseteq Id(R)$, then by Proposition 3.16, PBLR-2 holds for $I$.
Hence $I$ is a pseudo BL-ring.

###### Proposition 3.20

Let $R$ be a pseudo BL-rings. $R$ are closed under each of the following
operations,

(1)finite direct products,

(2) arbitrary direct sums,

(3) homomorphic images.

Proof.

$\left(1\right)$ Let $R=\displaystyle{\prod_{k=1}^{n}}R_{k}$ where each
$R_{k}$ is a pseudo BL-ring. Since each $R_{k}$ is generated by idempotents,
one gets that any ideal $\mathit{I}$ of $\mathit{R}$ is of the form,

$I=\displaystyle{\prod_{k=1}^{n}}I_{k},$

where $I_{k}$ is an ideal of $R_{k}.$

Let $I=\displaystyle{\prod_{k=1}^{n}}I_{k}$ and
$J=\displaystyle{\prod_{k=1}^{n}}J_{k}$ to be two ideals of $\mathit{R}$, we
get,

$I\cdot
J=\displaystyle{\prod_{k=1}^{n}}I_{k}\cdot\displaystyle{\prod_{k=1}^{n}}J_{k}=\displaystyle{\prod_{k=1}^{n}}I_{k}\cdot
J_{k}.$

Analogously, we also have $I\rightarrow
J=\displaystyle{\prod_{k=1}^{n}}I_{k}\rightarrow J_{k}$ and $I\rightsquigarrow
J=\displaystyle{\prod_{k=1}^{n}}I_{k}\rightsquigarrow J_{k}.$

Then

$I\cap
J=\displaystyle{\prod_{k=1}^{n}}I_{k}\cap\displaystyle{\prod_{k=1}^{n}}J_{k}=\displaystyle{\prod_{k=1}^{n}}(I_{k}\cap
J_{k})=\displaystyle{\prod_{k=1}^{n}}(I_{k}\cdot(I_{k}\rightsquigarrow
J_{k})=\displaystyle{\prod_{k=1}^{n}}I_{k}\cdot\displaystyle{\prod_{k=1}^{n}}(I_{k}\rightsquigarrow
J_{k})=I\cdot(I\rightsquigarrow J)$

and

$\displaystyle{\prod_{k=1}^{n}}(I_{k}\cap
J_{k})=\displaystyle{\prod_{k=1}^{n}}(I_{k}\rightarrow J_{k})\cdot
I_{k}=\displaystyle{\prod_{k=1}^{n}}(I_{k}\rightarrow
J_{k})\cdot\displaystyle{\prod_{k=1}^{n}}I_{k}=(I\rightarrow J)\cdot I.$

Thus $R$ satisfies PBLR-1, and because
$I+J=\displaystyle{\prod_{k=1}^{n}}I_{k}+\displaystyle{\prod_{k=1}^{n}}J_{k}=\displaystyle{\prod_{k=1}^{n}}(I_{k}+J_{k}),$
we have,

$(I\rightarrow J)+(J\rightarrow
I)=\displaystyle{\prod_{k=1}^{n}}(I_{k}\rightarrow
J_{k})+\displaystyle{\prod_{k=1}^{n}}(J_{k}\rightarrow
I_{k})=\displaystyle{\prod_{k=1}^{n}}((I_{k}\rightarrow
J_{k})+(J_{k}\rightarrow I_{k}))=\displaystyle{\prod_{k=1}^{n}}R_{k}=R,$

and

$(I\rightsquigarrow J)+(J\rightsquigarrow
I)=\displaystyle{\prod_{k=1}^{n}}(I_{k}\rightsquigarrow
J_{k})+\displaystyle{\prod_{k=1}^{n}}(J_{k}\rightsquigarrow
I_{k})=\displaystyle{\prod_{k=1}^{n}}((I_{k}\rightsquigarrow
J_{k})+(J_{k}\rightsquigarrow I_{k}))=\displaystyle{\prod_{k=1}^{n}}R_{k}=R.$

Thus $\mathit{R}$ satisfies PBLR-2. Therefore $\mathit{R}$ is a pseudo BL-
ring.

$\left(2\right)$ Let $R=\displaystyle{\bigoplus_{k=1}^{n}}R_{k},$ where each
$R_{k}$ is a pseudo BL-ring. Since each $R_{k}$ is generated by idempotents,
one gets that any ideal $I$ of $R$ is of the form,

$I=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}$

where $I_{k}$ is an ideal of $R_{k}.$

Let $I=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}$ and
$J=\displaystyle{\bigoplus_{k=1}^{n}}J_{k}$ to be two ideals of $R,$ we get,

$I\cdot
J=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\cdot\displaystyle{\bigoplus_{k=1}^{n}}J_{k}=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\cdot
J_{k};$

analogously, we also have $I\rightarrow
J=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\rightarrow J_{k}$ and
$I\rightsquigarrow J=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\rightsquigarrow
J_{k}.$ Then

$I\cap
J=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\cap\displaystyle{\bigoplus_{k=1}^{n}}J_{k}=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\cap
J_{k})=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\cdot(I_{k}\rightsquigarrow
J_{k})=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}\cdot\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\rightsquigarrow
J_{k})=I\cdot(I\rightsquigarrow J)$

and

$\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\cap
J_{k})=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\rightarrow J_{k})\cdot
I_{k}=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\rightarrow
J_{k})\cdot\displaystyle{\bigoplus_{k=1}^{n}}I_{k}=(I\rightarrow J)\cdot I.$

Thus $\mathit{R}$ satisfies PBLR-1, and because
$I+J=\displaystyle{\bigoplus_{k=1}^{n}}I_{k}+\displaystyle{\bigoplus_{k=1}^{n}}J_{k}=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}+J_{k}),$
we have,

$(I\rightarrow J)+(J\rightarrow
I)=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\rightarrow
J_{k})+\displaystyle{\bigoplus_{k=1}^{n}}(J_{k}\rightarrow
I_{k})=\displaystyle{\bigoplus_{k=1}^{n}}((I_{k}\rightarrow
J_{k})+(J_{k}\rightarrow I_{k}))=\displaystyle{\bigoplus_{k=1}^{n}}R_{k}=R$

and

$(I\rightsquigarrow J)+(J\rightsquigarrow
I)=\displaystyle{\bigoplus_{k=1}^{n}}(I_{k}\rightsquigarrow
J_{k})+\displaystyle{\bigoplus_{k=1}^{n}}(J_{k}\rightsquigarrow
I_{k})=\displaystyle{\bigoplus_{k=1}^{n}}((I_{k}\rightsquigarrow
J_{k})+(J_{k}\rightsquigarrow
I_{k}))=\displaystyle{\bigoplus_{k=1}^{n}}R_{k}=R.$

Thus $R$ satisfies PBLR-2. Therefore $R$ is a pseudo BL-ring.

$\left(3\right)$ Let $R$ be a PBL-ring and $I$ be an ideal of $R$. We recall
that the ideals of $R/I$ are the form $J/I$, where $J$ is an ideal of $R$ with
$I\subseteq J.$

Let $J$ and $K$ two ideals of $R$ such that $I\subseteq J,K.$ Then
$(J/I)\cap(K/I)=(J\cap K)/I=((J\rightarrow K)\cdot J)/I=(J\rightarrow
K)/I\cdot(J/I)=((J/I)\rightarrow(K/I))\cdot(J/I)$; furthermore, $(J\cap
K)/I=J\cdot(J\rightsquigarrow K)/I=(J/I)\cdot(J\rightsquigarrow
K)/I=(J/I)\cdot(J/I\rightsquigarrow K/I),$ thus $R/I$ satisfies PBLR-1.

We also have $(J/I\rightarrow K/I)+(K/I\rightarrow
J/I)=(J+K)/I\rightarrow(K+J)/I=((J\rightarrow K)+(K\rightarrow J))/I=R/I$ and
$(J/I\rightsquigarrow K/I)+(K/I\rightsquigarrow
J/I)=(J+K)/I\rightsquigarrow(K+J)/I=((J\rightsquigarrow K)+(K\rightsquigarrow
J))/I=R/I$ thus $R/I$ satisfies PBLR-2. Therefore $R/I$ is a pseudo BL-ring.

We establish the connection between pseudo BL-ring and some well known rings.

###### Definition 3.21

A unitary ring is called a Von Neumann ring if $R/P$ is a division ring for
all prime ideals of $R$.

###### Definition 3.22

A non commutative Bear ring is a ring in which for every ideal $I$ of $R$,
there exist idempotents $e,e^{\prime}\in R$ such that $I^{\ast}=eR$ and
$I^{-}=Re^{\prime}$.

An ideal in a Bear ring (commutative or not) is called a Bear-ideal if for
every $a,b\in R$ such that $a-b\in I$, then $a^{\ast}-b^{\ast}\in I$ and
$a^{-}-b^{-}\in I$.

###### Definition 3.23

([8]) A reducing ring is a ring in which 0 is the only nilpotent element, that
is, the only element $x\in R$ for which there exists an integer $n\geq 1$ such
that $x^{n}=0$.

###### Lemma 3.24

Let $R$ be a ring and $I$, $J$ be ideals of $R$. If $I\cap J=\\{0\\}$, then
$I\subseteq J^{\ast}$, $I\subseteq J^{-}$.

Proof. This is easily derived from the definition of an ideal and the
operations $(^{\ast})$ and $(^{-})$ involved.

###### Proposition 3.25

In a reduced ring with identities, PBLR-3 holds if and only if this ring is a
Bear ring.

Proof. Let $R$ be a reduced ring with identities in which PBLR-3 hlods. Let
$K$ be an ideal of $R$, then $K\cap K^{\ast}=\\{0\\}$ and $K\cap
K^{-}=\\{0\\}$ implies $K^{\ast}+(K^{\ast})^{\ast}=R$ and
$K^{-}+(K^{-})^{-}=R$. Thus, there are $k_{1}\in K^{\ast}$,
$k_{1}^{{}^{\prime}}\in(K^{\ast})^{\ast}$, $k_{2}\in K^{-}$,
$k_{2}^{{}^{\prime}}\in(K^{-})^{-}$ such that
$1_{L}=k_{1}+k_{1}^{{}^{\prime}}$ and $1_{R}=k_{2}+k_{2}^{{}^{\prime}}$.These
mean that,

$\left\\{\begin{array}[]{ll}k_{1}=k_{1}\cdot
1_{L}=k_{1}(k_{1}+k_{1}^{{}^{\prime}})=k_{1}^{2}&\hbox{}\\\ k_{2}=1\cdot
k_{2}=(k_{2}+k_{2}^{{}^{\prime}})k_{2}=k_{2}^{2}&\hbox{}\end{array}\right.$

which imply that $k_{1}$ and $k_{2}$ are idempotents.

It remains to show that $K^{\ast}=k_{1}R$ and $K^{-}=Rk_{2}$. Let $x\in
K^{\ast}$, then $x=1_{L}\cdot x=(k_{1}+k_{1}^{{}^{\prime}})x=k_{1}x\in
k_{1}R$.

Let $y\in k_{1}R$, then there is $r\in R$ such that $y=k_{1}r\in K^{\ast}$
because $k_{1}\in K^{\ast}$. Therefore $K^{\ast}=k_{1}R$.
By the similar way, $K^{-}=Rk_{2}$. Then $R$ is a non commutative Bear ring.

Conversely, assume that $I$ and $J$ are two ideals of a Bear ring such that
$I\cap J=\\{0\\}$. We have to show that $I^{\ast}+J^{\ast}=R=I^{-}+J^{-}$.

Since $R$ is a Bear ring, there exist $e$ and $e^{\prime}$ idempotents in $R$
such that $J^{\ast}=eR$ and $J^{-}=Re^{\prime}$. Thus $I\subseteq eR$ and
$I\subseteq Re^{\prime}$ (by Lemma 3.24). Hence for all $i\in I$,
$i=er=r^{\prime}e^{\prime}$ for some $r,r^{\prime}\in R$ and

$\left\\{\begin{array}[]{ll}0=er-er=er-e^{2}r=(1_{L}-e)er&\hbox{}\\\
0=r^{\prime}e^{\prime}-e^{\prime}r^{\prime}=r^{\prime}e^{\prime}-(e^{\prime})^{2}r^{\prime}=r^{\prime}e^{\prime}(1_{R}-e^{\prime})&\hbox{}\end{array}\right.$

which imply $1_{L}-e\in I^{\ast}$ and $1_{R}-e^{\prime}\in I^{-}$.
Therefore,

$\left\\{\begin{array}[]{ll}1_{L}=(1_{L}-e)+e\in
I^{\ast}+(I^{\ast})^{\ast}&\hbox{}\\\ 1_{R}=(1_{R}-e^{\prime})+e^{\prime}\in
I^{-}+(I^{-})^{-}&\hbox{}\end{array}\right.$

Since $(I^{\ast})^{\ast}$ and $I^{-}+(I^{-})^{-}$, then $I^{\ast}+J^{\ast}=R$
and $I^{-}+J^{-}=R$.

###### Proposition 3.26

Every Bear-ideals $I$, $J$ of a Bear ring $R$ satisfy, $(I\rightarrow
J)+(J\rightarrow I)=R$ and $(I\rightsquigarrow J)+(J\rightsquigarrow I)=R$.

Proof. Straightforward by using Propositions 3.25 and 3.14 in this order.

The same result as in the Proposition 3.15 holds for Bear rings and Bear-
ideals.

###### Proposition 3.27

Every quotient of a Bear ring (by an Bear ring) is a multiplication Bear ring.

###### Lemma 3.28

Every Von Neumann is a multiplication ring.

Proof. Let $I$ and $J$ be two ideals of a non commutative Von Neumann ring $R$
and $P$ a prime ideal of $R$. Since all multiplicative ring have the PBLR-1
property and vice-versa (by Proposition 3.6), then by Definition 3.21 of a non
commutative Von Neumann ring, we only have to show that $I/P\cap
J/P=(I/P)\cdot((I\rightsquigarrow J)/P)$ and $I/P\cap J/P=((I\rightarrow
J)/P)\cdot(I/P)$. Since in the division ring $R/P$ the ideals $I/P$ and $J/P$
are trivials, we just have to check four cases.

(Case 1) If $I/P=J/P=\\{0/P\\}$, then $I/P\cap J/P=\\{O/P\\}$ and
$(I/P)\cdot((I\rightsquigarrow J)/P)=((I\rightarrow
J)/P)\cdot(I/P)=\\{0/P\\}$. Hence the property PBLR-1 holds.

(Case 2) If $I/P=\\{0/P\\}$ and $J/P=R/P$, then $I=\\{0\\}$, which imply
$I/P\cap J/P=\\{0/P\\}$ and $(I/P)\cdot((I\rightsquigarrow
J)/P)=((I\rightarrow J)/P)\cdot(I/P)=\\{0/P\\}$. Hence the property PBLR-1
holds.

(Case 3) If $I/P=R/P$ and $J/P=\\{0/P\\}$, using the definitions of
$(I\rightsquigarrow J)/P$ and $(I\rightarrow J)/P$, we easily prove that
$(I/P)\cdot((I\rightsquigarrow J)/P)=((I\rightarrow
J)/P)\cdot(I/P)=\\{0/P\\}$. Hence the property PBLR-1 holds.

(Case 4) If $I/P=R/P$ and $J/P=R/P$, using the definitions of
$(I\rightsquigarrow J)/P$ and $(I\rightarrow J)/P$, we easily prove that
$(I/P)\cdot((I\rightsquigarrow J)/P)=((I\rightarrow J)/P)\cdot(I/P)=R/P$.
Hence the property PBLR-1 holds.

we complete the proof.

###### Proposition 3.29

Let $R$ be a unitary Von Neumann ring. Then $R$ is a pseudo BL-ring if and
only if it satisfies $I/P=J/P=\\{0\\}$ implies $(I\rightarrow J)/P=R/P$. For
all ideals $I$, $J$ of $R$ and all prime ideals $P$ of $R$.

Proof. This result follows directly from the Lemma 3.28.

##  4 Representation of pseudo-BL algebras

The purpose of this section is to find a representation of pseudo BL-ring in
the sense of subdirectly irreducible algebras. We start this section with the
definitions of subdirectly irreducible ring and special primary ring.

###### Definition 4.1

A ring $R$ is said to be subdirectly irreducible if every subdirect product of
$R$ is trivial.

Equivalently, a ring $R$ is subdirectly irreducible if and only if the
intersection of all non-zero ideals of $R$ is non-zero.

###### Definition 4.2

A ring $R$ is a special primary ring if $R$ has a unique maximal ideal $M$ and
if each proper ideal of $R$ is a power of $M$.

If $P$ is a prime ideal of ring $R$ and if $S=R\setminus P$, we shall denote
$0_{S}^{\ast}$ (respectively $0_{S}^{-}$), the $S$-component of the right zero
ideal, by $N^{\ast}(P)$ (respectively $N^{-}(P)$), that is,
$N^{\ast}(P)=\\{x\in R~{}|~{}xs=0$ for some $s\in R\setminus P\\}$
(respectively $N^{-}(P)=\\{x\in R~{}|~{}sx=0$ for some $s\in R\setminus
P\\}$).

###### Lemma 4.3

Let $R$ be a ring that is generated by idempotents and $P$ be a prime ideal of
$R$. Then,

$\displaystyle{\bigcap_{P}}N^{\ast}(P)=\\{0\\}~{}and~{}\displaystyle{\bigcap_{P}}N^{-}(P)=\\{0\\}.$

Proof. To show that $\displaystyle{\bigcap_{P}}N^{\ast}(P)=0$ and
$\displaystyle{\bigcap_{P}}N^{-}(P)=0$, it is sufficient to prove that if
$x\neq 0$, then there exists a prime ideal $P$ such that $x\notin N^{\ast}(P)$
and $x\notin N^{-}(P)=0$.

Let $x\neq 0$, then $(xR)^{\ast}\neq R$ and $(Rx)^{-}\neq R$ (because if we
assume that the are all equal, then for all $z\in R$, $z\cdot x=0$ and $x\cdot
z=0$ with $x\neq 0$, which mean that for all $z\in R$, $z=0$. So $R=\\{0\\}$
contradiction). Thus by Proposition [2.10, [8]] there exists a prime ideal $Q$
of $R$ such that $(xR)^{\ast}\subseteq Q$ and $(Rx)^{-}\subseteq Q$.

Assume that $x\in N^{\ast}(Q)$ and $x\in N^{-}(Q)$, then $sx=0$ and $xs=0$ for
some $s\notin Q$.

If $s\cdot x=0$, then $(s\cdot x)R=\\{0\\}$, thus $s\in(xR)^{\ast}\subseteq
Q$. Therefore $x\notin N^{\ast}(Q)$.

If $x\cdot s=0$, then $R(x\cdot s)=\\{0\\}$, thus $s\in(xR)^{-}\subseteq Q$.
Therefore $x\notin N^{-}(Q)$.

Hence,
$\displaystyle{\bigcap_{P}}N^{\ast}(P)=\displaystyle{\bigcap_{P}}N^{-}(P)=\\{0\\}$.

###### Proposition 4.4

Every unitary pseudo BL-ring with left and right unit is isomorphic to a
subring of a direct product of special primary rings.

Proof. Let $R$ be a pseudo BL-ring with left and right unit, and $P$ a prime
ideal of $R$. Then by Proposition 3.6 it is know that $R$ is a multiplicative
ring.

Let consider the mappings $f:R\rightarrow\displaystyle{\prod_{P}}R/P$ such
that $f(x)=(\frac{x}{1_{R}})/P$ a sequence on the prime ideals of $R$ and
$g:R\rightarrow\displaystyle{\prod_{P}}R/P$ such that
$g(x)=(\frac{x}{1_{L}})/P$ a sequence on the prime ideals of $R$. We easily
check that $f$ and $g$ are ring homomorphisms. Using the previous Lemma 4.3,
the kernels of $f$ and $g$ are define to be
$\ker(f)=\displaystyle{\bigcap_{P}}N^{\ast}(P)=\\{O\\}$ and
$\ker(g)=\displaystyle{\bigcap_{P}N^{-}(P)}=\\{0\\}$. Hence $R$ is isomorphic
to $f(R)$ and $g(R)$ two subring of $\displaystyle{\prod_{P}}R/P$. Since $R$
is a multiplicative ring, then by Theorem 9.23 and Propositions 9.25 and 9.26
in [10], each $R/P$ is a special primary ring.

###### Proposition 4.5

Every unitary pseudo BL-ring with left and right unit is isomorphic to a
subring of a direct product of discrete valuation rings.

Proof. We use the same idea as in Proposition 4.4 and [10].

###### Proposition 4.6

Let $R$ be a subdirectly irreducible pseudo BL-ring with minimal ideal $M$.
Then,

(1) $M$ is an annihilator ideal.

(2) The annihilator ideals of $R$ are linearly ordered and finite in number.

Proof. (1) We know by definition of $M^{\ast}$ that it is an ideal of $R.$
Since $M$ is the minimal ideal of $R,$ then $M\subseteq M^{\ast},$ and because
$M\neq\\{0\\},$ then $M^{\ast}\neq R.$ Therefore, by the maximality of $M,$ we
obtain that $M=M^{\ast};$ similarly, we show that in the case of right ideal
$M^{-}$ of $R,$ we also have $M=M^{-};$
therefore $M$ is an annihilator ideal.

(2) Let $R$ be a pseudo BL-ring, then $A(R)$ is a pseudo BL-algebra; are
pseudo MV-algebra. Consequently $AN^{\ast}(R)$ and $AN^{-}(R)$ are
respectively the left pseudo $MV-$ center (and right pseudo $MV$-center) of
$A(R)$. Moreover, for all ideal $I$ of $R$, we have $(\bigvee
I)^{\ast}=\bigcap I^{\ast}$ and $(\bigvee I)^{-}=\bigcap I^{-}$ which imply
that every subset of $AN^{\ast}(R)$ and $AN^{-}(R)$ have an infimum. Thus
every subset of $AN^{\ast}(R)$ and $AN^{-}(R)$ also have a supremum because if
$S$ is a subset of $AN^{\ast}(R)$ (or $AN^{-}(R)$), then $\bigwedge S=(\bigvee
S^{\ast})^{\ast}$ (or $\bigwedge S=(\bigvee S^{-})^{-}$). Hence $AN^{\ast}(R)$
and $AN^{-}(R)$ are complete pseudo $MV-$algebras. Also, for every non zero
ideal $I$ of $R$, $M\subseteq I$ implies that $I^{\ast}\subseteq M^{\ast}$ and
$I^{-}\subseteq M^{-}$.

Therefore, for every proper ideals $J$ in $AN^{\ast}(R)$ and $K$ in
$AN^{-}(R)$, we have $J^{\ast}\subseteq M^{\ast}$ and $K^{-}\subseteq M^{-}$
this induce that $AN^{\ast}(R)\setminus\\{R\\}$ and
$AN^{-}(R)\setminus\\{R\\}$ have both of them a maximum element, namely
$M^{\ast}\neq R$ and $M^{-}\neq R$ because $M\neq\\{0\\}$.

Let $X,Y\in AN^{\ast}(R)$ such that $X$ is not include in $Y$ and $Y$ is not
include in $X$, then $X\rightarrow Y,Y\rightarrow X\neq R$ and $X\rightarrow
Y,Y\rightarrow X\subseteq M^{\ast};$ hence, by pre-linearity axiom,
$R=X\rightarrow Y\vee Y\rightarrow X\subseteq M^{\ast};$ thus $M^{\ast}=R,$
which is a contradiction, so $(AN^{\ast}(R),\subseteq)$ is a pseudo
$MV-$chain.
By the same way we prove that $(AN^{-}(R),\subseteq)$ is a pseudo $MV-$chain.

The next result is the Representation Theorem for pseudo BL-ring.

###### Theorem 4.7

Every pseudo BL-ring $R$ is a subdirect product of a family $\\{R_{x}|x\in
R\setminus\\{0\\}\\}$ of subdirectly irreductible pseudo BL-rings satisfying,

(1) $A(R_{x})$ is isomorphic to $AN^{\ast}(R_{x})\oplus D^{\ast}(R_{x})$ and
to $AN^{-}(R_{x})\oplus D^{-}(R_{x})$ for all $x\neq 0$.

(2) Every ideal of each $R_{x}$ is either an annihilator ideal or dense.

(3) $A(R)$ is a subdirect product of $\\{A(R_{x})|x\in R\setminus\\{0\\}\\}$.

(4) $A(R_{x})$ is a pseudo BL-algebra with a unique atom.

Proof. Let $R$ be a pseudo BL-ring, it is well known that $R$ is a subdirect
product of subdirectly irreductible homomorphic images of $R$. Using the
Zorn’s lemma, for all $x\in R$ and $x\neq 0$, there is an maximal ideal
$K_{x}$ that do not contain $x$, which implies that
$\displaystyle{\bigcap_{x}}K_{x}=\\{0\\}$. Hence each factor $R/K_{x}$ is
subdirectly irreductible and $R$ is the product of the family
$\\{R/K_{x}~{}|~{}x\in R\setminus\\{0\\}\\}$. Since $R/K_{x}$ is a pseudo BL-
ring by Corollary 3.16.2 and Proposition 3.20. Let pick up the set
$\\{R_{x}~{}|~{}x\in R\setminus\\{0\\}\\}$ to be $\\{R/K_{x}~{}|~{}x\in
R\setminus\\{0\\}\\}$. Then the rest of the proof is similar to Theorem 4.2 in
[8].

The following corollary is the same as Corollary 4.3 in [8].

###### Corollary 4.7.1

Let $R$ be a subdirectly irreductible BL-ring. Then

(1) For every annihilator ideal $I\neq R$ and every dense ideal $J$ with
$I\subseteq J$, then $J\rightarrow I=I$ and $J\rightsquigarrow I=I$.

(2) For every ideals $I$, $J$ of $R$, either ($I\rightarrow J$ and
$I\rightsquigarrow J$) or ($J\rightarrow I$ and $J\rightsquigarrow I$) are
denses.

Proof. Let $R$ be a subdirectly irreductible BL-ring. As established in the
proof of Theorem 4.7, $A(R)$ is isomorphic to $AN^{\ast}(R)\oplus D^{\ast}(R)$
and to $AN^{-}(R)\oplus D^{-}(R)$.

(1) By the definition of the implication in the ordinal sum of hoops, the
condition stated hold.

(2) Since $A(R)$ is a pseudo BL-algebra, using the same way as in [2] and [3],
we prove that the sets $D^{\ast}(M)$ and $D^{-}(M)$ of dense elements of any
pseudo BL-algebra $M$ is an implicative filter, $M/D^{\ast}(R)$ is isomorphic
to $AN^{\ast}(M)$ and $M/D^{-}(R)$ is isomorphic to $AN^{-}(M)$.

Therefore, $A(R)/D^{\ast}(R)$ is isomorphic to $AN^{\ast}(R)$, and
$A(R)/D^{-}(R)$ is isomorphic to $AN^{-}(R)$. Futhermore $A(R)/D^{\ast}(R)$
and $A(R)/D^{-}(R)$ are linearly ordered because $AN^{\ast}(R)$ and
$AN^{-}(R)$ are linearly ordered. Now using the definitions of order,
$\rightsquigarrow$ and $\rightarrow$ on $A(R)/D^{\ast}(R)$ and $A(R)/D^{-}(R)$
we conclude the proof.

##  5 Conclusion

It is a well-known result that a $t$-norm has a residuum if and only if the
$t$-norm is left-continuous. Therefore, this shows that Basic Logic is not the
most general $t$-norm-based logic. In fact, a logic weaker than Basic Logic,
called Monoidal $t$-norm-based logic (MTL for short), was defined by Esteva
and Godo in [4] and proved to be the logic of left-continuous $t$-norms and
their residua. Our research in that way will consist to study commutative
rings and non commutative rings $R$ for which $A(R)$ is a MTL-algebra and
pseudo MTL-algebra.

## Acknowledgments

This work is supported by the Foundations of Chongqing Municipal Key
Laboratory of Institutions of Higher Education ([2017]3), Chongqing
Development and Reform Commission (2017[1007]), and Chongqing Three Gorges
University.

## References

  * [1] L. P. Belluce and A. Di Nola, _Commutative rings whose ideals form an MV-algebra_ , Math. Log. Quart.,  55, 2009, 468-486.
  * [2] M. Busaniche and F. Montagna, _Hájek’s logic BL and BL-algebras_ , In Handbook of Mathematical Fuzzy Logic, 1, 2011.
  * [3] A. Di Nola, G. Georgescu, and A. Iorgulescu, _Pseudo-BL algebras: part I, part II_ , Multiple Valued Logic, 8, 2002, 673-714 and 717-750.
  * [4] F. Esteva and L. Godo, _Monoidal $t$-norm based logic:towards a logic for left-continuous $t$-norms_, Fuzzy Sets Syst., 124, 2001, 271-288.
  * [5] G. Georgescu and A. Iorgulescu, _Pseudo-MV algebras: a non-commutative extension of MV-algebras_ , Information Technology, 1999, 961-968.
  * [6] P. Hájek, _Metamathematics of fuzzy logic_ , Kluwer Acad. Publ., Dordrecht, 1998.
  * [7] A. Kadji, C. Lele and J.B.Nganou, _A non-commutative generalization of Łukasiewicz rings_ , Journal of Applied Logic 16, 2016, 1-13.
  * [8] O.A. Heubo-Kwegna, C. LELE, S. Ndjeya and J.B. Nganou, _BL-rings_ , Logic Journal of the IGPL 26, 2018, 290-299.
  * [9] T.Y. Lam, _A First Course in Non-commutative Rings_ , Springer-Verlag, New York, 1991.
  * [10] M.D. Larsen and P.J. McCarthy, _Multiplicative theory of ideals_ , Academic Press, New York and London, 1971.
  * [11] T. Ukegawa, _Some Property of Non-Commutative Multiplication Rings_ , Proc. Japan Acad., 54, 1978, 279-284.


# Bayesian Inference of a Social Graph with
Trace Feasibility Guarantees
††thanks: This work is funded by the ANR (French National Agency of Research)
by the “FairEngine” project under grant ANR-19-CE25-0011.

Effrosyni Papanastasiou  Sorbonne University, CNRS, LIP6
F-75005, Paris, France
<EMAIL_ADDRESS>Anastasios Giovanidis  Sorbonne University,
CNRS, LIP6
F-75005, Paris, France
<EMAIL_ADDRESS>
###### Abstract

Network inference is the process of deciding what is the true unknown graph
underlying a set of interactions between nodes. There is a vast literature on
the subject, but most known methods have an important drawback: the inferred
graph is not guaranteed to explain every interaction from the input trace. We
consider this an important issue since such inferred graph cannot be used as
input for applications that require a reliable estimate of the true graph. On
the other hand, a graph having trace feasibility guarantees can help us better
understand the true (hidden) interactions that may have taken place between
nodes of interest. The inference of such graph is the goal of this paper.
Firstly, given an activity log from a social network, we introduce a set of
constraints that take into consideration all the hidden paths that are
possible between the nodes of the trace, given their timestamps of
interaction. Then, we develop a non-trivial modification of the Expectation-
Maximization algorithm by Newman [1], that we call Constrained-EM, which
incorporates the constraints and a set of auxiliary variables into the
inference process to guide it towards the feasibility of the trace.
Experimental results on real-world data from Twitter confirm that Constrained-
EM generates a posterior distribution of graphs that explains all the events
observed in the trace while presenting the desired properties of a scale-free,
small-world graph. Our method also outperforms established methods in terms of
feasibility and quality of the inferred graph.

###### Keywords:

social graph, network inference, network reconstruction, expectation
maximization

##  I Introduction

Network inference, or reconstruction is the problem of predicting the presence
or absence of edges between a set of nodes that form the vertices of a graph,
given an observed set of data, i.e., the trace [2]. Network inference has long
been considered an important task; initially, it attracted a lot of attention
in computational biology with various works reconstructing biological networks
using representation learning, Bayesian networks, etc [3]. At the same time,
studies applying network inference on social network data began emerging in
literature and continue until today, thanks to the rapid growth of Online
Social Networks (OSNs) [4, 5, 6]. The main goal of such works is to infer the
influence between users - an important property of a social network [7] \- and
usually rely on diffusion models that capture the way information is diffused
through the network. Such models include the Independent Cascade (IC) model,
also called Susceptible-Infected-Recovered (SIR) in epidemiology [8, 9] and
the Susceptible-Infected (SI) model [10]. The Linear or General Threshold
model has also been extensively used for network inference [7].

After the choice of a diffusion model, the corresponding model parameters can
be learned with several approaches, such as maximum likelihood [7, 11],
Expectation-Maximization (EM) [8, 1, 9] and other static or continuous-time
models [7]. For example, Saito et al. [8], used the IC model and applied the
EM algorithm to learn the pairwise transmission probabilities of influence
between users. More recently, Bourigault et al. [9] presented an embedded
version of the IC model on OSNs that learns information diffusion
probabilities along with the representation of users in the latent space. More
recently, Newman [1] proposed an EM algorithm that is designed for network
inference given unreliable data with the help of a set of parameters that
estimate the size of the errors. Peixoto [12] approached network
reconstruction similarly to Newman and combined it with community detection,
proving that the task of inferring edges can improve the accuracy of community
detection and vice-versa.

In the aforementioned inference procedures, we observed that the feasibility
of the trace in relation to the inferred network is not always guaranteed.
This means that the inferred network may not accurately and completely explain
the input trace. For example, the application of the algorithm proposed by
Saito et al. [8] applied on a Twitter cascade of user tweets and retweets,
showed that, while it can predict high diffusion probabilities for some pairs
of users and, thus, explain why we observe some retweets in the trace, it
cannot do so for every original tweet. As a result, for a considerable number
of retweets, we do not know the source of their influence and we, therefore,
cannot explain their existence in the trace. The same is true for Newman’s
network reconstruction algorithm [1].

In cases like the above, we say that the trace is not feasible with respect to
the inferred network. We argue that the concept of trace feasibility is an
important condition that an inference framework must meet if we wish to
understand the produced networks with relation to the trace and get them to
explain every instance of our data. Therefore, we approach the problem of
network inference in a novel way by developing a method that infers a
posterior distribution of feasible networks that can accurately explain the
given trace while respecting the temporal order of the observed events (e.g.,
posts). Towards this goal, we propose a non-trivial modification of the EM
inference procedure developed by Newman [1] by introducing a set of
constraints that take into consideration all the (yet unknown) paths that are
possible according to the timestamps of interaction between the nodes and
therefore derive feasible graphs.

Our algorithm works for OSN traces that include hundreds of thousands to
millions of nodes. We focus the analysis on data from Twitter but we could
apply the constraint set on other domains as well. However, to do so, the
feasibility constraints should be adjusted each time to the type of data that
we work with.

##  II Environment

###  II-A Assumptions on the environment

In the present paper, we will work with traces available from OSNs like
Twitter or Weibo. On these platforms, a set of users can generate content that
we call posts. For example, in the case of Twitter, users can post either
original posts (i.e., tweets) or reposts (i.e., retweets) of original posts
from other users. For this paper, we make three crucial assumptions:

  1. 1.

Users repost from users they follow, i.e., their followees.

  2. 2.

The followee from whom each user reposts is included inside the available
trace.

  3. 3.

Each user can repost the same post only once.

Of course, the above do not always hold in reality, but they serve as a
simplification for our work. As an extension, our method could be modified to
include cases where users repost outside the available trace or users, or from
users who are not even their followees (e.g., if they traced a tweet from
trending topics, hashtags, search, etc).

For the diffusion of posts, we choose the SI diffusion model from epidemiology
[10]: with respect to each post, a user can transition from the susceptible
state (i.e., when one of their followees posts or reposts something) to the
infected state (i.e., when the user reposts it) only once and cannot
transition back. In addition, we consider that an infected user can influence
their yet uninfected followers during all the consecutive timestamps.

###  II-B Trace description

Throughout this paper, we use $\mathcal{P}$ to denote our trace that is a log
of T posts and reposts, generated by a set $\mathcal{U}$ of $|\mathcal{U}|=$N
users on an OSN ($\text{N}\leq\text{T}$). Each line in $\mathcal{P}$ is a
quadruple $(pid,t,uid,rid)$ that includes four types of information: i) the
unique post id $pid$; ii) its timestamp $t$; iii) the $uid\in\mathcal{U}$ of
the user who posted it; and iv) a repost id $rid$ that is either equal to $-1$
if the post is an original post, or equal to the $pid$ of the original post if
it is a repost. All posts in $\mathcal{P}$ are ordered according to their
timestamps. It is important to underline here that social media logs, like in
Twitter do not provide the identity of the user from whom someone found and
reposted a post; they only include the $rid$, from which we can then track the
original author.

##  III Problem formulation

###  III-A Problem definition

Since posts propagate by reposting, we assume the existence of an underlying
friendship network between the N different users in the trace that is unknown
to us. This network is a directed social graph $G=(V,E)$ where the nodes are
the users of the trace ($V=\mathcal{U}$) and the edges include the friendships
between the users. We represent $G$ with an adjacency matrix N$\times$N,
denoted by A, where each element $A_{ij}$ is equal to $1$ if user $j$ follows
user $i$ and $0$ otherwise. Our intuition is that if a user $j$ shares content
frequently from user $i$, it is more probable that $j$ follows $i$. The goal
of this work is to infer the unknown friendship network $G$, with trace
feasibility guarantees, by inferring the hidden path each original post takes
from user to user in the trace. It is important to note here that we can only
retrieve friendships between users that have had at least one interaction with
each other in the given trace. The richer the trace, the more complete our
network inference will be.

###  III-B Preliminaries

Our method relies on rich information extracted from a social media trace
during the pre-processing phase. We begin by extracting from $\mathcal{P}$ the
set of original posts denoted by $\mathcal{S}$ with cardinality
$|\mathcal{S}|=$ S. We denote by $r_{s}$ the $uid$ of the user who originally
posted each post $s$, i.e., $(s,t,r_{s},-1)\in\mathcal{P}$ for some $t$.

######  Definition 1 (Episode)

For each original post $s\in\mathcal{S}$ we define an episode as a set of
users $\mathcal{E}_{s}$ =
$r_{s}\cup\\{u\in\mathcal{U}|\exists(pid,t):(pid,t,u,s)\in\mathcal{P}\\}$. The
whole set of episodes is denoted by $\mathcal{E}$ and includes S episodes in
total.

Each episode $\mathcal{E}_{s}$ includes the user who originally posted $s$,
denoted by $r_{s}$, followed by the users who reposted it, in chronological
order. We use $i\stackrel{{\scriptstyle s}}{{\prec}}j$ to say that user $i$
appears in $\mathcal{E}_{s}$ before $j$, and we call this pair a temporally
ordered pair $(i,j)_{s}$. We count $M_{ij}$ out of the S total episodes where
$i\stackrel{{\scriptstyle s}}{{\prec}}j$. If $M_{ij}>0$, then it is possible
that $j$ has reposted from $i$ an original post or repost and we call this
pair an active pair. Hence, it is a very important quantity for the inference
of the hidden post propagation paths and we will make use of it in the next
sections. The total number of active pairs is denoted by L and is equal to
$\sum_{i\neq j}\mathbf{1}(M_{ij}>0)$, where $\mathbf{1}(z)=1$ when $z$ is
true. All information extracted from the trace is summarized in Table I.

TABLE I: Trace Information Symbol | Definition
---|---
$\mathcal{P}$ | Set of posts and reposts in the trace, $|\mathcal{P}|=$ T
$\mathcal{S}$ | Set of original posts in the trace, $|\mathcal{S}|=$ S
$\mathcal{U}$ | Set of users that posted or reposted a post
N | Number of different users appearing in the trace
$\mathcal{E}$ | Set of episodes, $|\mathcal{E}|=$S
$\mathcal{E}_{s}\in\mathcal{E}$ | Episode of post $s$, $1\leq s\leq$ S
$r_{s}$ | The id of the user that originally posted $s$
$i\stackrel{{\scriptstyle s}}{{\prec}}j$ | User $i$ reposted or posted $s$ before $j$
$M_{ij}$ | Number of episodes where $i\stackrel{{\scriptstyle s}}{{\prec}}j$
L | Number of active pairs with M${}_{ij}>0$

###  III-C Diffusion model per episode

Given an episode $\mathcal{E}_{s}$ and an ordered pair $(i,j)_{s}$, we first
define the value $X_{ij}(s)\in\\{0,1\\}$ that is equal to $1$ if user $j$
reposted $s$ directly from $i$ (i.e., post $s$ propagated from $i$ to $j$) and
equal to $0$ otherwise. However, the real value of $X_{ij}(s)$ is still
unknown to us. Therefore, for the given post $s$, if we look into the temporal
order of its reposts, we could think of several feasible ways or paths through
which the post could have spread to reach the users that reposted it. These
paths form a propagation graph $G_{s}=\\{V_{s},E_{s}\\}$ per episode, with the
users in episode $\mathcal{E}_{s}$ as nodes ($V_{s}=\mathcal{E}_{s}$), and the
edges set $E_{s}$ containing the edges that are activated for the given post.
Each activated edge follows the direction of propagation, e.g., an edge
$(i,j)$ in $G_{s}$ means that $X_{ij}(s)=1$.

As mentioned before, it is crucial that the paths in $G_{s}$ take into account
the temporal order of the users’ posts and reposts. For example, we can think
of a hypothetical episode $\mathcal{E}_{s}$ of post $s$, depicted in Fig. 1.
The user Frosso (Fr) was the first who posted $s$, followed by Phoebe (Ph) and
then, Anastasios (An). Therefore, the possible propagation graphs, based on
the chronological ordering of each repost in the episode, are the following:

  * •

Users Phoebe and Anastasios reposted it both directly from Frosso. This
corresponds to a propagation graph $G_{s}$ with two directed paths: i) from
the node Frosso to the node Phoebe; and ii) from the node Frosso to the node
Anastasios (case I in Fig. 1).

  * •

Phoebe reposted it from Frosso and then Anastasios from Phoebe. This
corresponds to a propagation graph $G_{s}$ with one directed path: from Frosso
to Phoebe and then to Anastasios (case II in Fig. 1).

Notice that each path in each possible tree follows the time-ordering of
reposts. In addition, $G_{s}$ is an arborescence with root $r_{s}$ [13]: this
means that (i) $G_{s}$ is a DAG; and (ii) given the vertex $r_{s}$ called the
root and any other vertex $u$ in $G_{s}$, there is exactly one directed path
from $r_{s}$ to $u$. Equivalently, $G_{s}$ is a directed, rooted tree in which
all edges point away from the root.

##  IV Feasibility and constraints

###  IV-A Feasibility definition

Given our problem definition, for each original post in $\mathcal{S}$, we need
to infer a propagation DAG that is feasible in relation to the trace.

Figure 1: Possible propagation graphs for episode $\mathcal{E}_{s}$.

######  Definition 2 (Feasible propagation DAG per episode)

Given an episode $\mathcal{E}_{s}$ from the trace, we say that a propagation
DAG $G_{s}=\\{V_{s},E_{s}\\}$ is feasible in relation to $\mathcal{E}_{s}$, if
$V_{s}=\mathcal{E}_{s}$ and there exists (at least) one directed path from the
root user $r_{s}$ to every other user $j\in V_{s}\backslash r_{s}$. For each
edge $(i,j)$ of the path it holds that $i\stackrel{{\scriptstyle
s}}{{\prec}}j$ in the trace.

Using a DAG for each episode, $G_{s}$ with $s=1,2,..,\text{S}$, we can
construct the full adjacency matrix A of the final friendship graph $G$ as
follows: we set $A_{ij}=1$ if there exists at least one propagation DAG
$G_{s}$ where the edge $(i,j)$ exists, and $0$ otherwise.

######  Definition 3 (Feasible friendship graph)

We define the adjacency matrix A of an inferred network $G$ as feasible in
relation to an OSN trace if, for every original post $s$ there exists a
subgraph in $G$, which is a feasible propagation graph $G_{s}$ as defined in
Def. 2.

For example, in Fig. 2, given a trace of three episodes
$\mathcal{E}=\\{\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}\\}$ that
involves five users Frosso (Fr), Anastasios (An), Phoebe (Ph), Rachel (Ra),
Joey (Jo), we can see the case of a non-feasible $G$ and a feasible
$G^{\prime}$. $G$ is non-feasible since there exists no feasible path from
source node Frosso to Anastasios for the case of episode $\mathcal{E}_{1}$ and
there exists no feasible path from source node Anastasios to Frosso for the
case of episode $\mathcal{E}_{3}$. In contrast, $G^{\prime}$ is feasible since
there exists a feasible propagation graph for each episode.

###  IV-B Feasibility constraints on retweets behavior

The real value of $X_{ij}(s)$ defined in Section III is not available, but we
can limit the possible combinations by introducing a set of constraints on
$X_{ij}(s)$, that ensure that a user $j\in\mathcal{E}_{s}$ has reposted $s$
directly by at least one user $i\in\mathcal{E}_{s}$ who has reposted $s$
earlier according to the trace. As a result, for each episode
$\mathcal{E}_{s}\in\mathcal{E}$, and each user
$j\in\mathcal{E}_{s}\backslash\\{r_{s}\\}$, the constraints take the following
form:

$\sum_{i\in\mathcal{E}_{s}\text{ s.t. }i\stackrel{{\scriptstyle
s}}{{\prec}}j}{X}_{ij}(s)\geq 1,\forall
j\in\mathcal{E}_{s}\backslash\\{r_{s}\\}.$ (1)

For all episodes we will get T-S constraints in total, i.e., as many
constraints as the number of reposts with
$\sum_{s=1}^{\text{S}}(|\mathcal{E}_{s}|-1)\cdot(|\mathcal{E}_{s}|)/2$ unknown
variables in total. The way we formed the constraints, we allow the
possibility that a user $j$ has reposted the post $s$ from more than one users
instead of only one user for reasons that will become clear in the following
section. For example, for episode $\mathcal{E}_{s}$ in Fig. 1 we will get
constraints: $X_{FrossoPhoebe}(s)\geq 1$ and $X_{FrossoAnastasios}(s)$ $+$
$X_{PhoebeAnastasios}(s)\geq 1$. This means that the user $Phoebe$ has
definitely reposted $s$ from $Frosso$ and that $Anastasios$ has reposted it
from $Frosso$, $Phoebe$, or both.

Figure 2: Example of feasibility check given a trace.

###  IV-C Diffusion probabilities

To be able to infer $X_{ij}(s)$ we make an important assumption: For every
ordered pair $(i,j)_{s}$ in an episode $\mathcal{E}_{s}$, user $j$ reposted
post $s$ from $i$ independently of other episodes with unknown probability
$\sigma_{ij}\in[0,1]$ that is common for all episodes. In other words,
$X_{ij}(s)$ is an independent Bernoulli random variable with mean
$\sigma_{ij}$ that is independent of $s$.

Our choice to model the uncertainty about the path by using an independent
Bernoulli random variable with a fixed mean $\sigma_{ij}$, assumes that user
$j$ does not have a contextual behavior that depends on the content of the
episode, but rather behaves with randomness when choosing their sources of
information. This serves as a simplification for the inference; as an
extension, it could be further refined to include context-dependent mean
values for different types of episodes. The value of $\sigma_{ij}$ can be seen
as the limiting frequency that user $j$ reposts directly a post from $i$ when
the number of episodes goes to infinity. Given an ordered pair $(i,j)_{s}$,
$\sigma_{ij}$ is equal to:

$\sigma_{ij}=\mathbb{E}\left[X_{ij}(s)\right].$ (2)

Given our intuition that the number of times a user $j$ reposts a user $i$ is
indicative of their friendship we introduce to the problem the quantity
$Y_{ij}$, as the (unknown) number of times that j reposted from $i$, out of
the $M_{ij}$ possible ones (the number of times they appear as an active
pair). That is:

$Y_{ij}=\sum_{m=1}^{M_{ij}}X_{ij}(s).$ (3)

Since $Y_{ij}$ is the sum of $M_{ij}$ independent Bernoulli random variables
with mean value $\sigma_{ij}$, $Y_{ij}$ is an independent Binomial random
variable with mean value $M_{ij}\sigma_{ij}$. That is:

$\mathbb{E}[Y_{ij}]=\sum_{m=1}^{M_{ij}}\mathbb{E}[X_{ij}(s)]=\sum_{m=1}^{M_{ij}}\sigma_{ij}=M_{ij}\sigma_{ij}.$
(4)

The value of $\sigma_{ij}$ plays an important role in the inference of the
relationship between $i$ and $j$, as we will demonstrate in the following
sections.

####  IV-C1 Constraints on diffusion probabilities $\sigma_{ij}$

Having transformed the problem from solving over $X_{ij}(s)$ to solving over
$\sigma_{ij}$, we can constrain $\sigma_{ij}=\mathbb{E}\left[X_{ij}(s)\right]$
to be inside a specific set of values. If we take the expectation of the
constraints in (1), for each episode $\mathcal{E}_{s}\in\mathcal{E}$, and each
user $j\in\mathcal{E}_{s}\backslash\\{r_{s}\\}$, we end up with the following
set of constraints on parameters $\sigma_{ij}$:

$\displaystyle\sum_{i\in\mathcal{E}_{s}\text{ s.t. }i\stackrel{{\scriptstyle
s}}{{\prec}}j}\sigma_{ij}\geq 1,\forall
j\in\mathcal{E}_{s}\backslash\\{r_{s}\\}$ (5)
$\displaystyle\sigma_{ij}\in[0,1],\text{ }\forall(i,j)\in\mathcal{U}.$ (6)

We define with Fσ the feasibility space of the parameters vector
$\boldsymbol{\sigma}$ that includes all $\sigma_{ij}\text{
parameters},(i,j)\in\mathcal{U},\text{ such that (5) and (6) hold.}$ In this
case, for episode $\mathcal{E}_{s}$ in Fig. 1 the constraints change to the
following: $\sigma_{FrossoPhoebe}\geq 1$ and $\sigma_{FrossoAnastasios}$ $+$
$\sigma_{PhoebeAnastasios}\geq 1$. This means that user $Phoebe$ has reposted
$s$ from $Frosso$ with probability $\sigma_{FrossoPhoebe}=1$ and that the
probabilities of $Anastasios$ reposting it from $Frosso$ and $Phoebe$ must sum
up to a value inside the interval $\in[1,2]$.

As a result, the parameters $\sigma_{ij}\in[0,1]$ are the problem unknowns
that replace the $X_{ij}(s)\in\\{0,1\\}$ for all episodes where an action from
user $i$ precedes an action from $j$. For the whole trace $\mathcal{E}$, we
will get a set of constraints
$\mathcal{C}=\\{c_{1},c_{2},...,c_{(\text{T-S})}\\}$, where, each element
$c_{k}\in\mathcal{C},1\leq k\leq$ (T-S), corresponds to the constraint of a
$(r_{s},j)$ tuple, where $r_{s}\in\mathcal{E}_{s}$ and user
$j\in\mathcal{E}_{s}\backslash\\{r_{s}\\}$, and is defined by (5)-(6). By
imposing this set of constraints on the parameters $\sigma_{ij}$, we have
drastically reduced the number of our problem’s unknowns to the number of
possible $(i,j)$ pairs from the users set $\mathcal{U}$, i.e., we now have
$\text{N}(\text{N}-1)$ unknowns.

####  IV-C2 Removing redundant constraints

We notice that given a trace, some constraints become redundant and can be
removed according to the following rules:

  * •

If all parameters $\sigma_{ij}$ that are included in a constraint
$c_{k}\in\mathcal{C}$, are also included in a different constraint
$c_{w}\in\mathcal{C}$, then $c_{w}$ is removed from $\mathcal{C}$.

  * •

In (5), we observe that the first constraint of each episode includes only one
variable, which is the $\sigma_{ij}$ between the first user $i=r_{s}$ and the
second user $j$ in the episode. Therefore, given also that
$\sigma_{ij}\in[0,1]$, all parameters between the first and the second user of
each episode become $\sigma_{ij}=1$. As a result, the first constraint per
episode is removed, since the solution for these parameters has already been
found.

Note that for $M_{ij}=0$, $\sigma_{ij}=0$. Generally, the exact number of
constraints by which our problem will be reduced depends on the
characteristics of each trace.

##  V Problem Modeling and Learning Method

As mentioned in the introduction, we develop a non-trivial modification of
Newman’s EM algorithm proposed in [1] that was designed for network inference
given erroneous data. In our case, our data is not erroneous, but rather
incomplete; however, we take advantage of Newman’s probabilistic modeling and
we adapt its parameters and the EM equations to our case.

###  V-A Parameters

Firstly, in a similar fashion to Newman [1], we assume that the relationship
between the underlying network $G$ and the trace can be expressed in the form
of a probability function $\textit{P}(\text{data}|\textbf{A},\theta)$, which
is the probability of generating the particular trace $\mathcal{P}$, given the
adjacency matrix A and a set of additional model parameters, denoted by
$\theta$. The parameters $\theta$, added to cover a larger range of
possibilities for the type of graph and the way the data is generated, are the
following:

  1. 1.

To model our uncertainty about the structure of the graph $G$, we assume a
uniform prior probability $\rho$ of the existence of an edge in any position
between any pair of nodes, i.e. $G$ has been drawn under the Erdős–Rényi model
with parameter $\rho$.

  2. 2.

The values $\sigma_{ij}$, which is the fixed probability that $j$ shares
content from $i$.

  3. 3.

The true-positive utilization rate $\alpha$: the probability of post
propagation through existing edges of the underlying network $G$.

  4. 4.

The false-positive utilization rate $\beta$: the probability of post
propagation through non-existing edges of the underlying network $G$.

We see that $\alpha$ and $\beta$ are global parameters, conditioned on the
existence or not of an edge in the ground truth network $G$.

###  V-B Learning Method

To find the most probable value of the parameters $\theta$ given the observed
data and infer a graph with maximum likelihood, we will develop an application
of Expectation-Maximization (EM): an iterative algorithm designed to find the
maximum a posteriori (MAP) estimates of parameters in statistical models that
depend on unobserved latent variables. Each EM iteration will alternate
between two steps: i) an expectation (E) step, which creates the expectation
of the log-likelihood using the current estimate for the parameters $\theta$;
and ii) a maximization (M) step, which finds the parameters that maximize the
expected log-likelihood of the E-step. The estimated parameters are then used
in the next E-step and so on until convergence is reached.

We begin in the same way as Newman [1] and we apply the Bayes’ rule:

$\textit{P}(\textbf{A},\theta|\text{data})=\frac{\textit{P}(\text{data}|\textbf{A},\theta)\textit{P}(\textbf{A}|\theta)\textit{P}(\theta)}{\textit{P}(\text{data})}.$
(7)

The probability that we get the specific set of reposts, given A and the
parameters $\theta=${$\alpha,\beta,\rho,\boldsymbol{\sigma}$}, differs here
from Newman since we have introduced the hidden number of interactions between
users, $Y_{ij}$. Given the ordered nodes of an episode, each repost path is
chosen independently per episode. In addition, we assumed as prior knowledge
that between any two nodes in A an edge has been drawn with probability
$\rho$. Therefore we get:

$\displaystyle\textit{P}(\text{data}|\textbf{A},\theta)\textit{P}(\textbf{A}|\theta)=\prod_{i\neq
j}{\left[\alpha^{Y_{ij}}{(1-\alpha)}^{M_{ij}-Y_{ij}}\rho\right]}^{A_{ij}}\ $
$\displaystyle\times{\left[\beta^{Y_{ij}}{(1-\beta)}^{M_{ij}-Y_{ij}}(1-\rho)\right]}^{1-A_{ij}}.$
(8)

Given this type of modeling, when $A_{ij}=1$, the $Y_{ij}$ out of the $M_{ij}$
experiments are successful, each with probability $\alpha$. When $A_{ij}=0$,
the $Y_{ij}$ out of $M_{ij}$ experiments are successful, each with probability
$\beta$. For the whole set of parameters $\theta$, we assume a uniform prior
probability $\textit{P}(\theta)$. If we sum (7) over all possible networks A,
we find that
$\textit{P}(\theta|\text{data})=\sum_{\textbf{A}}\textit{P}(\textbf{A},\theta|\text{data})$.
Then, as suggested by Newman [1], we can apply the well-known Jensen’s
inequality on the $\log$ of $\textit{P}(\theta|\text{data})$:

$\log\textit{P}(\theta|\text{data})=\log\sum_{\textbf{A}}\textit{P}(\textbf{A},\theta|\text{data})\geq\sum_{\textbf{A}}q(\textbf{A})\log\frac{\textit{P}(\textbf{A},\theta|\text{data})}{q(\textbf{A})}$
(9)

where $q(\textbf{A})$ is any probability distribution over networks A
satisfying $\sum_{\textbf{A}}q(\textbf{A})=1$. We also define the posterior
probability of an edge existing between $i$ and $j$ by
$Q_{ij}=\textit{P}(A_{ij}=1|\text{data},\theta)=\sum_{\textbf{A}}q(\textbf{A})A_{ij}$.

For the E-step, we modify the Newman algorithm by taking the expectation over
the set of random variables $Y_{ij}$ at both sides of (9):

$\displaystyle\mathbb{E}[\log\textit{P}(\theta|\text{data})]\geq\mathbb{E}[\sum_{\textbf{A}}q(\textbf{A})\log\frac{\textit{P}(\textbf{A},\theta|\text{data})}{q(\textbf{A})}]$
$\displaystyle=\sum_{\textbf{A}}q(\textbf{A})\big{(}\mathbb{E}[\log\textit{P}(\textbf{A},\theta|\text{data})]-\log
q(\textbf{A})\big{)}.$ (10)

To find $\mathbb{E}[\log\textit{P}(\textbf{A},\theta|\text{data})]$, we
replace (8) into (7). Setting
$\Gamma=\textit{P}(\theta)/\textit{P}(\text{data})$, the expectation of the
log of (7) becomes:

$\displaystyle\mathbb{E}[\log\textit{P}(\textbf{A},\theta|\text{data})]=log\Gamma+\sum_{i\neq
j}\Big{[}{A_{ij}}\Big{(}\log\rho+{\mathbb{E}[Y_{ij}]}\log\alpha+$
$\displaystyle+(M_{ij}-\mathbb{E}[Y_{ij}])\log{(1-\alpha)}\Big{)}+(1-A_{ij})\Big{(}\log(1-\rho)+$
$\displaystyle+{\mathbb{E}[Y_{ij}]}\log\beta+(M_{ij}-\mathbb{E}[Y_{ij}])\log{(1-\beta)\Big{)}\Big{]}}.$
(11)

Then, by replacing (4) into (11), and then (11) into (10), we get:

$\displaystyle\mathbb{E}[\log\textit{P}(\theta|\text{data})]\geq\sum_{\textbf{A}}q(\textbf{A})\log\frac{D_{ij}}{q(\textbf{A})}$
(12)

$\text{where, }D_{ij}=\Gamma\prod_{i\neq
j}{\left[\rho\alpha^{M_{ij}\sigma_{ij}}{(1-\alpha)}^{M_{ij}(1-\sigma_{ij})}\right]}^{A_{ij}}\\\
\times{\left[(1-\rho)\beta^{M_{ij}\sigma_{ij}}{(1-\beta)}^{M_{ij}(1-\sigma_{ij})}\right]}^{1-A_{ij}}.$
(13)

For the M-step of the EM algorithm, the function that we want to maximize is
$\mathbb{E}[\log\textit{P}(\theta|\text{data})]$. To do so, we need to find
the unknown values, $q(\textbf{A})$ and
$\theta=${$\alpha,\beta,\rho,\boldsymbol{\sigma}$}, that maximize the
expectation on the left-hand side of (12), under the feasibility constraints
on the parameters set $\theta$. From these, only the $\sigma_{ij}$ have an
important constraint set, specified in (5) and (6).

###  V-C Solution

####  V-C1 With respect to $q(\textbf{A})$

We notice that the choice of $q(\textbf{A})$ that achieves equality (i.e.
maximizes the right-hand side) in (12) is:

$q(\textbf{A})=\dfrac{D_{ij}}{\sum_{\textbf{A}}D_{ij}}.$ (14)

From (14), in a similar fashion to Newman’s method [Eq. (13), 20], and because
$\Gamma$ cancels out, we get:

$q(\textbf{A})=\prod_{i\neq j}Q_{ij}^{A_{ij}}(1-Q_{ij})^{1-A_{ij}}$ (15)

where $Q_{ij}$ is the posterior probability that there exists an edge between
$i$ and $j$:

$\medmath{Q_{ij}=\dfrac{\rho\alpha^{M_{ij}\sigma_{ij}}(1-\alpha)^{M_{ij}(1-\sigma_{ij})}}{\rho\alpha^{M_{ij}\sigma_{ij}}(1-\alpha)^{M_{ij}(1-\sigma_{ij})}+(1-\rho)\beta^{M_{ij}\sigma_{ij}}(1-\beta)^{M_{ij}(1-\sigma_{ij})}}}.$
(16)

The expression here is also different from Newman, since in the exponents we
get the expected number of events (using $M_{ij}\sigma_{ij}$) instead of the
number of times $j$ reposts from origin $i$ directly (that is provided
directly by the data). Notice also that for $M_{ij}=0$, $Q_{ij}$ becomes equal
to the prior probability $\rho$. Moreover, from (14) we observe that
$q(\textbf{A})$ is the posterior probability distribution over all possible
networks A, $\textit{P}(\textbf{A},\theta|\text{data})$ when $Y_{ij}$ is
replaced by its expected value $M_{ij}\sigma_{ij}$.

####  V-C2 With respect to $\sigma_{ij}$

Our goal now is to find the parameters $\theta$ that maximize the right-hand
size of (12), given the maximising distribution for $q(\textbf{A})$ in (14),
hence given the values of $Q_{ij}$ in (15). If we take into account that
$Q_{ij}=\sum_{\textbf{A}}q(\textbf{A})A_{ij}$ and also that
$\sum_{\textbf{A}}q(\textbf{A})=1$, by rearranging the right-hand side of
(12), the problem becomes equivalent to maximizing:

$\displaystyle\sum_{\textbf{A}}q(\textbf{A})\sum_{i\neq
j}\sigma_{ij}M_{ij}\left(A_{ij}\log\frac{\alpha}{1-\alpha}+(1-A_{ij})\log\frac{\beta}{1-\beta}\right)\
$ $\displaystyle=\sum_{i\neq
j}\sigma_{ij}M_{ij}\left(Q_{ij}\log\frac{\alpha}{1-\alpha}+(1-Q_{ij})\log\frac{\beta}{1-\beta}\right).$
(17)

Finally, if $\boldsymbol{\sigma}$ is a vector of size L that includes all
$\sigma_{ij}$ instances, we end up with the following linear optimization
problem:

$\displaystyle\max_{\sigma}\sum_{i\neq j}\sigma_{ij}(W_{ij}-\lambda)$ (18)
$\displaystyle\text{s.t.
}\boldsymbol{\sigma}\in\textit{F}_{\boldsymbol{\sigma}}$
$\displaystyle\text{where
}W_{ij}=M_{ij}\left(Q_{ij}\log\frac{\alpha}{1-\alpha}+(1-Q_{ij})\log\frac{\beta}{1-\beta}\right)$
$\displaystyle\text{and }\lambda>0\text{ some given penalty for
regularisation.}$ (19)

Our goal is to infer a graph that is feasible and also has the minimum
possible number of edges; this is why we added the value $\lambda$ as a
penalty into the maximization goal per each iteration. Without it, all $(i,j)$
pairs with $W_{ij}>0$ would immediately get their $\sigma_{ij}=1$, leading to
the inference of more edges than necessary. Therefore, we choose to set
$\lambda$ equal to the largest $W_{ij}$ value, i.e. $\lambda=\max_{(i,j)\in
W}W_{ij}$. This choice of $\lambda$ forces the optimization goal to be
negative and thus, to be guided only by the provided constraints. It is
equivalent to penalizing the total expected number of inferred edges.

####  V-C3 With respect to $\alpha,\beta,\rho$

Next, we maximize the right-hand side of (12) in terms of parameter $\alpha$
by differentiating it with respect to $\alpha$ and then setting it equal to
zero (while holding $\sigma_{ij}$, $q$ constant):

$\sum_{i\neq
j}Q_{ij}M_{ij}\left(\frac{\sigma_{ij}}{\alpha}-\frac{1-\sigma_{ij}}{1-\alpha}\right)=0.$
(20)

After rearranging, we get:

$\alpha=\dfrac{\sum_{i\neq j}M_{ij}\sigma_{ij}Q_{ij}}{\sum_{i\neq
j}M_{ij}Q_{ij}}.$ (21)

Similarly for $\beta$ and $\rho$, we get:

$\displaystyle\beta=\dfrac{\sum_{i\neq
j}M_{ij}\sigma_{ij}(1-Q_{ij})}{\sum_{i\neq j}M_{ij}(1-Q_{ij})},$ (22)
$\displaystyle\rho=\dfrac{1}{\text{N(N}-1)}{\sum_{i\neq j}Q_{ij}}$ (23)

where N is the number of total different users in the trace.

Finally, we end up with an iterative EM algorithm that iterates between
finding an optimal value for q, i.e. a value that allows for (12) to hold with
equality (E-step), and then holding it constant to maximize the right-hand
side of (12) (and therefore also the expectation in the left-hand side of
(12)) with respect to $\theta$ (M-step), through the updates in (18), (19),
(21), (22), (23). Our algorithm converges when the L2 norm of improvement
$||\textbf{Q}_{new}-\textbf{Q}_{old}||<\epsilon$ falls under some threshold
$\epsilon$ that we choose in advance, where Q is the matrix containing all the
$Q_{ij}$ values.

##  VI Experimental Evaluation

###  VI-A Dataset

To evaluate our approach we use a real-world Twitter dataset coming from
Kaggle, referred to as Russian 111https://www.kaggle.com/borisch/russian-
election-2018-twitter. It contains almost 2 million tweets and retweets
emitted from 181,621 users during the Russian presidential elections of 2018.
Users are anonymous and tweets are ordered in time. We choose the first
500,000 lines of the trace. Each line is a quadruple [PostID, TimeStamp,
UserID, RePostID]. We remove all the tweets that have not been retweeted by
any users and all the retweets for which we do not know the user who
originally posted it. In addition, we delete retweets that appear more than
once for the same user and tweet. The final statistics are summarised in Table
II.

###  VI-B Experimental Settings

####  VI-B1 Environment

We run the experiments on a Google Cloud virtual instance with 16 vCPUs and
128 GB RAM. For the solution of the optimization problem, we use PuLP
222https://pypi.org/project/PuLP/, an open-source linear programming library
for Python.

####  VI-B2 Number of constraints

For a trace set of size $|\mathcal{P}|=216,989$ the number of constraints is
$198,543$. After removing the redundant ones according to Section IV-C2, we
observe an approximately 10% percent decrease in the number of constraints
($=170,209$). However, the level of decrease generally depends on the sparsity
of the trace network itself. The more connected the initial network, the
higher the decrease we observe.

TABLE II: Basic statistics on Russian after pre-processing | Russian
---|---
Time window | 20 days
Trace size $|\mathcal{P}|$ | 216,989
#original tweets | 14,781
#retweets | 202,208
#users | 42,011
% users with #tweets >0 | 13.00
% users with #retweets >0 | 94.30

####  VI-B3 Initialization and convergence rule

Parameters $\alpha$, $\beta$ and $r$ are initialized randomly. The threshold
$\epsilon$ of our algorithm’s convergence criterion on the L2 norm
$||\textbf{Q}_{new}-\textbf{Q}_{old}||<\epsilon$ is set equal to
$\epsilon=0.001$.

(a)

(b)

Figure 3: Constrained-EM results.

##  VII Results and Comparison

Our algorithm Constrained-EM takes 109 iterations and approximately 60 hours
to converge. The converged parameters of our method, are
$\alpha^{*}=0.9932,\beta^{*}=0.0001,r^{*}=0.0034$. This means that there is an
approximately $99\%$ probability that a post propagated through an edge
present in the inferred network $G$. The small value of $\beta$ suggests that
there are very few false-positive utilized edges: a post from the trace
propagates through an edge where none exists around $0.001\%$ of the time.

In Fig. 3 (left), we show the final values of $Q_{ij}$ in relation to the
number of times $M_{ij}$ that each $(i,j)$ edge is observed in the trace. As
we can see, when $M_{ij}$ is relatively small, $Q_{ij}$ alternates between the
whole range of $[0,1]$. As $M_{ij}$ becomes larger, the $Q_{ij}$ is either $0$
or $1$ and finally, for the larger values of $M_{ij}$, the value of $Q_{ij}$
stabilizes to $1$. This could be attributed to the fact that the more times an
edge is observed in a trace, the more certain we become about the existence of
the edge; equivalently the more times a user retweets after some other user,
the more certain we become about the existence of a friendship between them.
Moreover, the different $Q_{ij}$ results for the same $M_{ij}$ values depict
the important role the constraints play in the inference process. Regarding
the $\sigma_{ij}$ values, we observe in Fig. 3 (right) that for
$\sigma_{ij}>0.5$, $Q_{ij}$ is almost $1$ and for $\sigma_{ij}<0.5$, $Q_{ij}$
becomes $0$. For $\sigma_{ij}=0.5$, $Q_{ij}$ alternates between values in
[$0.1,1$]. Hence, we confirm our intuition that the probability that user $j$
follows $i$ depends on the probability $\sigma_{ij}$ that $j$ reposts $i$.

(a) Constrained-EM

(b) Saito et al. [8]

(c) Star

(d) Chain

(e) Newman [1]

Figure 4: Propagation graph inference for an episode $\mathcal{E}_{s}=\\{1,2,...,9\\}$ from the trace. TABLE III: Inferred graph metrics for each method Graph Type | % Feasible Episodes | #Edges | Avg out-deg. | Max out-deg. | Max in-deg. | Diameter | Avg shortest path | #Scc
---|---|---|---|---|---|---|---|---
Constrained-EM | 98.90 | 100,073 | 2.38 | 448 | 133 | 28 | 5.95 | 17
Saito et al. [8] | 10.06 | 20,542 | 0.49 | 21 | 18 | 88 | 8.78 | 0
Star | 100.00 | 162,570 | 3.87 | 4,524 | 173 | 18 | 6.03 | 23
Chain | 100.00 | 194,964 | 4.64 | 224 | 252 | 183 | 6.66 | 12
Newman [1] | 0.48 | 21,431 | 0.51 | 59 | 1,481 | 12 | 4.55 | 8

###  VII-A Comparison

To generate the hidden friendship network $G$ inferred by Constrained-EM, we
round up the edges $(i,j)$ with $Q_{ij}>0.5$ to $1$, and the edges with
$Q_{ij}<=0.5$ to $0$. Each existing $(i,j)$ edge suggests that user $j$
follows user $i$. Then, we compare Constrained-EM with the following inference
methods:

  * •

Star: a baseline inference method that creates an edge from the user who
originally posted each tweet $s$ in the trace, to every other user who
retweeted it.

  * •

Chain: a baseline inference method which, for each episode $\mathcal{E}_{s}$
in the trace, creates a single long path between the user nodes in
$\mathcal{E}_{s}$ according to the timestamps of their actions: from the user
who originally posted $s$, to the user who retweeted $s$ first, to the next
user who retweeted $s$, and so on.

  * •

Saito et al. [8]: an EM-based algorithm that considers the friendship graph as
a pre-given and infers the influence probabilities $k_{ij}$. For evaluation,
we create a graph by drawing an edge $(i,j)$ whenever $k_{ij}>0.5$.

  * •

Newman [1]: the EM-based algorithm by Newman, presented in the introduction.
It is not designed to consider hidden paths between user tweets and retweets
and therefore infers networks that are not feasible. However, it would be
useful to observe the differences with our method. For evaluation, we create a
graph by drawing an edge $(i,j)$ whenever the friendship probability $Q_{ij}$
for a user pair $(i,j)$ is greater than $0.5$.

To evaluate each method, since the ground truth is not available, we count how
many episodes in the trace are feasible, given the graph inferred by each
method. Moreover, we examine to what extent the properties of each graph
resemble those of a real network. Therefore, we first look into the
propagation graph inferred by each method, given a random episode from the
trace $\mathcal{E}_{s}=\\{1,2,...,9\\}$ (users are anonymized by integers) and
demonstrate it in Fig. 4. Then, we compare each method on different graph
statistics (Table III). On top of that, we compare the in and out-degree
complementary cumulative distribution functions (CCDFs) of each graph (Fig.
5). From these, we can make the following observations for each method:

####  VII-A1 Star

Fig. 4 shows that the graph inferred by Star explains the whole episode
$\mathcal{E}_{s}$ by connecting the author directly to each user that
retweeted it. This is repeated for all episodes in the trace, achieving
$100\%$ feasibility, as shown in Table III. However, the way nodes are
connected is heuristic and untrustworthy. This is also reflected in the
unrealistically high maximum out-degree of its graph ($=4,524$), compared to
the other methods.

####  VII-A2 Chain

Fig. 4 shows that the graph inferred by Chain explains the whole episode
$\mathcal{E}_{s}$ with a $100\%$ feasibility rate for all episodes. Again,
Chain may return a feasible graph, but its high diameter $(=183)$ prevents us
from choosing it as a real-world scenario.

####  VII-A3 Saito et al. [8]

In Fig. 4 we observe that for episode $\mathcal{E}_{s}$, the inferred graph
explains only the retweet by user $2$ (through the $(1,2)$ edge). For the
whole trace, it explains only $10\%$ of it (Table III). Moreover, we observe
that the graph has no strongly connected components (#Scc in Table III) which
could also explain the small number of feasible episodes.

####  VII-A4 Newman [1]

The vanilla method by Newman that does not use any constraints, cannot explain
any interaction in episode $\mathcal{E}_{s}$, as expected. For the whole
trace, it explains less than $0.50\%$ of the episodes.

####  VII-A5 Constrained-EM

Fig. 4 shows that our method can explain the whole $\mathcal{E}_{s}$, while
for all episodes it achieves an almost $99\%$ feasibility for the given
convergence rule (Table III). The remaining $1\%$ that is left unexplained is
attributed to the (rare) case when in an $\mathcal{E}_{s}$ there exist more
than two users that have the same $M_{ij}$ values and thus, are not
distinguished with sufficient certainty ($\sigma_{ij}=0.5$). We underline that
our method is feasible with the least number of edges $(=100,073)$ compared to
Star and Chain. Moreover, in Fig. 5, especially in out-degree CCDF,
Constrained-EM presents a close to scale-free behavior, with both a heavy tail
and an almost linear distribution line. On top of that, the average shortest
path of our graph is close to 6. Given the well-known notion of six degrees of
separation, or equivalently, the idea that in a small-world graph, any two
pairs of nodes are separated by less than six nodes [14], we conclude that our
graph has properties close to these of a scale-free, small-world network.
Hence, we consider it to be a trustworthy framework for feasible network
inference.

(a)

(b)

Figure 5: CCDF for all methods (on a log-log scale).

##  VIII Conclusion and Future work

As demonstrated above, given a log of tweets and retweets, our method
Constrained-EM successfully infers a feasible friendship graph that explains
each tweet’s propagation from user to user, while being economical in the
number of drawn edges. On top of that, we showed that our graph has properties
that are close to these of a scale-free, small-world network. Therefore,
Constrained-EM generates feasible graphs that are more reasonable than simple
heuristics like Star and Chain. It is worth noting that our method could be
applied on other domains where feasibility constraints can be imposed, such as
epidemics, biology, etc. As future work, we plan to investigate ways in which
Constrained-EM can be improved in terms of convergence speed.

## References

  * [1] M. E. J. Newman, “Network structure from rich but noisy data”, Nature Physics, vol. 14, 2018, pp. 67-75.
  * [2] J-P. Vert and Y. Yamanishi, “Supervised graph inference”, in Proceedings of the 17th International Conference on Neural Information Processing Systems, 2004, pp. 1433–1440.
  * [3] N. Friedman, M. Linial, I. Nachman, and D. Pe’er, “Using bayesian networks to analyze expression data”, in Journal of Computational Biology, vol. 7, pp. 601–620, 2000.
  * [4] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks”, Journal of the American society for information science and technology, vol. 58, no. 7, pp. 1019–1031, 2007.
  * [5] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network”, in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 137–146.
  * [6] M. E. J. Newman, “Clustering and preferential attachment in growing networks”,  Physical Review Letters E, vol. 64, no. 2, 2001.
  * [7] A. Goyal, F. Bonchi, and L. Lakshmanan, “Learning influence probabilities in social networks”, in Proceedings of the 3rd ACM International Conference on Web Search and Data Mining, 2010, pp. 241-250.
  * [8] K. Saito, R. Nakano, and M. Kimura, “Prediction of Information Diffusion Probabilities for Independent Cascade Model”, in International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, vol. 5179, 2008, pp. 67-75.
  * [9] S. Bourigault, S. Lamprier, and P. Gallinari, “Representation Learning for Information Diffusion through Social Networks: an Embedded Cascade Model”, in International Conference on Web Search and Data Mining, 2016, pp. 573-582.
  * [10] D. J. Daley and J. Gani, Epidemic Modelling: An Introduction. Cambridge University Press, 1999.
  * [11] C. Lagnier, L. Denoyer, E. Gaussier, and P. Gallinari, “Predicting Information Diffusion in Social Networks using Content and User’s Profiles”, in 35th European Conference on IR Research, 2013, pp. 74-85.
  * [12] T. P. Peixoto, “Network reconstruction and community detection from dynamics”, Physical Review Letters, vol. 123, no. 12, 2019.
  * [13] G. Gordon, “A greedoid polynomial which distinguishes rooted arborescences”, in Proceedings of the American Mathematical Society, 1989.
  * [14] A-L. Barabási, “Network Science Book”, Center for Complex Network Research, Northeastern University, 2014.