Mohamed Kallel
email: kallel_mohamed2004@yahoo.fr

Mohamed Salim Bouhlel
email: medsalim.bouhlel@enis.rnu.tn

Jean-Christophe Lapayre
email: jean-christophe.lapayre@univ-fcomte.fr

SECURITY OF THE MEDICAL MEDIA USING AN HYBRID AND MULTIPLE WATERMARK TECHNIQUE

Keywords: Multiple watermark, hybrid watermark, spatial field, frequency field, security, integrity, trace

This paper proposes a new approach of multiple and hybrid watermark using two linked fields of insertion. This approach associates two different series of marks: one is sturdy guaranteeing the supervision of diffused media though the network and testifying to the identity of the owner of the medical image; the other series of marks, which is frail, insuring the integrity, the trace and the archives of medical diagnoses. In fact, this approach allows to benefit from the advantages of different insertion spaces (spatial and frequency field) and kind of two different fields of watermark. In the spatial field, the diagnosis of the doctor (frail marks) is inserted guaranteeing its records and its trace. In the frequency, the sturdy mark is inserted allowing to ensure the automatic control of the media through the network and testifying to the proprietor of the medical image.

Introduction

The rapid expansion of the internet and the development of digital technologies have increased the accessibility of digital media. For this reason, the image authentication becomes very important. Therefore, the security techniques are required where verification of integrity [START_REF] Fourati | Medical Image semi fragile Watermarking In The Frequential Field[END_REF]] and guaranteeing record and trace of each intervenient. The use of the watermark technique in medical field has many benefits. In fact, the watermark technique can be used to guarantee the trace of the doctor's diagnoses. Then, it follows the evolutionary state of the patient and it forms a whole report of the patient. Hybrid and multiple watermark technique provides a possible solution to the above problem. In fact, in this sheet of paper, we are going to conceive a new approach of multiple and hybrid watermark using two linked fields of insertion. In section 1, we are going to explain the choice of the two insertions field. In the next section, we are going to give the positive effect of our approach and we are going to explain the insertion phase and the extraction phase. Then we are going to provide an optimism technique to increase the sturdiness of our approach. Finally, we will present experimental results in section 4. Conclusions are drawn in section 5.

The choice of frequency/spatial field

This approach associates two different series of marks: one is sturdy guaranteeing the supervision of diffused media though the network and testifying to the identity of the owner of the medical image; the other series of marks, which is frail, insuring the integrity, the trace and the archives of medical diagnoses. The spatial field provides an important capacity of insertion [START_REF] Stankovié | Watermarking in the Space/Spatial-Frequency Domain Using Two-Dimensional Radon-Wigner Distribution[END_REF]] and arranges a higher image quality than other insertion field [START_REF] Kallel | A multiple Watermarking Scheme for Medical Image in the Spatial Domain[END_REF]]. In fact this author used in this work a spatial field to ensure the imperceptibility of the mark and to guarantee the information integrity. For this reason, we have chosen the spatial field and we are going to be limited to only four combinations which are the following: frequency/spatial, spatial/frequency, spatial/wavelet, wavelet/spatial. It is noted that the combination spatial/wavelet, wavelet/spatial are to be eliminated because the issued space of waved decomposition is considered as a spatial field [START_REF] Trichili | A new medical image watermarking scheme for a better telediagnosis[END_REF]]. In fact, this author has proved that the spatial field and the wavelet field was considered the same because the tow field can specify the place of the pixel in the image (spatial localization). Thus, the spaces are limited only to two combinations. As our multiple watermark application is vulnerable to any eventual transformation (frail watermark). So, we are going to apply it in the second insertion field. As a consequence, we are going to study the hybrid watermark in the frequency/spatial field.

The positive effect of our approach

Just as for every watermark method, our approach is formed of insertion and extraction phase which we are going to explain in detail for every insertion field. On the one hand, in the medical field, the information is authentic and very important and we must ensure a secure transfer of this file. For this reason, we have judged that it is imperative to use the spatial field for the application of our approach guaranteeing in this way, high image quality, enough insertion capacity in order to introduce the diagnoses of different doctors and integrity of the inserted mark in view of the fact that the LSB plan insertion offers a certificate of authenticity during the extraction phase [START_REF] Giakoumaki | A medical image watermarking scheme based on wavelet transform[END_REF]]. On the other hand, it will be important to use the frequency field for the sturdy mark insertion allowing to ensure the automatic control of diffused media through the network and testifying to the proprietor of the medical image. The presence of this sturdy mark prevents any attempt of pirate taking advantage then of this insertion field.

The insertion phase

The insertion phase in the frequency field

In this phase, we have set for objective the duality between sturdiness in comparison to different attacks and the imperceptibility of the mark.

Choice of porters coefficients of the mark

The insertion procedure in the DCT (Discrete Coefficient Transform) field is too delicate because a little modification of low frequencies may cause a strong degradation of the quality of the image. As a result, the insertion in high frequencies may proved to be inefficient since a lesser attack which the image may undergo, can also change the inserted mark. That's why; it is very interesting to choose a tape of average frequencies insuring a good compromise between high resistance towards different attacks and a low degradation of the image quality. Consequently, we have chosen the average frequencies for the insertion of our mark.

Insertion diagram

In the frequency domain, the amount of asked calculation, which performs a transformation on a whole image, is important. That's why; we divide our image with size 256x256 pixels in 1024 blocks with size 8x8 pixels; and every block will be tattooed [START_REF] Emek | A Cascade DWT-DCT Based Digital Watermarking Scheme[END_REF]]. We apply for every block the DCT; every bit of the chosen mark will be inserted in a coefficient belonging to the tape of average frequencies under a substitutive way according to the following insertion formula: The parameter α is used to clarify the degree of perceptibility of the mark. It will be used as a factor of compromise between a good imperceptibility and an efficient sturdiness. We have chosen to insert the binary acronym of the European project TeNeCi (Tele-Neurology Cooperative) with size of 32x32 bits as shown in figure 1. The inverse DCT is eventually applied following the insertion of mark in order to rebuild the watermarked image.

The insertion phase in the spatial field

The insertion phase in the spatial field consists of converting the original image into a binary code. Then, the carried out diagnosis via the doctor is converted into ASCII code next in a binary code in order to insert in the zone to which it was permitted in the coded original image with the help of a reserved key [START_REF] Kallel | A multiple Watermarking Scheme for Medical Image in the Spatial Domain[END_REF]]. This procedure is repeated successively for every concerned doctor so as to achieve a multiple watermark technique [START_REF] Osborne | Multiple embedding using robust watermarks for wireless medical images". 3thd international conference on mobile and ubiquitous multimedia[END_REF]].

The extraction phase

The extraction phase in the frequency field

This phase allows to check whether the inserted mark during the insertion phase is present or not in a watermarked image. In our diagram, we have insured this checking without having resort to the original image, only the inserted mark is necessary. The extraction diagram which we have developed focuses on a successive inverse operations than those adopted during the insertion phase. So, we are going to cut up the image into 1024 blocks with 8x8 pixels. To every block, we apply the DCT and we separate the porter coefficient of the mark. Following the extraction of the mark, we move to the identification step which aims at proving the source of the image and guarantee its characteristics. For this reason, we have created a bank of 999 marks which are generated randomly to which we add our original mark. Next, we calculate the correlation between the extracted mark and the thousand of marks of the bank. As to confirm that the detection of the mark is efficient, it is compulsory that the maximum correlation suits to the inserted mark. This correlation is defined as the following:

Cor = <A,B> =       -       - - - ∑∑ ∑∑ ∑∑ m n mn m n mn m n mn mn B B A A B B A A ² ) ( ² ) ( ) ( ) ( (2)
A and B are respectively the inserted mark and the extracted one.

With: A the average of the coefficient of the A matrix.

B the average of the coefficient of the B matrix.

Extraction phase in the spatial field

In this extraction phase of the spatial field, we perform the conversion into a binary code of the watermarked image in order to have a binary image composed of 8 plans. Then, we extract the mark and we transform it to ASCII code. Next into a character chain so as to have eventually the carried out diagnosis on be half of the correspondent doctor(s).

Optimism

For our approach of watermark, the first inserted mark must be indeed sturdy as well since, this concealed mark in the medium, is the guarantor of the identity of its right. Once it erased, transformed or substituted, the image is no longer protected and its owner do not possess any proof of copyright as well. Besides, the user of this image is not certain on behalf of its servant. So we have judged important to increase the sturdiness of our approach; we have had then the idea of inserting every bit of the mark many times in the coefficient of every block of the modified image (in the average frequencies of the frequency field). This redundancy has offered us more chance of finding the inserted mark during the extraction phase. In every block, we are going to insert one bit of the binary mark with its size 32x32 bits with a redundant manner. In fact, the same bit will be inserted 3 times in 3 different coefficients of tape of average frequencies for every block of the transformed image. This redundancy has offered us during the extraction phase more chance in order to find the exact value of the inserted bit guaranteeing then a well-sturdiness of the develop approach. Therefore, we have inserted an important amount of information, which lifts the major constraint in the domain of image watermark which is the compromise between the sturdiness of the system and the quality of the watermarked image. In fact, when we insert the information with a redundant matter, the system becomes sturdier but in counterpart, it damages more the medical image. In addition, we are going to measure the correlation within and without the suggested optimization and this in order to quantify the fidelity of the extracted image contrary to the inserted mark. The figure 2 presents the variation of the correlation for the different tested images.

Fig. 2. The correlation variation

According to the above figure, we notice that the variation of the correlation for the optimistic approach presents high value in comparison to classical elaborate approach. This is done, in fact, to the redundant insertion of the same mark in the image increasing then the possibility to get back it during the extraction phase. The figure 3 presents the variation of PSNR before and after the optimization and this is so to measure the degradation which was undergone by the image following the insertion of the mark [START_REF] Fourati | Medical Image semi fragile Watermarking In The Frequential Field[END_REF]].

Fig. 3. PSNR variation

We note, according to this figure, that the optimistic approach presents a lower PSNR variation than the classical one. But, it always keeps satisfactory values as they are superior to 30 dB [START_REF] Puech | A New Crypto-Watermarking Method for Medical Images Safe Transfer[END_REF]]. To sum-up, we can notice that for the optimistic approach, the correlation increases whereas the PSNR decreases. This is expected as the increasing of the amount of the inserted information leads to the quality of the original image less better and more accentuated correlation.

Results

We apply this technique to 30 different medical images with the size of 256x256 pixels and 8 bit/pixels resolution in order to evaluate the watermark image, to check the sturdiness of the first inserted mark in the frequency domain and the sensibility of the second insertion mark in the spatial field in comparison to different attacks and more precisely the capability of the approach of guaranteeing the trace and the records of the inserted diagnoses.

The quality of the watermarked image

The imperceptibility of the inserted mark is primordial mainly for the medical images as the least modification of the medical image may lead to inappropriate diagnoses. Figure 4 shows the imperceptibility of the image following the insertion in the two fields. According to the figure 4, we can notice that following the insertion in the frequency field, the watermarked image presents a PSNR of 42,87 dB; which proves the imperceptibility of the first series marks. After the insertion of the diagnoses in the spatial field, the final watermarked image presents a PSNR of 42,71 dB; and eventually the good quality of this medical image.

The sturdiness of the first mark in comparison to different attacks

In order to prove the sturdiness of the developed approach in the frequency field in comparison to different attacks, we have tried to apply possible diverse attacks which the image can undergo as it is shown in table 1. We have used the JPEG compression, added noise, histogram equalization, and filter. In the absence of attacks, the correlation between the inserted mark and this extracted is near to 1. The finding peak permits the identification of the mark in the total of 1000 chosen marks. It coincides with the position 500 where we have introduced the inserted mark. However, this correlation decreases when we apply attacks to the watermarked image. But, the finding peak shows that the correlation of the extracted mark and the inserted mark is well-considered. We have also studied the case of the absence of the mark; we have tried to search for an eventual inserted mark. A diagram of an efficient watermark mustn't detect the mark if nothing is inserted in the image. The obtained curve, in this case, doesn't present any peak (and thus no detected mark), which proves the efficiency of our approach that allows to distinguish the case where no watermark is presented in the image. Moreover, the developed watermark approaches permits to deny incorrect marks. We have inserted in the image another binary mark with the size of 32x32 pixels as it is mentioned in figure5 . We have tried to detect the mark of this image in order to ensure the efficiency of our approach and prove that it distinguishes from the inserted mark and doesn't detect wrong marks. The curve of the finding correlation in this case (table1) doesn't present any peak, hence the efficiency of this approach and its ability to distinguish the inserted mark one from another.

The sensibility of the second set of marks in comparison to different attacks

In table 2, we are going to study the sensibility of the watermark diagram in comparison to different types of attacks.

Table2. Sensibility in comparison to attacks during the insertion in the fields

With the reference to this table, we notice that the ultimate attacks, which the medical image can undergo, cause the non-comprehensibility of the inserted mark. In fact, The JPEG compression, the histogram equalization, the median filter and the added noise causing the modification in the image character. The used watermark being frail, the modification which have changed the image, reflect also on the set of the inserted marks. For the case of non-attacked image (intact and non falsified image), the inserted diagnosis is well-detected: character by character and this for all the set of inserted marks by the different interventionists guaranteeing then the record of the diagnoses and the trace of the doctors. Once, the image underwent an attack during its transmission, the vulnerable inserted diagnosis in the extraction phase is incomprehensible so as to warn the user of the presence of the change of the transmitted image avoiding then every risk of having a wrong diagnostic or a different diagnostic from the one inserted.

Conclusion

In this paper, we have presented a multiple and hybrid watermark approach using both two different fields of insertion. We have inserted in the frequency field a sturdy mark allowing to guarantee the automatic control of the diffused media through the network and testify to the identity of the proprietor of the medical image, the presence of this sturdy mark prevents any attempts of pirate. In the spatial field, we have included the diagnoses of the doctors (frail marks) guaranteeing its records and its trace. We have explained in this research the choice of the two fields of the used insertions by clarifying its advantages. Then, we have explained in detail the insertion and the extraction phase in the two aforementioned fields. Next, we have studied the performance of our approach according to different criteria: the sturdiness of the first mark, the quality of the watermarked image, the sensibility of the second mark (the series of diagnoses) in comparison to different attacks and the guarantee of the trace and the archive of diagnoses. We have also optimized the developed approach by increasing the criterion of sturdiness through a multiple insertion of the same sturdy mark. This redundancy offers us, in fact, more possibility in order to find the inserted mark in the first field of insertion following the extraction phase. This developed technique is used so as to help the doctors, in a collaborative work, to take the decision in a short time.

  of the porter image of the mark i b : bit of the inserted mark

Fig. 1 .

 1 Fig. 1. The project acronym

Fig. 4 .

 4 Fig. 4. The quality of the image following its insertion in the two fields

  Table1. Sensibility in comparison to attacks following the insertion in the frequency filedAttacksAttacked watermarked image Correlation between the detected mark and the bank of used marks.

Fig

  Fig. 5. Incorrect mark


Mitchell Paukner

Lucy Pepin

Manda Riehl
email: riehlar@uwec.edu

Jarred Wieser

Pattern Avoidance in Task-Precedence Posets

We have extended classical pattern avoidance to a new structure: multiple taskprecedence posets whose Hasse diagrams have three levels, which we will call diamonds. The vertices of each diamond are assigned labels which are compatible with the poset. A corresponding permutation is formed by reading these labels by increasing levels, and then from left to right. We used Sage to form enumerative conjectures for the associated permutations avoiding collections of patterns of length three, which we then proved. We have discovered a bijection between diamonds avoiding 132 and certain generalized Dyck paths. We have also found the generating function for descents, and therefore the number of avoiders, in these permutations for the majority of collections of patterns of length three. An interesting application of this work (and the motivating example) can be found when task-precedence posets represent warehouse package fulfillment by robots, in which case avoidance of both 231 and 321 ensures we never stack two heavier packages on top of a lighter package.

Introduction

In this paper, we continue a rich tradition of extending the notion of classical pattern avoidance in permutations to other structures. Given permutations π = π 1 π 2 • • • π n and ρ = ρ 1 ρ 2 • • • ρ m we say that π contains ρ as a pattern if there exist 1 ≤ i 1 < i 2 < • • • < i m ≤ n such that π ia < π i b if and only if ρ a < ρ b . In this case we say that π i 1 π i 2 • • • π im is orderisomorphic to ρ and that π i 1 π i 2 • • • π im reduces to ρ. If π does not contain ρ, then π is said to avoid ρ. The classical definition of pattern avoidance in permutations has shown itself to 1 be worthwhile in many fields including algebraic geometry and theoretical computer science. Analogues of pattern avoidance have been developed for a variety of combinatorial objects including Dyck paths [START_REF] Bernini | Pattern-avoiding Dyck paths[END_REF], tableaux [START_REF] Lewis | Pattern avoidance for alternating permutations and reading words of tableaux[END_REF], set partitions [START_REF] Sagan | Pattern avoidance in set partitions[END_REF], trees [START_REF] Rowland | Pattern avoidance in binary trees[END_REF], and many more. In this paper, we extend the concept of pattern avoidance to a particular ordered graph structure. We use a definition of pattern avoidance that is similar to that used in the study of heaps [START_REF] Levin | Pattern avoidance in k-ary heaps[END_REF], but separate from that used in previous studies of trees. Definition 1.1. A task-precedence poset is a poset which represents the order relations between several tasks to be completed.

We are particularly interested in considering d identical task-precedence posets, and here we focus our attention on those sets of tasks that require one task be completed before any others, and one final concluding task after any others, with no restrictions on the rest of the tasks in the list. When considering a list of 4 tasks, the Hasse diagram of this poset is a diamond, and as such we will refer to a task-precedence poset of this type with v tasks as a diamond with v vertices (each with v -2 vertices in the middle level). We then assign unique labels from {1, 2, . . . , vd} to each vertex such that the labels obey the order relations of each diamond. We then refer to the set of all such labelled collections of diamonds as D v,d .

Given an element D of D v,d we associate a permutation π D by recording the vertex labels as they are encountered reading the labels on each diamond consecutively, left to right by levels, beginning with the least element. For example, if D is as pictured in Figure 1, then π D = 256791348 [START_REF] Mountz | A day in the life of a Kiva robot[END_REF]. We say that D contains (respectively avoids) ρ as a pattern if π D contains (respectively avoids) ρ as a classical pattern, using the definition above. We will abuse notation and sometimes refer to an element of D v,d and its associated permutation interchangeably. Let D v,d (P ) be the elements of D v,d that avoid all patterns in list P. While Figure 1 contains 123, 132, 213, 231, 312, it is a member of D 5,2 (321). We were motivated to consider this question from a real-life application, namely a fleet of robots all completing the same sequence of tasks in a warehouse for package fulfillment. In 2011, instead of having human employees walk the warehouse floor retrieving items one after another to complete an order, Amazon began utilizing Kiva robots in their package fulfillment warehouses [START_REF] Mountz | A day in the life of a Kiva robot[END_REF]. Each robot executes 4 pieces of the larger task. First the robot drives to the appropriate rack and mounts the rack on its back. Then it can either drive through the warehouse highways to its picker (the human employee who will retrieve the item off the rack without leaving their station), or it can rotate itself so that the appropriate side of the rack is facing the picker. Both of these need to be completed before the final step: having the item picked off the rack. In this way, completing one order of d items from Amazon.com is exactly the task-precedence poset represented by d diamonds with 4 vertices each. If we furthermore assign the robots to the diamonds based on the weight of the item that is to be shipped (with the heaviest object being retrieved by the robot in diamond 1, and the lightest object by the final diamond), then avoiding 231 and 321 simultaneously is a sufficient condition to ensure the human picker does not receive two heavier objects to pack after a lighter object has already been packed.

One could consider other applications that arise from task-precedence problems, but our motivating example is best generalized by generalizing the 4 tasks per autonomous robot to v tasks. Definition 1.2. The generating f unction f or descents (P ) x des y d , and

(gf d) for D v,d (P ) is f P v,d (x, y) = D∈D v,d
f P v (x, y) = ∞ d=1 f P v,d (x, y).
For example, D 5,1 (213) is the set of diamonds with associated permutations 1 2 3 4 5, 1 2 4 3 5, 1 3 4 2 5, 1 4 2 3 5, and 1 4 3 2 5. So, Throughout this paper, the main question we answer is "How many elements are in D v,d (P )?" for any collection P of patterns of length 3. In general we fix v ≥ 4 and a set of patterns P and then determine a formula for the sequence {|D v,d (P )|} d≥1 , with key results for v = 4 shown in Table 1. The third column of the table gives entries from the Online Encyclopedia of Integer Sequences [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]. Our results for pattern-avoiding diamonds have connections with many other combinatorial objects, as evidenced by the low reference numbers. Sequences A260331, A260332 and A260579, however, are new results particular to this study of task precedence posets.

f 213 5,1 (x, y) = y(1 + 3x + x 2
Our secondary question, which answers our primary question, is to find f P v,d (x, y). Then when we substitute x = 1 and take the coefficient of y d , we obtain |D v,d (P )|.

In Section 2 we consider collections of diamonds that avoid a single pattern of length 3. In Section 3 we consider collections of diamonds that avoid a pair of patterns of length 3, and in Section 4 we consider collections of diamonds avoiding three or more patterns of length 3.

Diamonds avoiding a single pattern of length 3

Before we count pattern-avoiding diamonds, it is useful to enumerate all diamonds.

Theorem 1. |D v,d (∅)| = (vd)! v d (v-1) d
Proof. Let v ≥ 4 and d ≥ 1, there are (v -2)! ways to arrange the internal vertices of any given diamond. For the first diamond there are vd v label possibilities times the (v -2)! possible permutations of the internal vertices. For the next diamond there are (v-1)d v (v -2)! label possibilities. Continuing in this way, we obtain

vd v (v -1)d v • • • 2v v (v -2)! d = (vd)! (v!) d ((v -2)!) d = (vd)! v d (v -1) d . Theorem 2. |D v,d (123)| = 0
Proof. It is impossible to avoid 123 while having a diamond since the pattern is inherent in all valid diamond labellings. Proof. The theorem is clear from how D v,d (p) rc is created from the reverse-complement of p.

Corollary 1. For k ≥ 1, D v,d (p 1 , p 2 , . . . , p k ) rc = D v,d (p rc 1 , p rc 2 , . . . , p rc k ). Thus we immediately see that 132 ∼ W 213, 231 ∼ W 312, {132, 312} ∼ W {213, 231}, {132, 321} ∼ W {213, 321}, and {231, 321} ∼ W {312, 321}.
Definition 2.3. Given a permutation π in S n , lis(π) is the length of the longest increasing subsequence in π.

For example, in the permutation 1 2 5 6 3 4 7 8 the longest increasing subsequence is 1 2 5 6 7 8 and lis = 6. Definition 2.4. Given a permutation π in S n , rlmax(π) is the number of right-left maxima in π.

For example, in the permutation 2 4 6 8 1 3 5 7 a maximum is reached when reading right-to-left twice and rlmax = 2. Definition 2.5. Let Dyck v,d be the set of all paths from (0, 0) to (d, vd) using only (0, 1) and (1, 0) steps (East and North steps) which stay weakly under y = vx. In figure 2.1, the longest distance from a corner in the Dyck path to the line y = 4x is seven (from [START_REF] Levin | Pattern avoidance in k-ary heaps[END_REF][START_REF] Fuss | Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat[END_REF] to [START_REF] Levin | Pattern avoidance in k-ary heaps[END_REF][START_REF] Rowland | Pattern avoidance in binary trees[END_REF]) and height(p) = 7.

Lemma 2. Any element of D v,d (132) has the elements on each diamond labelled in increasing order.

Indeed, otherwise the label of the first element of the diamond together with the first descent would form a 132.

Theorem 4. σ∈D v,d(132) w rlmax(σ) x des(σ) y d z lis(σ) = p∈Dyck v,d w touchpoints(p) x corners(p) y d z height(p) .
Proof. We define a map φ from Dyck v,d to D v,d (132). To find φ(p), first write out the heights of the East steps. For each height, include a subscript j that indicates how many East steps are at that height. Reverse this sequence and add 1 to every item in the list, leaving the subscripts unchanged. Each of the elements of this list becomes the first label of a diamond, and then place vj labels in increasing order using the smallest elements that have not already been used as labels.

As an example, refer to Figure 2.1. The heights of the East steps are 0, 4, 5, 12. When this sequence is reversed and 1 is added to each term, the resulting sequence is 13 1 , 6 1 , 5 1 , 1 1 . Thus the permutation associated with this Dyck path is 13 14 15 16 6 7 8 9 5 10 11 12 1 2 3 4.

The importance of the subscripts j are evident from the image of Figure 2.3. The heights of the East steps are 0, 3, 3, 10, and the resulting sequence is 11 1 , 3 2 , 1 1 . Thus the permutation associated to image is 11 12 13 14 4 5 6 7 8 9 10 15 1 2 3 16.

This map is certainly reversible, with the first label on each diamond forming a list, unless there is an increase between diamonds, in which case the first label is repeated. Then the list is reversed and 1 is subtracted from each element, giving us the heights of the East steps in the Dyck path.

This bijection is particularly natural when you examine common statistics on both paths and permutations. Following touchpoints, corners, and height through the bijection, we find they correspond exactly to right-left maximum, descents, and longest increasing sequence on the permutation.

Corollary 2. Thanks to our bijection, |D

v,d (132)| = |Dyck v,d | = ( d(v+1) d ) (vd+1) . [5] Theorem 5. |D v,d (132)| = ( d(v+1) d ) (vd+1)
Proof. By Theorem 4, 132 is d-Wilf-equivalent to 213. Definition 2.9. We define D d v,j to be the collection of labelled diamonds for d -1 full diamonds with v vertices each followed by an incomplete diamond with j vertices for j = 1, . . . , v -1. Likewise D d v,j (p) are those diamonds that avoid pattern p. Note, when j = 1 there exist no order relations in the final partial diamond.

The following figure is an example of an unlabelled member of D d v,j .

Definition 2.10. α d v,j (x) (or sometimes simply α d v,j for brevity) is the generating function for descents for D v,d (231). In other words,

α d v,j (x) = D∈D ( v,d 231)
x des(π D ) .

For example, D

(x) = 1 + 4x + 4x 2 + x 3 . Theorem 6. f (231) v,d (x, 1) = α d v,v (x) = α d v,(v-1) + x d-1 i=1 α d-i v,(v-1) α i v,v
where

α 1 v,j =      1, if j = 1 C j-1 , if j = 2, . . . , v -1 C v-2 , if j = v and C i is the i th Catalan number.
Proof. We proceed by partitioning elements of D d v,j (231) by where the largest label occurs. Let m = v(d -1) + j where v(d -1) + j is the largest label in (d -1) diamonds with v vertices followed by an incomplete diamond with j vertices. Now, assume j = 1. The m th element can appear on the final least element or on the greatest element of any of the full diamonds. When m occurs on the final least element there are (d -1) diamonds with v vertices that precede m, we then have α d-1 v,v as the generating function for descents(gfd) for the vertices before m that will avoid (231). When m appears on the greatest element of the last complete diamond, α d-1 v,(v-1) is the gfd for the vertices before m, and α 1 v,1 is the gfd for the vertices following m. Because we have created a descent from m to the least element of the final diamond, we must multiply our gfd by x to account for this extra descent. Thus, the gfd when m appears on the greatest element of the last complete diamond is then

α d-1 v,(v-1) α 1 v,1 x. m α d-1 v,v α 1 v,1 Figure 2.4: α d v,1
When m appears on the greatest element of the second to last complete diamond, our gfd for the vertices before m is then α d-2 v,(v-1) and α 2 v,1 for the vertices following m. Once again, we have an extra descent in π D from m to the following least element, thus we multiply our generating function by x. When m appears on the greatest element of the second to last diamond, our gfd is then

α d-2 v,(v-1) α 2 v,1
x. This pattern continues and finally when m appears on the first complete diamond,

α 1 v,(v-1)
is the gfd for vertices before m and α d-1 v,1 for the vertices following m with an extra descent from m to the following least element. The gfd when m appears on the greatest element of the first diamond is then α 1 v,(v-1) α d-1 v,1 x. Hence

α d v,1 (x) = α d-1 v,v + x d-1 i=1 α d-i v,(v-1) α i v,1
Now, assume we have (d-1) diamonds followed by an incomplete diamond with j vertices where j = 2, . . . , v -1. The m th element can appear on any of the interior vertices but not on the least element of the incomplete diamond, or m can appear on the greatest element of any complete diamond. When m appears on any of the interior vertices of the final diamond we need to count the descents before m, after m, and from m. The descents that occur before m can be counted by α d v,j-g where g is the number of interior vertices following m including m. The descents following m are counted by α 1 v,g because the same number of descents can occur in the remaining interior vertices as when we have a single incomplete diamond. We then count the descent that results from m by multiplying our gfd by x, but we do not get a descent from m when it appears on the final interior vertex. We then sum over all possible g to give us the gfd when m appears on the interior vertices of the final diamond which gives

us α d v,j-1 α 1 v,1 + x j-1 g=2 α d v,j-g α 1 v,g . m α d v,(j-g) α 1 v,g Figure 2.5: α d v,j
Also, m can appear on the greatest element of any of the full diamonds. When m appears on the greatest element of the last complete diamond the gfd for vertices that appear before m is α d-1 v,(v-1) and α 1 v,j for the vertices following m. We count the descent from m by multiplying our gfd by x. The total gfd when m appears on the greatest element of the last diamond is then α d-1 v,(v-1) α 1 v,j x. This pattern continues so when m appears on the first complete diamond, the gfd for vertices before m is α 1 v,(v-1) and α d-1 v,j for the vertices following m. We once again count the descent from m by multiplying our gfd by x. The gfd when m appears on the greatest element of the last diamond is then

α 1 v,(v-1) α d-1 v,j x. Thus α d v,j (x) = α d v,j-1 α 1 v,1 + x j-1 g=2 α d v,j-g α 1 v,g + x d-1 i=1 α d-i v,(v-1) α i v,j
for j = 2, . . . , v -1. Lastly, we look at when we have d complete diamonds. The m th element can appear on any of the greatest elements. When m appears on the greatest element of the last diamond, the gfd is α d v,(v-1) which counts descents before m. When m appears on the greatest element of the second to last complete diamond, the gfd for vertices that appear before m is α d-2 v,(v-1) and α 1 v,v for vertices following m. We count the descent from m to the following least element by multiplying the gfd by x. The gfd when m appears on the greatest element of the last diamond is then α

d-2 v,(v-1) α 1 v,v (x)
. This pattern continues so when m appears on the first complete diamond the gfd for vertices before m is α 1 v,(v-1) and α d-1 v,v for vertices following m. The descent from m to the following least element is counted by multiplying the gfd by x. The gfd when m appears on the greatest element of the last diamond is then

α 1 v,(v-1) α d-1 v,v (x). Hence α d v,v (x) = f (231) v,d (x, 1) = α d v,(v-1) + x d-1 i=1 α d-i v,(v-1) α i v,v
We can use this result to recursively obtain f The sequences we obtained for various v = 4, 5, 6, . . . after using this recursive technique were not found in OEIS. We added the sequence to the encyclopedia when v = 4 and we hope that in the future a connection is found to other combinatorial objects.

y d = α d v,v (1) = |D v,d (231)

The pattern 321

We were unable to find a closed formula for the pattern 321. In Table 2.3, we present the first few terms of the sequence and the first few generating functions for descents. We believe that a technique recently used by Bevan,et.al. [2] could be successful in this case too. Their technique involved refining a bivariate generating function via a statistic called last inversion foot, using a result of Bousquet-Melou, and finding a functional equation, to eventually give a growth factor for the sequence. But for now, this remains open.

v=4 d |D v,d | f (321) v,d (x) 1 2 1 + x 2 106 1 + 71x + 29x 2 + 5x 3 3 5976 1 + 991x + 2747x 2 + 1765x 3 + 430x 4 + 42x 5
3 Diamonds avoiding a pair of patterns of length 3

Next, we study pairs of patterns of length 3. While there are 15 such pairs of patterns, we focus on the 8 pairs of patterns {σ, ρ} where |D v,d (σ, ρ)| is non-trivial.

Diamonds avoiding the set of patterns {132, 213}

Lemma 4. In order to avoid 132 and 213, the labels on each diamond must be increasing and consecutive.

Proof. By Lemma 2, the labels appear in increasing order on each diamond. Then any label "missing" from consecutive labelling would either create 213 if it occurred before its surrounding labels, or a 132 if it occurred after. Therefore the labels on each diamond must be consecutive and increasing.

Theorem 8. f (132,213) v,d (x, y) = ∞ d=1 σ∈D(132,213) y d x des(σ) = 1 -yx 1 -y(1 + x)
Proof. By Lemma 4, we know that the labels on each diamond are consecutive and increasing, so there is a diamond labelled 1, 2, . . ., v, another labelled v + 1, . . ., 2v, etc. So the only thing we must ensure is that the entire collection of diamonds avoids 132 and 213 between the respective diamonds. In their foundational paper, Simion and Schmidt enumerated permutations avoiding 132 and 213 [START_REF] Simion | Restricted permutations[END_REF], and the recursive nature of their proof can also be adapted to find our generating function for descents.

The labels v(d -1) + 1, . . . , vd must occur on either the first diamond, or the last. In the first case, they create a descent. In the second, they do not, giving a (1 + x) term in the generating function. We continue recursively and obtain:

D∈D v,d (132,213) y d x des(σ(D)) = 1 + ∞ d=1 y d (1 + x) d-1 = 1 + 1 1 + x -1 + 1 1 -y(1 + x) = x 1 + x + 1 (1 + x)(1 -y(1 + x)) = x(1 -y(1 + x)) + 1 (1 + x)(1 -y(1 + x)) = 1 -yx 1 -y(1 + x) Corollary 4. f (132,213) v,d
(1, y)

y d = |D v,d (132, 213)| = 2 d-1
3.2 Diamonds avoiding {132, 312} and {213, 231} Lemma 5. In order to avoid 132 and 312, the final diamond is labelled with either v(d -1) + 1, v(d -1) + 2, . . . , vd or 1, v(d -1) + 2, . . . , vd Proof. Since v ≥ 4, the label vd must appear on the final diamond in order to avoid 312. Likewise the interior vertices on the final diamond must be in consecutive increasing order in order to avoid 132, so the v -1 final vertices are v(d -1) + 2, . . . , vd. If the label on the first vertex of the last diamond were some number j other than 1 or v(d -1) + 1, then the first vertex of whichever diamond v(d -1) + 1, along with v(d -1) + 1, and j would form a 132.

Theorem 9. f (132,312) v,d (x, y) = ∞ d=1 σ∈D(132,312) y d x des(σ) = 1 -yx 1 -y(1 + x)
Proof. We proceed similarly to the proof of Theorem 8 with a recursive argument. By Lemma 4, the final diamond has only two possibilities, one of which forms a descent with the previous diamond, and one of which doesn't. Thus our descent generating function gains a (1 + x) term for each additional diamond, and exactly as in Theorem 8, the result follows.

Diamonds avoiding {132, 321} or {213, 321}

Lemma 6. Any diamond avoiding 132 and 321 has at most one descent. Moreover, if there is a descent, it involves the label 1.

Proof. By examination of cases, any arrangement of two descents forms either a 132 or a 321. If a descent does not involve the 1, then either the 1 occurs before, causing a 132, or the 1 occurs after, causing a 321.

Theorem 10. f (132,321) v,d (x, y) = ∞ d=1 σ∈D(132,321) y d x des(σ) = 1 -2y + y 2 + vxy 2 (1 -y) 3
Proof. By Lemma 6, we need only enumerate those diamonds with one descent where the descent involves the 1. Everything after the 1 increases, as does everything before the 1. In fact, the permutations associated to diamonds that avoid 132 and 321 look like a portion of the identity permutation was cut off the front and inserted after position vi, for i = 1, . . . , d -1. When i = d -1, there are v possibilities for how many numbers appear consecutively with 1, including 1. When i = d -2, there are 2v possibilities, etc. When i = 1, there are (d -1)v possibilities. Thus we have v 2 d(d -1) diamonds with one descent, and one with zero descents. Thus,

y d x des(σ) = ∞ d=0 y d [1 + v 2 d(d -1)x] = ∞ d=0 y d + vx 2 ∞ d=0 y d d(d -1) = 1 1 -y + vx 2 (y 2 ) 2 (1 -y) 3 = 1 1 -y + vxy 2 (1 -y) 3 = (1 -y) 2 (1 -y) 3 + vxy 2 (1 -y) 3 = 1 -2y + y 2 + vxy 2 (1 -y) 2 Corollary 8. f (132,321) v,d (1, y)
y d x des(σ) = x + yx(1 + x) v-2 + 1 (1 + x)(1 -y(1 + x) v-2 )
Proof. Let n = vd be the largest label on a diamond D ∈ D v,d (231, 312). Avoiding the pattern 231 means the 1 must be at the beginning and avoiding the pattern 312 implies everything after n must be decreasing which forces n to the end of the permutation. By a result of Simion and Schmidt on permutations, there are 2 v-3 ways to arrange the middlelevel vertices within each of the d diamonds in order to avoid both 231 and 312 creating between 0 and v -3 descents [START_REF] Simion | Restricted permutations[END_REF]. There are also two ways to either swap or not the last element of each diamond with the first element of the next. This gives the generating function as follows.

D∈D v,d (231,312)

y d x des(σ(D)) = 1 + ∞ d=1 y d (1 + x) (v-2)d-1 = 1 + 1 (1 + x) ∞ d=1 (y(1 + x)) (v-2)d = 1 - 1 (1 + x) + 1 (1 + x)(1 -y(1 + x) v-2 ) = x + yx(1 + x) v-2 + 1 (1 + x)(1 -y(1 + x) v-2 ) Corollary 11. f (231,312) v,d
(1, y)

y d = |D v,d (231, 312)| = 2 d(v-2)-1

Avoiding {231, 321}

Lemma 7. All labels that appear after n = vd must be consecutive and increasing, and if a n = n, then a n = n -1.

f (231,321) v,d (x, 1) = β d v,v = β d v,(v-1) + x d-1 i=1 β d-i v,(v-1)
where

β 1 v,j =      1, if j = 1 2 j-1 , if j = 2, . . . , v -1 2 v-2 , if j = v
is the generating function for descents for D v,d (231, 321).

Proof. We approach the proof similarly to that of Theorem 6 and partition our diamonds by the position of the largest element and proceed recursively. Because the proofs are very similar, we omit the details of this proof for brevity. The only differences are that since we are now avoiding 321, we have no descents after the appearance of the largest label, and we have different initial conditions on one diamond.

The table below is an example of using this recursive technique to find the generating function for descents for D 5,3 (231, 321). (1, y)

v=5 d 1 2 3 α d 5,1 1 1 + 4x + 3x 2 1 + 13x + 41x 2 + 37x 3 + 12x 4 α d 5,2 1 1 + 5x + 6x 2 1 + 15x + 54x 2 + 62x 3 + 24x 4 α d 5,3 1 + x 1 + 7x + 13x 2 + 3x 3 1+18x+80x 2 +128x 3 + 73x 4 + 12x 5 α d 5,4 1 + 3x 1 + 10x + 25x 2 + 12x 3 1+22x+121x 2 +248x 3 + 184x 4 + 48x 5 α d 5,5 1 + 3x 1 + 11x + 28x 2 + 12x 3 1+24x+134x 2 +273x 3 + 196x 4 + 48x 5
y d = α d v,v (1)

Diamonds avoiding three or four patterns of length 3

There are only two nontrivial cases to examine when we avoid three patterns of length 3: (132, 213, 321) and (231, 312, 321). Proof. Let n = vd be the largest label in d diamonds with v vertices. Avoiding the pattern (132) forces all labels before n to be larger than all labels after. Avoiding the pattern (213) forces all labels before n to be increasing. Avoiding the pattern (321) forces all labels after n to be increasing. This indicates that all vertices that appear before n will be the consecutive numbers prior to n and all vertices after n will be the remaining elements ordered consecutively. A label a i = n iff i = vs for some s = 1, . . . , d, and there is only one arrangement for the rest of the elements. Therefore, there can only be, at most, one descent and it occurs between diamonds. So, Since any permutation can be created from the identity using swaps, restricting our changes to swaps will not exclude any possibilities. Lemma 9. All swaps must be disjoint in order to avoid (321).

y d x des(σ) = 1 + ∞ d=1 y d (1 + (d -1)x) = 1 1 -y + xy 2 ∞ d=1 (d -1)y d-2 = 1 -y + xy 2 (1 -y)
Proof. We simply examine the cases when two swaps overlap in some way, either with two swaps executed on 3 elements, or two overlapping swaps on 4 elements.

(x) = (1 + x) d-1 d ⌊ v-2 2 ⌋ k=0 v -2 -k k x k
Proof. Every final element of a diamond can either remain unchanged or be swapped with the least element of the next diamond. This then gives the generating function (1 + x) d-1 for each possible swap. Let k represent the nonconsecutive positions from which to choose a swap among the interior vertices. Note that in a diamond there are v -3 positions to swap since there are v -2 interior vertices. By Lemma 8 and Lemma 9 any consecutive interior vertices can be swapped disjointly, and can only be swapped disjointly. Since the swaps must be nonconsecutive, k must be chosen from v -3 -(k -1). This gives v-2-k k . We then sum over all k in order to generate all possible descents for a single diamond. Since we have d diamonds in which to execute these swaps, we raise to the d th power. The gfd for D v,d (231, 312, 321) is then Proof. The base cases are |D 3,1 | = 1 which is the identity, and |D 4,1 | = 2. which is the identity permutation and the permutation with the interior vertices swapped. Let there be a single diamond with v vertices, where are v -2 interior vertices that can be swapped which gives the the D v,1 permutations that avoid the three patterns. Now consider a single diamond with v + 1 vertices. The final interior vertex will either be the v element when there is no descent in the last two interior vertices, or the v -1 element when there is a descent between the final two interior vertices. When v is the final interior vertex, there are v -2 vertices that can be re-arranged. Thus there are the D v,1 permutations. When there is a descent in the final two interior vertices, there are v -3 interior vertices that can be re-arranged, thus there are the Proof. Let n be the largest label in any permutation. Due to the structure of the diamonds, any set of permutations involving 123 cannot be avoided. For any other collection of 4 or more patterns, the result is easily seen using the lemmas for avoiding a single pattern earlier in the paper.

(1 + x) d-1 Σ ⌊ v-2 2 ⌋ k=0 v-2-k k x k d .

Figure 1 . 1 :

 11 Figure 1.1: An element of D 5,2 (321).

2. 1 Definition 2 . 2 .Lemma 1 .

 1221 The patterns 132 and 213 Definition 2.1. We let p rc be the reverse-complement of a pattern p, and D ∈ D v,d (p) rc be the reverse-complement of D ∈ D v,d (p), by which we mean that D is labelled with π rc D instead of π D . Two patterns on diamonds, α and β, are said to be d-Wilf-equivalent if they have the same enumeration, that is, if |D v,d (α)| = |D v,d (β)| for all v and d. If so, we write α ∼ W β. The reverse-complement of a task precedence poset remains a legal poset. Theorem 3. D v,d (p) rc = D v,d (p rc )

Definition 2 . 6 .Definition 2 . 7 .Definition 2 . 8 .

 262728 Given any p ∈ Dyck v,d , touchpoints(p) is the number of times p touches the line y = vx, excluding the point (v, dv).In Figure2.1, the Dyck path touches the line y = 4x four times and touchpoints(p) = 4. Given any p ∈ Dyck v,d , corners(p) is the number of North steps that are followed by one or more East steps in p.In figure2.1, there are four places where the Dyck path has one or more North steps followed by one or more East steps and corners = 4. Given any p ∈ Dyck v,d , height(p) is the greatest vertical distance from any point on p to the line y = vx.

2. 2 Figure 2 Figure 2 . 2 :Figure 2 . 3 :

 222223 Figure 2.1: A Dyck path from (0,0) to (4,16)

(

  v,d 231)(x, 1) for any v and d.Corollary 3. f (231) v,d(1, y)

Table 3 : 1 , 2 , 3 . 7 .

 31237 The total number of permutations for D 5,d that avoid the pattern (231) for d = Theorem |D v,d (231)| = |D v,d (312)| Proof. By Theorem 1, 231 is d-Wilf-equivalent to 312.

=

  |D v,d (132, 312)| = 2 d-1 . Corollary 6. By Theorem 1, (213, 231) is d-Wilf-equivalent to (132, 312).

  Corollary 7. f (213,231) v,d(1, y)y d = |D v,d (213, 231)| = 2 d-1 .

= 2 Corollary 9 . 2 3

 292 |D v,d (132, 321)| = 1 + v d(d-1) D v,d (213, 321) and D v,d (132, 321) are d-Wilf Equivalent by Theorem 1. Corollary 10. f (213,321) v,d (1, y) y d = |D v,d (213, 321)| = 1 + v d(d-1)

Definition 3 . 1 .

 31 Let β d v,j be the generating function for descents for D v,d (231, 321). Recall Figure 2.2 is an example of d -1 full diamonds with v vertices followed by an incomplete diamond with j vertices for j = 1, . . . , v -1. Theorem 12.

4. 1

 1 Diamonds avoiding {132, 213, 321} Theorem 13. f (132,213,321) v,d (x, y) = ∞ d=1 σ∈D(132,213,321) y d x des(σ) = 1y + xy 2 (1y) 2

Definition 4 . 1 .

 41 A swap is when two consecutive labels from the identity permutation switch positions in the permutation.

Theorem 14 .

 14 The generating function for descents for D v,d (231, 312, 321) is f (231,312,321) v,d

=

  |D v,d (231, 312, 321)| = 2 * 4 d-1 . Corollary 16. |D v,1 (231, 312, 321)| is the Fibonacci numbers.

  D v-1,1 permutations. Hence |D v+1,1 | = |D v,1 | + |D v-1,1 |.Therefore, |D v,1 (231, 312, 321)| follows the Fibonacci numbers.

4. 3 3 Theorem 15 .

 3315 Diamonds avoiding four patterns of length Let S be a set of at least 4 distinct permutations of length 3.Then |D v,d (S)| = 0, if 123 ∈ S 1, if 123 ∈ S

Table 1 :

 1 ). Enumeration of pattern-avoiding diamonds when v = 4

	Patterns P	{|D 4,d (P )|} d≥1	OEIS	Result
	∅	2, 280, 277200, 10090080000, . . .	A260331 Theorem 1
	123	0, 0, 0, 0, 0, 0, 0, 0, 0, . . .	A000007 Theorem 2
	132 213	1, 5, 35, 285, 2530, 23751, 231880, 2330445, . . . A002294	Theorem 4 Theorem 5
	231 312	2, 18, 226, 3298, 52450, 881970, . . .	A260332	Theorem 6 Theorem 7
	321	2, 106, 5976, . . .	A260579 OPEN
	{132, 213}	1, 2, 4, 8, 16, 32, 64, 128, 256, . . .	A000079 Theorem 8
	{132, 312} {213, 231}	1, 2, 4, 8, 16, 32, 64, 128, 256, . . .	A000079	Theorem 9 Theorem 6
	{132, 321} {213, 321}	1, 5, 13, 25, 41, 61, 85, 113, 145, . . .	A001844	Theorem 10 Theorem 9
	{231, 312}	2, 8, 32, 128, 512, 2048, . . .	A004171 Theorem 11
	{231, 321} {312, 321}	2, 14, 98, 686, 4802, 33614, 235298, . . .	A109808	Theorem 12 Theorem 13
	{132, 213, 321} 1, 2, 3, 4, 5, 6, 7, 8, 9, . . .	A000027 Theorem 13
	{231, 312, 321} 2, 8, 32, 128, 512, 2048, 8192, 32768, 131072 . . . A081294 Theorem 14

Table 2 :

 2 The recursive steps necessary to find the generating function for descents for D 5,3 (231).

Table 4 :

 4 The recursive steps necessary to find the generating function for descents for D 5,3 (231, 321).

	(231,321) v,d Corollary 12. f

Table 5 :

 5 The total number of permutations for D 5,d that avoid the patterns (231, 321) when d = 1, 2, 3.

	= |D v,d (231, 321)|.

Corollary 13. By Theorem 1, (231, 321) is d-Wilf-equivalent to (312, 321).

  We will proceed by examining what changes can be made to the identity permutation while still avoiding 231, 312, and 321.

		2
	Corollary 14. f v,d (132,213,321)	(1, y)| y d = |D v,d (132, 213, 321)| = d.
	4.2 Diamonds avoiding 231, 312, 321

Lemma 8. If for labels a i , a j , a k if a i , a j < a k , then i < k or j < k in order to avoid the patterns (312) and (321).


Julien Lefèvre
email: julien.lefevre@univ-amu.fr

Guillaume Auzias
email: guillaume.auzias@univ-amu.fr

Spherical parameterization for genus zero surfaces using Laplace-Beltrami eigenfunctions

Keywords: Riemannian Manifold, Laplace-Beltrami Operator, Surface Parameterization, Nodal Domains

In this work, we propose a fast and simple approach to obtain a spherical parameterization of a certain class of closed surfaces without holes. Our approach relies on empirical findings that can be mathematically investigated, to a certain extent, by using Laplace-Beltrami Operator and associated geometrical tools. The mapping proposed here is defined by considering only the three first non-trivial eigenfunctions of the Laplace-Beltrami Operator. Our approach requires a topological condition on those eigenfunctions, whose nodal domains must be 2. We show the efficiency of the approach through numerical experiments performed on cortical surface meshes.

Introduction

Spherical parametrization of 3D closed (genus-0) meshes is a classical approach in computer graphics for texture mapping, remeshing and morphing [START_REF] Sheffer | Mesh parameterization methods and their applications[END_REF]. Neuroimaging data analysis is an important field of applications since representing the brain as a closed surface is increasingly popular in the community, in line with the specific advantages for e.g. visualization and inter-subjects mapping [START_REF] Fischl | Cortical surface-based analysis: Ii: Inflation, flattening, and a surface-based coordinate system[END_REF]. Several works [START_REF] Gu | Genus zero surface conformal mapping and its application to brain surface mapping[END_REF][START_REF] Auzias | Model-driven harmonic parameterization of the cortical surface: Hip-hop[END_REF] translated most recent methodological advances from computer graphics to brain mapping, and put emphasis on two properties that are particularly desirable in this field [START_REF] Lai | Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization[END_REF]: the spherical parameterization must be fold-free to ensure the validity of neuroimaging data analysis that rely on the spherical representation, and computationally efficient in order to be applicable to large number of individual meshes whose sub-milimetric resolution involves typically more than 100 K vertices. In this work, we propose a fast and simple approach to obtain a spherical parameterization of a certain class of genus 0 surfaces. Our approach is a particular case of the one defined by Bérard in [START_REF] Bérard | Volume des ensembles nodaux des fonctions propres du laplacien[END_REF], by considering only the three first non-trivial eigenfunctions of the Laplace-Beltrami Operator. A comparable approach has also been proposed in [START_REF] Lai | Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization[END_REF] but implies to solve a highly non linear partial differential equation. We note also an empirical approach based on the spatial regularity of the first eigenfunctions in [START_REF] Lombaert | Diffeomorphic spectral matching of cortical surfaces[END_REF]. We complement these papers with preliminary theoretical contributions, which echo with empirical findings that make it very appealing for neuroimaging studies. In particular, our contributions support the C ∞ diffeomorphic nature of our mapping, under specific condition on the considered surface. We show through numerical experiments performed on 138 cortical surface meshes that this condition is systematically met in practice. Moreover, the resulting mapping is computed in few seconds and almost diffeomorphic with less than 1% of folded triangles on average.

Background and main results

We recall first classical results on Spectral theory and Laplace-Beltrami eigenfunctions. The interested reader can refer to [START_REF] Zelditch | Local and global analysis of eigenfunctions[END_REF].

Laplace-Beltrami eigenfunctions

Definition 1 Given (M, g) a compact 2-Riemannian manifold without boundary, denoting x(p) = (x 1 , x 2 ) a local coordinate system, i.e. a local diffeomorphism M → R 2 around a point p, the Laplace-Beltrami operator acting on C ∞ functions is

∆f = 1 det(g) i,j ∂ xj det(g)g i,j ∂ xi f (1)
Remark 1. In the applications M will be a closed surface in R 3 and the metric g will correspond to the euclidean inner product.

If we consider the eigenvalue problem:

∆f = -λf (2)
we know that it has eigenvalues 0 = λ 0 < λ 1 ≤ λ 2 ... and corresponding eigenfunctions Φ 1 , Φ 2 , ... (See Fig 1 for a visual intuition of some Φ i ). The eigenfunctions are orthogonal in the sense of the scalar product < u, v > M = M uvdµ, where the volume form dµ is given by det(g)dx 1 dx 2 .

Definition 2 Given an eigenfunction Φ of the Laplace-Beltrami Operator, we call nodal set the set of points where Φ vanishes. We denote it N (Φ) in the following. The nodal domains correspond to the connected components of the complementary of the nodal set.

We have some qualitative results on the nodal domains of eigenfunctions:

Theorem 1 (Courant's nodal domain theorem) The number of nodal domains for the n-th eigenfunction is inferior or equal to n + 1.

There is a global result on the dimension of nodal sets when M is a 2-manifold:

Theorem 2 (S.H. Cheng [START_REF] Cheng | Eigenfunctions and nodal sets[END_REF]) Except on a closed set of points, the nodal set of an eigenfunction Φ is a C ∞ 1-manifold, i.e. a line in our applications.

Last we recall the Green formula for an open set D ∈ M that will be of great use in the following:

D Φ∆Ψ dµ = - D g(∇Φ, ∇Ψ )dµ + ∂D Φ(∇Ψ • n)dμ (3)
dμ is the induced metric on the boundary. For simplicity, we use the notation • instead of the riemannian metric g(., .) and remove the volume forms in the following.

Fig. 1: From left to right: eigenfunctions Φ 1 , Φ 2 and Φ 3 . Colormap goes from blue (negative) to red/yellow (positive). Each nodal sets are in green.

Main conjecture

Based on empirical findings we suggest the following result, which allows to define a natural spherical parameterization:

Conjecture 3 Let M be a genus zero surface in R 3 . Let Φ 1 , Φ 2 and Φ 3 be three orthogonal eigenfunctions of the Laplace-Beltrami operator. We assume they have only two nodal domains. Then the mapping

Φ : M -→ S 2 p -→ Φ 1 (p) 2 + Φ 2 (p) 2 + Φ 3 (p) 2 -1 Φ 1 (p), Φ 2 (p), Φ 3 (p)
is well defined and it is a C ∞ diffeomorphism.

Remark 2. The orthogonality condition is more general than assuming different eigenvalues and allows applying the conjecture on the sphere itself. In that case Φ is exactly the identity (up to a multiplicative constant). Namely, given a point p and its spherical coordinates p = (sin θ cos φ, sin θ sin φ, cos θ), a choice of three first normalized eigenfunctions is Remark 3. The mapping Φ is a particular case of the mapping

Φ λ : M → S N (λ)
proposed by Pierre Bérard in [START_REF] Bérard | Volume des ensembles nodaux des fonctions propres du laplacien[END_REF] where N (λ) is the number of eigenvalues inferior to λ. But it is important to note that the proper definition of Φ is easier in [START_REF] Bérard | Volume des ensembles nodaux des fonctions propres du laplacien[END_REF] when λ is large enough because the denominator is guaranteed to never vanish. It was also shown that Φ λ is an embedding for λ large enough. In our case the restrictions on the topology of the eigenfunctions could guarantee the diffeomorphic aspect for only 3 eigenfunctions.

Remark 4. We first proposed a sketch of proof for the injectivity of Φ by using properties of the mapping

F : p → Φ 1 (p), Φ 2 (p), Φ 3 (p) .
In particular, we used the formula ∆F(p) = 2H(p)N(p) linking laplacian of coordinates and mean curvature for hypersurfaces, combined with ∆F = (-

λ 1 Φ 1 , -λ 2 Φ 2 , -λ 3 Φ 3 )
. But it is important to see that the first formula holds if ∆ is the Laplace-Beltrami operator of F(M) (provided it is a submanifold !) which makes the second equation not true anymore. Nevertheless our initial flaw was at the origin of experimental observations that yield the conjecture:

Conjecture 4 With the previous notations and hypotheses, F(M) is a genuszero surface whose mean curvature has a constant sign.

Preliminary results

Our initial strategy to tackle the first conjecture was:

to prove first that intersection points of two nodal sets exist, thanks to global arguments. to characterize those intersections in terms of the angle between the two isolines (equivalently the gradient of the eigenfunctions), by using local results on eigenfunctions. That sort of results are known for auto-intersection of nodal sets.

Those two first steps would allow a correct definition of the mapping Φ but the diffeomorphic aspect remains the most difficult part.

Proposition 1 Let M be a genus zero surface in R 3 . We consider two eigenfunctions Φ and Ψ with only two nodal domains and different associated eigenvalues. Then their nodal sets have at least one intersection point.

λ B ΦΨ = B -Ψ ∆Φ = B ∇Ψ • ∇Φ - ∂B Φ ∇Ψ • n λ B ΦΨ = B -Φ∆Ψ = B ∇Ψ • ∇Φ - ∂B Ψ ∇Φ • n to obtain (λ -λ) B ΦΨ = ∂B Φ ∇Ψ • n - ∂B Ψ ∇Φ • n (4)
The boundary ∂B equals N (Φ) ∪ N (Ψ ). On N (Φ) (resp. N (Ψ )) we have Φ = 0 (resp. Ψ = 0) and on N (Ψ ) (resp. N (Φ)) we have also ∇Ψ •n = 0 (resp. ∇Φ•n = 0) since N (Ψ ) is a level set of Ψ (resp. Φ). Then the two integrals in the right term of (4) vanish which leads to B ΦΨ = 0. It is a contradiction since both Φ and Ψ have a constant sign on B.

Remark 5. We can find simple examples where this proposition fails when the nodal domains are more than 2. For very elongated ellipsoids the second and third eigenfunctions have respectively 3 and 4 nodal domains. Numerical simulations (not shown here) revealed that the three first eigenfunctions have isolines that are all parallel and nodal sets have no intersection points.

Remark 6. It is probably harder to find examples of surfaces for which there is only one intersection point. This singular configuration implies a colinearity of ∇Φ and ∇Ψ at the crossing point. Conversely if there is no colinearity at an intersection point, one can intuitively conclude that there is at least a second intersection point by an argument à la Jordan.

Next our initial attempt to characterize the local behavior at the intersection point followed ideas exposed in [START_REF] Cheng | Eigenfunctions and nodal sets[END_REF]. In particular Theorem 2.5 says that when the nodal lines of a given eigenfunction meet, they form an equiangular system. The proof relies on local approximations of solutions of elliptic partial differential equations close to the origin in the C ∞ case thanks to a theorem by Lipman Bers. Nevertheless this strategy appeared to be too general in our case and we were not able to obtain a relationship linking angle between nodal sets of two eigenfunctions and other quantities such as the local mean curvature, even if numerical computations may reveal interesting behaviors (see Fig 3 right).

Experimental results

Data We implemented our approach on 138 triangular meshes of cortical surfaces from the OASIS database that were segmented through FreeSurfer software. The number of vertices ranges from 106914 to 167230 vertices. Laplace-Beltrami eigenfunctions were computed through a variational formulation of Equation ( 2) and a discretization with Finite Element Methods [START_REF] Germanaud | Larger is twistier: Spectral analysis of gyrification (spangy) applied to adult brain size polymorphism[END_REF]. On Fig 1 we displayed the three first eigenfunctions and the nodal set in green for a given surface. We observed that the three first eigenfunctions had only 2 nodal domains (yellow and blue in each case). The codes were implemented in MATLAB on a Mac with a 2.6 GHZ processor. CPU time ranges from 3.76s to 6.71s.

Diffeomorphic aspects

On Fig 2 we illustrated our approach for a brain mesh at left on which the mean curvature was computed following [START_REF] Germanaud | Larger is twistier: Spectral analysis of gyrification (spangy) applied to adult brain size polymorphism[END_REF] and was represented as an image. The surface F(M) was represented on the middle with the initial curvature. The orientation followed the one of the brain at left. On the right we showed the sphere Φ(M) and the inital mean curvature with the same orientation as previously. Next we verified that for all the meshes, the number of nodal domains of the three first non-trivial eigenfunctions were exactly 2. We evaluated the number of flipped faces in percentage, ranging from 0.008% to 7.01% (average: 0.29±0.7%). Reproducibility On Fig 3 left and middle we represented the intersection points of the 3 first nodal sets for all the meshes superimposed in the Talairach space, a classical reference system in neuroimaging. We observed first that those intersection points are only 6 for each brain and secondly that they are consistently distributed in 3D. This result is of course related to the stability of the first eigenfunctions across the different brains and is more directly interpretable by looking at points than functions. On

Discussion and perspectives

In this work we have proposed a spherical mapping with preliminary mathematical and empirical results in favor of a C ∞ diffeomorphic property. Cortical surfaces were very suitable in our case because they satisfy the property proposed in our mathematical part, with a number of nodal domains equal to 2. In practice we obtained (a limited number of) flipped faces due to mesh irregularities. Moreover the computation time was 5s in average, which outperforms the recent approach in [START_REF] Lai | Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization[END_REF]. Our approach offers a correct stability across a group of brain shapes, in the sense that interesting features such as intersection of nodal sets are quite consistent. Our mapping is probably suboptimal when it comes to match brain meshes with respect to strategies using more eigenfunctions [START_REF] Lombaert | Diffeomorphic spectral matching of cortical surfaces[END_REF]. Nevertheless our method would be very appropriate for a faster initialization of a spherical mapping instead of a Gauss map and Tutte map [START_REF] Gu | Genus zero surface conformal mapping and its application to brain surface mapping[END_REF]. It can also be used "on the fly" for extensive simulations [START_REF] Lefevre | Surface smoothing: a way back in early brain morphogenesis[END_REF]. We could try to generalize our results for any kind of spherical mesh by looking for eigenfunctions associated to larger eigenvalues in the spectrum, with only 2 nodal domains. But there is no guarantee that there exist 3 eigenfunctions of this kind. We could think also to possible extensions for manifolds of higher dimension. In [START_REF] Bates | The embedding dimension of laplacian eigenfunction maps[END_REF] results have been obtained to bound the embedding dimension of Laplacian eigenfunctions map thanks to Ricci curvature and injectivity radius. A topological condition on the number of nodal domains could produce complementary views on this question.

Aknowledgments

We would like to thank the reviewers for their very constructive comments. In particular a careful observation by one the reviewer is at the origin of the remark 4 and of important modifications in the structure of the manuscript.

3 4π cos θ, 3 4π sin θ cos φ and 3 4π

 333 sin θ sin φ.

Proof.

  Let λ and λ be the two eigenvalues associated to Φ and Ψ . Since Φ and Ψ have two nodal domains, their nodal sets divide M in two parts respectively. If we assume that N (Φ) ∩ N (Ψ ) = ∅, we have a partition of M in three connected domains D 1 , D 2 , D 3 and the two nodal sets (of measure 0).whereD 1 = {p|Φ(p) > 0, Ψ (p) > 0} D 2 = {p|Φ(p) > 0, Ψ (p) < 0} D 3 = {p|Φ(p) < 0, Ψ (p) < 0}The figure on the right provides a schematic illustration of the configuration.Inspired by this figure, we define B = D 2 and use the Green formula in two different ways:

Fig 4

 4 left showed an example of such faces and we observed that they correspond to local defects in the mesh, probably affecting a proper approximation of eigenfunctions.

Fig. 2 :

 2 Fig. 2: Left: Cortical surface M and its mean curvature. Colormap goes from blue to red/yellow (positive). Middle: F(M). Right: spherical surface with the initial curvature.

  Fig 3 right we displayed the distribution of angles between nodal sets. The distribution is unimodal in one case (intersection of Φ 1 and Φ 3 ) and bimodal for the other cases.Distorsions Finally we obtained evaluations of geometric distorsions through angular errors and relative error on lengths across all the meshes (Fig 4middle and right). Those errors are discrepencies between the values measured on the initial mesh and on the spherical representation. Even if the errors are larger than for methods that explicitly minimize distorsions[START_REF] Fischl | Cortical surface-based analysis: Ii: Inflation, flattening, and a surface-based coordinate system[END_REF][START_REF] Auzias | Model-driven harmonic parameterization of the cortical surface: Hip-hop[END_REF], the average values are of the same order of magnitude.

Fig. 3 :

 3 Fig. 3: Left and middle: The 6 intersection points of the 3 first nodal sets for all the meshes superimposed in the Talairach space. A slightly transparent cortical mesh is shown to illustrate the reproducibility. Right: Distribution of angles between nodal sets of 1st and 2nd, 1st and 3rd, 2nd and 3rd eigenfunctions. On the three figures the colors are matched.

Fig. 4 :

 4 Fig. 4: From left to right: Examples of flipped triangles in green, distributions of angular error (in degree) and relative error on distances (%).

This work is funded by the Agence Nationale de la Recherche (ANR-12-JS03-001-01, "Modegy").


Amine Abdaoui
email: amin.abdaoui@lirmm.fr

Jérôme Azé
email: jerome.aze@lirmm.fr

Sandra Bringay
email: sandra.bringay@lirmm.fr

Pascal Poncelet
email: pascal.poncelet@lirmm.fr

Collaborative Content-Based Method for Estimating User Reputation in Online Forums

Keywords: Trust, reputation, online forums, social networks

come

Introduction

Online forums are areas of exchange generated by their own users. Therefore, the veracity and the quality of the posted information vary wildly according to their author. With the massive and rapid growth of these conversational social spaces, it becomes very difficult for human moderators to separate good posts from bad ones. Consequently, more and more forums are implementing automated trust and reputation metrics to infer the trustworthiness of posts and the reputation of their authors. These metrics vary from ranks based on a simple post count to more elaborated reputation systems based on collaborative ratings. If the first category of metrics tries simply to reward users according to the number of their posts, the second category uses collaborative intelligence to rate a user's posts and then aggregate these ratings to give him a reputation value [START_REF] Lampe | Slash(Dot) and Burn: Distributed Moderation in a Large Online Conversation Space[END_REF]. This idea has been successfully applied in many online forums such as news groups (Slashdot 1 ), question-answering websites (Stack Exchange 2 ), etc. However, collaborative rating is not so popular in other communities such as health forums, where users prefer to post a new message in order to thank each other rather than clicking the 'like' or 'vote up' button. The objective of this work is to use this implicit collaborative intelligence hidden in the textual content of the replies in order to infer user reputations. Many definitions of trust and computational trust exist in the literature [START_REF] Sztompka | Trust: A Sociological Theory[END_REF], [START_REF] Golbeck | Trust and Nuanced Profile Similarity in Online Social Networks[END_REF]. Here we define the trust that a user A has in another user B as: "the belief of A in the veracity of the information posted by B", and the reputation of a user A as "the aggregation of trust values given to user A". To infer such trust from textual replies and aggregate user reputations, we need to know both the recipient of each forum message and the trust expressed in it. However, the forum structure does not always provide explicit quoting or direct answering functionalities. Besides, when these functionalities are provided, many users prefer posting a message answering the whole thread rather than a one answering or quoting another specific message. In order to deal with this issue, we propose a rule based heuristic to extract an interaction network where the nodes are the users and the edges are the replying posts. Regarding the semantic evaluation of each post's content, the features that we are looking for are agreement and valorization for trust, and disagreement and depreciation for distrust. The rest of posts are considered as neutral. Finally, we propose a metric to aggregate trust and distrust replies that a user receives and infer his reputation in the forum. The proposed reputation metric considers propagation aspects by giving more weight to the replies posted by trusted users and less to the replies posted by untrusted ones.

The rest of the paper is organized as follows: section 2 presents a summary of related work that match our methods. Section 3 gives the theoretical framework, presents the corpus of our study and describes the proposed approach. Section 4 presents and discusses the obtained results using manual annotations. Finally, section 5 gives our main perspectives.

Related work

Most of the methods found in the literature in order to extract interaction networks from online communities use the HTML structure of the web page [START_REF] Adamic | Knowledge Sharing and Yahoo Answers: Everyone Knows Something[END_REF]- [START_REF] Zhang | Expertise Networks in Online Communities: Structure and Algorithms[END_REF]. They try to identify explicit message quoting. However, explicit quoting functionality is not always provided in online forums, and even when it exists many discussion participants do not use it. Moreover, a message may have many recipients. Consequently, posting it as an answer to another specific one may be insufficient. Gruzd and Haythornthwaite [START_REF] Gruzd | Automated Discovery and Analysis of Social Networks from Threaded Discussions[END_REF] presented an automatic approach to discover and analysize social networks from threaded discussions in online courses. The authors proposed a Name Entity Recognition system to extract name mentions inside the textual content of posts. After a preprocessing step (removing quotations, stop words, etc.), their method used a dictionary of names combined with manually designed linguistic rules. Another textual based method has been proposed by Forestier et al. [START_REF] Forestier | Extracting Social Networks Enriched by Using Text[END_REF] to extract a network of user interactions. They suggested to infer three types of interactions: structural relations, name citations, and text quotations. While structural relations can be inferred directly from the structure of the forum, name citations and text quotations require analyzing the textual contents. First, name citation relations have been extracted by searching pseudonyms of authors inside the posts. Then, text quotations are extracted by comparing sequences of words inside a message and the messages that have been posted before in the same thread.

On the other hand, existing trust metrics dealing with online forums can be organized in two main categories: structure-based trust metrics and content-based trust metrics. The first category focus on the structure of the website (including the number of postings, the distance between messages, quotes, citations, etc.) [START_REF] Skopik | Trust and Reputation Mining in Professional Virtual Communities[END_REF], while the second one use the textual content of messages to infer trust and reputation. For example Wanas et al. [START_REF] Wanas | Automatic Scoring of Online Discussion Posts[END_REF] automatically score posts based on their textual content. Their method is inspired from forums that use collaborative intelligence to rate posts. They tried to model how users would perceive a post as good or as bad. However, unlike Wanas, we believe that the textual content of the messages that reply to a user's post may reveal a lot of information regarding the trust or the distrust that the other users have in this post and therefore in its author. Consequently, instead of inferring a user's reputation from his own posts, we suggest to consider the messages replying to his posts. Moreover, we would like to give more importance to a reply made by a trusted user and less to a reply made by an untrusted user. A large effort has been done to include propagation aspects in order to rank webpages [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF]. Similarly, we propose a reputation metric that include these propagation aspects.

3

Materials and methods

Corpus of study

CancerDuSein.org is a French health forum specialized in breast cancer. 1,050 threads have been collected which amounts 16,961 messages posted by 675 users. It represents all the data that have been posted between October 2011 and November 2013. This forum allows users to thank each other using a "like" button, but this functionally is rarely used. Less than 1.4% of messages received at least one "like". On the other hand, CancerDuSein.org gives a rank to each user based on the number of posts since his registration. However, we believe that these ranks are not sufficient to infer reputations.

Theoretical framework

Let 𝐺 = (𝑉, 𝐸, 𝑡, 𝑟) be a multigraph where: 𝑉 is the set of users, 𝐸 is the multiset of 'reply-to' edges between these users, 𝑡 is a function that returns the transmitter of a reply, and 𝑟 is a function that returns the recipient of a reply:

𝑡 ∶ 𝐸 → 𝑉 𝑟 ∶ 𝐸 → 𝑉 𝑒 → 𝑡(𝑒) 𝑒 → 𝑟(𝑒)
Let 𝑣 ∈ 𝑉 be a user. Then 𝐸 𝑣 ⊆ 𝐸 is the set of edges that reply to the user 𝑣:

𝐸 𝑣 = {𝑒 ∈ 𝐸 ∶ 𝑟(𝑒) = 𝑣}
Let 𝐸 𝑣 + , 𝐸 𝑣 -and 𝐸 𝑣 𝑛 ⊆ 𝐸 𝑣 be the subsets of trust, distrust and neutral edges that reply to the user 𝑣. Note that 𝐸 𝑣 = 𝐸 𝑣 + ∪ 𝐸 𝑣 -∪ 𝐸 𝑣 𝑛 and 𝐸 𝑣 + ∩ 𝐸 𝑣 -∩ 𝐸 𝑣 𝑛 = ∅.

Extracting the interaction network

We suggest searching nine types of relations using manually designed heuristic rules, checked sequentially in the following order: Explicit quoting: CancerDuSein.org allows users to explicitly quote another user's post. However, only 349 posts on the Website are explicit quoting. They have been detected automatically using the HTML tag <quote>. Second posts: Messages posted at the second place in each thread have been considered as replying to the first one.

Names and pseudonyms: If a message contains the pseudonym or the name of a user who previously posted a message in the same thread, then this user is considered as the recipient of the message. The following preprocessing steps were been applied to detect names and pseudonyms: 1) Remove all non-alphabetic characters except spaces; 2) Replace all accented characters by the corresponding non-accented ones; 3) Lowercasing.

Grouped posts: If a message contains a group marker ("hello everyone", "Hi girls", "Thank you all", etc.) then all the users who previously posted in the same thread are considered as recipients for this post.

Second person pronouns:

In French, singular second person pronouns and plural second person pronouns are different. If a singular second person pronoun is used then the recipient is considered to be the author of the previous post.

Activator posts: If the activator 3 posts a new message in the same thread, we consider that his new message is adressed to all the users who posted after him. Questions: If the message contains a question, then the message is addressed to all the users who previously posted in the same thread. Answers: If there is a question posted before in the thread, the recipient is the user who posted this question. Default: If none of the above rules before are satisfied, we consider that the recipient of the message is the activator.

Predicting trust and distrust

Once the interaction network is constructed, we need to classify each post with one of the following three classes: (1) Positive: the post expresses trust to its recipient; (2) Negative: the post expresses distrust to its recipient; (3) Neutral: otherwise.

Building lists of trust and distrust expressions:

We manually created two lists of expressions that should indicate if a message expresses trust (or distrust) to its recipient. These lists have been obtained by manual annotations of a set of threads using the brat tool 4 . The annotators were asked to choose trust, distrust or neutral for each thread post and to indicate the expressions that justify their choice. These expressions have been manually validated, and then corrected, lowercased and lemmatized.

Handling negation: If a trust expression is under the scope of a negation term, it is considered as a distrust expression and vice versa.

Computing the frequencies and classifying the posts: All posts have been automatically lowercased, lemmatized, and corrected using the Aspell5 spell checker. Then, each post is assigned to the majority category carried by its words.

Proposed metrics

For each user 𝑣, we define a reputation value R(𝑣) as follows:

𝑅 𝑛+1 (𝑣) = { ∑ 𝑅 𝑛 (𝑡(𝑒)) 𝑒∈𝐸 𝑣 + ∑ 𝑅 𝑛 (𝑡(𝑒)) 𝑒∈𝐸 𝑣 + + ∑ 𝑅 𝑛 (𝑡(𝑒)) 𝑒∈𝐸 𝑣 - , 𝑖𝑓 𝐸 𝑣 𝑛 ≠ 𝐸 𝑣 0.5 , 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
This equation is recursive and can be computed by starting with reputations equal to 1 and iterating until it converges. The proposed reputation equation depends on both the number of trust and distrust replies a user receives and the reputations of the users who posted these replies.

We also define two complementary metrics: the neutral rate of the user 𝑁𝑅(𝑣), and the reliability of the computed reputation value 𝑅𝑒𝑙(𝑅(𝑣)). Where 𝑚𝑎𝑥𝑅 is a constant that represents the maximum replies that a user should receive in order to have a reliability of one in his reputation.

𝑁𝑅(𝑣) = {

Results

Evaluating the network extraction step

Two datasets were used to test our rule based heuristic. The rules have been designed according to a development set (10 threads) and tested on other 10 unseen threads.

Prior-assessment: 15 non-expert annotators, unaware of the designed rules, annotated our two datasets. Each one annotated between 1 and 5 threads so that each thread had 3 different annotators. The goal was to find the recipient(s) of each post without knowing the results of our heuristic.

Post-assessment: Three expert annotators (the authors) annotated the links found by the heuristic in the two datasets. The goal was to validate or not the links found automatically with the possibility of adding a link which was not found by the heuristic.

Evaluation: Using these annotations, the quality of the developed heuristic was evaluated. The links obtained automatically were compared with those obtained from the annotations by considering only those that have been validated by two or more annotators (a majority vote). We compare the results of the prior-assesment and the post-assesment with two baselines. The first one considers the activator of the thread as the recipeint of all the messages posted in this thread (activator). The second baseline considers the author of the previous message as the recipient (previous). Discussion: Our heuristic obtained higher F1-scores than both baselines. The results obtained using a post-assessment are better than those obtained using priorassessment. This observation can be explained by the nature of the prior-assessment itself which gives much more freedom in choosing the links. Surprisingly, the results obtained on the test set have been better than those obtained on the development set.

Evaluating the trust prediction step

Two new datasets have been used to evaluate the automatic trust inference. Unlike the first step where both datasets had prior-assessment and post-assessment, here priorassessment has been done only for the first dataset and post-assessment has been done only for the second one.

Prior-assessment: Three annotators annotated the trust expressed in 97 messages without knowing the results of the automatic system. The agreement between them was less than the recipient assessment but still acceptable.

Post-assessment:

The same three annotators annotated the trust expressed in 102 other messages. The results of the automatic system have been displayed, and annotators can chose the same value of trust or another one.

Evaluation:

The results obtained by comparing the classification made by the system with the annotations (majority vote) are presented Table 2.

Table 2. Precision, recall and F1-score of the trust inference system using prior-assessment and post-assessment Discussion: The results obtained for the trust class are good but the recall is higher than the precision using both assessments. Therefore, our list of trust expressions seems to be sufficient to find the majority of trust posts. Moreover, the results obtained on the neutral class are also good, but the precision is higher than the recall.

Finally, the results obtained on the distrust class have been the worst but it is difficult to make conclusions regarding the small number of distrust posts.

Evaluating the proposed metric

In our experiments, the constant 𝑚𝑎𝑥𝑅 has been fixed to the average number of replies received by each user. The reputations of 157 users had reliabilities greater than 0.5.

Fig. 1.

User reputations that had more than 0.5 of reliability according to the number of posts Discussion: Figure 1 shows that all considered reputations are greater than 0.7. This observation can be explained by the fact that CancerDuSein.org is a forum where little distrust is expressed, since the users aim at first to exchange emotional support. Moreover, the user reputations seem to be independent from the number of posted messages, which reinforces our opinion that the number of postings do not represent a good estimation of user reputations or ranks.

Conclusion

Many perspectives can be considered in order to improve the work and to better explore the idea. First, the user's reputation can be computed for each thread topic in addition to the global reputation in the whole forum. In fact, the user's expertise may change according to the discussed topic. Then, we are now scrolling other French forums in order to apply our method on a larger number of forums. Finally, we are planning to compare ourselves to PageRank or HITS based models built on the user interaction network.

Table 1 .

 1 Precision (P), recall (R) and F1-score (F1) of baselines and our heuristic obtained on both dataset using prior and post assessments

	P	R	F1

http://www.slashdot.org/

http://www.stackexchange.com/

The user who opened the thread by posting the first message.

www.brat.nlplab.org

www.aspell.net

6

Bibliography