Asma Trabelsi
email: trabelsyasma@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Ensemble Enhanced Evidential k-NN classifier through rough set reducts

Keywords: Evidential Editing k-Nearest Neighbors classifier, rough set reducts, belief function theory, uncertain attributes, ensemble classifier

Data uncertainty is seen as one of the main issues of several real world applications that can affect the decision of experts. Several studies have been carried out, within the data mining and the pattern recognition fields, for processing the uncertainty that is associated to the classifier outputs. One solution consists of transforming classifier outputs into evidences within the framework of belief functions. To gain the best performance, ensemble systems with belief functions have been well studied for several years now. In this paper, we aim to construct an ensemble of the Evidential Editing k-Nearest Neighbors classifier (EEk-NN), which is an extension of the standard k-NN classifier for handling data with uncertain attribute values expressed within the belief function framework, through rough set reducts.

Introduction

A multiple classifier system, also referred to as a classifier ensemble, has been proven to be an effective and efficient way for solving complex classification problems and achieving high performance [START_REF] Ponti | Combining classifiers: from the creation of ensembles to the decision fusion[END_REF]. The construction of an ensemble of classifiers consists mainly on two distinct levels: the generation of a set of base classifiers and the combination of their output predictions. It should be emphasized that the process of improving ensemble accuracy requires the best choice of the base classifiers and also the combination operator. In this paper, we focus only on the generation of good base classifiers for enhancing accuracies. Ensuring diversity between the base classifiers has been defended as a successful means for the production of a good ensemble of base classifiers. Although diversity can be achieved in several ways, the manipulation of the input feature space has been theoretically and experimentally proven to be one of the best methods for establishing high diversity between base classifiers [START_REF] Bryll | Attribute bagging: improving accuracy of classifier ensembles by using random feature subsets[END_REF][START_REF] Tumer | Classi er combining: analytical results and implications[END_REF][START_REF] Turner | Decimated input ensembles for improved generalization[END_REF]. In fact, it does not only allow the correlation reduction between the combined classifiers, but it also performs faster thanks to the reduced size of the input feature space [START_REF] Bryll | Attribute bagging: improving accuracy of classifier ensembles by using random feature subsets[END_REF][START_REF] Bunke | Feature selection algorithms for the generation of multiple classifier systems and their application to handwritten word recognition[END_REF][START_REF] Kim | Toward a successful crm: variable selection, sampling, and ensemble[END_REF][START_REF] Tumer | Input decimated ensembles[END_REF]. The process of generating feature subsets with good predicting power is still under study. One commonly used solution is the random subspace method (RSM) offtenly called random subspacing. The major shortcoming of this latter technique is the random partition of the original input features. As a matter of fact, the random selection may potentially increase the risk of irrelevant and redundant features as part of the selected subsets. The rough set theory, introduced by Pawlak [START_REF] Pawlak | Rough sets[END_REF], has been successfully applied in pattern recognition, data mining and machine learning domains, more particularly for attribute reduction problems. The reduced attribute set, representing the minimal subset of attributes that enables the discernation of objects with different decision values, is referred to as reduct. Since there have been usually multiple reducts for a given data set, the concept of ensemble classifiers through rough set reducts have been introduced and applied in a range of practical problems such as text classification [START_REF] Shi | Rough set and ensemble learning based semi-supervised algorithm for text classification[END_REF], biomedical classification [START_REF] Shi | A novel ensemble algorithm for biomedical classification based on ant colony optimization[END_REF], tumor classification [START_REF] Wang | Tumor classification by combining PNN classifier ensemble with neighborhood rough set based gene reduction[END_REF], web services classification [START_REF] Saha | Classification of web services using tensor space model and rough ensemble classifier[END_REF], etc. It is important to emphasize that several real world application data suffer from some kinds of uncertainty, imprecision and also incompleteness that mainly pervade the attribute values. However, to the best of our knowledge, there are no rough set techniques allowing to obtain the possible reducts from data with uncertain attribute values. In this paper, we aim to develop a classifier ensemble through rough set reducts (RSR) for dealing with uncertain data. More precisely where the uncertainty exists in the attribute values and is represented within the belief function theory, a flexible way for managing and representing all kinds of uncertainty. We therefore propose a new method for generating approximate reducts from such a kind of data. Since tens or hundreds of reducts may be generated, a selected subset of these reducts have to be used for constructing the base classifiers, notably the most diverse ones. Herein, we have used the Evidential k-Nearest neighbors [START_REF] Trabelsi | Ensemble enhanced evidential k-nn classifier through random subspaces[END_REF], an extension of the well known k-NN to handle the uncertainty that occurs in the attribute values within the belief function framework, as base classifiers. Given a query instance, the output beliefs of the base evidential classifiers will then be merged through a combination operator that is offered by the belief function framework [START_REF] Smets | The combination of evidence in the Transferable Belief Model[END_REF]. The remaining of this paper is organized as follows: Section 2 is dedicated to recall some basic concepts of the belief function theory. Section 3 is committed to highlighting the fundamental concepts of the rough set theory. We describe, in Section 4, our proposed idea for constructing an ensemble of classifiers via rough set reducts for handling uncertain data. Our conducted experimentation on several synthetic databases is presented in Section 5. Finally, the conclusion and our main future work directions are reported in Section 6.

Belief function theory: Fundamental concepts

The belief function theory has been shown to be a convenient way for representing, managing and reasoning under uncertainty. In this Section, we briefly recall some fundamental concepts underlying this theory.

Information representation

Let Θ = {θ 1 , θ 2 , . . . , θ N } be a frame of discernment with a finite non empty set of N elementary hypotheses that are assumed to be exhaustive and mutually exclusive. An expert's belief over a given subset of Θ has to be represented by the so-called basic belief assignment m (bba) as follows:

A⊆Θ m(A) = 1 (1)
Each subset A of 2 Θ having fulfilled m(A) > 0 is called a focal element.

Combination operators

In several real-world problems, information has to be gathered from distinct sources. These latter have to be merged with the aim of obtaining the most accurate information possible. The belief function framework provides a set of combination rules for fusing such kinds of information. The conjunctive rule, proposed by Smets within the Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF], is one of the best known rules. Given two information sources S 1 and S 2 with respectively m 1 and m 2 as bbas, the conjunctive rule, denoted by ∩ , will be set as:

m 1 ∩ m 2 (A) = B∩C=A m 1 (B)m 2 (C), ∀A ⊆ Θ. (2)
The belief fully involved to the empty set reflects the conflictual mass. With the aim of retaining the basic properties of the belief function theory, Dempster have proposed in [START_REF] Dempster | Upper and Lower probabilities induced by a multivalued mapping[END_REF], a normalized version of the conjunctive rule. This latter allows to manage the conflict by redistributing the conflictual mass over all focal elements. It is obtained as follows:

m 1 ⊕ m 2 (A) = 1 1 -K B∩C=A m 1 (B)m 2 (C), ∀A ⊆ Θ (3)
where the conflictual mass K caused by the combination of the two bbas m 1 and m 2 through the conjunctive rule, is given as follows:

K = B∩C=∅ m 1 (B)m 2 (C) (4)

Decision making

The pignistic probability BetP , proposed in [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF], is an efficient and binding way for decision-making. It transforms beliefs into probability measures as follows:

BetP (A) = B∩A=∅ |A ∩ B| |B| m(B), ∀A ∈ Θ (5)
Making decision consists of selecting the most likely hypothesis, meaning the hypothesis H s with the highest pignistic probability:

H s = argmax A BetP (A), ∀A ∈ Θ (6)

Dissimilarity between bbas

Numerous measures have been introduced for computing the dissimilarity degree between two given bbas [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF][START_REF] Ristic | The TBM global distance measure for the association of uncertain combat id declarations[END_REF][START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF]. The Jousselme distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] is regarded as one of the well-known ones. Formally, the Jousselme distance, for two given bbas m 1 and m 2 , is defined by:

dist(m 1 , m 2 ) = 1 2 (m 1 -m 2 ) T D(m 1 -m 2 ) ( 7
)
where the Jaccard similarity measure D is set to:

D(X, Y ) =    1 if X=Y = ∅ |X ∩ Y | |X ∪ Y | ∀ X,Y ∈ 2 Θ (8)
3 Rough set theory

The rough set theory, which is proposed by Pawlak [START_REF] Pawlak | Rough sets[END_REF], constitutes a valid mathematical solution for handling imperfect data for several machine learning applications. Examples include clustering [START_REF] Parmar | MMR: an algorithm for clustering categorical data using rough set theory[END_REF], classification [START_REF] Jensen | Fuzzy-rough nearest neighbour classification and prediction[END_REF][START_REF] Khoo | A rough-set-based approach for classification and rule induction[END_REF] and attribute reduction [START_REF] Bhatt | On fuzzy-rough sets approach to feature selection[END_REF][START_REF] Kumar | Fuzzy-rough discriminative feature selection and classification algorithm, with application to microarray and image datasets[END_REF], etc. Attribute reduction within the rough set theory consists of discovering the minimal subsets of relevant features, also named reduct, from the original set. Authors in [START_REF] Skowron | The discernibility matrices and functions in information systems[END_REF], have introduced the notation of discernibility matrix and function as a way for finding reducts for a given data T . Suppose that T = {x 1 , . . . , x D } is a data composed with D objects x i ( i ∈ {1, . . . , D}) characterized by N attributes A={a 1 , . . . , a N } having values V = {v i 1 , . . . , v i N } and a class label Y i ∈ C = {c A , . . . , c Q } (i.e. Q is the number of classes). The discernibility matrix of T , denoted by DM , is a |D| × |D| matrix in which the element DM (x i , x j ) for an object pair (x i , x j ) is defined as follows ∀ i, j = {1, . . . , D} and ∀ n = {1, . . . , N }:

DM (x i , x j ) = {a n ∈ A|v i n (x i ) = v j n (x j ) and Y i = Y j }
Each element DM (x i , x j ) represents the set of all condition attributes discerning objects x i and x j that have not the same class label. The notion of discernibility function can be defined from the discernibility matrix as follows:

f (DM ) = ∧{∨(DM (x i , x j ))|∀x i , x j ∈ T, DM (x i , x j ) = ∅} (9)
Reducts may be yielded by transforming the discernibility function from conjunctive normal form into disjunctive normal form. The major shortcoming of this solution is its costly computation which makes it impractical for large or even medium sized data sets. Therefore, several heuristics have been discussed to overcome this drawback. Johnson's heuristic algorithm and the hitting set approach are ones of the most known algorithms [START_REF] Debie | Reduct based ensemble of learning classifier system for real-valued classification problems[END_REF].

Classifier ensemble through rough set reducts

In this paper, we aim to construct an ensemble of classifiers from data characterized by uncertain attribute values expressed within the belief function framework. Particulary, we propose to construct an ensemble of the Enhanced Evidential k Nearest Neighbors (EEk-NN), an extended version of the classical k-NN for handling evidential data, through rough set reducts. The general structure of our proposed idea is depicted in Figure 1.

Fig. 1: The general structure of the proposed method.

Given a training data with uncertain attribute values, we have to generate firstly all possible rough set reducts R = {r 1 , . . . , r M }. Subsequently, we have to choose the ones enabling the construction of a good ensemble of EEk-NNs. Mainly, we have to pick out the most diverse ones. The decision yielded by each individual classifier, for a given query instance, will be merged using the Dempster operator, one well used belief function combination rules for merging distinct classifiers.

Numerous reduct generation methods have been proposed in the literature and the commonly used ones are mainly based on the information entropy and the discernibility matrix. Examples include the Johnson algorithm and the hitting set approach. The former one consists of a greedy search technique for piking out a single reduct which is generally close to the optimal, while the latter one allows the computation of multiple reducts. Within the hitting set approach, a multiset ζ will contain the non empty sets of a given discernability matrix and the minimal hitting sets of ζ are exactly the reducts.

Since the computation of reducts using the hitting set approach is an NP-hard problem, genetic algorithms have been used for generating approximate hitting sets, meaning approximate reducts. One example is the SAVGenetic algorithm reducer [START_REF] Lee | Multi-disciplinary Trends in Artificial Intelligence[END_REF], a Rosetta toolkit algorithm providing multiple reducts on the basis of the hitting set paradigm [START_REF] Komorowski | The rosetta rough set software system[END_REF]. Since this algorithm is widely used, it has not the ability to handle uncertain data. Herein, we propose to extend the SAVGenetic algorithm reducer for handling data with uncertain attribute values represented by belief functions.

In analogy with the SAVGenetic algorithm, our proposed algorithm consists firstly of computing the discernability matrix for data with uncertain attributes. We have already proposed, in [START_REF] Trabelsi | Feature selection from partially uncertain data within the belief function framework[END_REF], a belief discernability matrix for discerning pairs of objects with uncertain attribute values expressed in terms of belief functions.

Given a data set T ={x 1 ,. . .,x D } with a finite set of D objects x i (i ∈ {1, . . . , D}). Every object x i is defined by a set of N uncertain attributes A = {a 1 , . . . , a N } with values uV i = {uv i 1 , . . . , uv i N } and a certain class label Y i ∈ C = {c 1 , . . . , c Q }. Each uncertain attribute value uv i n relative to an instance x i (with n in {1, . . . , N }) will be expressed by a basic belief assignment m Θn i where Θ n reflects the frame of discernment relative to the attribute n. Let S denotes a tolerance threshold (i.e. in this paper S is set to 0.1 for maximizing the search space) and dist reflects the Jousselme distance. The entries of our proposed belief discernibility matrix, denoted by Λ , have been set as follows ∀ i, j ∈ {1, . . . , D} and n ∈ {1, . . . , N }:

Λ (x i , x j ) = {a n ∈ A|dist(m Θn i , m Θn j ) > S and Y i = Y j } (10)
A multiset ζ will then contain the non empty set of Λ and the approximate hitting sets of ζ correspond exactly to the approximate reducts. Our algorithm's fitness function corresponds exactly to that of the standard SAVGenetic algorithm. It consists of two main parts. The former one rewards subsets with shortest size, while the latter one rewards subsets that are hitting sets (i.e. meaning subsets having a non empty intersection with all elements of the discernability matrix). It is set as follows for each subset B ∈ 2 N :

f (B) = (1 -α) × |A| -|B| |B| + α × min{ε, [ ∈ ζ | ∩ B = ∅|] |ζ | } ( 11
)
where α ∈ [0, 1] reflects the adaptive weighting between the two terms and ε expresses the minimal hitting set fraction.

It is important to note that rough set approaches may generate tens or even hundreds of reducts and the most diverse ones have to be chosen for ensemble learning. One simplest algorithm for picking out diverse reducts is introduced in [START_REF] Debie | Reduct based ensemble of learning classifier system for real-valued classification problems[END_REF]. It consists of choosing randomly a reduct from the initial list and then adding progressively reducts that are diverse as much as possible from the chosen ones. The diversity degree is set as:

Div s = 1 - k∈L Reds∩Red k Reds∪Red k L ( 12
)
where L is the number of the chosen reducts and Red s is the candidate reduct.

The candidate reduct with the highest diversity will be added to the list of the chosen reducts.

Experimentations

More recently, we have introduced an ensemble of EEk-NNs through the random subspace method (RSM) and we have proven its performance compared with the individual EEk-NN that is trained in full feature space [START_REF] Trabelsi | Ensemble enhanced evidential k-nn classifier through random subspaces[END_REF]. In this paper, we aim to evaluate the performance of the ensemble of EEk-NNs through rough set reducts (RSR). Thus, we propose to carry out a comparative study with the ensemble proposed in [START_REF] Trabelsi | Ensemble enhanced evidential k-nn classifier through random subspaces[END_REF]. We relied mainly on the percentage of correct classification criterion (PCC). In what follows, we present our experimentation settings and results.

Experimentation settings

As we are handling data with uncertain attribute values expressed in terms of belief functions, we have proposed to construct synthetic databases by injecting uncertainty on real databases obtained from the the UCI machine learning repository [START_REF] Murphy | UCI repository databases[END_REF]. We provide, in Table 1, a brief description of some categorical databases where #Instances, #Attributes and #Classes denote, respectively, the number of instances, the number of attributes and the number of classes. We have tackled different uncertainty levels P :

-Certain case: P =0 -Low uncertainty case: (0 < P < 0.4) -Middle uncertainty case :(0.4 ≤ P < 0.7) -High uncertainty case (0.7 ≤ P ≤ 1) Suppose that T is a database composed with D instances x i (i ∈ {1, . . . , D}).

Each instance x i is characterized by N uncertain attribute values uv n i (n ∈ {1, . . . , N }). Suppose that Θ n is the frame of discernment relative to the attribute n. Each attribute value uv n i relative to an instance x i such that uv n i ⊆ Θ n will be expressed in terms of belief functions as follows:

m Θn {x i }(uv n i ) = 1 -P (13)
m Θn {x i }(Θ n ) = P
It is important to note that some databases suffer from incompleteness. The belief function theory allows to represent and manage missing attribute values. In this paper, the missing attribute values will be modeled as follows:

m Θn {x i }(uv n i ) = 0 ∀ uv n i ⊆ Θ n (14)
m Θn {x i }(Θ n ) = 1

Experimentation results

In this experimentations, we have relied on the 10-fold cross validation strategy for learning the individual Enhanced k-Nearest Neighbors classifiers. One key issue which has to be addressed is the number of neighbors that may give satisfactory results. In our experimentation tests, we evaluate five values of k which respectively correspond to 1, 3, 5, 7 and 9. Another substantial key element when designing an ensemble of classifier is the number of individual classifiers used to get the final decision. The conclusion conducted following to the study of [START_REF] Opitz | Popular ensemble methods: An empirical study[END_REF] proves that ensembles of 25 classifiers are sufficient for reducing the error rate and consequently for improving performance. Thus, in our paper, the number of the merged classifiers will be equal to 25. The final PCCs, which are obtained through the combination of the classifier outputs using the Dempster rule, will be given from Table 2 to Table 6, where RSM reflects the results yielded through the random subspace method and RSR reflects the results obtained with the rough set reducts method. The PCC results given from Table 2 to Table 6 and the average classification accuracies depicted in Figure 2 have proven the efficiency of the ensemble classifiers that are obtained through the rough set reduct approach over that yielded using the random subspace method. In fact, the average accuracies achieved by the RSR method for the different values of k are almost always greater than those achieved by the RSM method. Taking the Voting Records database as example, the average accuracy done by the RSR approach are equal to 95.03, 92.84, 92.84, 93.65 and 93.65, while there are equal to 90.11, 91.04, 90.92, 90.70 and 90.69 for respectively k=1, k=3, k=5, k=7 and k=9. The conclusion derived from the carried out experimentation tests may be justified by the fact that random subspace methods may negatively affect the classification process as irrelevant and redundant features can part of the selected subsets .

Conclusion

The idea underlying this paper is to increase accuracy for a given classification system through ensemble systems. Herein, we have constructed an ensemble of the so-called Enhanced Evidential k-Nearest Neighbors for dealing with uncertain data, more precisely where the uncertainty pervades the attribute values and is represented with belief functions. With the aim of assessing the performance of our proposed technique, we have conducted a comparative study with ensemble constructed through random subspaces. The yielded results have shown the efficiency of the rough set reducts over random subspaces. As we combine distinct classifiers, in this paper, we have relied on the Dempster rule of combination. As there are other combination rules, in our future work, we intend to pick out the combination operator that yields the best classification results. With the aim of increasing accuracy, we look forward to take into consideration not only the diversity between reducts, but also the diversity between the merged classifiers and the accuracy of the individual classifiers to yield more performance.

Fig. 2 :

 2 Fig. 2: Average accuracies.

Table 1 :

 1 Description of databases.

	Databases	#Instances #Attributes #Classes
	Voting Records	435	16	2
	Monks	432	7	2
	Breast Cancer	286	9	2
	Lymphography	148	18	4
	Tic-Tac-Toa	958	9	2

Table 2 :

 2 Results for Voting Records database (%).

		k = 1	k = 3	k = 5	k = 7	k = 9
		RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR
	No	90.23	93.72	91.62	93.72	90.93	93.72	91.93	93.72	91.16	93.72
	Low	90.46	93.95	91.62	93.95	91.16	93.95	90.06	93.95	91.39	93.95
	Middle	91.39	93.95	91.39	93.95	91.86	93.95	91.62	93.95	90.93	93.95
	High	88.37	95.53	89.53	89.76	89.76	89.76	89.76	90	89.30	90
	Average 90.11	95.03	91.04	92.84	90.92	92.84	90.70	93.65	90.69	93.65

Table 3 :

 3 Results for Lymphography database (%).

		k = 1	k = 3	k = 5	k = 7	k = 9
		RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR
	No	83.57	86.42	82.85	86.42	85.71	85	84.28	85	80.71	85
	Low	81.42	77.85	90	77.85	81.42	73.85	78.85	78.57	79.28	77.85
	Middle	83.57	81.42	82.85	81.42	83.57	80.71	81.42	80	82.85	80
	High	62.24	72.85	62.85	73.75	61.42	73.57	62.85	73.57	61.42	73.57
	Average 77.70	79.62	77.38	79.81	78.03	79.28	76.82	79.10	76.06	79.10

Table 4 :

 4 Results for Tic-Tac-Toa database (%).

		k = 1	k = 3	k = 5	k = 7	k = 9
		RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR
	No	62.10	62	61.15	63.89	61.05	62.42	60.84	62	60	60.63
	Low	55.36	56.73	55.78	57.05	55.89	54.52	55.89	55.26	55.57	55.68
	Middle	55.57	57.57	56	57.47	56	55.47	56.21	56.10	56.21	56
	High	57.78	57.89	57.68	58.10	58	57.89	58.31	58.21	50.31	59.15
	Average 57.70	58.54	57.25	59.2	57.73	57.57	57.81	57.89	57.52	57.86

Table 5 :

 5 Results for Monks database (%).

		k = 1	k = 3	k = 5	k = 7	k = 9
		RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR
	No	73.13	85.45	60.26	85.45	61.68	85.45	69.03	85.45	79.81	85.45
	Low	71.01	84.36	59.49	84.36	94.16	84.36	70.65	84.36	76.54	84.36
	Middle	69.85	85.27	60.26	85.27	68.9	85.27	72.84	85.27	70.72	85.27
	High	56.14	64.72	53.68	64.72	52.03	64.72	53.72	64.72	54.18	64.72
	Average 67.35	79.95	58.42	79.95	69.19	79.95	66.56	79.95	70.31	79.95

Table 6 :

 6 Results for Breast Cancer database (%).

		k = 1	k = 3	k = 5	k = 7	k = 9
		RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR	RSM	RSR
	No	73,13	75.08	76.18	75.07	75.10	73.71	74.04	76.03	76.03	76.9
	Low	73.10	73.57	76.10	76.18	74.89	75.10	73.91	74.04	75.8	76.9
	Middle	73.92	73.75	75.59	76.18	74.32	75.10	73.80	74.04	76	76.9
	High	73.01	73.75	75.45	76.18	74.62	75.10	72.12	74.04	76.13	76.9
	Average 73.29	74.03	75.83	75.90	74.73	74.75	73.46	74.53	75.99	76.9


Malika Ben Khalifa
email: malikabenkhalifa2@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

Multiple criteria fake reviews detection using belief function theory

Keywords: Online reviews, Multi-criteria evaluation, Fake reviews, Uncertainty, Belief function theory

Checking online reviews before making a purchase becomes a permanent habit. Hence, online consumer reviews, product and services play an increasingly spreading role in consumer purchasing decisions. Unfortunately, the importance of advertising and the attraction of profit have led to the appearance of fake reviews in order to mislead readers. Considering that the reviews are generally imperfect, the spam reviews detection becomes one of the most important problems. To tackle this problem, we propose a new method of multi-criteria fake reviews under belief function theory. This approach treats the uncertainty in the rating reviewers' given to multiple evaluation criteria, takes into account the similarity between all provided reviews and deals with missing data. We evaluate our method through artificial datasets. Then, we use a real dataset to validate it. The results prove that the proposed approach is a useful solution for the fake reviews detection problem.

Introduction

The Web 2.0 movement has increased the use of the online reviews which are posted on social media, opinion-sharing websites, blogs, forms and merchant websites. User generated reviews in which they express their opinions, attitudes, and feeling regards to their experiences with some products or services. Such opinions straightforwardly influence future customers purchase decisions and consequently the success of businesses. Companies and products with high rating reviews attracted more customers and can yield monetary gains. However negative reviews damage the companies' reputation and cause financial loss. Unfortunately, driven by the desire for profit, spammers have tried to cheat the online review system by creating deceptive reviews in order to mislead readers. The fake review is an unreal review because it does not reflect the opinion's real consumer. It can be positive to over qualify some products and to promote some services and brands, or negative to distort the perceived quality of the competitors' products and damage the companies' reputation.

Therefore, the fake reviews detection becomes an essential task in order to stop this online threat, to save companies reputation, to maintain a trustful environment between consumer and producer and to protect online reviews system. As a consequence, this non-trivial and challenging problem attracted significant researchers' attention. They proposed several detecting online fraud techniques which serve to spot the fake reviews from the genuine ones. These methods use various heuristics, such as duplicated reviews [START_REF] Jindal | Opinion spam and analysis[END_REF] or fake reviews detection from non-experts [START_REF] Ott | Finding deceptive opinion spam by any stretch of the imagination[END_REF] to generate a reference data. A large number of works tries to detect fake reviews relying on review text information as the style of writing [START_REF] Banerjee | Applauses in hotel reviews: Genuine or deceptive[END_REF][START_REF] Fusilier | Detection of opinion spam with character n-grams[END_REF]. Other methods have focused on the detection of group spammers cause of their power in the deviation of the products or services identification through their members whose can publish numerous fake reviews in a few minutes. A set of eight indicators has elucidated in [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF] that tries to catch the behavior of the group members such as time and rating deviation. Researchers establish some techniques to detect spammers. Most of these are networks reviews based approaches [START_REF] Akoglu | Opinion fraud detection in online reviews by network effects[END_REF][START_REF] Fayazbakhsh | Review spam detection: A network-based approach[END_REF] with tree types of nodes namely: review, reviewer and stores. Although the fake reviews detection is an uncertain problem, no one of these previous works is able to manage uncertainty in the reviews. However, we have proposed a preliminary related work dealing with the uncertainty but in only one overall criterion [START_REF] Ben Khalifa | Fake reviews detection under belief function framework[END_REF]. We think that the reviewer can better express his opinion through different evaluation criteria. Hence in this paper, we propose a new method, Multi-Criteria Belief Fake Reviews Detection (MC-BFRD), to handle uncertainty in the reviews' ratings given by each reviewer to several evaluation criteria using the belief function theory. Indeed, this theory is able to handle uncertainty and manage imperfections. It can manipulate various pieces of information from different reviewers and also allows to deal with partial and total ignorance. The rest of this paper is organized as follows: In Section 2, we present the fundamental concepts of the belief function theory. Then, in Section 3, we elucidated our proposed method (MC-BFRD). Experimentation evaluations are discussed in Section 4. Finally, we conclude in Section 5.

Belief Function Theory

The belief function theory was introduced by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] as a model to represent beliefs. It is considered as an efficient tool able to deal with uncertainty and to manage several types of imperfection. Various models have been proposed from this theory. One of the most used is the Transferable Belief Model (TBM) [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] that we adopt in our method.

Basic concepts

The frame of discernment Ω is a finite and exhaustive set of different events associated to a given problem. 2 Ω is the power set of Ω that contains all possible hypotheses and it is defined by: 2 Ω = {A : A ⊆ Ω}. A basic belief assignment (bba) or a belief mass defined as a function from 2 Ω to [0, 1] that represents the degree of belief given to an element A such that: A⊆Ω m Ω (A) = 1. A focal element A is a set of hypotheses with positive mass value m Ω (A) > 0.

Discounting operation

Discounting [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] allows us to weaken the masses by the discount rate α ∈ [0, 1] such that (1 -α) is the degree of confidence of the source. The bba is discounted as follows:

α m Ω (A) = (1 -α)m(A) ∀A ⊂ Ω, α m Ω (Ω) = α + (1 -α)m(Ω).
(1)

Combination Rules

Two bbas, m Ω 1 and m Ω 2 induced by two distinct and cognitively independent reliable sources of information can be combined by several rules of combination. Each rule has its specificities and its characteristics. Then, we will introduce some of the most used ones.

1. Conjunctive rule (CRC): It is introduced in [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF], denoted by ∩ and defined as:

m Ω 1 ∩ m Ω 2 (A) = B∩C=A m Ω 1 (B)m Ω 2 (C) (2)
2. Dempster's rule of combination: It is the normalized version of the conjunctive rule that denies the mass on the empty set [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. It is denoted by ⊕ and defined as:

m Ω 1 ⊕ m Ω 2 (A) = m Ω 1 ∩ m Ω 2 (A) 1-m Ω 1 ∩ m Ω 2 (∅) if A = ∅, ∀A ⊆ Ω, 0 otherwise. (3)
3. T he combination with adapted conf lict rule (CW AC): This combination [START_REF] Lefèvre | How to preserve the confict as an alarm in the combination of belief functions?[END_REF] is an adaptive weighting between the two previous combination rules acting like the conjunctive rule if bbas are opposite and as the Dempster rule otherwise. They use the notion of dissimilarity that is obtained through a distance measure, to ensure this adaptation between all sources. The CWAC is formulated as follows:

m Ω ↔ (A) = ( ↔ m Ω i )(A) = D max m Ω ∩ (A) + (1 -D max )m Ω ⊕ (A) (4)
where D max represents the maximal value of all the distances, it can be used to find out if at least one of the sources is opposite to the others and thus it may be defined by:

D max = max[d(m Ω i , m Ω j )], (5)
where

i ∈ [1, M ], j ∈ [1, M ],
M is the total number of mass functions and d(m Ω i , m Ω j ) is the distance measure proposed by Jousselme [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]:

d(m Ω 1 , m Ω 2 ) = 1 2 (m Ω 1 -m Ω 2 ) t D(m Ω 1 -m Ω 2 ), ( 6
)
where D is the Jaccard index defined by:

D(E, F ) = 1 if E = F = ∅, |E∩F | |E∪F | ∀E, F ∈ 2 Ω \∅ (7)

Vacuous extension

In some cases we need to combine two bbas m Ω1 1 and m Ω2 2 that have not the same frame of discernment. So, we use the vacuous extension of the belief function which extend the frames of discernment Ω 1 and Ω 2 , corresponding to the mass functions m Ω1

1 and m Ω2 2 , to a joint compatible frame of discernment Ω defined as follows:

Ω = Ω 1 × Ω 2 (8)
The extended mass function of any evidential value of the extended focal element B, denoted by Ω1↑Ω1×Ω2 , is defined as follows:

m Ω1↑Ω1×Ω2 1 (B) = m Ω 1 (A) if B = A × Ω 2 (9)
Where

A ⊆ Ω 1 , B ⊆ Ω 1 × Ω 2 .
It transforms each mass to the cylindrical extension B to Ω 1 × Ω 2 .

Decision Making

The Transferable Belief Model (TBM) proposed by [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF] is composed by two main levels: The credal level where evidence is defined by bbas and combined and the pignistic level where bbas are represented by probability functions called the pignistic probabilities denoted by BetP and defined as:

BetP (B) = A⊆Ω |A ∩ B| |A| m Ω (A) (1 -m Ω (∅)) ∀ B ∈ Ω ( 10
)
3 Multi-Criteria Belief Fake Reviews Detection (MC-BFRD)

Given a dataset of N reviewers and q evaluation criteria. We consider that each reviewer R i judges a product or a service by giving votes V ij , with values between 1 and 5 stars (respectively poor, below average, average, good and excellent), to each proposed criterion C j .

General case

In the general case of our MC-BFRD, we assume that each reviewer assigns votes to all the evaluation criteria without missing anyone. Our method follows four main steps will be established and will be explained in-depth.

Step 1: Modeling reviewer's opinion by mass functions As we adopt the belief function theory to model uncertainty in votes, each vote V ij corresponding to each criterion C j , with j in [1, q] the number of evaluation criterion, will be transformed into a mass function (i.e. bba) m Ωj ik with Ω j ={1, 2, 3, 4, 5} where one of the elements in Ω j represents the stars' number given by each reviewer R i . We propose to model this uncertainty by considering the vote, the vote-1 and the vote+1 for each given rating criterion review. In the upper extreme case, we only consider the vote and the vote-1 and in the lower one we model the vote and the vote+1. We transform each vote value V ij given by the reviewer R i corresponding to each criterion C j into bbas defined as follows:

m Ωj ik ({k}) = 1 where k ∈ {V i , V i+1 , V i-1 } -In the upper extreme case, k ∈ {V i , V i-1 }. -In the lower extreme case, k ∈ {V i , V i+1 }.
We propose to model the reliability degree of the reviewer R i on each criterion C j by (1 -α ij ) where α ij is its discounting factor. Its value is between [0, 1], if α ij = 0 the reviewer is totally reliable and if α ij = 1, it means that the reviewer is totally unreliable and it will not be taken into consideration. α ij is calculated as follows:

α ij = Number of votes different from the current vote of R i on C j Total votes' number for each criterion C j (11)
So, each vote V ij is weakened by its relative reliability degree (1 -α ij ) using the discounting operation (Eq.1). Thus, the reliability of the reviewer for each criterion will be taken into consideration.

In addition, we propose to take into account the distance between i th value of the given vote for the corresponding criterion C j denoted by V ij and the values that model it (vote, vote+1 and vote-1) noted k and represented by m Ωj ik . This distance is modeled by β ijk which will be considered as a weakening factor. Its value is between [0, 1], if β ijk = 0 then the model vote corresponds to the one provided and if β ijk = 1 it means that the vote model is very different from the one given. The discounting factor β ijk is calculated as follows:

β ijk =
|V ij -k| The maximum vote value [START_REF] Ott | Finding deceptive opinion spam by any stretch of the imagination[END_REF] As a result, each simple support function associated to each vote given to each criterion is weakened by its relative reliability degree (1 -β ijk ) using the discounting operation (Eq.1). Then, we aggregate the discounted bbas representing the provided vote using the Dempster rule (Eq.3) in order to represent each vote given to each criterion through one combined bba, m Ωj i with i = 1, . . . , N and j = 1, . . . , q. Moreover, in order to express the reviewer's opinion through one bba, we have to apply the following steps:

-We define Ω c as the global frame of discernment relative to all criteria. It represents the cross product of the different Ω j denoted by:

Ω c = Ω 1 × Ω 2 × . . . × Ω q (13)
-We extend the different bba s m Ωj i

to the global frame of all criteria Ω c to get different bba s m Ωj ↑Ωc i -We combine different extend bba s using the Dempster rule of combination.

m Ωc i = m Ω1↑Ωc i ⊕ m Ω2↑Ωc i ⊕ . . . ⊕ m Ωq↑Ωc i (14)
Finally, m Ωc i represents the reviewer's opinion given through the different votes criteria.

Step 2: Distance between the current reviewer's opinion and all the other opinions' aggregation

To evaluate the opinions provided by each reviewer R i through the different given criteria C j , we compared it to all other reviewers' opinions as follows: For each vote given to each criterion, we aggregate all the other reviewers' votes given to the same criterion represented by bbas using the CWAC combination rule (Eq.4) chosen, because it can manage the conflict in different votes. The result of this combination is one bba m Ωj ic , which represents the whole reviewers' votes for each criterion except the current one as follows:

m Ωj ic = m Ωj 1 ↔ m Ωj 2 ↔ . . . ↔ m Ωj i-1 ↔ m Ωj i+1 ↔ . . . ↔ m Ωj N .
As a result, for each reviewer we have q bba s m Ωj ic , we propose to aggregate them in order to represent all reviewers' opinions except the current one in one joint bba. So, we must firstly extend them to the global frame of criteria Ω c to get different bba s m Ωj ↑Ωc ic . Then, we combine different extend bba s using the Dempster rule of combination:

m Ωc ic = m Ω1↑Ωc i ⊕ m Ω2↑Ωc i ⊕ . . . ⊕ m Ωq↑Ωc i (15)
This bba represents the all reviewers' votes except the current one given to all the q different evaluation criteria. Then, for each reviewer we calculate the distance d(m Ωc i , m Ωc ic ) using the distance of Jousselme (Eq.6), in order to measure the similarity between each review's opinion and all others on all the different evaluation criteria.

Step 3: Construction of a new bba modeling the reviewer's opinion into fake or not fake The distance founded in the previous step represents the degree of compatibility between each reviewer opinion and all the other ones'. The closer they are, more the reviewer is reliable. So, we propose to transform the distance value into a new bba with Θ = {f, f } f = fake and f = not fake as the following equation:

       m Θ i ({f }) = γ * 1 1+e -a.ds+ a 2 m Θ i ({ f }) = γ * (1 - 1 1+e -a.ds+ a 2 ) m Θ i (Θ) = 1 -γ (16)
with ds = d(m Ω i , m Ω ic ), γ =
The standard deviation of all votes The maximum value of the standard deviation and a = 10 where a corresponds to the slope at the point of inflection. Taking the equation -ax + a/2 allows the inflection point to be x = 0.5.

Step 4: Decision Making

The decision process is assured by the pignistic probability BetP . We select the hypothesis with the greater value of BetP and we considered it as the final decision.

Missing values' case

In our MC-BFRD general case, we assume that reviewers give votes to all the evaluation criteria, but we can frequently find reviewers who vote some evaluation criteria and miss others. So, we propose to adapt our method in order to deal with the incomplete data. Therefore, we update the first step, which consists in modeling reviewer's opinion by mass functions, as follows:

In the case of incomplete data, we add the case of the vacuous vote, represented by a vacuous bba m Ω i (Ω) = 1. Furthermore, we continue with the same instructions of the first step. Moreover, the next steps will be exactly identical as those of the general case, namely distance between the current reviewer's opinion and all the other opinions' aggregation, construction of a new bba modeling the reviewer's opinion into fake or not fake and decision making.

MC-BFRD Experimentation

In the fake reviews detection, the evaluation is one of the most challenging problems considering the unavailability of the labeled dataset because it is not obvious to distinguish between the fake and the real reviews. Thus, researchers have used human evaluation in most previous work. However, human evaluation remains subjective since different evaluators often have different levels of tolerance. In this paper, we conducted experiments on four different artificial datasets then we propose to test our method behavior through one real dataset.

MC-BFRD evaluation

We propose to evaluate our method through the creation of four different artificial dataset that we labeled artificially by fake or not fake. Our labeling is based on the majority of votes' combinations given to the various proposed criteria.

Experimental protocol

Given four datasets in which reviewers judge an hotel by giving votes to three different criteria in order to express their opinion on four different hotels.

-The first dataset composed by 220 reviewers that votes hotel with 3 different criteria. The majority of the opinions are composed by 3, 4 and 5 stars that we labeled as not fake and the others as fake. -The second dataset contains 420 reviewers that express their opinion through three different criteria. We label the majority reviewers opinions' composed by 3, 4 and 5 stars as not fake and the rest as fake.

-The third dataset composed by 270 reviewers that give votes to some criteria to evaluate one hotel. The majority of the opinions are composed by 1 and 5 stars that we labeled as not fake and 2, 3 and 4 stars as fake. -The fourth dataset contains 265 reviewers that judge an hotel by voting three different criteria. This dataset provides incomplete data. We label the majority of reviewers opinions composed by 1 and 2 stars as not fake and the others as the fake ones.

Table 1 presents the description of the different datasets. The most used classification evaluation measures is accuracy. It is defined as follows:

Accuracy =

The number of well classified instances The total number of classified instances (17)

Experimental results

Table 2 presents for the average accuracies of the four executed datasets with the majority voting (MV) and our MC-BFRD. It demonstrates that our method gives a higher accuracy in all tested datasets that reach 92% with the third dataset while the majority vote method provides a modest accuracy where the best one was 57%. It proves that our method gives better results in comparison of those obtained with the majority vote with a large gap.

MC-BFRD behavior validation

In order to evaluate the performance of our MC-BFRD, we conduct a real database extracted from Tripadvisor. It consists of a 1550 reviewers who express opinion on "Melia Caribe Tropical hotel" by writing reviews, giving an overall and vote other criteria like rooms, location, cleanliness, business and services. Moreover, this dataset contains some missing values. In our MC-BFRD, we deal with the different evaluation criteria. Figure 1 details the obtained results with the Tripadvisor dataset in which our proposed method uncovers 703 fake reviews and 847 genuine ones.

Conclusion

In this paper, we tackle the fake reviews detection problem in an uncertain context using the belief function framework. We proposed to deal with uncertainty in the different given rating reviews to multiple evaluation criteria and and takes into consideration the compatibility with all other ones. In fact, our new method shows effectiveness in uncovering the fake reviews from the honest ones. Moreover, this approach be applied in several fields such as e-commerce and e-business and help different websites to detect fraudulent rating reviews. As future work, we will integrate some other notions like reviewers' trustiness and we will also take into consideration the different spam indicators.

Fig. 1 .

 1 Fig. 1. BetP results of Tripadvisor dataset

Table 1 .

 1 Dataset description

	Dataset Number of reviewers Labeled as fake	Labeled as not fake
	Dataset1 220 reviewers	20 reviewers' opinions 200 reviewers' opinions
	Dataset2 420 reviewers	70 reviewers' opinions 350 reviewers' opinions
	Dataset3 270 reviewers	20 reviewers' opinions 250 reviewers' opinions
	Dataset4 265 reviewers	25 reviewers' opinions 240 reviewers' opinions

Table 2 .

 2 Average accuracies (MV vs. MC-BFRD)

	Dataset MV accuracy MC-BFRD accuracy
	Dataset1 0.44	0.90
	Dataset2 0.50	0.80
	Dataset3 0.57	0.92
	Dataset4 0.40	0.79


Sabrine Mallek
email: sabrinemallek@yahoo.fr

Imen Boukhris
email: imen.boukhris@hotmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Evidential Multi-relational Link Prediction Based on Social Content

Keywords: link prediction, multiplex social networks, belief function theory, uncertainty, social content

A novel framework to address the link prediction problem in multiplex social networks is introduced. In this framework, uncertainty found in social data due to noise, missing information and observation errors is handled by the belief function theory. Despite the numerous published studies on link prediction, few research are concerned with social data imperfections issues which cause distortions in social networks structures and probably inaccurate results. In addition, most works focus on similarity scores based on network topology whereas social networks include rich content which may add semantic to the analysis and enhance results. To this end, we develop a link prediction method that combine network topology and social content to predict new links existence along with their types in multiplex social networks. Structural and social neighbors information are gathered and pooled using belief function theory combination rules. It is subsequently revised according to global information about the multiplex. Experiments performed on real world social data show that our approach works well and enhances the prediction accuracy.

Introduction

Recent years have witnessed the huge growth of the World Wide Web, enabling access to rich social content. Personalized recommendations [START_REF] Chen | A novel similarity index for better personalized recommendation[END_REF] are effective tools to alleviate the massive data. Recommendation in social networks [START_REF] Bao | Recommendations in location-based social networks: a survey[END_REF] comes to a vogue in fields such as network science and computer science (i.e., data mining and machine learning). In particular, potential connections recommendation is generally performed by evaluating similarities between social entities. Such task is handled by link prediction. Classical works use network topology to perform predictions, discarding valuable social content. Various social networks include information about the entities. For example, personal information such as age, gender and address, behavioral information like smoking and sporting activities and beliefs and opinions such as political preferences and favorite sports team. Obviously, considering such patterns adds semantic to prediction and allows personalized recommendations in multiplex social networks where nodes connect via multiple relationships types simultaneously.

Social networks structure highly depends on the accurate nature of data. Yet, such data are usually missing and incorporate erroneous labels due to noise and observation errors [START_REF] Adar | Managing uncertainty in social networks[END_REF][START_REF] Kossinets | Effects of missing data in social networks[END_REF]. This induces uncertainties regarding the network structure. As pointed out in [START_REF] Svenson | Social network analysis of uncertain networks[END_REF], one can encounter two kinds of uncertainty in social networks (i) whether a specific node is distinct or not (ii) or whether a link actually exists between two nodes. Furthermore, multiplex social networks are more affected with such uncertainties. According to [START_REF] Sharma | Missing data in multiplex networks: A preliminary study[END_REF], inaccuracies concerning multiplex social networks components are very common due to unreliable experimental settings and technical issues. To avoid data imperfections, one may discard some of the data risking the loss of useful information or use all uncertain data [START_REF] Kossinets | Effects of missing data in social networks[END_REF]. In both cases, this will inadequately affect the analysis.

To cope with uncertainty problems, we embrace 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]. Such theory enables us not only to present and manage data imperfections but it also allows tools to update, pool evidence and make decisions. We develop a fruitful link prediction framework that takes both topological features and social content in multiplex social network into account. Furthermore, our framework considers the worthwhile information given by relationships mixture and use it properly to study social linkage.

The rest of the paper is organized as follows. Section 2 gives some related works on link prediction. In section 3, belief function basic concepts are re-called. Section 4 details our proposals for evidential link prediction in multiplex social networks. Section 5 reports the experimental results and section 6 concludes the paper.

Link prediction Related Work

Let G(V, E) be a social network graph where V is the set of nodes and E is the set of edges. Link prediction is the problem of determining the potential existence of a link between unconnected nodes (u, v) given an observed state of the network. Many link prediction methods have been proposed that can be classified into three families: structural similarity based methods, supervised methods and latent models based methods.

Structural similarity approaches Generally, similarity based methods use two types of topological information: local information and global information. Local methods explore node neighborhoods where popular measures include Common Neighbors [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF], Adamic/Adar [START_REF] Adamic | Friends and neighbors on the web[END_REF], the Jaccard Coefficient [START_REF] Jaccard | Étude comparative de la distribution florale dans une portion des Alpes et du Jura[END_REF], Preferential Attachment [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF] and Resource Allocation [START_REF] Zhou | Predicting missing links via local information[END_REF]. For instance, the common neighbors method, denoted by CN , computes the number of common neighbors between (u, v). By contrast, global methods use structural topology of the global network. Well known scores include the shortest path, Katz score [START_REF] Katz | A new status index derived from sociometric analysis[END_REF] and SimRank [START_REF] Jeh | Simrank: A measure of structural-context similarity[END_REF]. Even though global methods give generally better results than local based methods [START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF], they have limited use. Actually, computing global score require information of the whole network which can be time consuming. Furthermore, global topological information is not always accessible. Above all, the additional complexity, by comparison with local methods, does not certainly pay off since the latter methods are very able to give great performance results. Meanwhile, other works use alternative information for link prediction. The authors in [START_REF] Yu | A new method for link prediction using various features in social networks[END_REF] combine network proximity to node attributes to predict links in weighted social networks by promoting associations between nodes with similar features. Yet, the approach only applies to weighted networks. In [START_REF] Hasan | Link prediction using supervised learning[END_REF], link prediction is performed using authors features to predict co-authorships. However, some attributes are not convenient to assess similarities between authors.

Supervised learning based approaches Link prediction can be reformulated into a binary classification problem where the objective is to predict the classes of query links. For the most part, topological scores are employed as predicator attributes and the existence of links represent class labels [START_REF] Hasan | Link prediction using supervised learning[END_REF][START_REF] Ahmed | An efficient algorithm for link prediction in temporal uncertain social networks[END_REF]. Some other works use other features, for example the authors in [START_REF] Aghabozorgi | A new similarity measure for link prediction based on local structures in social networks[END_REF] used network motifs as features for supervised learning link prediction. In [START_REF] De Sa | Supervised link prediction in weighted networks[END_REF], community information, connectivity, interaction and trust information are were used as features for supervised link prediction. In [START_REF] O'madadhain | Prediction and ranking algorithms for event-based network data[END_REF], co-participation in events over time are predicted using both network and entity features under supervised learning. Although, link prediction under supvised learning benefits from all the advantages of classification, some issues need to be handled such as the convenient classification model, the appropriate combination of features and class imbalance.

Latent models based approaches Such methods assume a particular organizing principles of the network structure, with some rules and parameters captured by maximizing the likelihood of the observed structure. Predicted links are determined on the basis of their probabilities computed according to these rules and parameters. Many methods combine matrix factorization and latent features to predict new links [START_REF] Menon | Link prediction via matrix factorization[END_REF]. Others use Markov Random Field [START_REF] Wang | Local probabilistic models for link prediction[END_REF][START_REF] Zalaghi | Link prediction in social networks using markov random field[END_REF], Bayesian nonparametric models [START_REF] Williamson | Nonparametric network models for link prediction[END_REF] or stochastic relational models [START_REF] Yu | Gaussian Process Models for Link Analysis and Transfer Learning[END_REF]. Yet, this family of methods suffer from high computational costs due to matrix decomposition, factor matrices and latent features learning which limits their application to large networks.

Challenges Obviously, using social content enhances link prediction as it adds semantic to the task. In online social networks, users information is generally undisclosed for legal, ethical or practical concerns. Furthermore, information about the social entities cannot be considered fully accurate i.e., when collecting social data from surveys, the asked people can lie to some questions, when gathering data from online social networks, users can put wrong and misleading information or even invent fake profiles. Link prediction algorithms are sensitive to such noisy and missing data especially in complex networks such as social networks [START_REF] Zhang | Measuring the robustness of link prediction algorithms under noisy environment[END_REF] and biological networks [START_REF] Ceci | Semi-supervised multi-view learning for gene network reconstruction[END_REF]. To handle such ambiguity, we take uncertainty into account in link prediction by embracing the belief function theory which provides effective tools to manage imperfect knowledge. We draw on local methods and consider social content of node attributes to enhance predictions and add semantic.

Actually, we tackled the link problem under the belief function theory framework in previous works. In [START_REF] Mallek | The link prediction problem under a belief function framework[END_REF] and [START_REF] Mallek | An evidential method for multi-relational link prediction in uncertain social networks[END_REF], two link prediction approaches are proposed based on network topology solely in uniplex and multiplex social networks. In [START_REF] Mallek | Evidential link prediction in uncertain social networks based on node attributes[END_REF], a link predicator is presented which handles uncertainty in social data and uses node attributes. Yet, the latter method operates only on uniplex social networks. It can obviously be applied to multiplex networks by considering links types' separately however relevant information concerning the multiplex will be neglected. This motivated us to develop a new link prediction framework for multiplex social networks that considers uncertainty and social content and takes into account worthwhile information of the multiplex structure.

Belief Function Theory Basic Concepts

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] has well-defined mathematical concepts managing uncertain knowledge. A problem is represented by a finite set of exhaustive and mutually exclusive events called the frame of discernment denoted by Θ. Evidence in the belief function theory is quantified through a mass function m : 2 Θ → [0, 1], called basic belief assignment (bba), which satisfies:

A⊆Θ m(A) = 1. (1)
Evidence induced from two reliable and distinct sources of information is pooled using the conjunctive rule of combination [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF] denoted by ∩ . It is applied as follows:

m 1 ∩ m 2 (A) = B,C⊆Θ:B∩C=A m 1 (B) • m 2 (C).
(

) 2
Sometimes one needs to combine two bba's m 1 and m 2 defined on two disjoint frames Θ and Ω. To do this, the vacuous extension is applied. First, the bba's are extended to the product space Θ×Ω = {(θ i , ω k ), ∀i ∈ {1, . . . , |Θ|}, ∀k ∈ {1, . . . , |Ω|}}. Then, the vacuous extension, denoted by ↑, is applied as follows:

m Θ↑Θ×Ω (C) =      m Θ (A) si C = A × Ω, A ⊆ Θ, C ⊆ Θ × Ω 0, otherwise (3)
When the source of information is not completely trustworthy, a discounting operation [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] can be applied to m using a discounting rate α ∈ [0, 1]. The discounting operator is defined as following where α m is the discounted bba:

α m(A) = (1 -α) • m(A), ∀A ⊂ Θ α m(Θ) = α + (1 -α) • m(Θ). (4)
On the other hand, in some cases, a bba m may be revised by reinforcing the evidence committed to an element A of the frame. The belief function theory offers a mechanism of reinforcement [START_REF] Mercier | [END_REF] which operates according to a reinforcement rate β ∈ [0, 1]. It is defined by:

β m(A) = (1 -β) • m(A) + β β m(B) = (1 -β) • m(B), ∀B ⊆ Θ and B = A. (5)
To specify the relation between two different frames of discernment Θ and Ω, the multi-valued mapping mechanism [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] is applied. It is function, denoted by τ , which assigns the subsets B ⊆ Ω that may correspond to a subset A ⊆ Θ as follows:

m τ (A) = τ (B)=A m(B). (6)
Decision in the belief function framework can be made according to the pignistic probability denoted by BetP . It is computed on the basis of the bba m as follows [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF]:

BetP (A) = B⊆Θ |A ∩ B| |B| m(B) (1 -m(∅)) , ∀A ∈ Θ. ( 7
)
4 Evidential link prediction in multiplex social networks

We introduce our proposals for evidential multi-relational link prediction using social contents. The novel method draws on local information approaches from literature. We consider a multiplex social network graph with uncertainties encapsulated at the links structure presented in Fig. 1 In the following, we present our framework to predict the existence of a link uv of type i in the detailed five steps below.

Step 1: Evaluating similarity

Our proposals are based on local information methods. To evaluate the likelihood of existence of uv i , we use social content of node attributes and structural information. The sets of neighbors τ (u) and τ (v) linked to u and v according to at least a link of type i are extracted. Then, we match the features of u to those of the nodes in τ (v), and those of v to τ (u). Consequently, both semantic and structural information are used by the predicator. Accordingly, the similarity between node 1 and node 2 is assessed as follows:

S node1,node2 = #matched attributes #total attributes (8)
According to assessed similarities, we detect the most similar node u ∈ τ (u) and v ∈ τ (v) to respectively v and u. This is motivated by the idea that social entities with similar connections are likely to connect. For instance, when the characteristics or behavior of a person is very similar to another one's friend i.e., same hometown, same college and same work, then they are more likely to be friends.

Step 2: Reliability evaluation

When the neighbors are not common neighbors or not completely similar, they are not considered fully trustworthy. Thus, their evidence is revised using a discounting operation. The bba's m uu i and m vv i are discounted respectively using α = 1 -S uv and α = 1 -S vu . For instance, for m uu i , discounting is computed as follows:

     α m uu i ({E uu }) = (1 -α ) • m uu i ({E uu }) α m uu i ({¬E uu }) = (1 -α ) • m uu i ({¬E uu }) α m uu i (Θ uu i ) = α + (1 -α ) • m uu i (Θ uu i ) (9)

Step 3: Information pooling

In order to pool evidence given by similar neighbors, we need to unify our referential, for that a vacuous extension (Equation 3) is performed on the product space PS = Θ uu × Θ vv . The obtained masses are fused using the conjunctive rule (Equation 2). We get the overall bba m PS ∩ as follows:

m PS ∩ = m uu i ↑PS ∩ m vv i ↑PS (10)
Next, the obtained bba's are transfered to the frame Θ uv i by applying a multi-valued mapping mechanism (Equation 6) according to the procedure presented in [START_REF] Mallek | An evidential method for multi-relational link prediction in uncertain social networks[END_REF].

Step 4: Evidence update

The next step is to take into account the multiplex structure. When u and v already have common neighbors, we evaluate the rate of common neighbors connected by the links of type i denotes by CN uvi according to the total number of common neighbors denotes by CN uv tot , we get:

δ uvi = |CN uv i | |CN uv tot | . Then, m uvi is discounted using β = 1 -δ uvi . We obtain β m uvi .
On the other hand, when u and v already connect via m link(s) (m ∈ [1, γ -1]) (γ is the number of link types), the rate S m+1 * i of simultaneous links of more than two types in the multiplex is computed, where * = {1, . . . , m} are the types of the shared links. If S m+1 * j = 0, the bba is reinforced on the element "exists" using φ = S m * j S m G as a reinforcement rate. Finally, we obtain the mass γ m uv i .

Step 5: Link selection

Decision about the link existence is made according to the score BetP uvi (E). Local information approaches from literature rank similarity scores according to a decreasing order and predict links with highest score values. In the same way, link selection is made by ranking query links according to pignistic probabilities on the element "exists" where the top k ones are predicted.

Complexity

Our link prediction framework is based on local information approaches as we only consider neighboring nodes for prediction. However, unlike these methods, our framework handles uncertainty found in social data. Link prediction methods based on local information are known to have the lowest computational complexity among existing methods from literature [START_REF] Yang | A new link prediction algorithm based on local links[END_REF] especially compared to global methods. Actually, local similarity scores are easy and simple to compute. As our method builds upon local methods, the theoretical complexity would be approximately the same. For the most part, it is based on the common neighbors method. The theoretical complexity of the latter is O(N.k 2 ) [START_REF] Gao | Link prediction methods and their accuracy for different social networks and network metrics[END_REF], where N denotes the number of nodes and k is the average degree of all nodes in the network. The additional computational costs for manipulating and pooling evidence are minor since we consider frames of discernment with only two elements. Indeed, the multiplex structure adds a layer of complexity as we count simultaneous links which costs O(N ). Thus, the overall theoretical complexity is O(N 2 .k 2 ).

Experimental study

To evaluate the performance of our novel framework, we perform tests on the relationships network collected from the social evolution dataset [START_REF] Madan | Sensing the health state of a community[END_REF]. It contains 21K links connecting 84 persons according to 5 link types. Data include information regarding the social entities collected through sociometric surveys such as political opinions, diet attitudes, favorite music genres or smoking behavior. Data are pre-processed to construct the evidential multiplex social network by simulating bba's according to the procedure presented in [START_REF] Mallek | Evidential link prediction based on group information[END_REF]. The technique is based on graph sampling and simulation methods popular in literature. We conduct a comparative study of our novel method, denoted by mLPNA, with three other link prediction in evidential social networks. The first method, denoted uLPLI, is an evidential link prediction approach based on local information for uniplex social networks [START_REF] Mallek | The link prediction problem under a belief function framework[END_REF]. It is inspired from the Common Neighbors method and uses solely structural properties. uLPLI is applied to each layer of the multiplex apart then overall performance is averaged over layers. The second method, denoted mLPLI, is the multiplex version of the uLPLI approach [START_REF] Mallek | An evidential method for multi-relational link prediction in uncertain social networks[END_REF]. The third baseline method is the uniplex version of our proposed approach [START_REF] Mallek | Evidential link prediction in uncertain social networks based on node attributes[END_REF], denoted by uLPNA. All methods apply to evidential networks. What we are mainly concerned about here, is to evaluate the contribution of considering social content of node attributes and handling multiplex structure in the prediction task. Precision and recall results are reported in Fig. 2. As illustrated in Fig. 2, we notice that mLPNA reaches the highest precision and recall results i.e., 86% precision and 64% recall. On the other hand, it outperforms its uniplex version i.e., 59% for uLPNA. mLPLI and uLPLI have lowest results which proves that considering node attributes information enhances performances. The same observation is made for recall results. That is, performance results in terms of both precision and recall are highest when social content and multiplex structure are considered in prediction.

The results are consistent with our assumptions. Social content combined to network topology add a semantic meaning to the link predicator. That is to say, the novel framework is more effective and accurate for predicting new links between social entities across layers. It improves the prediction quality. Furthermore, it is more suitable to multiplex social networks as it tackles social data uncertainty issues and handles such complex structure. The empirical results demonstrate that our approach has better predictive power than other methods that do not take social content and/or multiplex structure information into account. In addition to social content, our work opens up another dimension for addressing the link prediction problem.

Conclusion

In this paper, we have developed a framework to address the link prediction problem in multiplex social networks by combining topological properties and social content. Social data imperfections are handled thanks to the belief function theory. Similarities are assessed by matching nodes features where common neighbors are endorsed as trustworthy sources of information. Overall evidence is revised according to the global multiplex structure and potential links are predicted through a fusion procedures. The results of our framework confirm that semantic information based on nodes attributes promotes link prediction results and permits to understand relevant clues and better discern social entities linkage.

A straightforward direction for future work would be to study the case where there are missing attribute values which may be due to hidden profile information or to noise generated from anonymization. Therefore, we get uncertain node attributes and links structures in the network.

Fig. 2 .

 2 Fig. 2. Precision and recall results measured on the Relationships network

  . A multiplex social network is given by a graph G(V, E 1 , . . . , E n ) where V = {v 1 , . . . , v |V | } is the set of nodes, and E 1 , . . . , E n are the sets of links where n is the number of connection types. Each link uv ∈ E i has assigned a bba defined on the frame of discernmentΘ uv i = {E uv , ¬E uv } denoted by m uv i .The elements E uv and ¬E uv mean respectively that uv exists or is absent. The mass function m uv i represents the degree of evidence about the existence of a link of type i between (u, v).

	Mary	Bob
	Carli	Joe
	Amy	Peter
	Fig. 1. Evidential multiplex social network


Dr Sanna Arpiainen
email: sanna.arpiainen@vtt.fi

Dr Kevin Vynck

James Dekker

Dr Markku Kapulainen

Dr Worawut Khunsin

Dr Timo Aalto

Mikael Mulot

Dr Gudrun Kocher-Oberlehrer

Rudolf Zentel

Clivia M Sotomayor Torres

David Cassagne

Dr Jouni Ahopelto

Prof J Ahopelto

Prof D Cassagne

Prof C Sotomayor-Torres

Prof C Sotomayor-Torres

Prof R Zentel

Self-Assembled Three-Dimensional Inverted Photonic Crystals on a Photonic Chip

Keywords: integration, inverted opals, photonic band gap, photonic crystals, waveguides

Three dimensional photonic crystals (PhCs) exhibiting a full photonic band gap have high potential in optical signal processing and detector applications. However, the challenges in the integration of the 3D PhCs into photonic circuits have so far hindered their exploitation in real devices. This paper demonstrates the fabrication of 3D PhCs exploiting the capillary directed self-assembly (CDSA) of monodisperse colloidal silica spheres, their inversion to silicon shells, and integration with silicon waveguides. The measured transmission characteristics agree with numerical predictions and provide strong indication of a full photonic band gap in the inverted 3D photonic crystals at wavelengths close to 1.55 µm.

Introduction

Photonic crystals have experienced numerous developments and outcomes since their advent in the late 80's. [1,2] The early works focused on 3-dimensional (3D) photonic crystals that promise a full control over the light emission and propagation in space due to complete photonic band gap [3][4][5][6][7][8][9][10][11][12][13][14][15][16] . 3D photonic crystals can provide a route to the realization of very compact photonic devices. The photonic functions typically require embedded single or line defects to control, bend or localize the electromagnetic field inside the crystal. Recently, however, the main emphasis has been on 2-dimensional photonic crystals due to easier fabrication and straightforward integration with planar waveguides, [17][18][19] though modelling, fabrication and properties of 3-dimensional photonic crystals have also been reported in many papers. [20][21][22][23][24][25][26][27] 3D photonic crystals can be realized in various ways, including mechanical stacking of rodlike structures, [3] lithographic and holographic 3D patterning, [4] focused ion beam (FIB) carving and multidirectional plasma etching. [20][21] For practical photonic circuit applications the challenges are in the scalability to production volumes and, in particular, in the integration with other photonic components.

The approach that is probably the most suitable to large-scale low-cost fabrication of photonic structures is that based on self-assembly of sub-micrometer-sized particles into artificial opals, their subsequent inversion [5,6] and the inclusion of well-defined photonic defects. [5,[7][8][9][22][23] These opals are typically produced by colloidal self-assembly based on gravitational, [10] electrophoretic [11] or vertical sedimentation. [12] Site-selective colloidal self-assembly by micromoulding in capillaries [13] or capillary directed self-assembly (CDSA) [24] combine bottom-up and top-down techniques and have high prospect for controlled large scale fabrication of opals on wafers and their integration into photonic circuits.

Inverted opals can exhibit a full photonic band gap, enabling the design of high-Q optical nanocavities, and slow-light propagation, thereby enhancing the light-matter interaction which is beneficial to many processes, e.g., photo-oxidation [28] and photoisomerization. [29] The combination of microfluidic channels and inverted photonic crystals with optical access to monitor the evolution of the biological process will have interesting applications in bionanotechnology. The frequency and direction-dependent transmission enables efficient separation of the emitted signal from the exciting mode when characterizing photoemissive processes. [30] In integrated optics the tolerances with respect to lattice order and alignment and to surface quality of the defect lines or defect cavities, combined with the large scale production requirements, are still beyond the reach of the currently available technologies.

Utilizing the PhCs as elements in an integrated photonic circuit requires connecting the PhCs to optical waveguides. This major and crucial step has not been achieved so far. In this report we demonstrate integration of inverted 3D opals with silicon ridge waveguides to realise photonic chips. In the fabrication we have used CDSA [24] to build 3D PhCs in predetermined locations on silicon substrate, connected with waveguides to couple light in and out.

Sample Fabrication

The process flow for the fabrication of the photonic chips with inverted fcc photonic crystals is shown in Figure 1. The structures were patterned on 10 µm thick silicon on insulator (SOI) film by UV lithography and subsequent plasma etching to include both the ridge waveguides and the capillary channels for the directed self-assembly. The waveguides were either defined as 9 µm wide ridges with their surroundings etched 4.5 µm deeper into the SOI film or as 10 µm wide rectangular ribs defined by etching through the SOI film as shown in Figure 2.

The waveguide cores were covered by a 200-250 nm thick SiO2 optical cladding and a 20 nm thick alumina (Al2O3) film. Al2O3 is required to protect the chip during the removal of the silica spheres in the inversion process. Al2O3 can be grown conformally with atomic layer deposition (ALD) and it has extremely high selectivity to silicon, 1:80000, in SF6 based plasma which allows for the efficient removal of excess silicon deposited during the inversion.

Most importantly, after annealing at 900 ºC for 30 minutes the Al2O3 film becomes chemically resistant to certain hydrofluoric acid (HF) based chemistries that can be used in silica sphere removal. Figure 1. Schematic process flow for the fabrication of inverted photonic crystals on a photonic chip. The SOI wafer (a) is first thermally oxidized (b) and the oxide is patterned to form the hard mask for SOI etch. After patterning a soft polymer mask (d), the deep structures are etched half-way with the first ICP etch (e), the polymer mask is removed with oxygen plasma (f) and the final topography is defined with the second ICP etch (g). The waveguides are thermally oxidized and protected with ALD Al2O3 layer, the opals are formed into the cavities with capillary directed self-assembly (h) and a conformal thin silicon film is deposited on all surfaces (i). The top silicon layer is then removed with plasma etch (j) and the silica spheres are removed with HF based wet etch (k).

Artificial opals were deposited from 2-5 vol. % aqueous dispersion of monodisperse colloidal silica spheres with a diameter of 890 nm synthetized by Unger's method. [27,32] A droplet of suspension, 0.2-0.8 µL in volume, was dispensed into a reservoir defined on the substrate, and readily directed via capillary channels into the opal basins. The agglomeration of the spheres into the basins and their simultaneous self-assembly into face centered cubic (fcc) lattice were driven by solvent evaporation. The opal deposition was performed in a process chamber with 93 % relative humidity and at 30 ºC temperature. Prior to the opal deposition the substrates were chemically hydrophilized in NH4OH:H2O:H2O2 solution , and an about 40 hour settling time was required to reduce the Al2O3 hydrophilicity (amount of surface OH groups) to optimal level for CDSA. Opal deposition on highly hydrophilic Al2O3 substrate immediately after the chemical treatment led to uncontrolled spreading of the suspension over the surface, whereas in slightly too hydrophilic substrates the suspension occasionally escaped from the capillary channels and opal basins as shown in Figure 2c. After drying the opal, 100-130 nm thick silicon film was conformally deposited on the structure by low pressure chemical vapour deposition (LPCVD) from silane [5] at 560 °C. During this process the silica sphere diameter reduced to 860 nm as defined from SEM images. The inversion was completed by removal of the silica opal template in a HF based silica wet etch, a dilute mixture of CH3COOH and NH4F, that is able to etch SiO2 selectively against annealed Al2O3. Amorphous silicon grown by LPCVD has a high concentration of dangling bonds leading to considerable absorption at near-infrared. Annealing at 600 ºC transforms the material into polycrystalline phase which is transparent at wavelengths above the fundamental absorption gap of silicon at 1.15 µm. Annealing of LPCVD amorphous silicon at 600 °C has been found to reduce the near-IR attenuation in thin slab waveguides from 42±2 dB/cm to 25±3 dB/cm and additional long heat treatment at 1100 °C and subsequent chemical mechanical polishing (CMP) to further reduce the attenuation down to 10±2 dB/cm [32] . However, in the case of 3D photonic crystals, the surface roughness introduced by the crystallite formation during the high temperature annealing cannot be removed by CMP and crystallization also increases strain that may relax via formation of cracks inside the PhC.

Modeling and simulations

The behaviour of incident light at the waveguide -PhC interface was simulated by the 3D finite-differential time-domain (FDTD) method using the freely available software package MEEP [START_REF] Oskooi | [END_REF] . The band structure of the inverted opals was calculated with the MIT Photonics- f. e.

Bands [34] that computes the fully-vectorial eigenmodes of Maxwell's equations with periodic boundary conditions in a planewave basis.

The FDTD simulations were performed for a 4-5 µm long PhC interposed by waveguides with height and width of 3 µm. The 3D PhC was defined as a face centered cubic (fcc) lattice of air spheres with diameter d, embedded in a silicon background as shown in Figure 3. The normalized frequency a/ is related to the lattice dimensions as a = d . For simplicity, the spheres were cut at the side interfaces, otherwise maintaining the fcc arrangement. In addition, the air necks between the spherical voids and the finite silicon shell thickness around them were not included into the model. The silicon fill factor results in significant changes in the spectral width and position of the photonic band gap, yet the purpose of FDTD simulations here is to get insight into the origin of the spectral features observed experimentally rather than making a quantitative comparison. The fcc lattice was oriented according to the experimental arrangement, with (111) plane at the surface and (110) planes perpendicular to the waveguide end facets. The direction of the mode propagation is thus parallel to both of these high symmetry planes. The planes perpendicular to the mode propagation (parallel to the waveguide end facets) define a reciprocal lattice point M located in the mid-point of the line combining the L and the U high symmetry points. Silicon was treated as dielectric with frequency independent refractive index (n = 3.45), which is adequate at near infrared wavelengths above the optical absorption gap tail at 1.15 µm. The simulated field intensity distribution illustrates the behavior of a continuous wave reaching the interface between the waveguide and PhC at a wavelength in the middle of the photonic band. The light is clearly stopped by the inverse opal, but the decrease in transmission is not complete as the light reflected by the inverted opal is partially coupled into the silicon walls and substrate where it propagates and reaches the output ridge waveguide, as can be seen in Figures 3a and3b. The simulated transmission and reflection spectra are directly related to the photonic band structure [34] of the inverted opal as illustrated in Figure 3c.

In the FDTD simulation, the full photonic band gap (PBG) of the inverse opal is observed as a clear dip in transmission, accompanied by a smaller decrease in the range of the pseudo gap in M direction.

Optical and structural characterization

The fabricated inverted photonic crystals were analysed by scanning electron microscopy as shown in Figures 2d-f. The band structure of the experimental inverted opals in Figure 4a was defined according to the dimensions measured from the SEM images, the silicon shell being 100 nm and the holes between the spheres roughly 60 nm. The location of these holes in between the PhC and the silicon handle wafer were excluded by normalising each amplitude with the average reflection amplitude. As shown in the Figure 4, at the photon energies in range of full photonic band gap (a/ = 0.8-0.87 or 1.4-1.53 µm) there is a drastic decrease in the amplitude, extending over the adjacent pseudo gaps between the 11 th and 12 th bands and 5 th and 6 th bands, thus covering the range from 1.3 to 1.65 µm. The amplitude is also strongly reduced near the position of the first order pseudo gap (a/ = 0.43-0.54, 2.2-2.9 µm) in the L direction. The transmission through the waveguide -PhCwaveguide structure shown in Figure 5 was measured by end coupling the incident light from a single mode optical fiber into the waveguide. White light supercontinuum laser was used as the light source, as it offers a wide spectral range from 600 to 1800 nm with high intensity that is optimal for probing the band structure of embedded PhCs.

The transmission spectra in Figure 5 show the silicon absorption below 1.15 µm and a 5 dBm reduction in the transmitted intensity from 1.4 to 1.53 µm, corresponding to the spectral position of the full photonic band gap at reduced frequencies of a/0.8-0.87, similar to the simulated fully infiltrated PhC in Figure 3. In the partially filled PhC the full band gap is wider than in the simulated structure and thus the effect of the pseudo gap in the direction of mode propagation (M) overlap the band gap. The reduction in the transmitted intensity, assumed to correspond the M pseudo gap in the simulated structure, can however be seen also in the measured spectrum, with spectral range of 1.3 µm to 1.65 µm exactly corresponding to the three pseudo gaps in the L direction.

Discussion

Even though the wider region in the FDTD simulation also corresponds to the pseudo gap in L direction, the origin of these spectral features is probably different. In the simulation the lattice is perfect, and the reduction is mainly due to reflection which is close to unity across the whole range of interest. In the real structure, scattering from defects and surface roughness is likely to play an important role, smearing out the narrow pseudogaps and enabling light to couple and propagate along allowed directions (e.g. U or W), thereby reducing the actual amount of light that is transmitted through the PhC. Furthermore, it is known that small imperfections on periodic PhCs can lead to light localization phenomena, [2,35] which would result in a drastic reduction of the light transmission. Investigating the effect of disorder on light propagation in our integrated inverted opals is clearly beyond the scope of this work but it should be addressed carefully in the future.

Conclusion

To conclude, we have reported the first realization of 3D PhC fabricated by self-assembly, coupled to ridge waveguides in a photonic circuit. Simultaneous measurement of the band gap from L and M directions and comparison with numerical simulations verifies both the fcc order of the lattice and the existence of the band gap in the integrated 3D PhC near the operating telecommunication wavelength (1.55 µm). While this work constitutes an important step towards the use of 3D inverse opal PhCs in integrated optics, it also emphasizes issues that need to be addressed in future works, namely the light coupling to the substrate and surrounding structures such as the walls of the PhC basin, as well as the structural imperfections, which result in losses in the transmission and reflection.

Experimental Section

Photonic chip fabrication and opal deposition: Bonded silicon on insulator (SOI) wafers with a 10 µm thick (100) SOI film (5 -cm) on a 1 µm thick buried oxide (BOX) were patterned into a photonic chip as described elsewhere. [24] A 200-250 nm thick SiO2 film was grown by dry oxidation at 900 ºC and covered with a 20 nm Al2O3 film by ALD from trimethylaluminium (TMA) and water at 300 ºC and annealed at 900 ºC for 30 minutes. The wafers were covered with protective resist (AZ5214e), diced and the chip edges were polished with a diamond paste. After resist removal, Al2O3 was hydrophilized in NH4OH:H2O:H2O2 1:5:1 at 65 ºC for 5-10 minutes and rinsed in de-ionized water. After 40 hours settling in air, a 0.2-0.8 µl droplet of 2-5 vol. % aqueous dispersion of 890 nm silica spheres was dispensed into a reservoir on the substrate. The suspension was directed via capillary channels into opal basins in a process chamber with 93 % relative humidity of the solvent (water) and 30 ºC temperature.

Inversion: 100-130 nm of amorphous silicon was deposited by SiH4 decomposition at 560 ºC.

The silica spheres were removed in CH3COOH:NH4F(40%):H2O 1:1:1 solution, after which the hazardous etch residues were rinsed in de-ionized water for 40 minutes. Silicon was crystallized by annealing in nitrogen ambient at 600 ºC for 2-16 hours and some of the samples further at 900 ºC for 2 hours.

Figure 2 .

 2 Figure 2. Scanning electron micrographs showing the cross sections of a) the rib and b) the strip waveguides. c) Top view of the integrated opal before inversion. The small overflow of silica spheres illustrates the importance of careful control of the surface properties and is due to too high level of hydrophilicity of the Al2O3 surface during the opal self-assembly. d,e) Top views of the silicon inverted opals show the fcc arrangement. The partial destruction of the topmost silicon shells results from the removal of the thick silicon grass, still visible in the cross section image f) of a typical inverted opal.

Figure 3 .

 3 Figure 3. 3 FDTD and band structure simulations with a fully filled silicon inverse opal. a) Top view and b) side view of a continuous TE-polarized wave traveling via a 3 µm by 3 µm strip waveguide through a 5 µm wide hexagonal well containing the PhC. The photon energy in the simulation corresponds to the mid band gap energy. c) Calculated band structure and simulated transmitted and reflected spectra for the corresponding structure. The full band gap at 0.78 < a/ < 0.82 induces high reflection and corresponding reduction in the transmitted intensity. The effect of the pseudo gap in M direction at 0.76 < a/ < 0.84 is similar, but not as strong.

Figure 4 .

 4 Figure 4. Optical analysis of the inverted 3D PhC interposing ridge waveguides. a) Simulated band structure of inverted fcc crystal constructed from thin silicon shells as in the experiment. b) Normalized Fabry-Perot amplitude of the reflected IR light as measured from top of the PhC in L direction. The pale blue regions indicate pseudo gap position in L direction and the violet region indicates the full photonic band.

Figure

  Figure 2e also clearly indicates the fcc arrangement instead of the less favourable hcp.

Figure 5 .

 5 Figure 5. Transmission spectra measured through the waveguides coupled to the photonic crystal. The measurement was carried out with two different spectral analyzers to determine which spectral features are due to the non-linear dynamic response of the analyser and which are due to the sample. Pale blue colours indicate the pseudo gaps in M direction and violet corresponds to the full photonic band gap defined at W point as presented in Figure 4.

Acknowledgements

The work was supported by EU project PHAT and Academy of Finland Center of Excellence in ALD.

((will be filled in by the editorial staff)) Revised: ((will be filled in by the editorial staff))

Measurements: Reflected spectrum from the top of the PhC was measured with Bruker FTIR spectrometer equipped with a microscope using 15X lens with NA=0.4, working distance 25 mm and acceptance (half angle) 15 degrees.

The intense broad spectrum used in transmission measurements (via waveguides) was based on photonic crystal supercontinuum, generated by coupling the 1064 nm output radiation from a miniature Q-switched Nd-YAG laser into a highly non-linear photonic crystal fiber. The result is a broadband spectrum extending from 600 to 1800 nm with an approximately -15 dBm/nm output power. The supercontinuum light was coupled into a single mode photonic fiber, which was aligned with the ridge waveguide. Light coupling into the waveguide was monitored by detecting the mode profile at the waveguide output with a CCD IR camera and scattering from the vicinity of the PhC. The transmission spectra was found to depend strongly on the input fiber alignment since the waveguides were not truly single mode, but able to support a multitude of modes with only one properly confined into the ridge waveguide core. However, when properly aligned, the shape of the output signal was elliptical, with FWHM width of 7 µm and height 5 µm, respectively. The measurement configuration was complemented with a multimode optical fiber coupled to the waveguide end, and the transmitted intensity was recorded with optical spectrum analysers (OSAs).

Because the difference between the transmitted intensity and the reference was larger than the dynamic range of the OSAs, two different analysers, HP 86140A and Anritsu MS9710B, with different intensity distortion were used to confirm the main features of the spectra.

Scalable fabrication process of integrated 3D photonic crystals, based on a directed selfassembly of colloidal opals, is demonstrated. The propagation and loss characteristics of the photonic crystal, as probed both via the integrated waveguides and perpendicular to the top surface, agree with the FDTD simulation and indicate the existence of a full photonic band gap at around 1.55 µm.

Keywords integration; inverted opals; photonic band gap; photonic crystals; waveguides