Dimitrios Kravvaris

Katia Lida Kermanidis

Speakers' Language Characteristics Analysis of Online Educational Videos

Keywords: Educational video, transcript, popularity, clustering, k-means

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The advancement of social media adds a large amount of data on the web on a daily basis and especially in content-based communities such as YouTube and Daily Motion.

A very large number of videos in social media concern education, and in many cases, constitute part of the traditional online courses [START_REF] Moel De | Expanding the usability of recorded lectures[END_REF] and the upcoming massive open online courses [START_REF] Waldrop | Massive open online courses, aka MOOCs, transform higher education and science[END_REF]. They are usually created by universities, companies, organizations or even individual users. In many cases transcripts of the video lectures are available. The present research focuses on the study of educational videos from social media, oriented both to verbal content and to metadata of the pages that contain them. The present study thus, examines questions concerning issues such as why some educational videos are more popular than others and what are the characteristics that make a video popular. The issues arising are both interesting and complex. Our research innovation is that we examine them based on the audio language used in the educational videos. Through a qualitative study of the transcripts of the videos we extract the characteristics of the language used by the speakers (i.e. pace of speech, sentence length, commas, range of vocabulary etc.), which will be utilized in order to designate the speakers into to two basic types of speakers. These two types are based on whether the videos they take part in are popular or not. At this point another interesting question arises which we had to answer as well, i.e. what are these characteristics that define the popularity of a video after all, and how we can measure it? Using the metadata of the web pages that contain the videos we moved to an analysis related to the issue and propose a formula for defining video popularity. Finding the language characteristics of the speakers of the popular educational videos is very important both for the educational organizations and the individuals as creators of educational videos and for the scientific community since this study contributes to the research of linguistic data in the social media.

In the first part of the study we present relevant studies and point out how our research differs. In the second part we analyze the concept of popularity of online videos and we propose a formula for its estimation. In the third part we present the methodology used and include a thorough analysis of the characteristics used in our research. In the fourth part we present the experiments conducted as well as a commentary on the findings. Finally in the last part we present the findings of our research and how these can be utilized.

Related Work

As far as the videos are concerned, a lot of studies have been conducted in various field studies concerning video classification [START_REF] Gibbon | Introduction to Video Search Engines[END_REF], [START_REF] Filippova | Improved video categorization from text metadata and user comments[END_REF] in order for the videos to fall automatically in certain categories using video and text data. Studies that concern the searching of videos and more specifically studies focusing on information retrieval browsing very large document collections [START_REF] Cutting | Scatter/gather: a cluster-based approach to browsing large document collections[END_REF] and video retrieval on the web utilizing the integration of multiple features [START_REF] Yang | Searching for flash movies on the web: A content and context based framework[END_REF], [START_REF] Hindle | Clustering web video search results based on integration of multiple features[END_REF]. Finally, there have been studies that focus on video comparison [START_REF] Cheung | Efficient video similarity measurement with video signature[END_REF] in order to estimate the percentage of visually similar frames. The special characteristic of our research concerns the transcript of what the speakers say in each video. This has been used in other relevant studies concerning text mining such as text classification [START_REF] Passini | A Strategy for Training Set Selection in Text Classification Problems[END_REF][START_REF] Kiritchenko | Email classification with co-training[END_REF] and text clustering [START_REF] Amine | Evaluation of text clustering methods using wordnet[END_REF], [START_REF] Shehata | An efficient concept-based mining model for enhancing text clustering[END_REF], as well as studies concerning natural language processing [START_REF] Collobert | Natural language processing (almost) from scratch[END_REF][START_REF] Friederici | The brain basis of language processing: from structure to function[END_REF]. Our research was inspired by the research conducted by Jin and Murakami [START_REF] Jin | Authors' characteristic writing styles as seen through their use of commas[END_REF] who studied the authors' characteristic writing styles as seen through their use of commas.

When it comes to social media, and more specifically YouTube, it has been shown that the introduction of videos in higher education has opened new horizons both to the educators who want to contribute to education and to learners who want to learn [START_REF] Gilroy | Higher education migrates to YouTube and social networks[END_REF][START_REF] Selwyn | Social media in higher education[END_REF]. Thus, a new effort is being made in order for success in learning to be maximized. At this point our study comes in order to examine the educational videos in relation to their popularity on the YouTube. More specifically, we use the clustering method on metadata and on content data of the transcript of the video. Our purpose is to divide the videos in two categories: the most popular video category and the least popular videos category, and then to study which are qualitative speech characteristics of each category, regardless of the subject content of the videos.

Video Popularity

YouTube contains quite a few characteristics that could be utilized in order to define the popularity of a video, such as the number of views, of likes, of dislikes, the users' comments, the number of those who have chosen it as favorite and finally the number of video responses [START_REF] Chatzopoulou | A first step towards understanding popularity in youtube[END_REF][START_REF] Figueiredo | On the Dynamics of Social Media Popularity: A YouTube Case Study[END_REF]. The favorites and responses are the least used characteristics by the users. The views characteristic refers to the number of times the video has been viewed, while the likes, dislikes and comments can be used by registered users only.

Especially for comments we should mention that we face two problems: the first concerns the complicated and time consuming procedure required in order to characterize the users' opinion [START_REF] Liu | Sentiment analysis and opinion mining[END_REF][START_REF] Chen | AI and opinion mining[END_REF], and the second concerns the ability to comment the video lecture, which could be deactivated by the creator and, thus, we would have no relevant comments. Thus, in order to be fair concerning the videos in focus we chose to keep the characteristics that are definitely present and that attribute a positive value to the video. We ended up, therefore, using the views and the likes, in order to estimate the popularity of the videos. These two characteristics are based on human actions that show how many times a video has been viewed and how many people liked it.

We define as popularity P of a video i, which belongs to a certain category c, the normalized value of likes L and the number of views V according to formula

𝑃 𝑖,𝑐 = 𝐿 𝑖 𝑚𝑎𝑥𝐿 𝑐 + 𝑉 𝑖 𝑚𝑎𝑥𝑉 𝑐
where maxL and maxV are the maximum values of likes and views correspondingly, that were observed in the particular video category. Since designating the value of P as high or low is subjective, we used the mathematical method of median [START_REF] Beliakov | The median and its extensions[END_REF]. The median is a measure of central tendency. In our case it represents the value for which half of videos' popularity are higher and the other half are lower. In that way splitting in half the videos of high and low popularity we can use machine learning methods in order to extract knowledge concerning what makes a video more popular than another.

We chose not to use the lifetime of a video on YouTube as a parameter in estimating the popularity of a video, because there seemed to be a problem: The new videos with few likes and views seemed to be more popular which was wrong because older videos had more likes and views.

Methodology

Data

Our data were collected from YouTube, which is the third most visited social media site worldwide [START_REF] Wattenhofer | The YouTube Social Network[END_REF] and the largest provider of videos [START_REF] Moran | Teaching, Learning, and Sharing: How Today's Higher Education Faculty Use Social Media[END_REF]. YouTube provides its users with a specific space to upload videos that fall into the category of educational videos 1 .

Searching through the category of Education of YouTube by inserting keywords from different scientific fields such as computer science, physics, medicine, art, health, philosophy, energy and others, 20830 videos were collected among which 1108 (5.3%) had English transcripts. The total duration of the 1108 videos used in our research is 473 hours and have over 242 million views in total. From each video metadata attributes were collected using the YouTube API v2 [START_REF] Padilla | Beginning Zend Framework[END_REF] as well as qualitative attributes of speech (after processing the transcripts of videos). Grzybek's et al. [START_REF] Grzybek | The relationship of word length and sentence length: the inter-textual perspective[END_REF] and Mahowald's et al. [START_REF] Mahowald | Info/information theory: Speakers choose shorter words in predictive contexts[END_REF] research shows the importance of words, Hill's and Murray's research [START_REF] Hill | Commas and spaces: The point of punctuation[END_REF] note the value of commas and Palmer's study [START_REF] Palmer | Tokenisation and sentence segmentation, chapter 2[END_REF] highlights the importance of sentence segmentation of a natural language text. Thus, we used these important structural elements for the definition of our qualitative attributes. Below we refer to these attributes and their description in categories.  Metadata In this category there are two attributes. The first one is the Duration attribute which refers to the second of the total appearance of the online video. The second attribute is the AuthorUri which concerns the unique identity of the owner of the video on YouTube, which may refer to a University, an educational organization or an individual. Both attributes come from metadata of the YouTube page, which contain the video in focus.

 Words

The words category contains the qualitative characteristics of the transcript of the educational video. More analytically, the attribute NumOfWords concerns the number of words used by the speakers of the video. This attribute shows the real duration of speech, since we count neither the duration of speech, which contains times pauses, nor the duration of a video which contains other elements such as ads or short introductions before the educational video begins. The second attribute Avg-WordLength concerns the average word length. This attribute helps us form a complete view of the net length of speech we referred to earlier, since videos differ also in the length of words used, besides the number of words.

 Transcript Sentences

This category contains four attributes which concern: the number of the transcript sentences (NumOfSent), the minimum sentence length in characters (Min-SentLength), the average sentence length in characters (AvgSentLength) and the maximum sentence length in characters (MaxSentLength). All these four attributes describe the number and the length of the transcript sentences. Thus, through the transcripts we can extract qualitative information concerning the sentence length used by the speakers, supposing that longer sentences are more likely to contain more information for the listener that shorter ones.

 Sentences complexity

This category contains two attributes concerning the commas contained in the transcripts. The NumOfCommas attribute refers to the total number of commas contained in the transcript while the AvgNumOfCommasPerSent attribute shows the average number of commas per sentence. Commas are used in order to avoid ambiguity. They are mainly used in lists, for separation causes, to set off certain adverbs at the beginning of a sentence and in parenthetical phrases. All the above indicate that a sentence with commas is more complicated in structure and in meaning that one without commas [START_REF] Wiegand | Creating complex sentence structure[END_REF].

 Vocabulary

This category contains the NumOfUniqueWords attribute which shows the number of unique words in the transcript. The more unique words a transcript contains the wider the vocabulary used by the speaker, without it necessarily being more advanced since the videos come from different scientific fields and contain the domainspecific terminology of the corresponding fields.

 Flow of words

This category contains two attributes: the MicroRhythm attribute that refers to the micro flow of words and the MacroRhythm attribute which refers to the macro flow of words. More analytically, the MicroRhythm attribute measures the average flow of words in the time (measured in seconds) the corresponding transcript text is displayed on the screen, and the MacroRhythm attribute measures the flow of words in the total time the transcript texts are displayed on the screen.

 Evaluation

This category contains the evaluation attribute of our study named Popularity. This attribute is used for the binary classification of the educational videos. It has two values high and low as it was described in the previous section of the present paper.

Experimental Procedure

In the beginning we conduct a statistical analysis of our data. At this point we study any extreme cases and we suggest solutions to deal with them. The purpose is to preprocess our data so as to avoid problems during the experimental procedure, such as missing values in the data of our datasets.

In the experimental procedure we used the Weka version 3.6.10 software [START_REF] Weka | Data Mining Software in Java[END_REF]. We employed unsupervised learning methods for the clustering experiments. More specifically, a centroid-based clustering algorithm [START_REF] Kanungo | The analysis of a simple k-means clustering algorithm[END_REF] using SimpleKMeans, with the Euclidian distance function [START_REF] Kanungo | An efficient k-means clustering algorithm: Analysis and implementation[END_REF] has been used. The SimpleKMeans method is quite suitable for our experiments since it is easy to understand and to explain its clustering outcome [START_REF] Vora | A Survey on K-mean Clustering and Particle Swarm Optimization[END_REF]. Two clusters were chosen for the value of K (in SimpleKmeans), since we have two class values: high/low popularity. Moreover, we chose to use the clustering mode classes-to-clusters evaluation [START_REF] Färber | On using class-labels in evaluation of clusterings[END_REF], which assigns classes to the clusters based on majority and computes the classification error of the videos that have different value from the class value of the cluster they belong to. With the above procedure, on the one hand, we can study the differences between the qualitative characteristics of the videos (that come from the transcript), and, on the other hand, to evaluate how these characteristics can define the videos' popularity.

5

Experimental Results

Data Analysis

While analyzing our data we found out that there is a great difference in the duration of videos and for this reason we have discretized their duration in 10-minute intervals. The results are presented in figure 1 below, which shows the number of videos in each time category they belong to. We find that the greatest number of educational videos fall into the 1 to 10 minute category (47.5% of videos), while the 41 to 50 minute and 51 to 60 minute categories contain 25% of videos in total. In the first case, there are short videos concerning the time duration, while in the second case long ones, for this reason, thus, we divided the initial dataset into two new ones based on their duration. In this way we can conduct our study on data that have similar characteristics.

Short Videos

After conducting our experiment on the dataset that contains short (in terms of duration) videos we extract the following results shown on table 1. The videos that belong to Cluster-0 are in majority of high popularity, while the videos that belong to Cluster-1 are of low popularity. It should be mentioned that 66.54% of the videos have been correctly clustered. Considering that we have to do with data that are based on the human activity of speech the percentage can be characterized as highly positive. Based on the qualitative characteristics of the transcripts of the video speakers, as they were described above, we can describe the types of the speakers of each cluster. More specifically, the speakers of the popular videos (Cluster-0) present the following language characteristics, compared to speakers of the less popular videos (Cluster-1).  Greater net length of speech (NumOfWords, AvgWordLength).  Sentences with more information for the listener (NumOfSent, MaxSentLength, Min-SentLength, AvgSentLength).  More complex sentences (NumOfCommas, AvgNumOfCommasPerSent).  Greater number of unique words (NumOfUniqueWords).  Faster pace of flow of speech (MicroRhythm, MacroRhythm). Thus, on the case of short videos, in order for the educational video to be popular among internet users, the speaker should speak at a fast pace and use long and complex sentences, so as to take greater advantage of the time he is given to inform the audience about the issue in focus. The fact that users prefer to listen to a fast pace speaker is very interesting which means that they are closely paying attention to what the speaker is talking about and they are fully focused on the subject of interest in order to follow the speaker's speech pace.

Long Videos

From the experiment conducted on the dataset that contains long (in terms of duration) videos we extract the following results shown on table 2. In this case, also, as was also shown in the previous experiment, videos that belong to Cluster-0 are in majority of high popularity, while videos that belong to Cluster-1 are of low popularity. The correctly clustered videos reach 86.36%, which is extremely positive for the classification of the videos. 1343,6555 Following the same logic, as in the previous case of short videos, we can describe the types of speakers of every cluster. In this way, we can record comparatively the language characteristics of the speakers of the popular videos (Cluster-0) compared to the speakers of the less popular videos (Cluster-1). We find out that the speakers of the popular videos have:  Practical the same length of speech as the speakers of the less popular videos.

(NumOfWords, AvgWordLength).  Sentences containing less information for the listener (NumOfSent, MaxSentLength, MinSentLength, AvgSentLength).  More complex sentences (NumOfCommas, AvgNumOfCommasPerSent).  Lower number of unique words (NumOfUniqueWords).  Faster pace of micro flow of words (MicroRhythm), and almost the same pace of macro flow of words (MacroRhythm) as the speakers of less popular videos. This means that on average the speaker in a popular video uses more words at a given period of time. To sum up, in order for a long video to be frequently viewed and positively reviewed, the speaker has to speak at a fast pace, to limit his vocabulary to the issue in question and to use complex sentences, which, however, do not carry too much information. In that way the user stays focused on the speaker's words and does not get confused or bored while watching the video.

Similarities

Based on our findings, there are similarities between the characteristics of the speakers of the popular short videos and the popular long videos as these are shown in column Cluster-0 of tables 1 and 2. The similarities concern: a) the pace of speech, where we see that the speakers use almost the same number of words at a given period of time and b) the complexity of the sentences, where it is shown that speakers prefer to use more complicated in structure and in meaning sentences for their listeners. Thus, we conclude that, in order to create a popular educational video, regardless of its duration, the main speaker has to have a good command of the audio language and to be fully aware of the lecture subject so as to be able to express complex issues at a fast pace of speech. Knowing that the level of knowledge of the English language of the video listeners varies, the characteristics mentioned above seem to be very important in order for the lecture subject to be effective.

Conclusion

In our research we studied the language characteristics that a speaker of an educational video should have in order for the video to be more acceptable by the users of the social media. The whole procedure was based, on the one hand, on the qualitative research of the video transcripts, from which the language characteristics were extracted, and, on the other hand, on the classification of the videos in categories according to their popularity.

The popularity of the videos constituted the first part of an interesting analysis for our research. The formula suggested was based on the likes and views attributes, which besides YouTube, appear in other social media. The classification of the videos in most popular ones and least popular ones, based on the median method, ensured that this classification was objective.

Through our experimental procedure one can find out that in short videos speakers use speech more effectively. Speaking at a faster pace and using sentences with more information do not allow time to be wasted and help keep their listeners' interest. On the other hand, in popular long videos the speech contains more complex sentences than the speakers in popular videos. Finally, we show that both type of speakers in long and short popular videos have similar fast pace of speech. Their common characteristic that concerns the fast pace of speech seems to be interesting and urges us to study further what the pace should be in order for a listener to be satisfied.

Τhe education industry uses videos as a basic tool. Our research shows that new knowledge can be extracted through machine learning techniques from the large quantity of free data in social media. In this way it is possible to identify the factors that can conduce to creating more popular and higher quality educational videos.

Fig. 1 .

 1 Fig. 1. Distribution of videos based on time duration

Table 1 .

 1 Clustering results for short videos.

		600
		500
	videos	400
	Number of	200 300
		100
		0
		1 to 10 11 to 20 21 to 30 31 to 40 41 to 50 51 to 60 61 to 70 71 to 80 81+
			Video duration in minutes
	Attribute	Cluster-0 (209 videos)	Cluster-1 (317 videos)
	Duration	398,0909	179,7476
	AuthorUri	TEDEducation	Udacity
	MicroRhythm	3,2269	3,0254
	MacroRhythm	2,9277	2,6793
	NumOfWords	1064,9809	417,3817
	AvgWordLength	4,5849	4,6857
	NumOfSent	64,8852	27,1735
	MaxSentLength	479,3923	323,6498
	MinSentLength	19,3541	35,2114
	AvgSentLength	141,7913	124,3602
	NumOfCommas	56,3636	19,4795
	AvgNumOfCommasPerSent	0,9938	0,7671
	NumOfUniqueWords	383,6268	200,6467

Table 2 .

 2 Clustering results for long videos.

	Attribute	Cluster-0 (167 videos)	Cluster-1 (119 videos)
	Duration	2965,9641	2974,3529
	AuthorUri	MIT	YaleCourses
	MicroRhythm	3,0471	2,6756
	MacroRhythm	2,3240	2,4421
	NumOfWords	6779,0719	6684,5630
	AvgWordLength	4,2704	4,6612
	NumOfSent	465,0659	364,9244
	MaxSentLength	392,9521	818,7227
	MinSentLength	1,9162	10,3193
	AvgSentLength	77,5774	130,3118
	NumOfCommas	461,1617	322,4202
	AvgNumOfCommasPerSent	1,0453	0,9979
	NumOfUniqueWords	974,8323

http://www.youtube.com/education


Andreas Kanavos
email: kanavos@ceid.upatras.gr

Isidoros Perikos
email: perikos@ceid.upatras.gr

Pantelis Vikatos
email: vikatos@ceid.upatras.gr

Ioannis Hatzilygeroudis

Christos Makris
email: makri@ceid.upatras.gr

Athanasios Tsakalidis

Modeling ReTweet Diffusion Using Emotional Content

Keywords: Tweet Emotion Recognition, Microblogging, ReTweet Modeling, Sentiment Analysis

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

During the last years, Twitter has become the most popular microblogging platform all over the world. It is considered to be the most fast spreading and growing social network having more than 500 millions of users. Every day a vast amount of tweet information is published by the users of the platform to the public or to selected circles of their contacts. This information comes in the form of small posts which is allowed to have up to 140 characters each. The rise of Twitter has completely changed the users, transforming them from simple passive information searchers and consumers to active producers. This massive and continuous stream of Twitter data posts reflects the users opinions and reactions to phenomena from political events all over the world to consumer products [START_REF] Suttles | Distant Supervision for Emotion Classification with Discrete Binary Values[END_REF]. It is well pointed that Twitter posts relate to the user's behavior and often convey substantial information about the user's emotional state [START_REF] Bollen | Modeling Public Mood and Emotion: Twitter Sentiment and Socio-Economic Phenomena[END_REF].

The users' posts in Twitter, unlike other networks, have some special characteristics. The short length that the posts are allowed to have, results in more expressive emotional statements. Also, users express their daily thoughts in real time, something that often concludes in posting far more emotional expressions than might normally occur [START_REF] Roberts | EmpaTweet: Annotating and Detecting Emotions on Twitter[END_REF]. Analyzing tweets and recognizing their emotional content is a very interesting and challenging topic in the microblogging area. It is necessary for deeper understanding of people behavior but simultaneously for describing public attitude towards different events and topics as well. It therefore could be helpful in predicting the spread of posts and information diffusion in the network.

A fundamental way of information spread in the Twitter network is the ReTweets. A ReTweet happens when a user forwards a message they receive to circles of their followers. In addition, a ReTweet indicates that the user who retweets the post, found it very interesting and worth sharing with others [START_REF] Naveed | Bad News Travel Fast: A Content-based Analysis of Interestingness on Twitter[END_REF]. The way that a post is retweeted among users in the network can describe the amount of interest drawn upon it [START_REF] Naveed | Searching Microblogs: Coping with Sparsity and Document Quality[END_REF] and also its adoption by the users who made the ReTweets. Since ReTweets provide the most powerful clue that users find post information interesting, it would be important to study, analyze and model the way that information is spread in Twitter through ReTweets. Being able to model and predict the ReTweet occurrences of a given post is important for understanding and controlling information diffusion on Twitter [START_REF] Can | Predicting ReTweet Count Using Visual Cues[END_REF].

Emotion representation is a key aspect of an emotional recognition system. The most popular models for representing emotions are the categorical and the dimensional model ones. The categorical model assumes a finite number of basic, discrete emotions, each of which serves for a specific purpose. On the other hand, the dimensional model represents emotions on a dimensional approach, where an emotional space is created and each emotion lies in this particular space. A very popular categorical model is the Ekman emotion model [START_REF] Ekman | Basic Emotions[END_REF], which specifies six basic human emotions: "anger, disgust, fear, happiness, sadness, surprise". It has been used in several studies/systems that recognize emotional text and facial expressions related to these emotional states.

In this paper we present a work on modeling and predicting the information spread on Twitter based on its emotional content. More specifically, we propose the use of emotional behavior in each ReTweet as an additional parameter to user's social media analysis. With use of the Ekman emotion model, we can identify whether one or more out of the six basic human emotions exists or not. The aim of this system is to model the information spread in form of ReTweets in the network and in following, to predict the likelihood and the way that a new post will be retweeted by the users in a particular network. More precisely, we want to perform the following steps in the below mentioned order: firstly understanding Twitter topic, then modeling the ReTweet information flow in Twitter network and finally predicting when a new post will be retweeted and though the way of how it will be spread in the network (e.g. given a new post with particular emotional content, we want to predict whether it will be retweeted by other Twitter users; and if so, we would like to learn its depth and width in the Twitter network).

The remainder of the paper is structured as follows: Section 2 presents the related work. Section 3 presents our model while in section 4 we utilize our experiments. Moreover, section 5 presents the evaluation experiments conducted and the results gathered. Ultimately, section 6 presents conclusions and draws directions for future work.

The spread of Twitter and other social networks has attracted significant interest in sentiment analysis methods for recognizing textual opinions, statement polarity and emotions. Researchers have developed applications to identify whether a text is subjective or objective, and whether any opinion expressed is positive or negative [START_REF] Pang | Opinion Mining and Sentiment Analysis[END_REF]. In [START_REF] Roberts | EmpaTweet: Annotating and Detecting Emotions on Twitter[END_REF] authors investigated feature sets to classify emotions in Twitter and presented an analysis of different linguistic styles people use to express their emotions.

There is a lot of research interest in studying different types of information dissemination processes on large graphs and social networks. Naveed et al. [START_REF] Naveed | Bad News Travel Fast: A Content-based Analysis of Interestingness on Twitter[END_REF] analyze tweet posts and forecast for a given post the likelihood of being retweeted on its content. Authors indicate that tweets containing negative emoticons are more likely to be retweeted than tweets with positive emoticons. In [START_REF] Bakshy | The Role of Social Networks in Information Diffusion[END_REF] authors study the way that information diffuses in Twitter. A dataset of 1.6 million Twitter users was used in order to identify common information patterns of their tweets and many of these patterns involved transmission with third and fourth hop users. Also, the authors indicate that although stronger ties are individually more influential, the more abundant weak ties are responsible for the propagation of novel information.

In [START_REF] Goel | The Structure of Online Diffusion Networks[END_REF] the authors study the online social networks of the social news aggregator Digg as well as the microblogging service Twitter, both of which are used by people in order to share news stories and other content with their followers. The work indicates that the spread of information could be modeled as an epidemic process and though could have a non-conservative favor.

In addition, in [START_REF] Bollen | Modeling Public Mood and Emotion: Twitter Sentiment and Socio-Economic Phenomena[END_REF] authors utilized the Profile of Mood States psychometric method so as to analyze Twitter posts and reached the conclusion that "the events in the social, political, cultural and economic sphere do have significant, immediate and highly specific effect on the various dimensions of public mood". Commercial companies and associations could exploit Twitter for marketing purposes, as it provides an effective medium for propagating recommendations through users with similar interests. Moreover, viral marketers could exploit models of user interaction to spread their content or promotions quickly and widely [START_REF] Leskovec | The Dynamics of Viral Marketing[END_REF].

Peng et al. [START_REF] Peng | Retweet Modeling Using Conditional Random Fields[END_REF] study the ReTweet occurrences in Twitter and proposed a method utilizing Conditional Random Fields (CRF) so as to predict how likely a tweet will be retweeted by a user. The analyzed tweets and their prediction model take into account network aspects and post content parameters like the topic similarity of posts with the user's interest, the existence of URL and hashtags as well as mentions in the posts. In [START_REF] Can | Predicting ReTweet Count Using Visual Cues[END_REF], authors address the ReTweet modeling topic and focus on tweets that contain links to images shared through twitpic.com. They analyze images and extract correlated low-level and high-level image features in their predictive model for ReTweet count.

Finally, Petrovic et al. in [START_REF] Petrovic | RT to Win! Predicting Message Propagation in Twitter[END_REF] predict ReTweet occurrences by using a machine learning approach based on the passive-aggressive algorithm. Authors found that there is a substantial gain in using tweet content specific features and their pre-diction model takes into account user social features and tweet features. Social features concern user's number of followers, friends, statuses, favorites, the number of the times the user was listed, if the user is verified, and if the user's language is English; while tweet features concern the existence and the number of hashtags, mentions, URLs, trending words in the tweet, the length of the tweet, the novelty, the actual words in the tweet and last if the tweet is a reply. As far as we are aware, our work is primarily to investigate the impact of tweets emotional content, as determined on Ekman's scale, on its diffusion in the network in the form of ReTweets.

Model Overview

In our model, we want to predict whether a tweet with specific emotional states based on a user's recent tweets and specific user's Twitter analytics features, can be categorized in a particular class concerning the possibility of being retweeted by other users. We can specify this problem as classification one, because each class will consist of specific thresholds in each category. Furthermore, we want to predict whether the tweets from a specific user can be forwarded deep in the Twitter graph; meaning that many other users will forward this tweet (via ReTweeting).

The overall architecture of the proposed system is depicted in Figure 1 while the proposed modules and sub-modules of our model are modulated in the following steps.

User Metrics Calculation

Width

Prediction of ReTweeting Twitter Crawler

Depth Tweet Emotional Analysis

Fig. 1. Architecture of the Model

User Metrics Calculation

The social media crawler samples the Twitter and identifies a specific number of users who have posted a tweet in a specific topic during a specific time period (e.g. keyword search query). More specifically, the implementation of our method goes as follows: initially, we retrieve users who have posted a tweet within the given time period. Subsequently, we download their k last tweets (e.g. for our experiments k = 20), in order to give them as input in our Tweet Emotional Analysis module. Furthermore, from Twitter we can extract 6 basic user features as they can better describe user communication behavior in Twitter. The followers of a user, the number of contributions to the social network and the frequency of contribution are some aspects that differentiate user behavior. The set of 6 features contain the number of Followers, the number of Direct Tweets, the number of ReTweets, the number of Conversational Tweets (e.g. if a user replies to a post), the Frequency of user's Tweets (e.g. how "often" an author posts Tweets) and finally the number of Hashtag Keywords (e.g. words starting with the symbol # and with use of this symbol, a user can specify the thematic category of their specific Tweet) as in [START_REF] Kafeza | Identifying Personality-based Communities in Social Networks[END_REF], [START_REF] Kafeza | T-PICE: Twitter Personality based Influential Communities Extraction System[END_REF]. These metrics describe the user communication behavior in Twitter.

Tweet Emotional Analysis

In this subsection, the emotional analysis of the tweets based on the tool presented in [START_REF] Perikos | Recognizing Emotion Presence in Natural Language Sentences[END_REF] is described. The tool recognizes the existence of the six basic emotions proposed by Ekman [START_REF] Ekman | Basic Emotions[END_REF] in natural language sentences. Tweets texts are pre-processed (remove images, URLs, etc) and in following, the structure's analysis of the tweet using Stanford parser and Tree Tagger is conducted. Also, lexical resources such as the WordNet Affect [START_REF] Strapparava | WordNet Affect: an Affective Extension of WordNet[END_REF] are used to spot emotional words. Moreover, the tool analyses each word's emotional dependencies in order to specify its emotional strength and determine the overall emotional status of tweets based on its dependency graph. This module is shown in Figure 2.

We have extracted some tweets during a given period of time for a specific topic (e.g. #MH370 ). In following, we try to identify the emotional state of tweets (or specify their emotional content) through the aforementioned six basic emotions. Tweets are analyzed and for each one the existence of each basic emotion is determined. Since we ensure whether these tweets have a sentiment or are neutral (a tweet is neutral when no category of Ekman psychometric test appears in this tweet), we calculate the depth as well as the width (if any) of all tweets (e.g. ReTweeting depth and width). More specifically, we count the number that a tweet has been retweeted (width = 1); then if someone sees the ReTweet and decides to make a ReTweet of the above ReTweet, the width takes value 2, and so on. Suppose we have a tweet from a user X and many Twitter users want to share this tweet among their followers. So, for example, n users share this post. In the first step, our algorithm has width = 1 and depth = n. What is more, a user who "follows" one out of these n users wants to share the same ReTweet; they use this ReTweet in their profile and consecutively, the width for the specific post becomes 2.

Implementation

We based our experiments on Twitter and used Twitter API to collect tweets and calculate users metrics. We implemented our Twitter network using Twit-ter4J1 . We collected tweets published for a specific period of time (e.g. a couple of hours) for the keyword #MH370 concerning Malaysia Airlines Flight 370 disappearance. Our Twitter data consists of 13000 tweets, authored by 11130 users.

The prediction of ReTweeting is based on the emotional content of the tweets using Ekman model but also the user communication behavior. Each tweet is represented as a vector; this vector includes the existence of each emotion which is produced by Ekman's model as well as Twitter metrics of the user that produce the certain tweet such as their followers, the number of tweets, ReTweets, conversations, hashtag keywords and finally the frequency of posts.

Analysing the retrieved tweets, we extract the length of maximum path of each ReTweet. Moreover, the number of followers that have retweeted each tweet is additionally computed. We use the following approach to classify the ReTweets of a certain tweet. According to the categories of ReTweeting in Table 2, we predict the depth as well as the width of ReTweeting. Several classifiers are trained using the dataset of vectors. Classification is evaluated based on the separation of the dataset to training and test set. Furthermore, the approach we used was K-Fold Cross-Validation (e.g. K = 10 Fold). The classifiers that were chosen, are evaluated with the use of F-Measure metric. The classifiers were chosen from "bayes", "functions", "lazy", "trees" and "rules" categories of the Weka library2 , which is a widely used toolkit for machine learning and data mining such as classification, regression, clustering and feature selection. The classifiers from Weka are used with their default settings. The results are introduced in following section.

Evaluation

The reported values in the charts for the classification models are recorded as AdaBoost, IBK, J48, JRip, Multilayer Perceptron, Naive Bayes, PART, Rota-tionForest and SMO. The results of F-Measure for each classifier are illustrated in Table 3; where we select the best classifiers either for depth or width, depicted in bold in the table. We can observe that J48 achieves the highest F-Measure value for both the depth as well as the width ReTweeting. In the case of depth, RotationForest is selected as the next best classifier, where in case of width, JRip accomplishes the same performance as J48. Furthermore, Figures 3 and4 depict the values of F-Measure for each classifier for depth and width accordingly.

Additionally, we evaluate the model using posts with different emotion for the same user's behavior in order to consider the influence of emotion in the diffusion of ReTweets based on our model. Table 4 shows that tweets which are angry or sad are prone to be retweeted rather than tweets that are happy or neutral. In addition, Figure 5 presents the percentage of instances diffusion for each emotion. The bigger a circle is, the bigger diffusion exists for the according Ekman emotional state. In our work we present a methodology to model and predict the depth and width of diffusion of a tweet with a machine learning approach. More specifically, based on the result of the Ekman model (e.g. six basic human emotions represented by six emotional states) as well the Twitter analytics features, we can estimate the depth's and width's category of each ReTweet with a classification error; as we have already mentioned, our aim is to investigate the impact that information has in the network in the form of ReTweets. We also examine the influence of emotion in the diffusion, where we find out that posts containing negative emotional states are more likely to be retweeted than tweets with positive or neutral emotional states.

As future work, we plan to incorporate apart from the existence of any basic Ekman's state, also the valence of each emotional state. Next, we intend to make larger scale evaluation and utilize popular Twitter corpuses in order to get a deeper insight of our methodology's performance. Ultimately, we could take into consideration special tweet characteristics such as Hashtag Keywords and URLs in order to improve classification accuracy.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Classification of ReTweeting -Depth

Fig. 5 .

 5 Fig. 5. Rate of ReTweeting

Table 1 .

 1 Categories of Features

	Features	#	Description
	User Twitter Metrics	6	Followers, Direct Tweets, ReTweets, Conversational Tweets, Frequency, Hashtag Keywords
	Tweet Emotional Content	6	Anger, Disgust, Fear, Joy, Sadness, Surprise

Table 2 .

 2 Classes of ReTweeting

		#Instances in	#Instances in
	Level of ReTweeting	Depth	Width
		ReTweeting	ReTweeting
		5192	5192
		5667	4785
		2141	3023

Table 3 .

 3 Classification of ReTweeting -Depth and Width

	Classifiers	F-Measure (Depth) F-Measure (Width)
	AdaBoost	0.712	0.669
	IBK	0.843	0.817
	J48	0.896	0.872
	JRip	0.877	0.873
	Multilayer Perceptron	0.867	0.828
	Naive Bayes Classifier	0.683	0.581
	PART	0.865	0.862
	RotationForest	0.891	0.868
	SMO	0.687	0.669

Table 4 .

 4 Number of Instances per Emotional State

	Emotion Number of Instances Rate of ReTweeting
	Anger	212	78%
	Disgust	545	12%
	Fear	64	29%
	Happiness	344	31%
	Sadness	232	65%
	Surprise	142	17%
	Neutral	631	24%

Twitter4J library: http://twitter4j.org/en/index.html

Weka toolkit: http://www.cs.waikato.ac.nz/ml/weka/


Yosra Acodad
email: yosra.acodad@gmail.com

Amine Benamrane
email: benamraneamine@gmail.com

Imade Benelallam
email: imade.benelallam@ieee.org

El Houssine

E H Bouyakhf
email: bouyakhf@fsr.ac.ma

Profound Degree: a conservative heuristic to repair dynamic CSPs

For a better treatment of Dynamic Constraint Satisfaction Problems (DCSP s), several techniques have been developed to be used in repair algorithms. We cite, for example, the variables/values ordering heuristics and local search techniques. We distinguish between static heuristics, which calculate their values once at the beginning of the search, and dynamic heuristics that use an expensive intelligence in terms of solving time. In this paper, we propose a new static variable ordering heuristic, Profound Degree (pdeg), based on deg heuristic, which calculates the degree of influence of a given variable, on the whole constraints network, relatively to its position in the network. We evaluate this heuristic on the Extended Partial-order Dynamic Backtracking (EP BD) approach, which is an approach to repair DCSP s solutions, and we compare it to the best-known variables ordering heuristics (V OHs) for repairing. The evaluation of performance is on random binary problems and meeting scheduling problems, with the criteria of computation time, number of constraints checks and Hamming distance between the former and the current solution.

Introduction

In recent years, several improvements have been made in algorithms for solving and repairing DCSP s [START_REF] Dechter | Belief maintenance in dynamic constraint networks[END_REF] and [START_REF] Bessiere | Arc-consistency in dynamic constraint satisfaction problems[END_REF]. Among these, we quote V OHs [START_REF] Ortiz-Bayliss | Exploring heuristic interactions in constraint satisfaction problems: A closer look at the hyperheuristic space[END_REF], filtering techniques and conflicts analysis. In fact, the order in which variables are affected by a search algorithm is crucial. Indeed, the use of different V OHs to solve the same CSP can lead to very different results in terms of performance.

The used heuristics can be classified into two broad categories: Static variables ordering heuristics (SV OHs) and dynamic variables ordering heuristics (DV OHs).

In this paper, we present a new SV HO, prof ound degree heuristic (pdeg), which is inspired by the deg heuristic insofar as it uses the concept of neighborhood. In effect, pdeg is not limited to calculate the number of neighbor connections of concerned variable, but it also measures the impact of its eventual disturbances (since we study this heuristic under correction of DCSP s) in relation to all constraints network, i.e., it takes into consideration all levels of the network neighborhoods, by giving each level a different weight, then it keeps intact the value of the variable having a strong impact, in order to reduce disturbing the network. -Θ is a CSP . -α is a partial or complete assignment for Π that is called initial assignment.

-δ is a function that defines a distance between any two assignments.

A solution to a M P P is a solution to Π with minimal distance from α according to δ. Definition 2 (Distance set D) Let σ and γ be partial assignments for Θ. V is the set of variables and W (σ, γ) is the set of variables such that the value assignment for v in σ is different from the value assignment for v in γ :

W (σ, γ) = {v ∈ V | v, val ∈ σ, v, val ∈ γ, val = val } (1)
W (σ, γ) is called a distance set for σ and γ and the elements of the set are called perturbations.

Definition 3 (Function δ) In an M P P , the distance function of some assignment σ from α is defined as the cardinal of the set D(σ, α):

δ(σ, α) =| D(σ, α) | (2)
Otherwise, δ is the hamming distance between σ and α.

Definition 4 (Solution Value Assignment (SV A)) α is the initial assignment of a CSP . For each variable v i :

If v i , val i j ∈ α =⇒ v i .SV A = val i j ( 3
)
SV A is the acronym of Solution Value Assignment.

Extended Partial-order Dynamic Backtracking (EP DB)

Unlike several CSP resolution approaches that use a fixed order of variables, the Partial-order Dynamic Backtracking (P DB) [START_REF] Ginsberg | Gsat and dynamic backtracking[END_REF] uses a partial order, that is built from nogoods and safety conditions, that is dynamically modified during the search process.

Definition 5 (nogood) A nogood is a failure justification. It's an expression of the form :

(x 1 = v 1 ) ∧ ... ∧ (x k = v k ) → x = v
Definition 6 (safety conditions) A safety condition is defined as an assertion of the form: x < y, with x and y variables.

If S is a set of safety conditions, we denote by ≤ s the transitive closure of < , meaning that S is acyclic if ≤ s is antisymmetric.

x < s y =⇒ x ≤ s y, y s x (4)
In another way: x < s y, if there is a sequence (possibly empty) of safety conditions:

x < z 1 < z 2 < ... < z n < y

When having to generate a nogood during the search, due to conflict situation (creating a nogood caused by a violated constraint) or domain wipe out (nogoods resolution), and when no order is imposed in existing nogoods and safety conditions between variables concerned with this conflict, there may be significant choices for the variable that will emerge as the generated nogood conclusion. The performance of this approach depends mainly on the quality of this choice, which is not covered in P DB.

The major goal of EP DB is to extend the classic description of P DB, by exploiting its flexibility to repair assignments using repair-directed heuristics, when having to build an order between some variables, to control changes.

3 Profound Degree Heuristic (pdeg)

Description of heuristic

The deg V OH [START_REF] Dechter | Experimental evaluation of preprocessing techniques in constraint satisfaction problems[END_REF] has a major advantage, it's that it does not compute every time dynamic information about the current state of research (such as the current domains size dom or the current variables degree ddeg [START_REF] Bessiere | MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems[END_REF]), but it operates static information.

However, in the context of repairing solutions, this heuristic appears limited. In fact, no information regarding the position of variables in relation to the entire network is operated, whereby the change of a variable can affect not only the neighbors, but all of the variables in the network with a given probability. For this, we propose to calculate an estimation of this information for each variable X at the beginning of the research, considering all the network constraints, and by associating to each constraint a weight, higher or lower, in relation to its distance from X. pdeg is considered as the sum of those weights. Now consider the simple network above (figure 1). Suppose that each variable has a consistent value and due to a perturbation of the DCSP , the value of E must be changed. Assume that all constraints have the same tightness p 2 . Changing E will generate the following probabilities P :

P (violate(C EB )) = P (violate(C EF )) = p 2 P (violate(C BA )) = P (violate(C BC )) = P (violate(C BD )) = P (violate(C F G )) = p 2 * p 2 = p 2 2
If the probabilities of violating constraints are considered as weights, knowing that p 2 ∈ [0, 1], the weights of constraints network are:

W eight(C EB ) /E = W eight(C EF ) /E = p 2 W eight(C BA ) /E = W eight(C BC ) /E = W eight(C BD ) /E = W eight(C F G ) /E = p 2 2
This reflects that, whenever the constraint C is closer to the variable X, C is more influenced by the change of X, since the variables concerned by C are more influenced by changing X.

In fact, given two constraints C 1 and C 2 , if the constraint C 1 is closer to X than C 2 , then C 1 has a cost in calculation of the heuristic value of X which is more interesting than C 2 , since changing X engenders a risk of violating C 1 more important than violating C 2 .

In reality, constraints networks are not as simple as that, they are quite as figure 2:

On the other hand, the hardness of constraints network (especially when the constraints used in the modeling are intent) is not always known, reasons why choosing to replace the weight, that corresponds to the tightness of the constraints, by an average hardness of 1/2.

Inspired by this idea, pdeg heuristic accumulates, for each variable X, the weights of all constraints. These weights are higher each time the constraints are closer to X. neighbors ← getAllN eighbors(actual); 8.

f ilter(neighbors, total); 9.

actual ← getDistinct(neighbors); 10.

a ← neighbors.size(); 11.

b ← nbConstraints(actual); 12.

total.add(actual); 13. pdeg+ = 1/2 incLevel() × a + 1/2 incLevel() × b; 14. Return pdeg; Fig. 3: Description of pdeg heuristic

Execution of heuristic

Both of the value of pdeg and the level, that is incremented each time the constraint is far from the variable in question, are initialized by 0 (lines 1 and 2). The variable size contains the number of variables in the CSP (line 3) and actual and total lists, initiated by the variable for which having to calculate the pdeg, serve respectively to store all variables in the current level and all variables already involved in the calculation (lines 4 and 5).

Will not accounting all constraints network variables, the heuristic calculates the neighborhood of the current variables, then this neighborhood is filtered to include only new variables, to not record a same constraint twice (lines 6-8).

Note that getAllN eighbors() (line 7) recognizes a neighbor many times as the number of constraints that bind it with the current variables.

The heuristic puts into actual current neighbors eliminating redundancies, in a the number of neighbors of actual variables with redundancy (which is equivalent to the number of constraints with neighbors) not yet recognized and in b the number of constraints between these neighbors (lines 9 and 11). At this point, it adds to total the current neighbors and to pdeg the weight of neighbors, which is 1/2 to the power the level incremented, multiplied by the number of redundant neighbors, and it does the same thing for the number of constraints between neighbors, after incrementing the level (lines 12 and 13).

The heuristic leaves the while loop once all variables are accounted, which means it counted all the constraints of the network, and the value of pdeg is returned as the profound degree of the variable X (line 14). We consider the constraints network above and assume that all variables have a consistent value (A = 1, B = 1 and all other variables have values consistent with the whole constraints network). We suppose that the DCSP has undergone a disturbance that is the change of the nature of the constraint C AB , that was: A = B, and that became: A < B. To satisfy this constraint, the EP DB algorithm [START_REF] Acodad | Extended Partial-order Dynamic Backtracking algorithm for dynamically changed environments[END_REF] is restarted in order to repair solution. EP DB chooses to change the value of A, or the one of B, depending on the used heuristic.

Example of simulation

Using EP DB deg , heuristic values are:

deg(A) = 4 deg(B) = 6.
So the approach generates the nogood: B = 1 =⇒ A = 1, since it retains the value of the most relevant variable in the network, i.e., the one whose change can disrupt more the DCSP and delay resolution. For this reason, the value of A is changed. Now, using EP DB pdeg , the values of used heuristic are:

pdeg(A) = 1/2 × 4 + 1/2 2 × 1 + 1/2 3 × 14 + 1/2 4 × 2 = 4, 125 pdeg(B) = 1/2 × 6 + 1/2 2 × 0 + 1/2 3 × 3 + 1/2 4 × 1 + 1/2 5 × 9 + 1/2 6 × 2 = 3, 75
Then the approach generates the nogood: A = 1 =⇒ B = 1 and changes the value of B.

Experimental results

We carried out a series of experimental tests to compare the integration of pdeg heuristic, within the EP DB algorithm, to other V OHs.

Heuristics used for repairing are those that improve the best the behavior of EP DB, namely the degree (deg), the domain size (dom), the number of conflicts (conf ) and the ratio between the domain size and the weighted degree (dom/wdeg) [START_REF] Hemery | Boosting systematic search by weighting constraints[END_REF].

We evaluate the performance in terms of constraints checking (CCs), computing time (T ime(sc)) and Hamming distance (HD) [START_REF] Hebrard | Distance Constraints in Constraint Satisfaction[END_REF] and [START_REF] Zivan | Hybrid search for minimal perturbation in Dynamic CSPs[END_REF].

All experiments were performed on the Java platform.

Experiments on Randoms

Random CSP s are characterized by a quadruplet < n, d, p 1 , p 2 >, where n is the number of variables, d the number of values per variable, p 1 the network connectivity (density) and p 2 the constraints tightness. The density p 1 of a constraints graph is defined as the the ratio of the number of constraints relative to the maximum number of possible constraints in this network.

The tightness p 2 of a constraint corresponds either to the proportion of unauthorized tuples, or the probability that a tuple is not allowed.

Tests have been performed on sparse and dense problems, respectively < 20, 10, 0.25, 0.6 > and < 20, 10, 0.75, 0.27 >. The constraints tightness is selected such as areas are as complex as possible while problems have solution.

For logical reasons, we assume that the maximum rate of added constraints is equivalent to ∼25%. For each pair, 20 instances were solved using each heuristic, and the results are presented as an average of these 20 instances.

Figure 5 presents the effectiveness of heuristics applied to the EP BD, for the most complex regions of the low density selected. In terms of number of constraints tested CCs, Between 10% and 24% of new injected constraints, pdeg is the best, elsewhere, dom/wdeg and dom are the most efficient. Otherwise, the deg is the closest to pdeg, which seems the most stable.

In time graph, dom/wdeg recedes (also for dom but not in the same manner), due to the calculation of dom and wdeg heuristics, especially for wged. pdeg is almost always the best.

Concerning the Hamming distance HD, there is a competition between heuristics, and pdeg remains a good competitor in most regions.

Figure 6 shows the effectiveness of the heuristics for the most complex areas of the high density p 1 =0.75. In terms of number of CCs and execution time, pdeg usually looks the best although not improving too much the behavior of deg. Concerning Hamming distance, no heuristic is absolutely the best.

Experiments on Dynamic Meeting scheduling problems

A Meeting Scheduling Problem M SP is characterized by < m, p, n, d, h, t, a >, where m is the number of meetings, p the number of participants, n the number We present our results for the class < 20, 5, 15, 5, 10, 1, 70 > and we vary the rate of changed constraints from ∼1% to ∼25%. We generated 20 different instances solved using each heuristic in EP DB.

Discussion

For low densities, pdeg behaves better than deg, more remarkably than high densities. In fact, in high densities, almost all variables are connected, i.e., for each given variable, almost all other variables in the network are its neighbors. Therefore calculating pdeg of a variable almost returns to calculate its deg. pdeg leads, especially for low densities, to a minimum Hamming distance (HD). In fact, the idea of pdeg is to change the value of the least constraining variable in the network, i.e., the one that, when changing its value, will cause the least change to other variables. And knowing that the variables before the correction have SV As values, so a minimum change of network variables is a minimum change of SV As, then a maximum of SV As.

Although the heuristics dom, conf and dom/wdeg, in some regions, do less constraints checking than static heuristics deg and pdeg, they consume more computational time because of their dynamic aspect.

Conclusion

In this paper, we introduce a new V OH, pdeg heuristic, for estimating the influence of variables in the whole constraint network, in the process of repairing solutions in dynamic environments.

Based on the results of experiments on a wide class of problems, we found and proved that this heuristic, used in DCSP s correction, exceeds the heuristics deemed to be efficient when solving CSP s.

In fact, the idea of pdeg heuristic is to disturb only the parts of the constraints network, whose probability of influence is minimal. Indeed, for low to medium densities, as seen in the random problems with density p 1 = 0, 25 and the M SP (and especially for medium densities), using pdeg improves remarkably the repair of solution, not only in relation to research performance (time and CCs), but also with respect to the quality of the solution (Hamming distance).

As perspectives, we intend to integrate this heuristic in other algorithms for solving and repairing centralized and distributed CSP s, to hybridize it with other heuristics according to areas in which they show a remarkable improvement in order to lead to an optimal heuristic, and to experiment it on real problems.

2 Background 2 . 1

 221 Minimal Perturbation Problem (M P P ) Definition 1 (MPP) A Minimal Perturbation Problem (M P P ) is a triple Π = (Θ, α, δ), where:

Fig. 1 :

 1 Fig. 1: A simple constraints network

Fig. 2 :

 2 Fig. 2: A constraints network Function PDEG(X,CSP ) 1. pdeg ← 0; 2. level ← 0; 3. size ← CSP.V ars.size(); 4. actual ← X; 5. total ← X; 6. while(totat.size()! = size) 7.neighbors ← getAllN eighbors(actual); 8.f ilter(neighbors, total); 9.actual ← getDistinct(neighbors); 10.a ← neighbors.size(); 11.b ← nbConstraints(actual); 12.total.add(actual); 13. pdeg+ = 1/2 incLevel() × a + 1/2 incLevel() × b; 14. Return pdeg;

Fig. 4 :

 4 Fig. 4: Graph of constraints

Fig. 5 :Fig. 6 :

 56 Fig. 5: Number of CCs, Execution time performed and HD (p 1 =0.25, p 2 =0.60)

Fig. 7 :

 7 Fig. 7: Number of CCs, Execution time performed and HD


Eugénio Oliveira

Henrique Lopes Cardoso

Joana Urbano

Ana Paula

Rocha Liacc

Normative Monitoring of Agents to Build Trust in an Environment for B2B

Agents intending to be involved in joint operations need to rely on trust measures pointing to possible future solid partnerships. Using Multi-Agent Systems (MAS) as a paradigm for an electronic institution framework enables both to simulate and facilitate the process of autonomous agents, as either enterprises or individual representatives, reaching joint agreements through automatic negotiation. In the heart of the MAS-based electronic institution framework, a Normative Environment provides monitoring capabilities and enforcement mechanisms influencing agents' behavior during joint activity. Moreover, it makes available relevant data that can be important for building up contextualdependent agent's trust models which, consequently, also influence future possible negotiations leading to new and safer agreements. To support agents data generation and monitoring, we here present ANTE platform, a software MAS integrating Trust models with negotiation facilities and Normative environments, for the creation and monitoring of agent-based networks.

Introduction

In Multi-Agent Systems (MAS), the role of an Environment has been defined by Odel and Weynes et al [START_REF] Weyns | Environment as a first class abstraction in multiagent systems[END_REF] as a support for agents to exist, and the medium for agents to communicate. However, other than being a kind of a passive component providing services to the agents and facilitating, upon request, the Environment can also be seen as an active component, gathering and exploiting all kinds of information produced during MAS activity. This is mostly the case when the MAS is seen as a support for electronic institutions, a basis for automatic B2B operations [START_REF] Dignum | Meeting the deadline: Why, when and how[END_REF] [START_REF] Cardoso | Electronic Institutions for B2B Dynamic Normative Environments Artificial Intelligence & Law (special issue on Agents[END_REF]. In this paper we look at the MAS environment as a component that actively monitors all the relevant information produced by different agents engaging in activities related with both creating joint agreements and coordinating actions that enable their execution. Information, produced along these stages becomes useful for inferring relevant trustworthy capabilities of the agents in the network. In this paper, we highlight the approach taken in ANTE (Agreement Negotiation in Normative and Trust-enabled Environments) platform [START_REF] Oliveira | Software Agents: Can we Trust Them[END_REF] aiming at creating an active Environment that gathers information related with agents' activity for the sake of decision-making [START_REF] Cardoso | Agreement Negotiation in Normative and Trust-enabled Environments[END_REF]. ANTE encompasses a normative framework guiding agents interaction through norms that apply either sanctions or incentives. Useful information regarding agents' performance will influence future interactions and possibly agents joint work [START_REF] Cardoso | Social Control in a Normative Framework: An Adaptive Deterrence Approach, Web Intelligence and Agent Systems[END_REF].

The structure of the paper is as follows: After this introduction, we first describe how to use MAS environment, based on the power of a normative environment, to produce and gather relevant information about agents activity. Then, in section 3 we introduce a computational Trust Model that benefits from such information in order to assign trust measures to agents, preventing an agent from future involvement with untrustworthy partners. Section 4 briefly presents the ANTE platform that provides all the needed services plus the environment for agents to interact in a trustworthy way. We close the paper with a brief conclusion.

The relevance of the Environment

Many sophisticated problems we usually address can be classified as belonging to the Triple-D class of problems [START_REF] Oliveira | Software Agents: Can we Trust Them[END_REF]. They reflect a reality that simultaneously is of a Distributed, Decentralized as well as Dynamic nature. This means that, besides input data and output actions being disperse (Distributed) at different nodes of a network, also, and most important, decision-making can be, at least partially, taken at different nodes of the (Decentralized) system. Moreover, the system trying to solve the overall problem at stake, has to deal with a changing, evolving reality (Dynamic). To work jointly in solving this kind of problems, agents need to select, in run-time, their best trustworthy partners for executing the tasks through mutual agreements to coordinate joint work. In the core of software agent's definition we find the "situatedness" property and, thus, the Environment becomes an important component to be specified and designed for multi-agent systems.

As a relevant component of MAS, although not always considered per se, Environment can be seen as an active medium to facilitate the way how to reach certain consensus, agreements or mutual contracts. Instead of looking at the Environment as a regulator through the internal mechanisms of a Normative environment [START_REF] Dignum | Meeting the deadline: Why, when and how[END_REF][5] [START_REF] Cardoso | Social Control in a Normative Framework: An Adaptive Deterrence Approach, Web Intelligence and Agent Systems[END_REF], we here see the Environment as a medium in which notifications about the outcomes of actions agreed upon, after the establishment of joint contracts, appear together with the output of the Normative Environment that assesses them and, then, combines all those pieces of information in meaningful knowledge for future use. More precisely, through the environment embodied in ANTE, the software platform we have developed, relevant data is made available for building up contextual-dependent trust models which, as a consequence, will influence future possible agents negotiation leading to new, and better, agreements.

Environment as a facilitator

It is out of the scope of this paper to describe other environment facilities as it is the case of the negotiation protocols and mechanisms we advocate [START_REF] Cardoso | Agreement Negotiation in Normative and Trust-enabled Environments[END_REF] in the ANTE platform, for a dynamic and adaptive convergence towards final agreements then materialized into contracts. We, along this paper, want to mainly highlight the importance of the Environment in recording the relevant events produced by the agents and the normative environment outputs as a result of agents' activities during contract enactment. Appropriately combining the trace of such events, leads to a tightly coupled connection between electronic contract monitoring and a computational trust model for estimating agents' trustworthiness. The Normative dimension of the Environment handles a normative state NS (including all elements that characterize the current state of affairs for each established agreement), a set IR of institutional rules that manipulates NS and a set N of norms, which can be seen as a special kind of rules. NS includes institutional facts that represent institutional recognition of contract related real-world events. The Normative Environment also notifies the agents about relevant contract-related events. The same mechanism conveys information to feed the computation Trust model.

A contract C = < T ; CA; CI > is monitored by the normative environment and is defined as follows: A contract C is a relation of type T within which a group of agents in set CA commits to a joint activity, under the normative context using information CI, a set of definitions regarding the role of the participants, the values to be exchanged (e.g. products and money) or any parameters defining their provision. An electronic representation of a contract includes a set of norms that specify how a specific business is to be enacted. A norm is a rule whose conditions analyze the current NS and whose conclusion prescribes obligations agents ought to fulfill. As a consequence, sanctions may be imposed by prescribing obligations upon violation events, thus producing more relevant information in the environment. In the context of a MAS in which agents represent entities looking for partners to establish agreements and commit themselves to joint actions, the role of a normative environment [START_REF] Cardoso | Social Control in a Normative Framework: An Adaptive Deterrence Approach, Web Intelligence and Agent Systems[END_REF] is twofold. Given an agreement, it is necessary to check if the partial contributions of individual agents make their way in enabling a successful execution of tasks leading to the agreed overall goal. In many cases, the execution of the needed tasks is itself distributed, which requires agents to enact by themselves their part of the agreement. Monitoring this phase is therefore an important process and is possible through the analysis of the interactions and facts produced, and made visible, in the environment. Furthermore, it is possible that after successfully negotiating and reaching agreements, self-interested agents are no longer willing to fulfill their commitments, which becomes also visible to the environment, since normative rules generate notifications (prescribing sanctions) in reaction to such events.

As an example, the normative environment may apply norm n enforcing a sanction (e.g. a payment) when a violation regarding delivery has been detected. This puts in evidence the second role of a normative environment, that of enforcing norms by coercing agents to stand for their commitments. At the same time, the whole idea of an active environment is to use the relevant information generated through the normative environment and make it useful for further agents' reasoning strategy.

Information in the Environment

The way agents enact their contracts provides relevant information for trust building and, as a consequence, may decisively influence partners selection for future electronic contracts. In ANTE, an image of all the relevant real-world transactions between different agents become recognized as "institutional reality" [START_REF] Searle | The Construction of Social Reality[END_REF]. As stated above, a normative state NS records every element that is relevant in contract enactment and is composed of institutional reality elements. Agents active in the Environment subscribe to the normative environment to be notified about eminent contractual obligations and commitments to be fulfilled. Consider the following representation of a directed obligation with time constraints: Obl b , c(l < f < d). This is an obligation of agent b (the bearer) towards agent c (the counterparty) to bring about fact f between liveline l and deadline d. An obligation such as this can give rise to a rich set of events, such as temporal violations, due fulfilment or violation. As agents go on interacting according (or not) with pre-established contracts, the normative environment reacts appropriately, and produces more (normative) information about the on-going processes. The challenge is to be able to gather and manage all that produced data, to infer meaningful information about agents' future behavior.

Moreover, other than information generated during two agents' mutual interaction, there is other available information, coming from third parties, that may be relevant to characterize a specific agent. These indirect evidences about an agent's behavior (an "image" the agent builds up in the society of all currently active agents, due to previous interactions), is called reputation. Reputation is seen as the social-based process of transmitting beliefs about a specific agent (the trustee), as a consequence of social evaluation circulating and, according to [START_REF] Sabater-Mir | Repage:reputation and image among limited autonomous partners[END_REF], are represented as reported evaluations. There are computational trust models that use reputation as another piece of evidence to be taken into account about any particular agent. For that purpose, they need to estimate the credibility of both the transmitted information and of those agents reporting that information. Providing that third party agents, not directly involved in a particular negotiation are willing to provide their own perspective on a particular agent, this new piece of evidence will also be present in the environment and can also be identified as relevant to be merged with direct evidences [START_REF] Urbano | A Socio-Cognitive perspective of Trust[END_REF]. The perspective an agent is now able to infer, through the combination of the available information, about another agent becomes wider and more independent of local knowledge. However we still did not address the problem that could arise if reputation information and other available trust-based measures happen to be of different nature and formats. How to merge them, in a coherent way, through the computational Trust and Reputation Model is a challenge for our near future research.

Trust

We follow a basic and established definition for Trust (although not always consensual). Closely, but not completely following some of the ideas expressed in [START_REF] Falcone | Trust and deception in virtual societies[END_REF], we propose the following formal definition for trust: Trust(i; j; ϕ ) meaning that the Truster(i) trusts Trustee(j) to do Action(α) leading to the achievement of Goal( ϕ) if:

(GOAL i ϕ) (BEL i P OW ER j ϕ) (BEL i (α |= ϕ)) (BEL i IN T EN D j α)
, where is the usual 'necessity' modal operator, P OW ER j ϕ states that agent j is capable of achieving ϕ and IN T EN D j α is agent j's intention to execute action α. Intention means choice with commitment according to Cohen and Levesque's well accepted theory.

Agents should thus rely on Trust measures to select their best potential partners, improving their chances to achieve their own future goals. It has been established that, whenever decisions have to be made for selecting potential partners in a future activity, it becomes mandatory to rely on some kind of past evidence pointing to an estimate of the other agents' trustworthiness. We need to remember here that Trustworthiness is an intrinsic characteristic of an entity (here an agent) while Trust measures reflect other ones' (potentially different) assessment of that particular agent under evaluation. Exhaustive discussions are taking place about all the relevant factors that can influence a trust measure characterizing the perspective each agent builds up on other agent internal trustworthiness [START_REF] Falcone | Trust and deception in virtual societies[END_REF]. We may identify two different categories of such factors: subjective (propensity and disposition) and, most valuable, objective (past experience regarding previous direct interactions, current social image of the agent under scrutiny, the reputation and other indirect evidences). Another perspective over the computational trust model is if, indeed, a single measure is enough to measure an agent's trustworthiness. In fact, although we often look for competence, it sometimes is not the only dimension that matters for successful future joint activities. Other more subtle features like how benevolent and integer an agent can be, may be seen as determinant in deciding on how much shall an agent trust in another one. Another important concern is the contextual nature of trust: Situation, task and time dependence are different factors to take into account when measuring and ranking other agents' trust.

Computational Trust Models

There has been a number of proposals for computational trust models that rely in one or several of the factors and dimensions referred above. Direct past mutual interaction experience is the most common factor these models take into consideration as it is the case of [START_REF] Sabater | REGRET: Reputation in gregarious societies[END_REF]. A few computational models already include some kind of agent disposition to trust and emphasize the importance of context [START_REF] Rehak | Multidimensional Context Representations for Situational Trust[END_REF] [START_REF] Urbano | A dynamic agents behavior model for computational trust[END_REF]. Moreover, only recently we have called the attention to the importance of the dynamics of the relationships taking place, along the time, between the different agents, leading to a relative change of the power relationship and the evolution of mutual goodwill [START_REF] Urbano | A dynamic agents behavior model for computational trust[END_REF].

Proposed Trust Model Our computational Trust model, included in the ANTE software platform, has different components responsible for managing most of the factors recognized as influencing trust-based decision-making. As a model, it encompasses both the different dimensions of trustworthiness (integrity, ability, benevolence) and the truster's disposition to trust. As a software program, implementing most of the referred important aspects, although not yet all of them, it already includes an aggregator of past direct experience, Sinalpha, a Contextual Fitness component, a Social and an Integrity Tuner. Through such model we gain the ability to compute adequate Agent i estimations of Agent j trustworthiness to achieve a specific goal ϕ, in different environments, including those of high dynamics, where evidence on the agent under evaluation is scarce.

The two main components first aggregate past contractual behavior evidences (Sinalpha) and then consider how agents fit into the context under consideration (Contextual Fitness). The aggregator gets information from the environment about agents' performance regarding their past obligations (either fulfillment, partial fulfillment or violation). It uses a sinus-based curve that is reshaped at both top and bottom extremities [START_REF] Cardoso | Agreement Negotiation in Normative and Trust-enabled Environments[END_REF]. It uses a function of α that presents a sinusoidal shape (see Equation 1). By setting δ = +0.5, the trustworthiness value is restricted to the range [0;1]. trustworthiness = δ * (sinα + 1) (1) The trustworthiness score of the agent is minimum when α = 3π/2 and maximum at α = 5π/2. This score is updated using α(i+1) = α(i)+λ * ω, where λ reflects the outcome ( either positive or negative) associated with the piece of evidence being aggregated and where parameter ω defines the size of the ascending/descending step in the trustworthiness path. For example ω = 6 means that any trustee that is a newcomer, could be considered by the truster as fully trustworthy after presenting six outcomes of type F (fulfilled) in a row. Asymmetry about gaining and loosing Trust, maturity after reaching a certain status and distinguishing different patterns of past behaviour are properties that are featured by the model. It has been proved that the way the aggregator merges past evidences, gives a realistic idea of, although just for simple situations, agents' expected behaviours in future similar situations.

The second component of the model, responsible for social awareness, counts for the specific appropriateness of the target agent (Trustee) regarding that particular situation in which the other agent (Truster) is willing to get help, to work jointly or to engage in a relationship with [START_REF] Urbano | A dynamic agents behavior model for computational trust[END_REF]. It is based on the concept of a Context that captures and represents the relevant information about the current situation, that Contextual Fitness appreciates how an agent can be, at that specific time, trustworthy or not. A Context is here defined as an N-tuple including agent identity, current time, location and a set of task-related attributes: type, complexity, deadline and expected outcome. Contextual Fitness component, a situation-aware tuner may downgrade the trustworthiness scores computed by the aggregator (Sinalpha) whenever the agent under assessment has proved to behave poorly in that specific situation. We are using the information gain metric on the previous evidences on the agent different tendencies of failure. This approach differs from other situation-aware computational trust approaches by its flexibility and ability to reason in terms of context even when the evidence on the agent in evaluation is scarce. Briefly, we endow the environment with the capabilities of clustering different potential partners waiting for being selected and extract stereotypes characterizing in what conditions they have either fulfilled or violated their obligations. Therefore, it may be the case that a particular agent has a good trust measure, however it has an handicap regarding a specific feature that is of most relevance for the concrete partnership another agent is interested in (for example, a faster delivery time of a product). The most important to stress here is that the environment is empowered with the means to strongly influence the decision-making process of agents, by providing indicators that, once combined, become relevant for trust evaluation.

ANTE Platform

Grounded on the recognition of the Environment as a relevant component to give structure and support situated MAS, we have developed ANTE, a software framework in which agents can both establish agreements (and contracts) through negotiation and, simultaneously, benefit from monitoring capabilities pointing to more transparency of joint activities. Through the development of ANTE we intended to illustrate how an active environment may help in reliable and informed agents decision-making in what joint agreements is concerned [START_REF] Cardoso | Agreement Negotiation in Normative and Trust-enabled Environments[END_REF]. ANTE supports multi-agent collective work leading to agents' intention satisfaction, by providing negotiation as a mechanism for finding mutually acceptable agreements with trusted partners and the enactment of such agreements (contracts). Gathering appropriate data and evaluating the Normative State, enables feeding the Computational Trust model which, in turn, provides information for better selecting partners for future agreements.

In ANTE, the environment actively mediates interaction among agents in several different ways: i) The Environment is, primarily, a Facilitator by providing negotiation protocols, Ontology translation services and Contract building tools. In this perspective we can see it as an Interaction-Mediation level [START_REF] Weyns | Environment as a first class abstraction in multiagent systems[END_REF] regulating access to resources and mediating interaction between agents leading to possible agreements. ii) The Environment also provides mechanisms for the normative enactment of those agreements (established contracts among agent partners), generating Normative States (NS) and becoming responsible for monitoring those NS in an active way. ANTE includes a normative framework of constitutive and institutional rules, according to the institutional reality model, operating in a rule-based process. iii) Through evaluating the contract enactment phase, the Environment improves the chances for better future negotiations by progressively updating the available Trust measures to help in the partners' selection process. ANTE includes, at present, a computational Trust model made up of two main modules: SINALPHA aggregator and contextual fitness. iv) In the ANTE specification model, another component acts as a "social Environment" and is responsible for adaptive deterrence mechanisms (through dynamically calculated fines imposition) reacting to different agents population behaviors. In Figure 1 we display how the active environment is subject to the simulta-neous intervention of the agents activity (negotiation and contract execution) which leads to "institutional facts" monitored in the active environment. Those "institutional facts", in turn, feed and update the computational Trust Model. Monitoring rules are responsible for gathering all the needed information that becomes relevant to feed the computational Trust model which dynamically combines that information to infer agents' trust measures. This last component is, however, meaningless in the context of what is the aim of this paper: information merging to dynamically feed an agents' trust model. ANTE is a modular and extensible JADE-based architecture implementation, integrated with JESS rules engine, accessible through several different GUIs for agents to announce their needs as well as for inspecting the whole negotiation process, normative states and contract results. Although ANTE has been targeting electronic contracting in B2B domains, and because it encompasses several agreement technologies like negotiation, normative environments and computational trust models, it was conceived as a more general framework having in mind a wider range of application domains including social networks monitoring.

Experiments assessment We have used ANTE platform both as an environment as well as a set of services suitable for achieving agents agreement in a B2B scenario. As an environment it became a useful interface between negotiation services, normative environment services and computational trust services. Many different experiments have been performed, mainly involving agents as enterprise representatives negotiating several different attributes of particular goods (fabric type, quality and time of delivery). Since the description of a full range of different partial and integrated experiments we have made, can be found in [START_REF] Urbano | A Situation-aware and Social Computational Trust Model[END_REF],

we here just stress out a qualitative assessment about the summarized results coming out of the use of Trust during the partners selection negotiation phase together with normative sanctions application. Different experiments enable the agents to use Trust either to pre-select the most promising potential partners for the future joint activity (to supply a certain quantity of a certain type of fabric, until a specific deadline) or to use trust only during the negotiation phase, to better evaluate proposals under scrutiny. Other experiments combine these two possibilities. Also, several different metrics have been used. However, we here only report on the metric reflecting the number of well succeeded contracts that have been established following the use of these referred techniques. After a number of experiments we concluded that, by using the Computational Trust Model, the outcomes were strongly influenced, besides the agents behavior type, by other factors like, for example, the degree of similarity or dissimilarity of the agent proposals under comparison. Moreover, one of the most important conclusions was that using trust for pre-selecting the agents for future negotiation together with a moderate use of Trust measures during the negotiation process itself, was the best policy for an agent to follow. Using Trust for selecting partners increased the number of succeeded contracts in this B2B scenario.

Conclusions

Distributed, decentralized systems for dynamic situations, appropriate for Triple D kind of problems, are well represented by means of Multi-Agent System architectures. Distributed Agents, representing different entities (like enterprises), take their own decisions (selecting partners) in a decentralized way. Moreover, they react to dynamic situations (like other agent trustworthiness change) by appropriately using trust measures to help on their own decision-making (which partner to select). Following the same line of those authors who claim that the Environment should be considered as an important, separate component in the specification and design of Multi-agent Systems, we here advocate a set of capabilities that should be made available for more secure, comprehensive and trusted agents mutual activities possibly leading to more fruitful joint agreements, as it is the case of B2B e-contracts. Besides facilitating functionalities like negotiation protocols, ontology services, normative framework application and monitoring, we here, in this paper, strongly emphasize the importance of an Environment active role also as a support for information fusion. Gathering and evaluating information related with normative states and agents behavior regarding norms abidance and contracts fulfillment is of paramount importance for feeding computational Trust models. Combining agents activity-driven information, leading to updated and contextualized agents' Trust measures become crucial to guide future agents' activity and mutual agreements. A "social-based" Environment can also have the privilege of, by reasoning about all agents activity, to detect, prevent (or incentivize), patterns in the society regarding maleficent (or beneficial) agents' behavior. Moreover, and having in mind its active role to ease and promote possible agent agreements, "social Environment" has been empowered with the capability of adaptively impose fines for the sake of better regulate the agent population activities and promoting confidence in the possibility of future better agreements. This aspect of the environment lacks of further investigation. However, in this paper, we mostly emphasize how, through a normative framework responsible for monitoring agents contractual behavior and computational Trust models, the environment provides relevant evidences that, in the end, enables an agent to better characterize other potential partner agents and better decide about either to engage or not in a future relationship and better agreements, as it this the case for B2B contracts negotiation scenario. ANTE software platform has been developed taking all these features into consideration

Fig. 1 .

 1 Fig. 1. The Active environment. Facts (clauses violation/fulfillment) activate norms leading to possible sanctions, changing agents trustworthiness and, thus, influencing the way agents negotiate future contracts.