Asma Trabelsi
email: trabelsyasma@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefevre
email: eric.lefevre@univ-artois.fr

Decision tree classifiers for evidential attribute values and class labels

Keywords: Decision tree classifier, imperfect data, evidence theory

Decision trees are well-known machine learning techniques for solving complex classification problems. Despite their great success, the standard decision tree algorithms do not have the ability to process imperfect knowledge, meaning uncertain, imprecise and incomplete data. In this paper, we develop new decision tree approaches to cope with data that have uncertain attribute values and class labels. More concretely, we tackle the case where the uncertainty is represented and managed through the evidence theory.

Introduction

Decision trees are commonly seen efficient machine learning techniques that are widely used in several fields, notably in artificial intelligence [START_REF] Elouedi | Classification with belief decision trees[END_REF]. Their success is adequately explained by their ability to provide simple representations that are easily understandable by experts and even by ordinary users (i.e., non-expert users).

In several real world domains (e.g. medicine, fault detection and object recognition), data may suffer from imperfection due to some factors such as randomness and data incompleteness. Data imperfection may take different forms: it can be part either of the attribute values, the class labels or both of them. Since the standard decision tree versions cannot handle such kind of data, probability decision trees have been suggested [START_REF] Quinlan | Decision trees as probabilistic classifiers[END_REF]. Although the probability theory is widely used for modeling uncertainty, several researchers have proven that probability cannot always be the adequate tool for representing uncertain and incomplete data [START_REF] Masson | Ranking from pairwise comparisons in the belief functions framework[END_REF]. This shortcoming has led to the introduction of fuzzy decision trees [START_REF] Umanol | Fuzzy decision trees by fuzzy ID3 algorithm and its application to diagnosis systems[END_REF], the possibilistic decision trees [START_REF] Hüllermeier | Possibilistic induction in decision-tree learning[END_REF], the uncertain decision trees [START_REF] Dubois | Combining fuzzy imprecision with probabilistic uncertainty in decision making[END_REF][START_REF] Bezdek | Fuzziness vs. probability-again (!?)[END_REF][START_REF] Qin | DTU: a decision tree for uncertain data[END_REF]. Other theories have been proposed to deal with uncertain knowledge, notably the belief function theort also called the evidence theory. It has the advantage to represent all kinds of knowledge availability [START_REF] Denoeux | Reasoning with imprecise belief structures[END_REF], the process of incorporating belief function theory within decision tree techniques has been extensively studied [START_REF] Elouedi | Belief decision trees: theoretical foundations[END_REF][START_REF] Trabelsi | Pruning belief decision tree methods in averaging and conjunctive approaches[END_REF][START_REF] Vannoorenberghe | Handling uncertain labels in multiclass problems using belief decision trees[END_REF][START_REF] Sutton-Charani | Classification trees based on belief functions[END_REF][START_REF] Sutton-Charani | Training and evaluating classifiers from evidential data: Application to E2M decision tree pruning[END_REF][START_REF] Ma | Online active learning of decision trees with evidential data[END_REF][START_REF] Trabelsi | Handling uncertain attribute values in decision tree classifier using the belief function theory[END_REF][START_REF] Trabelsi | New decision tree classifier for dealing with partially uncertain data[END_REF]. Despite its benefits, decision trees that handle data with uncertain attribute values and class labels have not attracted attention from the community.

In this paper, we propose new decision tree classifier approaches to cope with data imperfection pervading both attribute values and class labels. The remaining of this paper is organized as follows. Section 2 is devoted to highlighting the fundamental concepts of the belief function theory. We recall, in Section 3, some basic concepts of standard decision tree classifiers. Section 4 is dedicated to describe machine learning algorithms within evidential data. Section 5 details our decision trees procedure. In Section 6, we detail the parameters enabling the construction of our proposed decision tree classifier techniques. Our experimentations are described in Section 7. We draw our conclusions and discuss future directions in Section 8.

Evidence theory

The evidence theory is seen as a very effective and efficient framework to represent and manage uncertain knowledge. In this section, we provide a brief overview of the fundamental concepts of this theory as introduced by Smets [START_REF] Smets | The combination of Evidence in the Transferable Belief Model[END_REF] with his Transferable Belief Model (TBM).

Knowledge representation

Let Θ = {θ 1 , θ 2 , . . . , θ N } denotes the frame of discernment including a finite non empty set of N elementary hypotheses. An expert's belief over the subsets of the frame of discernment Θ is represented by the so-called basic belief assignment (bba) denoted by m. It is carried out in the following manner: A⊆Θ m(A) = 1.

(

The basic belief mass (bbm), denoted by m(A), implies the degree of belief exactly assigned to the event A. Each subset A of 2 Θ having fulfilled:

m(A) > 0 (2)
is called a focal element.

From a mass function m, we can define the so called belief function denoted by bel. It reflects the sum of beliefs exactly committed to every subset of A by m [START_REF] Shafer | A mathematical theory of evidence[END_REF]. It is set to:

bel : 2 Θ → [0, 1] bel(A) = ∅ =B⊆A m(B). (3)

Combining information sources

Let m 1 and m 2 be two bbas induced from two independent information sources and defined in the same frame of discernment Θ. Several combination rules have been proposed to combine several bbas. One of the most widely used is the conjunctive rule [START_REF] Smets | The application of the Transferable Belief Model to diagnostic problems[END_REF]. This combination rule combines two bbas provided by reliable and distinct information sources. The resulting bba, denoted by m 1 ∩ m 2 , is defined by:

(m 1 ∩ m 2 )(A) = B,C⊆Θ:B∩C=A m 1 (B).m 2 (C). ( 4
)
Several real world applications require to combine bbas defined on different frames of discernment. Assuming that Θ 1 and Θ 2 are two frames of discernment, the idea consists of extending Θ 1 and Θ 2 to a joint frame of discernment

Θ = Θ 1 × Θ 2 .
The extended mass function of m 1 which is defined on Θ 1 and whose focal elements are the cylinder sets of the focal elements of m 1 is computed as follows:

m Θ 1 ↑Θ (X) =m 1 (Y ) where X = Y ×Θ 2 , Y ⊆ Θ 1 m Θ 1 ↑Θ (X) =0 otherwise.
(5)

Discounting

Information sources, within the belief function theory framework, may be quantified by reliability rates in the range between 0 and 1. Indeed, when a bba is induced from not fully reliable information sources, a discounting process is necessary to update beliefs. Let m be a bba induced from an information source with a reliability rate 1α. The discounted bba m α is obtained as follows [START_REF] Smets | The transferable belief model for expert judgements and reliability problems[END_REF]:

m α (A) =(1 -α)m(A) for A ⊂ Θ m α (Θ) =α + (1 -α)m(Θ). (6)

Decision making

Decision making aims to select the most reasonable hypothesis for a given problem. Several functions have been introduced for decision making within the belief function framework. In the Transferable Belief Model (TBM), the pignistic probability is commonly used to make a decision from a bba [START_REF] Smets | The Transferable Belief Model for quantified belief representation[END_REF]:

BetP (A) = B⊆Θ |A ∩ B| |B| m(B) 1 -m(∅) ∀ A ∈ Θ (7)
where

A∈Θ BetP (A) = 1. ( 8
)

The dissimilarity between two bbas defined on the same space of discernment

Several measures have been proposed to compute the dissimilarity between two given bbas [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF][START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF]. One of the earliest and best-known measures is the

   
The Jaccard similarity measure D is set to:

D(A, B) =      1 if A=B= ∅ |A ∩ B| |A ∪ B| ∀ A,B ∈ 2 Θ . (10)
Note that d(m 1 , m 2 ) ∈ [0, 1]. A value of 1 reflects that the two bbas m 1 and m 2 are in total disagreement, while a value of 0 means that m 1 = m 2 .

Decision tree classifier

Decision trees are recognized among the most effective and efficient machine learning approaches and they have been successfully applied to solve real world problems within the artificial intelligence field. This success is mainly due to their great ability for solving complex problems through humanreadable and computer-readable graphical representations. A plethora of algorithms have been introduced to construct decision trees from a given training set and to ensure the classification of query instances [START_REF] Breiman | Classification and Regression Trees[END_REF][START_REF] Quinlan | Induction of decision trees[END_REF][START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF].

The most used algorithms follow a Top Down Induction of Decision Tree approach (TDIDT) that consists on a recursive divide and conquer strategy by following the steps below:

• select, through the use of an attribute selection measure, the attribute that enables the best possible partitioning of the training set;

• split the current training data into training subsets according to the selected attribute values.

• nominate a training subset as a leaf when a stopping criterion is reached.

As regards the attribute selection process, several measures have been proposed in the literature [START_REF] De Mántaras | A distance-based attribute selection measure for decision tree induction[END_REF][START_REF] Quinlan | Induction of decision trees[END_REF][START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. The information gain, measuring the efficiency of an attribute when classifying the training instances, is one among the best known and most widely used measures. Given a training data S and an attribute A, the information gain will be set to:

Gain(S, A) = Inf o(S) -Inf o A (S) (11)
where

Inf o(S) = - Q i=1 p i .log 2 p i (12)
and

Inf o A (S) = - v∈Domain(A) |S A v | |S| ( 13
)
where p i reflects the proportion of objects having θ i as class (i.e. i ∈ {1, . . . , Q})

and S A v corresponds to the training subsets for which the attribute A has v as value.

One major limitation of this measure is that the attributes with the largest values are the most promoted ones [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. This had led to the introduction of the GainRatio measure used in the C4.5 algorithm [START_REF] Quinlan | Induction of decision trees[END_REF][START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. It is given as follows:

GainRatio(S, A) = Gain(S, A) SplitInf o(A) (14)
where

SpliInf o(A) = v∈Domain(A) |S A v | |S| .log 2 |S A v | |S| . (15)

Classification from evidential data

Evidential databases allow to process imperfect knowledge by expressing imperfect knowledge through the belief function theory. Each object O j within an evidential database is described by n evidential attributes A = {A 1 , . . . , A n }. Each attribute A k (i.e. k ∈ {1, . . . , n}) has a domain of discrete values denoted by Θ A k , and an evidential class label having Θ = {θ 1 , . . . , θ Q } as domain (i.e. Q represents the total number of classes). The idea behind evidential databases consists of representing all kinds of data availability, including total certainty as well as totally and partially ignorance:

• Total certainty: A certain bba, is a bba that has a singleton as its unique focal element, and it is used to represent the state of total certainty.

• Total ignorance: In case of total ignorance, a vacuous bba refers to a bba having Θ as its unique focal element.

• Partially ignorance: Regarding the case of partially ignorance, a quantity of belief has to be assigned to a subset of the frame of discernment Θ.

An example of evidential databases is given below.

Example 1. Assuming a credit risk management problem. Overall, a bank loan officer has to predict the customer profitability levels Θ={Good, Moderate, Bad} on the basis of some parameters (Attributes). To put it simply, in this example, Table 1 describes the data knowledge for training, where we relied on three characteristics:

• Income with possible values Θ Income ={No, Low, Average, High}.

• Property: This attribute reflects whether the loan requested by the client is greater or less than its property value and consequently it takes values as Θ P roperty ={Greater, Less}.

• Unpaid Credit: This attribute providing information about client's unpaid Credit with two possible values Θ U npaidCredit ={Yes, No}. We intend, in this paper, to construct decision tree classifiers from evidential data using the following notations:

O 1 m Income 1 ({High}) = 1 m P roperty 1 ({Greater}) = 0.6 m P roperty 1 ({Less}) = 0.3 m P roperty 1 (Θ P roperty ) = 0.1 m U npaidCredit 1 ({Y es}) = 1 O 2 m Income 2 ({Average}) = 1 m P roperty 2 ({Greater}) = 1 m U npaidCredit 2 ({N o}) = O 3 m Income 3 ({Low}) = 1 m P roperty 3 ({Less}) = 0.5 m P roperty 3 (Θ P roperty ) = 0.5 m U npaidCredit 3 ({Y es}) = 1 O 4 m Income 4 ({N o}) = 1 m P roperty 4 ({Less}) = 1 m U npaidCredit 4 ({N o}) = O 5 m Income 5 ({Low}) = 1 m P roperty
• T = {O 1 , . . . O M }: a given training set composed by M objects O j ; j = {1,. . . ,M }.
• S: a subset of objects belonging to the training set T .

• A={A 1 ,. . .,A n }: the set of n attributes.

• Θ A k : set of all possible values v of an attribute A k ∈ A where k = {1, . . . , n}.

• Θ= {θ 1 ,. . . , θ Q }: represents the Q possible classes of the classification problem.

• S A k v : subset of objects from S having v ∈ Θ A k as value.

• m j Θ A k (v): denotes the bbm assigned to the hypothesis that the actual attribute value of the object

O j belongs to v ⊆ Θ A k . • m Θ A k v :
is the certain bba corresponding to the attribute A k and having v as its unique focal element.

• m Θ j : corresponds to the bba relative to the class of the object O j .

• L= {L 1 ,. . . , L F }: represents the F generated leaves when building the decision tree.

Decision tree procedure

This section presents the two main levels enabling the use of our belief decision tree classifiers: the construction and the classification levels. We provide, in the following, a description of each level.

Construction level

The construction of our belief decision trees follows the same Quinlan algorithm steps [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. In fact, it requires a top down approach as the standard case. Assume that T is our training set, the different steps of our decision tree learning algorithm are given as follows:

1. We start by creating the root node from the whole training set T .

2. We check if the root node satisfies any stopping criteria.

• If one stopping criterion is reached, the treated node will be declared as a leaf for which we compute the probability distribution over the set of classes.

• If not, we pick out the attribute that maximizes a chosen attribute selection measure. The chosen one will be the root node of our decision tree relative to the set T .

3. We create a branch for each value v of the attribute A k chosen as a root. This partitioning step leads to several subsets S A k v where each one contains as much as possible homogenous objects according to the attribute value v.

4. We restart the same process from level 2 until all nodes are considered as leaves.

Classification level

Concerning the classification step, we propose to classify objects described by evidential attributes modeled with bbas. Let M ′ be the total number of testing instances O j (j = {1, . . . , M ′ }) and A = {A 1 , . . . , A n } be the set of n attributes characterizing our testing instances. The global frame of discernment relative to all the attributes, denoted by Θ A , is equal to the cross product of the different Θ A k :

Θ A = × k=1,...,n Θ A k . ( 16
)
Since objects are described by a combination of values where each of them corresponds to one attribute, we first have to compute for each object to be classified the joint bba expressing beliefs on its attribute values. To reach our ultimate goal, we proceed as follows:

• Firstly, we extend the different bbas m Θ A k j to the global frame of attributes Θ A (see Equation 5). Thus, we get the different bbas m Θ A k ↑Θ A j .

• Then, we combine the different extended bbas using the conjunctive combination rule as follows:

m Θ A j = ∩ k=1,...,n m Θ A k ↑Θ A j . (17)
If our joint bba m Θ A j is computed, we move on to evaluate the belief function bel Θ j [x] of each focal element x relative to the object O j . It will be noted that the computation of this function depends mainly on the focal elements of the bba m Θ A and on the subset x. This dependency is expressed in the following:

• When x is a singleton, the belief function bel Θ j [x] will be equal to the belief function corresponding to the leaf to which the focal element is attached;

• If not, we explore all possible paths corresponding to this combination of values. There are two possible cases:

-Case 1: All paths lead to the same leaf. In this case, the bel Θ j [x] will be equal to the leaf's belief function.

-Case 2: Paths lead to distinct leaves. In this case, bel Θ j [x] will correspond to the disjunctive combination [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] of each leaf's belief function through the disjunctive rule.

• The belief function of every query test O j has to be computed by averaging each focal element x using m Θ A when relied on the generalized Bayesian theorem [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF]:

bel Θ j [m Θ A ](θ) = x⊆Θ A m Θ A (x).bel Θ j [x](θ) for θ ⊆ Θ (18) then m Θ j [m Θ A ](θ) = B⊆θ (-1) |θ|-|B| .bel Θ j [m Θ A ](B) ∀ θ ⊆ Θ, θ = ∅ (19)
Note that m Θ j [m Θ A ](θ) reflects the degree of belief allocated to the class θ of the query test O j . In order to make the decision, the mass function will be transformed into probability measure through the pignistic probability. The class with the highest pignistic probability will be considered as the predicted class of the object O j .

Novel belief decision tree classifiers

In this paper, our aim consists of designing two decision tree classifiers for addressing evidential data, namely GainRatio Belief Decision Tree (GR-BDT) and Dif f Ratio Belief Decision Tree (DR-BDT).

GainRatio Belief Decision Tree (GR-BDT)

This subsection is devoted to highlighting the main parameters enabling the construction of the GR-BDT classifier which mainly includes the attribute selection measure, the partitioning strategy, the stopping criteria and the structure of leaves.

Attribute selection measure

The attribute selection measure is considered as one of the major parameters ensuring decision tree construction. It consists of choosing, for each decision node of the tree, the attribute test that will better separate the training instances into homogenous subsets. For the Gain Ratio approach, we have relied on the entropy measure that is calculated from the average probability obtained from the set of objects in the node. To choose the most appropriate attribute, we propose the following steps:

1. We compute the pignistic probability relative to each instance O j belonging to the training set:

BetP Θ [O j ](θ i ) = θ i ⊆B;B⊆2 Θ 1 |B| . m Θ j (B) 1 -m Θ j (∅) . (20)
2. We compute the average probability relative to each class by taking into consideration the objects in the set S (the learning set for which we look to identify the best attribute to split on). This function is set to:

BetP Θ [S](θ i ) = 1 O j ∈S P S j O j ∈S P S j .BetP Θ [O j ](θ i ) ( 21
)
where BetP Θ [O j ](θ i ) reflects the membership probability of the object O i to the class θ i and P S j corresponds to the probability that the object O j belongs to the subset S. Assuming that the attributes are independent and assuming that S = T , the probability P S j will be equal to the product of the different pignistic probabilities induced from the attribute bba's corresponding to the object O j and enabling this latter to belong to the node S.

Let A B = {A 1 , . . . , A O } ∈ A with values V B = {v 1 , . . . , v O }
be the set of attributes leading to the branch S, the probability P S j will be set to:

P S j = Ao∈A B BetP Θ Ao [O j ](v o ) (22)
3. Inspired by the Shannon measure of uncertainty [START_REF] Klir | Types and measures of uncertainty[END_REF], we compute the entropy Inf o(S) of the average probabilities in S which is set to:

Inf o(S) = - Q i=1 BetP Θ [S](θ i ).log 2 BetP Θ [S](θ i ). (23)
4. Assuming an attribute A k , for each value v ∈ Θ A k , we define the subset

S A k v
which is composed with objects having v as their value. Since the attribute A k 's values may be uncertain, the subset

S A k v will contain objects O j such that BetP Θ A k [O j ](v) = 0.
5. We compute, for objects in the subset S A k v , the weighted average pignistic probability BetP Θ [S A k v ] where v ∈ Θ A k and A k ∈ A. It will be set to:

BetP Θ [S A k v ](θ i ) = 1 O j ∈S A k v P S A k v j O j ∈S A k v P S A k v j .BetP Θ [O j ](θ i ) ( 24
)
where

P S A k v j
is the probability of the object O j belongs to the subset S A k v having v as a value of the attribute A k (its computation is done in the same manner as the computation of P S j ).

6. We compute Inf o A k (S) as discussed by Quinlan [START_REF] Quinlan | Induction of decision trees[END_REF], while using the pignistic probability instead of the proportions. We get:

Inf o A k (S) = v∈Θ A k O j ∈S A k v P S A k v j O j ∈S P S j .Inf o(S A k v ) (25)
where Inf o(S A k v ) is computed from Equation 23. 7. We compute the GainRatio relative to the attribute A k :

GainRatio(S, A k ) = Inf o(S) -Inf o A k (S) SplitInf o(S, A k ) ( 26
)
where the SplitInf o value is defined as follows:

SplitInf o(S, A k ) = - v∈Θ A k O j ∈S A k v P S A k v j O j ∈S P S j .log 2 O j ∈S A k v P S A k v j O j ∈S P S j . (27)
8. We repeat the same process for each attribute A k ∈ A (from step 3 to step 7) and then we select the one that has the maximum GainRatio. relying on the GainRatio measure, we try to illustrate the first attribute selection process when S=T . Note that, in the case of S=T , P S j equals 1 for all j ∈ {1, . . . , 6}. The probability of belonging of an object O j to a subset S A k k are given in Table 2.

• We start by computing the entropy Inf o(T ), using Equation 23. It is computed using the average pignistic probability that reflect the membership of objects to classes Good, M oderate or Bad (see Table 3). The entropy will then be set to:

Inf o(T ) = -0.41.log 2 0.41 -0.22.log 2 0.22 -0.37.log 2 0.37 =1.5426 According to the yielded results, we can deduce that the attribute Income is the one that maximizes the GainRatio. So, it will be chosen as the root node of the tree.

P S Income N o O 1 1 0 0 0 O 2 0 1 0 0 O 3 0 0 1 0 O 4 0 0 0 1 O 5 0 0 1 0 O 6 1 0
P S U npaidCredit N o O 1 1 0 O 2 0 1 O 3 1 0 O 4 0 1 O 5 0 1 O 6 1 0

Partitioning strategy

The splitting strategy consists of dividing the training set according to the values of the chosen attribute A k , meaning that a branch will be associated to each value v of the chosen attribute and each edge will contain a subset

S A k v from S.
Since we handle data with evidential attributes, each training object may belong to more than one subset. Indeed, each training object may belong to more than one branch with a membership probability computed in terms of the pignistic probability. To put it simply, a given object O j has to be assigned to each branch having v as value and should satisfy

BetP Θ A k [O j ](v) = 0.

Stopping criteria

The stopping criteria are similar to those used by the standard decision tree.

There exist mainly four stopping strategies:

1. Only one instance is part to the treated node.

2. Instances of the treated node belong to the same class.

3. There is no further attribute for checking.

4. The remaining attributes have GainRatio equal or less than zero.

Structure of leaves

It is important to underline that leaves for our constructed decision trees include objects with different class labels. As a matter of fact, each leaf will be represented by a belief function computed from the probability of objects belonging to that leaf:

m Θ [L f ](θ) = 1 O j ∈L f P L j O j ∈L P L j .m Θ j (θ) θ ⊆ Θ ( 28
)
where

P L f j
is the probability of the instance O j to belong to the leaf L f (i.e.

f ∈ [1, F ]). This latter is computed as the cross product of the pignistic probabilities of the object O j to belong to the nodes that link the root node and the corresponding leaf node L f .

Example 3. Assuming Example 2, we try to generate our GR-BDT classifier. As it is shown in the aforementioned example, we have deduced the performance of the Income attribute over the P roperty and the U npaidCredit attributes. Accordingly, the Income attribute has been chosen as a root node. The first generated tree is given in Figure 1. have not satisfied the stopping criteria.

Income P roperty L 1 = {O 2 } U npaid Credit L 2 = {O 4 } High Average Low N o
So, we apply the same process for the both subsets until the stopping criteria hold. The final generated decision tree is depicted in Figure 2.

Dif f Ratio Belief Decision tree (DR-BDT)

We provide, in the following, the parameters enabling the construction of the DR-BDT classifier.

Income P roperty

L 3 = {O 1 , O 6 } L 4 = {O 1 , O 6 } L 1 = {O 2 } U npaid Credit L 5 = {O 3 } L 6 = {O 5 } L 2 = {O 4 } High Greater Less Average Low Y es N o N o Figure 2:
The final generated tree of the GR-BDT classifier

Attribute selection measure

By analogy with [START_REF] Trabelsi | New decision tree classifier for dealing with partially uncertain data[END_REF], the DR-BDT classifier consists of computing the intragroup distance that measures for each attribute value how much objects are close to each other. We propose the following steps to pick out the best decision attribute:

1. We compute the intra-group distance between objects of S in terms of their classes:

SumD(S) = O i ∈S O j≥i+1 ∈S dist(m Θ i , m Θ j ) (29)
where dist represents the Jousselme distance between the two bbas m Θ i and m Θ j that correspond respectively to the bbas relative to the class of objects O i and O j .

2. Then, for each attribute value v, we compute SumD(S A k v ) as follows:

SumD(S A k v ) = O i ∈S O j≥i+1 ∈S D S A k v i .D S A k v j .dist(m Θ i , m Θ j ) (30)
where

D S A k v i
reflects the belonging of the object O i to the subset S A k v and it is set to:

D S A k v i = 1 -dist(m Θ A k v , m Θ A k i ) (31)
m Θ A k v is a certain bba where m Θ A k v (v) = 1.
3. For each attribute A k ∈ A, we compute SumD A k (S) as follows:

SumD A k (S) = v∈Θ A k SumD(S A k v ). (32)
4. We compute the Dif f Ratio relative to the attribute A k , where the SplitInf o will be calculated such as in Equation 14.

Dif f Ratio(S, A k ) = SumD(S) -SumD A k (S) SplitInf o(S, A k ) . (33)
Drawing inspiration from the clustering approach, the idea underlying the Dif f Ratio approach consists of minimizing the intra distance between objects, while maximizing the inter distance. That is the Dif f Ratio measure allows to band together similar objects as much as possible.

5. We repeat this process for each attribute A k ∈ A and then select the one that maximize the Dif f Ratio. • We start by calculating the intra-group distance between objects in terms of their classes using Equation 29. We get:

* SumD(T )= 9.0741.

• Then, we compute the total distance induced by each attribute. We obtain: From this, we can deduce that the attribute P roperty is the one that maximises the Dif f Ratio criterion. Accordingly, it will be chosen as the root node of the tree.

* SumD Income (T ) = 0.

Partitioning strategy

Each training object O i , within the DR-BDT classifier, may be part of more than one subset S A k v with a degree of belonging

D S A k v i : • When D S A k v i = 1
, the object O i belongs to the branch having v as a value.

• When D S A k v i = 0, the object O i may not belong to the branch having v as label. In contrast, it will be part of the remaining branches.

• else, the object O i belongs to all the branch of the attribute A k

Stopping criteria

The stopping criteria relative to the DR-BDT approach are similar to those of the GR-BDT:

1. Only one instance is part of the treated node.

2. Instances of the treated node belong to the same class.

3. There is no further attribute for checking.

4. The remaining attributes have Dif f Ratio equal or less than zero.

Structure of leaves

Leaves L f , within this approach, may contain objects O i with different class labels θ ∈ Θ. Thus, each leaf L f has to be characterized by a belief function m Θ [L f ] that is calculated in terms of the used approach.

Let

L f = v 1 f × . . . × v J f ∈ A 1 f × . . . × A J
f be the set of attribute values that correspond to the branch leading to L f (f ∈ [1, F ]) (i.e J corresponds to the number of edges from the tree's root node to the leaf node). The leaf mass m Θ [L f ] will then be computed as:

m Θ [L f ] = ∩ O i ∈L f mi Θ (34)
where mi

Θ reflects the discounted bba relative to m Θ i and is set to:

mi Θ (θ) = (1 -α f ).m Θ i (θ) θ ⊂ Θ (35) mi Θ (Θ) = α f + (1 -α f ).m Θ i (Θ) (36)
with

α f = 1 J . J t=1 (1 -D S A t f v t f i ). ( 37
)
Example 5. We move on now to generate the DR-BDT classifier relative to the training data given in Table 1. According to Example 4, we notice that the attribute P roperty has outperformed both the U npaidCredit and the Income attributes. Consequently, it should be chosen as the decision tree root. The first generated tree is given in Figure 3. have not fulfilling the stopping criteria. Therefore, the same process has to be applied for these subsets until a stopping criterion is satisfied. The final generated decision tree is given in Figure 4.

Experimentation settings and results

In this section, we evaluate the performance of our proposed decision tree approaches. In the following, we detail our experimentation settings and results.

Experimentation settings

With the aim of evaluating the performance of our three evidential classifiers,

we made experiments on several real world databases acquired from the UCI machine learning databases [START_REF] Murphy | UCI repository databases[END_REF]. We have also picked out several databases that have missing values. Table 4 provides the details of the used databases, where #Instances, #Attributes, #Classes and #Missing denote, respectively, the number of instances, the number of attributes, the number of classes and the existence or not of missing values. From a practical point of view, missing values have to be imputed and continuous variables have usually to be discretized into bins. However, the uncertainty introduced by missing values imputation and continuous variables discretization have to be addressed. In this paper, we propose to express data uncertainty with the belief function theory. From this, we assign certain bbas to categorical attribute values and we transform the continuous values into beliefs using the Evidential c-Means approach (ECM) [START_REF] Masson | Ecm: An evidential version of the fuzzy c-means algorithm[END_REF][START_REF] Samet | Evidential data mining: precise support and confidence[END_REF]. Regarding the missing data, we propose to impute these data using the Nearest Neighbors imputation approach [START_REF] Crookston | yaimpute: an R package for knn imputation[END_REF]. As we handle evidential data, we used the Jousselme distance measure instead of the standard distance metrics for computing the distance between instances. That is to say, the distance between the object with missing values and the objects with complete values should be calculated. The k Nearest Neighbors objects is then used for the imputation process. So, we assign, for each object with a missing attribute value, the mean bba of its k-Nearest Neighbors corresponding to that attribute.

Two kinds of experimentation have been considered. The first one aims to evaluate the performance of our decision tree versions against standard decision tree classifiers, particularly the C4.5 algorithm. Our second experimentation concerns the evaluation and the comparison of our decision tree approaches against existing evidential classifiers. For the comparison process, we have run the 5-folds cross validation technique and we have relied on the Percentage of Correctly Classification measure (PCC) as an evaluation criterion.

Experimentation results

This Section is devoted to comparing our proposed decision tree approaches over standard and evidential classifiers. Before tackling the comparison process, we suggest to compare both the GR-BDT and the DR-BDT in the way of selecting decision attributes. That is to say, we relied on the Spearman's rank correlation coefficient [START_REF] Spearman | The proof and measurement of association between two things[END_REF] for measuring the rank correlation between both approaches achieved at the root node. This rank measure takes values in the range between -1 and 1. A value of -1, 0 and 1 state respectively the case of negative correlation (different and dependent results), no correlation (different and independent results) and positive correlation (similar results) between the GR-BDT and the DR-BDT. The results obtained in Table 5 indicate the high difference between the GR-BDT and the DR-BDT when selecting attributes. In fact, almost all databases have yielded index correlation measure in the range [0,-1]. Note that, we compare both the GR-BDT and the DR-BDT against the standard C4.5 algorithm and some evidential decision tree classifiers.

Experimentation1: Comparison against the C4.5 algorithm

In this section, we experiment our proposed approaches and we compare them to the C4.5 algorithm using evidential databases. To do so, we transform categorical datasets with missing data upon the use of the evidential database transformation process. The comparison results in terms of the PCC criterion is given in Table 6. From this table, we can remark that the mean PCC yielded by the GR-BDT (84.68%) and the DR-BDT (85.61 %) has outperformed that obtained using the C4.5 algorithm (75.53%). From this, we can deduce that both our approaches yield interesting results and we can conclude that our proposed decision tree approaches have outperformed the C4.5 algorithm. This experimentation concerns the comparison of our decision tree approaches against the E2M DT and the naive approach presented in [START_REF] Sutton-Charani | Learning decision trees from uncertain data with an evidential em approach[END_REF]. The experimentation results are presented in Table 7, where we can remark that the mean PCCs achieved by the GR-BDT and the DR-BDT are a little bit greater then that obtained by the E2M DT and the Naive classifier. From this, we can deduce the efficiency of our proposed decision tree algorithms against the Naive and the E2M DT classifiers.

Conclusion

In this paper, we have proposed two decision tree classifier techniques to cope with imperfect knowledge expressed within the evidence theory. Precisely, we have tackled data with uncertain attribute values as well as uncertain class labels. Regarding the future research directions, we look forward to investigating more robust techniques for uncertain data modeling within the belief function framework. Notably, the case of incomplete data should be well studied and an extension of the E2M algorithm in the context of evidential data may be quite sufficient. We intend also to apply a pruning strategy with the aim of improving predictive accuracies. It would also be interesting to develop ensemble of our GR-BDT and DR-BDT. More concretely, we look forward to constructing GR-BDT and DR-BDT random forests.

5 ( 6 (

 56 {Y es}) = 1

Example 2 .

 2 Let us consider the training data given in Example 1. By

**

  Inf o U npaidCredit (T ) through Equation25. We get:* Inf o Income (T ) = 0.9738 Inf o P roperty (T ) = 1.3959 Inf o U npaidCredit (T ) = 1.4644• Then, we compute the Information Gain for each attribute: * GainRatio(Income) = 0.2965 * GainRatio(P roperty) = 0.1467 * GainRatio(U npaidCredit) = 0.0782

Figure 1 :

 1 Figure 1: The first generated tree of the GR-BDT classifier

Example 4 .

 4 Let us continue with the training data given in Example 1 and try to illustrate the attribute selection process when S=T on the basis of the Dif f Ratio criterion.

7479 ,*

 7479 SumD P roperty (T ) = 3.5076, * SumD U npaidCredit (T ) = 3.8291. • Then, we compute the Dif f Ratio for each attribute: * Dif f Ratio(Income) = 4.3404, * Dif f Ratio(P roperty) = 5.5677, * Dif f Ratio(U npaidCredit) = 5.2450.

  Both subsets S P roperty Greater = {O 1 , O 2 , O 3 , O 5 , O 6 } and S P roperty Less = {O 1 , O 3 , O 4 , O 5 , O 6 }

Figure 3 :

 3 Figure 3: The first generated tree of the DR-BDT classifier

Figure 4 :

 4 Figure 4: The final generated tree of the DR-BDT classifier

Table 1 :

 1 Uncertain training data within the belief function framework

	O	Income	Property	Unpaid Credit
	width=1.2center

Table 2 :

 2 The probability of belonging of objects in terms of the attribute values.

		Outlook
	P S Income High	P S Income Average	P S Income Low

Table 3 :

 3 Pignistic probability computed from bba of Class column of Table1Subsequently, we move on to compute Inf o Income (T ), Inf o P roperty (T ) and

		Good Moderate Bad
	BetP Θ (T )	0.41	0.22	0.37
	•

Table 4 :

 4 Description of databases

	Databases	#Instances	#Attributes	#Classes	#Missing
	Breast Cancer	286	9	2	Yes
	Primary Tumor	339	17	22	Yes
	Voting Records	435	16	2	Yes
	Soybean	638	36	2	Yes
	Ecoli	336	8	8	No
	Hepatitis	155	19	2	Yes
	Auto MPG	398	8	3	Yes
	Wine	178	13	3	No
	Echo-cardiogram	132	12	2	Yes

Table 5

 5

	provides the rank

Table 5 :

 5 Rank correlation approach between the GR-BDT and the DR-BDT

	Databases	ICM
	Breast Cancer	0.11
	Primary Tumor	-0.67
	Voting Records	0.32
	Soybean	0
	Ecoli	-0.89
	Hepatitis	0.09
	Auto MPG	-0.4
	Wine	-0.15
	Echo-cardiogram	-0.73

Table 6 :

 6 Comparison of percentage of correctly classification against the C4.5 algorithm

	(%)
		C4.5	GR-BDT	DR-BDT
	Breast Cancer	74.12 ± 0.44	78.14 ± 0.17	76.52 ± 0.23
	Primary Tumor	40.70 ± 0.19	69.23 ± 0.40	72.43 ± 0.27
	Voting Records	96.55 ± 0.17	97.01 ± 0.14	97.83 ± 0.36
	Soybean	90.77 ± 0.09	94.35 ± 0.20	95.67 ± 0.15
	Mean	75.53	84.68	85.61
	7.2.2. Experimentation 2: Comparison with the naive and the E2M classi-
	fiers

Table 7 :

 7 Comparison of percentage of correctly classification against the naive and the E2M algorithms (%)

		Naive	E2M DT	GR-BDT	DR-BDT
	Breast Cancer	74.63 ± 0.13	79.51 ± 0.27	78.14 ± 0.17	76.52 ± 0.23
	Primary Tumor	63.17 ± 0.33	68.76 ± 0.05	69.23 ± 0.40	72.43 ± 0.27
	Voting Records	81.89 ± 0.27	95.65 ± 0.14	97.01 ± 0.14	97.83 ± 0.36
	Soybean	89.23 ± 0.24	93.86 ± 0.32	94.35 ± 0.20	95.67 ± 0.15
	Ecoli	83.56 ± 0.02	85.11 ± 0.17	84.26 ± 0.09	84.92 ±0.21
	Hepatitis	78.05 ± 0.36	83.55 ± 0.31	85.37 ± 0.19	84.79 ± 0.35
	Auto MPG	80.60 ± 0.07	85.23 ± 0.29	93.18 ± 0.15	92.56 ± 0.26
	Wine	72.33 ± 0.37	75.14 ± 0.11	78.32 ± 0.32	80.47 ± 0.08
	Echo-cardiogram	94.56 ± 0.43	97.14 ± 0.15	96.26 ± 0.34	95.69 ± 0.16
	Mean	79.78	84.88	86.23	86.76

Acknowledgment

We would like to express our deep gratitude to Thierry Denoeux, Sébastien Destercke and Nicolas Sutton Charani for their help in doing the comparative study between our two proposed approaches and their E2M DT classifier.

Thanks are also due to the anonymous reviewers for their constructive and helpful comments and suggestions which have been in help to improve the quality of this paper.


Sabrine Mallek
email: sabrinemallek@yahoo.fr

Imen Boukhris

Zied Elouedi

Eric Lefèvre

Evidential Link Prediction in Social Networks based on Structural and Social Information

Keywords: Social network analysis, evidential social network, uncertain link prediction, belief function theory, structural information, social circle information

Social networks are large systems that depict linkage between millions of social entities. The study of their patterning and evolving is one of the major research areas in social network analysis and network mining. It includes the prediction of future associations between unlinked nodes, known as the link prediction problem. Traditional methods are designed to deal with social networks under a certain framework. Yet, data of such networks are usually noisy, missing and prone to observation errors causing distortions and likely inaccurate results. This paper addresses the link prediction problem under the uncertain framework of the belief function theory, an appealing framework for reasoning under uncertainty that permits to represent, quantify and manage imperfect evidence. Firstly, a new graph based model for social networks that handles uncertainties in links' structures is introduced. Secondly, a novel method for the prediction of new links that makes use of the belief functions tools is proposed. It takes advantage of both neighborhood and common groups information in social networks in order to predict new connections. The performance of the new method is validated on real world social networks. Experiments show that our approach performs better than traditional methods based on structural information.

Introduction

Social networks are highly dynamic structures that alter quickly over time by the creation of new links. Understanding the processes by which these systems evolve offers a new level of perception of the mechanisms that underlie social networks [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF]. Link prediction is a research field in social network analysis that studies the changes of social networks structures. It is an efficient tool to examine the uncertainty and potential connections between unlinked actors.

Link prediction has been drawing the attention of researchers from different domains. The task is to evaluate the potential existence of a link between nonadjacent nodes given a state of the network. Link prediction conducts research in various fields generally related, but not restricted, to computer science, such as recommender systems to suggest new friends or common interests [START_REF] Huang | Link prediction approach to collaborative filtering[END_REF], bioinformatics in the study of protein-protein interaction networks [START_REF] Lei | A novel link prediction algorithm for reconstructing proteinprotein interaction networks by topological similarity[END_REF] or link analysis and mining [START_REF] Getoor | Link mining: A survey[END_REF] for identifying hidden or missing criminals in terrorist networks [START_REF] Mahesar | Efficient link prediction method in dark networks analysis[END_REF].

It is a well known fact that the structure of social networks highly depends on the precise nature of the data. These latter are often missing and noisy [START_REF] Adar | Managing uncertainty in social networks[END_REF][START_REF] Kossinets | Effects of missing data in social networks[END_REF] (i.e., missing nodes and/or edges). They are also frequently prone to observation errors which causes distortions. A possible reason is the unreliability of the sources employed for the construction of the network (i.e., open source intelligence, human intelligence) [START_REF] Johansson | Constructing and analyzing uncertain social networks from unstructured textual data[END_REF]. In many cases, one has to deal with two major problems: consider all the nodes and edges and risk the possibility of adding false ones in the network or delete the uncertain ones and face the problem of missing nodes and edges [START_REF] Dahlin | A method for community detection in uncertain networks[END_REF]. On that point, incorporating uncertainty in the structure and analysis of social networks is expected to be crucial.

In recent years, a wide variety of methods have been proposed to address the LP problem. Yet, most of them handle social networks under a certain framework where the links take binary values, either 1 (exist) or 0 (¬ exist).

Nevertheless, a possible way to represent an uncertain network is to assign weights with values in [0, 1] to encrypt the uncertainty degrees [START_REF] Johansson | Constructing and analyzing uncertain social networks from unstructured textual data[END_REF]. The authors in [START_REF] Adar | Managing uncertainty in social networks[END_REF] pointed out the shifting degrees of uncertainty characterizing real world large-scale data. They outlined the importance of handling uncertainty in network data which is argued to be more substantial for social networks on account of their large structures. Actually, depiction of uncertainty in social networks has not been addressed in sociology and other fields literature. Traditional analysis focused on interactions in small groups since obtaining large datasets was difficult. Yet, the emergence of online networking and modern database technology allowed to get a great deal of data which stimulated the study of the characteristics of these networks. However, little interest has been dedicated to the examination of their uncertain aspects [START_REF] Svenson | Social network analysis of uncertain networks[END_REF].

The belief function theory also called the Dempster-Shafer theory was first introduced by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] in the context of statistical inference then generalized by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] as a theory for reasoning under uncertainty. It is an appealing framework considered as a generalization of Bayesian theory. More importantly, it permits to quantify, manage and represent imperfect evidence. Furthermore, it enables combining information from different sources and make decision. We suggest to make use of the belief function theory assets to introduce a new graph-based model for social networks that handles uncertainty at the level of the edges. Additionally, we develop a fruitful approach for LP that operates under uncertainty. Links with and without prior knowledge are considered in the prediction task, information from the common neighbors and shared groups is acquired and whole process of transfer, matching and fusion is applied to get an outlook on the potential new links. Additionally, a new technique for the generation of uncertain social networks is presented.

All in all, the main contributions of this work are as follows:

-The formulation of the problem of link prediction in social networks under the uncertain framework of the belief function theory.

-The development of a graph-based model for social networks that handles uncertainty at the edges level encoded by mass functions.

-The design of a novel framework for link prediction based on our graph model for uncertain social networks that operates merely with the belief function theory tools.

-The implementation of two algorithms for link prediction according to two strategies: with and without prior knowledge about the links existence.

-Experiments on real life social networks datasets to evaluate the effectiveness of our proposals.

The remaining of the paper is organized as follows: Section 2 summarizes the related work on the LP problem.

Section 3 provides some basic knowledge about the belief function theory. Section 4 presents the new framework for LP under uncertainty. Firstly, the new model for uncertain social network is introduced. Then, the proposed algorithms are presented through a detailed description of the individual steps. Section 5 gives the experimental setting and the results. Finally, Section 6 concludes the paper and draws future research directions.

Related work on link prediction

Link prediction is becoming increasingly important in many fields such as link analysis, information retrieval and network evolution [START_REF] Yang | Evaluating link prediction methods[END_REF]. In social networks, it is used to predict relationships to be formed, uncover relationships that probably exist but have not been observed, or even to assist individuals in forming new connections [START_REF] Samanthula | Interest-driven private friend recommendation[END_REF]. In this section, we formulate the link prediction problem and briefly review some exiting approaches. Then, we give some challenges and present our proposals.

Problem definition

The most straightforward definition of link prediction is the determination of the likelihood of new associations.

In formal terms, given a current snapshot of a social network graph G(V, E) where V is the set of nodes representing the social entities and E is the set of edges encoding social relations. The task is to predict potential future or missing edges according to the considered state of the graph. In fact, when the objective is to predict future links, one should consider a snapshot of the graph at time t and try to determine the likelihood of links' existence at time t + 1. In contrast, to predict missing links, one should consider a state of the graph at time t and try to infer the links that may existed at time t -1. They may be unobservable or missing from the data [START_REF] Luo | Detecting the missing links in social networks based on utility analysis[END_REF]. Yet, to predict future links, one has to consider data with time information regarding the links formulation. However, such data are not usually available. Thus, most methods test LP algorithms on static data where the network is built on the basis of the observable data, then extra links that are not visible but are likely to exist are derived [START_REF] Taskar | Link prediction in relational data[END_REF].

Existing methods

Most LP approaches assign weights to links according to the nodes properties. These weights represent computed scores based on the query network. Decision about new links existence is made by ranking the highest L scores, where L is a parameter fixed by the user. Various approaches apply directly this intuition to tackle LP. Meanwhile, another group of methods use the similarity score as features for supervised learning. Other methods use latent models to tackle LP. A brief survey of the latter approaches is presented in the following paragraphs.

Structural features. Structural based approaches can be categorized into two main families: local methods and global methods [START_REF] Lu | Link prediction in complex networks: A survey[END_REF]. The first family compute metrics based on structural similarities between the nodes' characteristics.

For example, the number of common neighbors between a pair of nodes. The second family uses nodes' proximity in the network, metrics based on the ensemble of paths are employed to detect the closest nodes. Generally, global methods operate better than the local ones [START_REF] Lu | Link prediction in complex networks: A survey[END_REF]. However, some paths based metrics are time consuming because they use the topological information of the whole network which is not always available. Besides, an important aspect that characterizes social networks is not treated which is the participation of actors in the social groups (clusters, circles).

As a matter of fact, in many social networks, users are involved in many social groups at the same time. Thus, methods that use both local and social circles information have been proposed [START_REF] Xie | Potential links by neighbor communities[END_REF][START_REF] Soundarajan | Using community information to improve the precision of link prediction methods[END_REF][START_REF] Valverde-Rebaza | Link prediction in complex networks based on cluster information[END_REF][START_REF] Wu | A balanced modularity maximization link prediction model in social networks[END_REF].

Supervised learning. Many supervised learning based approaches use similarity measures as features to tackle the LP problem. For instance, LP is formulated as a binary classification task, a set of features based on the nodes' similarities is selected [START_REF] Hasan | Link prediction using supervised learning[END_REF]. In [START_REF] Aghabozorgi | A new similarity measure for link prediction based on local structures in social networks[END_REF], the authors used network motifs as a structural feature under supervised learning to predict new links. The authors in [START_REF] Lu | Supervised link prediction using multiple sources[END_REF] addressed LP using classification models to learn the dynamics of social networks using auxiliary networks. In [START_REF] Ahmed | A supervised learning approach to link prediction in twitter[END_REF], a supervised learning strategy for link prediction is developed using structural metrics as features. In [START_REF] De Sa | Supervised link prediction in weighted networks[END_REF], supervised learning is applied to LP using different features such as community information, connectivity, interaction and trust information. Other works extract the essential attributes of nodes and edges and use them as features [START_REF] Hasan | A Survey of Link Prediction in Social Networks[END_REF]. However, such information are not generic and choosing the appropriate features can be critical since it depends on the network domain. Besides, node attributes are not usually available in data due to privacy and confidentiality issues. Although, the use of supervised learning allows to benefit of all the advantages of classification, there are three main challenges to be considered: (1) the choice of the appropriate classification algorithm, (2) the suitable combination of features to be considered in learning classifier (3) and handling the class imbalance problem.

Latent models. This group of methods use probabilities to assess the likelihood of links existence [START_REF] Kashima | A parameterized probabilistic model of network evolution for supervised link prediction[END_REF][START_REF] Wang | Local probabilistic models for link prediction[END_REF] where a class is assigned to each node of the network. Latent methods assume a particular arrangement principles of the structure of the network, along with some detailed rules and particular parameters retrieved by maximizing the likelihood of the observed structure. Then, the likelihood of query link is evaluated according to these rules and parameters.

They use generally Bayesian probabilistic models, they learn probabilities of the classes by fixing appropriate priors probabilities and adjust them later to estimate the likelihood of co-occurrence of the nodes pairs [START_REF] Kashima | A parameterized probabilistic model of network evolution for supervised link prediction[END_REF][START_REF] Wang | Local probabilistic models for link prediction[END_REF]. For example, in [START_REF] Menon | Link prediction via matrix factorization[END_REF], the authors extended matrix factorization and combined latent features with nodes and edges explicit features to predict new links. The authors in [START_REF] Wang | Local probabilistic models for link prediction[END_REF] addressed link prediction using a local probabilistic model based on Markov Random Field [START_REF] Kinderman | Markov random fields and their applications[END_REF], an undirected graphical model. To evaluate the likelihood a new link between connecting u and v, a central neighborhood set based on other nodes that are present in the local neighborhood of u or v is computed.

The authors in [START_REF] Yu | Gaussian Process Models for Link Analysis and Transfer Learning[END_REF] proposed stochastic relational models based on Gaussian process models for LP. Yet, latent models based methods suffer from high complexity costs du to matrix decomposition, factor matrices and latent features learning which makes such algorithms intractable for large networks.

Challenges

There are several challenges when dealing with the link prediction problem. The main challenge consists at the rapid growth and evolution of online social networks such as Facebook, T witter, Flickr, and so on. They are highly dynamic and evolve continuously. That is, effective direct approaches are mandatory to address these constraints [START_REF] Hasan | A Survey of Link Prediction in Social Networks[END_REF]. Besides, the cold start problem is a big challenge of LP. It is the problem of not having sufficient initial link structure for training the link prediction task [START_REF] Leroy | Cold start link prediction[END_REF]. This problem is especially encountered when the size of network is very small or we do not have any information about the structure of the links. It is also encountered when treating coupled networks, where the task is to predict the links in a network that we have no information except that is it interacting with another known one [START_REF] Dong | Coupledlp: Link prediction in coupled networks[END_REF]. Incompletion is another faced challenge while predicting links in online social networks. Actually, almost all social network data contain missing values [START_REF] Wang | Link prediction in social networks: the state-of-the-art[END_REF]. This is due to anonymization and privacy preservation concerns. As a result, only part of the data is collected.

Structural similarity measures

Our proposals draw on structural based models. More specifically, on the intuition of the methods that use local and group metrics. This category of methods is the most basic. Practically, traditional methods use the graph feature measures. One of the most inherent reason is that several similarity score are very easy and simple to compute, especially the local structural metrics [START_REF] Zhou | Predicting missing links via local information[END_REF]. Besides, they are generic since they are related to the graph topology and not to its domain. To this end, we recall, in the following, fundamental definitions of popular state of the art structural local measures and group information scores essential for the understanding of our algorithms.

Local information based measures. Among the well known structural local measures is the "Common Neighbors" [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF], denoted by CN(u, v). It gives the number of common neighbors shared between a pair of two nodes u and v in the social network. Let τ(u) denotes the set of neighbors of a node u. The Common Neighbors measure is defined as:

CN uv = |τ(u) ∩ τ(v)|. (1)
Suppose that the graph presented in Figure 1 is a social network. The set of nodes is {t, u, v, w, x, y, z}. Consider the nodes u and v. The set of neighbors of u is τ(u) = {t, x, y, z} and the set of neighbors of v is τ(v) = {t, w, x, y, z}.

Hence, the set of common neighbors of the pair (u, v) is {t, x, y, z}. Thus, CN uv = 4.

Another commonly used measure is the Jaccard Coefficient [START_REF] Jaccard | Étude comparative de la distribution florale dans une portion des Alpes et du Jura[END_REF] denoted by JC. It accounts all the neighbors of u and v. It is defined as follows:

JC uv = |τ(u) ∩ τ(v)| |τ(u) ∪ τ(v)| . (2)
For example, the Jaccard Coefficient of the nodes u and v presented in Figure 1 is JC uv = 4 5 . The Adamic/Adar measure denoted by AA uv weights the intake of each common neighbor x by the inverse of its degree, it is defined as:

AA uv = x∈(τ(u)∩τ(v)) 1 log|τ(x)| . (3)
The Adamic/Adar score of the nodes u and v from Figure 1 is computed as follows: [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF], denoted by PA, speculates that a new link has probability proportional to |τ(u)| to connect to u. Thus, the preferential attachment of u and v is proportional to the number of neighbors of u and v. It is computed as follows:

AA uv = 1 log|τ(x)| + 1 log|τ(y)| + 1 log|τ(z)| + 1 log|τ(t)| = 4.51. Preferential Attachment
PA uv = |τ(u)| • |τ(v)| (4)
For example PA uv (Figure 1) is computed as follows:

PA uv = |τ(u)| • |τ(v)| = 20.
Resource Allocation [START_REF] Zhou | Predicting missing links via local information[END_REF], denoted by RA, is based on the resource allocation process of networks. Common neighbors of two unlinked nodes u and v are considered as transmitters of resources where each one provides a unit so that u sends some resource to v. It is computed as follows:

RA(u, v) = z∈(τ(u)∩τ(v)) 1 |τ(z)| (5)
For example RA uv (Figure 1) is: [START_REF] Sørensen | A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons[END_REF] is used generally for ecological community data. It is defined as:

RA uv = z∈(τ(u)∩τ(v)) 1 |τ(z)| = 1, 58. The Sørensen index
S ørensen uv = 2|τ(u) ∩ τ(v)| |τ(u)| + |τ(v)| . (6)
The Sørensen score of u and v from Figure 1 is computed as follows:

S ørensen uv = 2|τ(u)∩τ(v)| |τ(u)|+|τ(v)| = 8 9 .
Salton Index [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF] is defined as follows:

S alton uv = |τ(u) ∩ τ(v)| √ |τ(u)| × |τ(v)| . (7)
The Salton score of u and v is computed as follows: Group information based measures. Group information based measures include the Common Neighbors of Groups (CNG) and Common Neighbors Within and Outside of Common Groups (WOCG) [START_REF] Valverde-Rebaza | Link prediction in complex networks based on cluster information[END_REF]. Let Λ C uv denotes the set of common neighbors of the pair (u, v) that belong to the social circle C. The CNG describes the size of the set of common neighbors of (u, v) that belong to at least one group C to which u or v is part of. It is defined as:

S alton uv = |τ(u)∩τ(v)| √ |τ(u)|×|τ(v)| = 0, 89. y z w u x v C 1 C 3 C 2 t C 4
CNG uv = |Λ C uv |. (8)
Suppose that the dashed circles C 1 , C 2 , C 3 and C 4 in the graph presented in Figure 1

WOCG uv = |Λ WCG uv | |Λ OCG uv | . ( 9
)
For example, the set of common neighbors within common groups of the pair of nodes (u, v) from Figure 1 is Λ WCG uv = {x} while the common neighbors outside the common groups is the set Λ OCG uv = {y, z}. Hence, WOCG uv = 1 2 . Both information of the nodes' neighborhoods and groups are considered in our proposals. We draw on structural local measures since these latter are simple to compute and they have proven their efficiency in many previous works [START_REF] Liben-Nowell | The link-prediction problem for social networks[END_REF][START_REF] Zhou | Predicting missing links via local information[END_REF][START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF].

While the above presented measures (local and group information based) are simple and effective [START_REF] Gao | Link prediction via local structural information in complex networks[END_REF], they do not take uncertainty into account. Therefore, in order to handle and manage imperfect social data, the belief function theory is embraced as a framework for reasoning under uncertainty. Mathematical notations and concepts of the belief function theory fundamental for the understanding of our proposals are given in the next section.

The uncertain framework of belief functions

The belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], is a suitable theory to represent and manage imperfect knowledge. It permits to handle uncertainty and imprecision in data and manage it in a flexible way. Assume the frame of discernment Θ, an exhaustive and finite set of mutually exclusive events associated to a given problem, and let 2 Θ denote the set of all subsets of Θ. Knowledge in the belief function theory is modeled by a basic belief assignment (bba), denoted by m, it is defined as follows:

m : 2 Θ → [0, 1] A⊆Θ m(A) = 1. ( 10
)
A is called a focal element if m(A) > 0.

As a special case of bba's, evidence on the frame of discernment is only committed to a particular subset A and Θ.

Such a mass function is called a simple support function (ss f ). It is defined as [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]:

             m(A) = 1 -ω, ∀A ⊂ Θ m(Θ) = ω. (11)
Reliability of the sources of evidence is an important parameter that needs to be considered. When it is quantified, the bba may be weakened before the combination on Θ. For that, a discounting mechanism can be applied [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]:

         α m(A) = (1 -α)m(A), ∀A ⊂ Θ α m(Θ) = α + (1 -α)m(Θ). ( 12
)
where α ∈ [0, 1] is the discount rate.

Evidence given by two reliable and distinct sources of information is combined using the conjunctive rule of combination denoted by ∩ . It is defined as [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF]:

m 1 ∩ m 2 (A) = B,C⊆Θ:B∩C=A m 1 (B) • m 2 (C). (13)
Furthermore, in order to combine two mass functions m 1 and m 2 defined on two disjoint frames Θ and Ω, we need to work under a unified frame. For that, the bba's are extended to the product space Θ×Ω. Then the vacuous extension operation, denoted by ↑, is applied. It is defined by:

m Θ↑Θ×Ω (C) =              m Θ (A) if C = A × Ω, A ⊆ Θ, C ⊆ Θ × Ω 0 otherwise. ( 14
)
To define the relation between two different frames of discernment Θ and Ω, the multi-valued mapping may be used [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. In formal terms, a multi-valued mapping function denoted by ϕ, joins the subsets X i ⊆ Ω that can possibly correspond to A i ⊆ Θ:

m ϕ (A i ) = ϕ(X i )=A i m(X i ). ( 15
)
To make decisions within the theory of belief functions, one may use the pignistic probability measure denoted by

BetP [START_REF] Smets | The Transferable Belief Model for Quantified Belief Representation[END_REF]:

BetP(A) = B⊆Θ |A ∩ B| |B| m(B) (1 -m(∅)) , ∀A ∈ Θ. ( 16
)

The evidential link prediction framework

In this section, we start by introducing our evidential graph model for uncertain social networks. Then, we present our algorithms for link prediction under uncertainty which extends state of the art methods and incorporates uncertainty at the same time.

The model: Evidential social network

A social network is commonly modeled by a graph G = (V, E) where V is the set of nodes and E is the set of links.

Yet, such conceptualization does not consider uncertainty that results from imperfect data or unreliability of the tools used for the construction of the network. In this respect, we suggest to encode the uncertainty degrees on the edges level by adopting the belief function theory [START_REF] Mallek | Evidential link prediction based on group information[END_REF][START_REF] Mallek | The link prediction problem under a belief function framework[END_REF]. Each edge uv has assigned a basic belief assignment denoted by m uv defined on Θ uv = {E uv , ¬E uv }, E uv depicts the event that the link between u and v exists and ¬E uv means that it is absent. Thus, this bba describes the degree of uncertainty regarding the existence and absence of uv. Hence, instead of having links with weights that can be either 1 or 0 to show whether or not a link does exist, a mass function with values in [0, 1] that quantifies the degree of uncertainty regarding a link existence is ascribed. Figure 2 gives an example of such a social network graph structure. The dashed circles indicate the social groups to which the users belong. The links are weighted by bba's. For example, m ad is the mass function that encodes the uncertainty degree regarding the existence of an association between nodes a and d. A node may join to multiple circles i.e., the node d participates to the three groups Group 1 , Group 2 and Group 3 .

Figure 2: An evidential social network with social groups

Methodology: Evidential link prediction (ELP) algorithms

Node neighborhood and group information are coupled to forge an overall mechanism for a method that fulfills the process of link prediction under uncertainty. In fact, local metrics are simple and generic, they have proven their efficiency in several social network domains [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF][START_REF] Kossinets | Empirical analysis of an evolving social network[END_REF]. As such, links connecting similar nodes are more likely to exist.

In turn, in many real world social networks, actors who share similar experiences or interests are more likely to share a relationship than those that do not have common characteristics. Therefore, group information add semantic and a better reflection of nodes linkage valuable for LP. The natural arrangement of groups in the network is used e.g., in facebook, the memberships of users to groups of interests.

On the other hand, there are two kinds of evidence regarding the edges existence: the first kind is when we are uncertain about whether the link really exists. In this case, the edge has a bba that quantifies this uncertainty. In the second case, we do not have any knowledge about the link existence. In other terms, the edge has not a mass function.

In fact, a preliminary work is done in [START_REF] Mallek | The link prediction problem under a belief function framework[END_REF] where we considered the case of not having any knowledge about the edges to be predicted and we inspected the corresponding evidence. However, the effect of group memberships is not taken into account, only structural local information is treated. In [START_REF] Mallek | Evidential link prediction based on group information[END_REF], we studied the case where the analyzed links already have prior evidence, the task is to update the current knowledge depending on graph state. In this work, our proposed method takes into consideration these two cases. Besides, it combines local topology and social circles membership to enhance LP.

Accordingly, our proposed problem for link prediction under uncertainty is as follows: Let G e (V e , E e , C e ) be an evidential social network where

V e = {v 1 , . . . , v |V| } is the set of nodes, E e = {(v i v j , m v i v j ) : v i v j , m : 2 Θ v i v j → [0, 1], and Θ v i v j = {E v i v j , ¬E v i v j
}} is the set of edges assigned with bba's, and C e = {C 1 , . . . , C |C| } is the set of overlapping circles. Let L be the set of analyzed links. The links in L might or not have initial bba's. The goal is to update or estimate the bba of query links according to whether or not there is prior information regarding their existence.

Prediction is made by considering local and group information.

The steps of the complete method for the prediction of a new link between a pair of nodes (u, v) are presented in the following, they are grouped depending on whether or not there is prior evidence regarding uv.

Without prior knowledge

Information acquiring. For each common neighbor z, extend vacuously the frames of each link zu and zv to the joint frame Θ zu × Θ zv using Equation 14. This allows to work on a unified referential. The induced bba's from the vacuous extension are then combined using the conjunctive rule of combination to get the masses of the possible pairs on

Θ zu × Θ zv .
Information transfer and fusion. To successfully transfer the obtained bba's to the frame Θ uv of uv, a multi-valued operation, denoted by ϕ, is used applied that ϕ: Θ zu × Θ zv → 2 Θ uv . The ϕ function (Equation 15) brings together combination sets to the mass of uv considering the common neighbor z denoted by m uv z as follows: -The masses of the pairs containing at least an element in {E zv , E zu } and not in {¬E zv , ¬E zu } are transferred to E uv ⊆ Θ uv such that:

m uv z ({E uv }) = ϕ(S )=E uv m(S ). ( 17
)
-The masses of the pairs that contain at least an element in {¬E zv , ¬E zu } and no element in {E zv , E zu } are transferred to ¬E uv ⊆ Θ uv as:

m uv z ({¬E uv }) = ϕ(S )=¬E uv m(S ). ( 18
)
-The masses of the pairs including at least an element in {E zv , E zu } and an element in {¬E zv , ¬E zu } are transferred to Θ uv such that:

m uv z (Θ uv ) = ϕ(S )=Θ uv m(S ). ( 19
)
where

S ⊆ Θ zu × Θ zv
To get the bba m uv , the masses considering all the m common neighbors z i ∈ {z 1 , . . . , z m } are fused using the conjunctive rule of combination (Equation 13) such that:

m uv = m uv z 1 ∩ m uv z 2 ∩ . . . ∩ m uv z m . ( 20
)
This step permits to fuse the information provided by the neighboring nodes and treat them as independent sources of evidence.

Information reviewing. Once we get a global evidence from of all the neighboring nodes, we review the resulting bba according to whether or not the two nodes uv share a common scial circle. We accomplish this by computing the rate of common neighbors in shared groups |Λ C uv | with the total set of common neighbors CN, that we denote λ uv defined as:

λ uv = |Λ C uv | |CN uv | . ( 21
)
When all the common neighbors of uv belong to shared groups, λ uv is equal to 1. It is equal to 0 when no common neighbor is part of a mutual circle. We review m uv using a discounting mechanism (Equation 12) such that β = 1 -λ uv is the discounting rate. The discounted mass denoted by β m uv is computed as follows:

                     β m uv ({E uv }) = (1 -β) • m uv ({E uv }) β m uv ({¬E uv }) = (1 -β) • m uv ({¬E uv }) β m uv (Θ uv ) = β + (1 -β) • m uv (Θ uv
D(uv, xy) = n i=1 (s i uv -s i xy ) 2 D max ( 22
)
where s i uv and s i xy are the values of structural similarity metrics for respectively uv and xy and D max is the maximum value of the Euclidean distance.

Reliability computation. To quantify the degree of reliability of the most similar link, we apply a discounting operation (Equation 12) using the distance value as a discount coefficient denoted by α = D(uv, xy). As such, the more alike the two links are, the more reliable the similar link is. Hence, the discounted mass denoted by α m xy is obtained as follows:

                     α m xy ({E xy }) = (1 -α) • m xy ({E xy }) α m xy ({¬E xy }) = (1 -α) • m xy ({¬E xy }) α m xy (Θ xy ) = α + (1 -α) • m xy (Θ xy )
If there is more than one most similar link, we choose the link with the highest mass on "exist" as the degree of certainty of its existence would be higher.

Information transfer and fusion. The discounted bba of the most similar link xy is transferred to the frame Θ uv using a multi-valued mapping γ: Θ xy → 2 Θ uv that brings together the elements as follows: α m xy ({E xy }) is transferred to

m uv xy ({E uv }), α m xy ({¬E xy }) is transferred to m uv xy ({¬E uv }) and α m Θ xy (Θ xy ) is transferred to m uv xy (Θ uv ).
Where m uv xy denotes the bba of uv on Θ uv given the most similar link, here xy. The next step is to update the bba of uv given the new evidence obtained from the most similar link. To do this, the initial bba m uv and m uv xy are aggregated using the conjunctive rule of combination.

Decision making

After applying one of the two strategies, one has to make a decision about the existence of the link uv on the graph. Decision is made on the basis of the pignistic probability using Equation 16. As a matter of fact, the value of the pignistic probability on the hypothesis "exist" BetP uv (E uv ) is used as a score to evaluate the likelihood of the existence of new links. Structural methods from literature rank query links on the basis of similarity scores values. In the same manner, we rank the pignistic probabilities value on the hypothesis "exist" in decreasing order and cast the top k predicted links with highest scores.

Overall summary

Both strategies of the ELP algorithms are schematically given in Figure 3. To sum up, when there is prior knowledge about the link existence, our algorithms collect information from the neighboring links shared with the common neighbors. They are considered as independent sources of information. Then, the collected evidence is pooled to get an overall picture about the link existence. This evidence is boosted through reliability inspection according to groups' information. On the other hand, when there is no prior evidence about the link existence, evidence about the link is gathered from similar links in the shared groups. The similarity is evaluated according to a distance that exploits local and group information structural features. The most similar link represents a source of information, its evidence is reviewed according to its degree of similarity with the query link. The new evidence is pooled with the initial knowledge of the link to be predicted to make decision about its existence. Finally, after passing through one of the strategies, pignistic probabilities are computed to predict potential links. To sum up, our framework takes an evidential social network as input along with a list of query edges. The analyzed links may already have assigned bba's or not. The ELP algorithms are subsequently applied to provide the potential existing links as the output of the framework.

Evidential social network

Predicted links

With priori knolewdge Without priori knolewdge

Information transfert and fusion

Pieces of evidence fusion

Complexity analysis

Analysis of computational time complexity of is essential in social networks. Our novel link prediction framework is based mainly on local information methods, it considers neighboring nodes for prediction. Yet, unlike these methods, it handles uncertainty in social data. Local information link prediction methods are known to have the lowest computational complexity among existing approaches from literature [START_REF] Yang | A new link prediction algorithm based on local links[END_REF]. As our framework is based on local methods, theoretical complexity would be comparable. For the most part, it builds upon the common neighbors approach, thus it follows up the same procedure. Let N denote the number of nodes and let k be the average degree of all nodes in the network. The theoretical complexity of the common neighbors approach (and most local methods)

is O(N.k 2 ) [START_REF] Gao | Link prediction methods and their accuracy for different social networks and network metrics[END_REF]. Additional computational costs due to representing and managing belief masses are very low as we handle frames of discernment with just two elements. Therefore, theoretical complexity of our proposed method is equal to O(N.k 2 ). Such complexity is acceptable for link prediction and social network analysis applications.

Empirical study

To evaluate the potential benefit of the proposed ELP method, uncertain social networks are needed. Yet, data of such networks are not available. Thus, we preprocessed real-world social networks with social circles of BlogCatalog [START_REF] Tang | Relational learning via latent social dimensions[END_REF], Flickr [START_REF] Tang | Relational learning via latent social dimensions[END_REF] and Facebook [START_REF] Mcauley | Learning to discover social circles in ego networks[END_REF]. Description of the datasets is provided in Table 1.

• BlogCatalog: a social blog directory website. The dataset incorporates a friendship network with group memberships.

• Flickr: image and video hosting website. It provides web services and online community. The dataset contains the friendship network and the group memberships of the users.

• Facebook: a social media platform enabling users to maintain their network of real-world relationships. The network includes social circles joining people with like-minded interests. To convert the networks into evidential social networks, we undergo two steps: (1) three graphs of the network are generated from the data (2) then mass distributions are simulated according to the presence of the links in the generated graphs.

Graphs generation

At first, three graphs, that we call G 0 , G 1 and G 2 , are produced from each dataset by removing randomly a portion of the edges. This procedure is inspired from a widely technique from the literature. In fact, in several works, a portion of the edges is pruned from the graph to be considered in the prediction process [START_REF] Yin | Structural link analysis and prediction in microblogs[END_REF][START_REF] Valverde-Rebaza | Exploiting behaviors of communities of twitter users for link prediction[END_REF][START_REF] Zhang | Potential Theory for Directed Networks[END_REF]. This graph generation technique is applied to all the networks datasets.

Mass functions simulation

To create the evidential version of the social network, each link uv is valued by a bba that is simulated based on G 2 , G 1 and G 0 as follows:

- That is, for each dataset, we get an evidential version from the original graph to which the ELP method is applied to predict the new links under uncertainty.

Link prediction process

In the experimental phase, the evidential link prediction approach is applied to the evidential version of each graph G 0 . The masses of the edges without prior knowledge are determined on the basis of the common neighbors. Edges with prior bba's whose corresponding BetP's claim their absence (i.e., the pignistic probability on the event "not exist" is less than 50%) are compared to the links of the shared groups to update the evidence. Pignistic probabilities are subsequently computed to make decisions about the links existence. The results are finally compared to the initial network. In the similarity measurment step, we use local and group information scores as features to compute distances: CN (Equation 1), JC (Equation 2), AA (Equation 3), PA (Equation 4), RA (Equation 5), Salton (Equation 7), Sørenson (Equation 6), CNG (Equation 8) and WOCG (Equation 9).

To quantify the accuracy of prediction algorithms, we use the commonly used metrics: precision and area under the receiver operating characteristic curve (AUC). The AUC evaluates the performance of an algorithm according to predicted links. It depicts the likelihood of the score of an existing randomly picked link being higher than that of A randomly chosen non-existent one. Similarity indices are computed by selecting a random existing link and a non-existent link each time. Then, a missing link and a nonexistent link are randomly picked to compare their scores, if among n independent comparisons, there are n times the missing link having a higher score and n times they have the same score, the AUC value is:

AUC = n + 0.5n n (23)
Typically, a greater AUC value indicates a better performance quality.

The precision expresses the number of correctly predicted existing links Q e versus the set of analyzed links Q. It is defined as follows:

Precision = Q e Q . ( 24
)

Comparative study with existing methods

A comparative study is conducted with popular approaches local information approaches mostly used in the literature: CN, JC, AA, PA, RA, Salton and Sørensen. Furthermore, we test two other baseline approaches based on group information: CNG and WOCG. For that, G 0 is considered as a certain graph. In the experimental setup a random fraction of 20% of the links is removed and is considered as the test set along with links that do not exist in the graph.

Performance is evualuated by averaging over 5 implementations with independently random divisions of the test set. gives the highest results in terms of AUC for all the dataset. For BlogCatalog, our method gives by far the best results compared to all other methods, followed by CN, then by AA and CNG, which achieve comparable results.

For Facebook, ELP achieves best predictions. Besides AA, CN and PA perform the next best with close accuracies to our best one, while others, such as Salton, Jaccard index, Sørensen and WOCG perform far worse in the cases for Facebook. Same observation for Flickr, ELP gives the highest AUC values. CN, AA perfom the next best accuracies, while WOCG performs the worse. That is, our method clearly outperforms traditional methods. To top it all off, the novel ELP algorithm is significantly better than simple traditional methods. The strength of our approach comes not only from the use of both local and social circles information from the networks, but also from handling uncertainty in the prediction task. Our method operates exclusively using the belief function theory tools. Evidence is adequately collected from neighboring social entities and pooled to get an overall picture thanks to combination rules given by the belief function theory. Evidence can be even revised by evaluating the degree of trustworthiness of these social entities. results are very important to evaluate link prediction algorithms as, in many cases, the main objective is to accurately detect the real existing links. For instance, in Facebook, it is more important not to miss the real actual friends whereas it does not really matter when unknown friends are suggested. As it is observed, the ELP approach has the best precision results compared to state of the art methods for all the datasets. As illustrated, the precision curve of the ELP is above the baseline approaches. That is, the method is able to predict the actual existing associations. It clearly sticks out from these results that handling uncertainty enhances the prediction quality. Moreover, combining measures based on both local information and social circles improves performances. One should also notice that our method is generic as it does not count on the social network domain. That is, it can be applied to social networks from various fields e.g., friendship networks, blog networks, dark networks, collaboration networks, etc.

Conclusions and future work

In this paper, we have proposed a new graph model for social networks that handles uncertainty at the edges level.

We have developed a new method social links prediction under an uncertain framework. The use of the belief function theory enabled to quantify both the belief regarding the link existence and the uncertainty using mass functions. We have treated both the cases of having or not evidence about the predicted links. The neighboring nodes are considered as independent sources of information, evidence is transferred and fused to get insight about the edges. It is then, revised and combined to successfully predict new connections. A fruitful technique for the generation of uncertain networks have also been proposed.

A major advantage of our method compared to the existing approaches is that it operates on uncertain social networks. Despite that, using the belief function theory tools, all the information from the neighbors can be combined effectively while remaining cautious about their reliability. Our algorithms can heuristically determine the potential existing links. An empirical study on real social networks clearly demonstrated the effectiveness of our approach.

As part of future work, extension to the case of both uncertain nodes and edges would be considered. It would also be interesting to extend our work to a more complex network structure. For instance, we can treat the case of muti-relationnal networks allowing several types of simultaneous social ties between the actors. Hence, predictions will be made in a more functional manner by inferring both links' existence and types.

Figure 1 :

 1 Figure 1: A social network with social circles. The dashed circles cluster nodes belonging to the same social group i.e., y and u belong to the circle C 1 represented by the dashed red circle.

) 4 . 4 .

 44 With prior knowledge Similarity measurement. When we have a prior evidence about uv, we compare it with each link xy included in the common shared circles using the Euclidean distance D(uv, xy). Structural similarity measures based on local and group information are used as features. The most similar link to uv with the smallest distance is considered in the prediction task. The distance metric is divided by its maximum to get values in [0, 1]. It is computed as follows:

Figure 3 :

 3 Figure 3: The ELP framework

  If uv exists in G 2 , G 1 and G 0 , a bba m uv is created such that m uv ({E uv }) ∈ [2/3, 1] and m uv (Θ uv ) = 1m uv ({E uv });-If uv exists in G 2 and G 0 or G 1 and G 0 then a bba m uv is simulated such that m uv ({E uv }) ∈ [1/3, 2/3[, m uv ({¬E uv }) ∈ ]0, 1/3] and m uv (Θ uv ) = 1 -(m uv ({E uv }) + m uv ({¬E uv })); -If uv exists only in G 0 then a mass function m uv is ascribed such that m uv ({E uv }) ∈ ]0, 1/3], m uv ({¬E uv }) ∈ [1/3, 2/3] and m uv (Θ uv ) = 1 -(m uv ({E uv }) + m uv ({¬E uv })); -If uv exists in G 2 and G 1 then a ss f m uv is created such that m uv ({¬E uv }) ∈ ]1/3, 2/3] and m uv (Θ uv ) = 1m uv ({¬E uv });-If uv exists only in G 2 or in G 1 then a ss f m uv is assigned such that m uv ({¬E uv }) ∈ ]0, 1/3] and m uv (Θ uv ) = 1m uv ({¬E uv }).

Figure 4 :

 4 Figure 4: Comparison of link prediction methods on BlogCatalog, Facebook and Flickr networks in terms of AUC

Figure 5 :Figure 6 :

 56 Figure 5: Precision of all algorithms for BlogCatalog according to the number of predicted links L

Figure 7 :

 7 Figure 7: Precision of all algorithms for Flickr according to the number of predicted links L

Figures 5 ,

 5 Figures 5, 6 and 7 report the performance results measured by precision according to the variation of the number of predicted links L for all the methods for respectively the BlogCatalog, Facebook and Flickr networks. Precision

  describe social groups. The node u belongs to the groups C 1 and C 2 and the node v is member of the groups C 2 and C 3 . The set of common neighbors of groups of the pair (u, v) is Λ uv = {x, y, z}. The common neighbor p is not considered since it belongs to the group C 4 which u and v are not part of. Thus, CNG(u, v) = |{x, y, z}| = 3.

	Let Λ uv = Λ WCG uv	∪ Λ OCG

uv be the set of common neighbors of groups of (u, v) such that Λ WCG uv is the set of common neighbors within common groups (WCG) and Λ OCG uv is the set of common neighbors outside the common groups (OCG). The WOCG measure is defined as:

Table 1 :

 1 Description of the datasets

	Dataset	#nodes #edges	#groups
	BlogCatalog 10,312 333,983	39
	Flickr	80,513 5,899,882 195
	Facebook	4,039	88,234	122
	5.1. Network pre-processing