Norbert Blenn

Bas Christian Doerr

Van Kester
email: vankester@student.

Piet Van Mieghem

Crawling and Detecting Community Structure in Online Social Networks using Local Information

Keywords: Social Networks, Community Detection, Crawling

As Online Social Networks (OSNs) become an intensive subject of research for example in computer science, networking, social sciences etc., a growing need for valid and useful datasets is present. The time taken to crawl the network is however introducing a bias which should be minimized. Usual ways of addressing this problem are sampling based on the nodes (users) ids in the network or crawling the network until one "feels" a sufficient amount of data has been obtained. In this paper we introduce a new way of directing the crawling procedure to selectively obtain communities of the network. Thus, a researcher is able to obtain those users belonging to the same community and rapidly begin with the evaluation. As all users involved in the same community are crawled first, the bias introduced by the time taken to crawl the network and the evolution of the network itself is less. Our presented technique is also detecting communities during runtime. We compare our method called Mutual Friend Crawling (MFC) to the standard methods Breadth First Search (BFS) and Depth First Search (DFS) and different community detection algorithms. The presented results are very promising as our method takes only linear runtime but is detecting equal structures as modularity based community detection algorithms.

Introduction

Analyzing human social behavior depends on observations of large scale networks. Online Social Networks (OSNs) proved to be good sources of information facilitating this kind of research, as the most popular OSNs such as Twitter, Facebook or LinkedIn consists of hundreds of millions of user accounts, thereby allowing an analysis at a sufficiently large scale.

However, it is usually not possible to obtain datasets from the operators of OSNs. Therefore, a common approach is to crawl the network per user. In this way, a user is randomly chosen and a list of his friends is downloaded. Out of the list of friends, again one user is selected and a list of friends retrieved. This method repeats in principle until every user in the network has been visited once. This method varies in the selection of the next friend, are ranging from Breadth First Search towards Depth First Search.

This automated process of downloading users typically requires a robot (a software program) to look at the profile page of a user and store the names of all friends. Such an operation usually takes between 0.1 to 2 seconds as it includes multiple HTTP requests to a server in order to iterate through the whole list of friends. An optimistic1 calculation shows that with one crawling computer, obtaining LinkedIn's database of 120 million users (as of Nov. 2011) would take approximately half a year. The same calculation for Facebook's dataset of 650 million users leads to a crawling time of ca. 2 years. By using massively parallel crawling techniques those times can be decreased. Clearly, by the time the last records have been obtained, the much of the retrieved information will be outdated.

A lot of work on social network analysis has been done using communities of users as a level of abstraction. A natural question is therefore whether it is possible to direct the crawling procedure in such a way that it is crawling the network community-wise. This would enable researchers to analyze useful subgraphs of the whole network while still obtaining data. In contrast, using the standard crawling methods like Breadth First Search or Depth First Search, one literally has to wait until the whole network is crawled before starting to analyze the data because there might be a few users critical to a particular single community still missing from the dataset, and their existence and criticality cannot be determined until all data is in.

In this paper we present a simple approach to crawl a network communitywise and detect communities at the same time. Our algorithm called Mutual Friend Crawling is compared to existing community detection methods.

The remainder of this paper is structured as follows. Section 2 summarizes the related work, in Section 3 our method of crawling is described, evaluated and the community detection is explained. Section 4 will compare the community detection with well known community detection algorithms and Section 5 will summarize our findings and give an outlook.

Related Work

Communities are defined in terms of the fraction of nodes of a network, that share more connections with each other than with the rest of the network. When analyzing a social network, some relevant questions are:

1. How many communities are there in the network? 2. Which nodes are in the same community? 3. How well are users in communities connected?

A well known metric to capture the community structure of a network is modularity. Modularity m as defined in Clauset, Newman and Moores's work [START_REF] Clauset | Finding community structure in very large networks[END_REF] is "the number of edges falling within groups minus the expected number in an equivalent network with edges placed at random." The definition of modularity is given in equation 1.

m = 1 2L N i N j (a ij - d i d j 2L
)1 {i and j belong to the same community}

For a given graph G with N nodes, L links and a given partition, the modularity denotes how well the community structure is expressed. The element a ij denotes the element corresponding to the ith row and jth column of the adjacency matrix of G and d i is the degree of node i. 1 {i and j belong to the same community} is the indicator function returning 1 if i and j are in the same community otherwise 0.

A modularity value of 0 defines that the number of links belonging to the same community is equal to the number a random graph would have. The higher the modularity the more pronounced the community structure, except for the trivial case of modularity = 1, in which all links of G are in the same community. Conversely, this means that negative values are a definition of something like an "anti-community" structure. A nice overview over modular graphs and how to achieve high modularity is given in Trajanovski [START_REF] Trajanovski | Maximum Modular Graphs[END_REF].

As we will present an algorithm to crawl community structure in real world OSNs having linear complexity, we compared our results to crawling techniques like Breadth First Search (BFS) and Depth First Search (DFS) as described in Cormen et al. [START_REF] Cormen | Introduction to algorithms[END_REF]. In both techniques the graph is crawled node per node adding all discovered nodes to a list of nodes to visit. The difference between BFS and DFS is based on the procedure how the next node to visit is selected. In BFS the first node of this list is selected to be visited next and removed from the list whereas in DFS the last node in the list is selected and marked as visited. Both techniques are leading the crawling procedure towards the inner core of the network due to the friendship paradaxon. This paradoxon, first observed by Field [START_REF] Feld | Why Your Friends Have More Friends Than You Do[END_REF] stating originally that your friends have more friends than you, will force a crawl towards nodes having a high centrality in the network. A related effect, noted by Kurant et al. [START_REF] Kurant | On the bias of BFS (Breadth First Search)[END_REF] describes that BFS and DFS is introducing an bias towards high degree nodes for an incomplete traversal of the network.

To our knowledge, BFS and DFS are the most used techniques to traverse a graph. We will show in section 3 that, in order to reveal the community structure of a graph BFS and DFS are not the best choice. One possible technique of crawling a network and detecting communities at the same time is to facilitate random walks. Random walks are known to stay inside communities as described in Pons and Latapy [START_REF] Latapy | Computing communities in large networks using random walks[END_REF] and Lai and Lu [START_REF] Lai | Enhanced modularity-based community detection by random walk network preprocessing[END_REF]. The main idea behind random walk community detection is that a community has more links between nodes of the community than between communities. Because of this definition, a random walk would traverse nodes of the same community more often than the ones of different communities. However, a random walk allows steps backwards to already visited nodes which is increasing the time taken to crawl the network.

Different community detection algorithms like fast and greedy community detection by Clauset et al. [START_REF] Clauset | Finding community structure in very large networks[END_REF], Spinglass by Reichold and Bornholdt [START_REF] Reichardt | Statistical mechanics of community detection[END_REF], edge betweenness clustering by Girvan and Newman [START_REF] Girvan | Community structure in social and biological networks[END_REF] or label propagation by Raghavan et al. [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] cannot be used to detect communities during crawling as those algorithms are meant to be applied onto the full topology of a network.

A related approach to detect community structure while crawling is presented by Nguyen et al. [START_REF] Nguyen | Adaptive algorithms for detecting community structure in dynamic social networks[END_REF]. Their algorithm Quick Community Adaptation (QCA) assumes that the community structure is already known for a complete network and manages to calculate community structure in dynamic networks. QCA tries to maximize modularity by assigning a "force" which attracts a node towards a community. However, this method also needs the whole network including assignments of nodes into communities. In their approach the used algorithm to estimate the initial community memberships is presented by Blondel et al. [START_REF] Blondel | Fast unfolding of community hierarchies in large networks[END_REF] called the Louvain(-la-Neuve) method. This algorithm calculates a modularity maximizing partition of a given graph by using the change in modularity when discovering a new node and adding it to an existing community. If the difference is not positive the node stays in its initially assigned community.

To compare the result of different clustering algorithms we decided to use the Jaccard similarity coefficient next to the already defined modularity. The Jaccard similarity coefficient defines the similarity of sample sets by measuring the quotient of the intersection and the union of both sets.To compare the result of different cluster assignments a definition of Fortunato and Castellano [START_REF] Fortunato | Community structure in graphs[END_REF] given in equation 2 is used.

I J (s 1 , s 2 ) = n 11 n 01 + n 11 + n 10 (2)
In equation 2, n 11 denotes the number of node pairs found in the same community whereas n 01 and n 10 are the number of pairs of nodes assigned to the same community by algorithm s 1 but not s 2 and vice versa.

Crawling and Detecting Communities

We introduce Mutual Friend Crawling which crawls nodes of a network in such a way that communities are visited one after another. First we will show that our approach is crawling all nodes belonging to one community before continuing with nodes of a connected community. Afterwards we will show how to detect communities using this approach.

In contrast to BFS and DFS, our algorithm assumes the knowledge about the degree of neighboring nodes. This assumption is reasonable in OSNs as the number of friends is very easy to obtain, whereas the process of receiving the actual links towards them needs more effort. For example in the OSN Twitter, each message contains a field containing the number of followers and friends the originating author has. Also, OSNs are most commonly crawled using a technique called screen scraping. Here, the OSN is accessed the same way a user does, by using HTTP requests to analyze web pages for relevant data. The number of friends is usually listed at the profile page of a user but several clicks (requests) on the list of friends are needed to obtain all node ids (friends) having a relationship with this user. If one is interested in more details of a user, for example the real name or group affiliations, this profile information will need to be obtained in any case and at the same time a friend count is also available without any additional overhead. In this way the needed crawling effort has not increased but only the order in which the data is gathered has changed.

Mutual Friend Crawling is based on the "reference score" (S R ) defined in equation 3. This score denotes the fraction of the number of already discovered links pointing to node f (references) so far in the crawling process and the total degree, i.e., total number of friends, of node f . S R = number of found references to f degree of node f

During the crawl, the next node to process is chosen from the list of the already discovered nodes having the largest S R . The full algorithm is specified in pseudo code in algorithm 1.

Algorithm 1 Mutual Friend Crawling Mutual Friend Crawling is based on a BFS algorithm having two major differences. The first one is a map used to store the number of found references as indicated in line 2, 4 and 15. The second difference is based on the way the next node to visit is chosen: instead of choosing simply the next one from the list as BFS does, MFC calculates the reference score (lines 6-9) and chooses the next node based on the maximum of the reference score (line 10 & 11).

The algorithm will therefore first visit nodes where to which the largest number of the overall links have already discovered. If a network has a community structure based on the definition of having more links in the community than links connecting communities our algorithm will crawl communities one after another.

In order to apply the algorithm on weighted graphs, a simple definition of the strength of a node as the sum of the weights of adjacent edges is sufficient. In this case the reference score S R is defined as the fraction of the sum of weights of already discovered links to the strength of the node as defined in 4.

S R =

(weights of found references to f) strength of node f (4)

Community Crawling

Figure 1 illustrates our crawling approach intuitively using a small example.

Using the definition of communities as stated above (more links "within" the group than ending "outside"), simple visual inspection already shows that there are six clusters. If we were to explore each cluster one after the other, the algorithm should first explore all nodes belonging to one color before starting with the next group of nodes. The nodes labels denote one possible order in which the graph could be crawled in order to visit communities one after another, thus leading to the intended and perfect exploration order. In order to test the proposed algorithm on multiple graphs a metric defining how strong the community structure in a given graph is expressed was needed. A simple metric is given by the ratio of links inside communities to the total number of links. We define this value as P in reflecting the probability an arbitrary chosen link is an intra community link.

We created a total of 100,000 artificial networks with different P in values using a graph generator, described in van Kester [START_REF] Van Kester | Efficient Crawling of Community Structures in Online Social Networks[END_REF], each with 10,000 nodes, 100,000 links and 100 equally sized communities have been generated. Two general types of graphs commonly found in network science were evaluated: The degree distribution of the first type follows a uniform distribution and the degree distribution of the second type is approximating a power-law function. All graphs have been crawled from all possible starting nodes. During the crawl we kept track of the order when nodes are visited, which allows us to analyze if a complete community has been crawled before going to the next one.

Figure 2 shows the crawling trajectories of those crawls. The figure is expressing how many nodes have to be crawled in order to visit all nodes of a community. In order to crawl the network community-wise the optimal traversal would need to visit all nodes of one community first before visiting the next node belonging to the next community. Because all communities are equally sized, the optimal traversal of the graph would lead to a diagonal line in figure 2. A bended line is expressing the fact that nodes from different communities were visited before all nodes of the previous visited community have been finished. The order in which multiple communities are crawled is not reflected in figure 2, as we are primarily interested in obtained one completely crawled community after another and not which one is obtained first. The used colors express trajectories of different crawling methods whereas green lines belong to DFS, blue to BFS and red to our Mutual Friend Crawling.

For high P in values, figure 2 illustrates that our algorithm performs as expected and leads the walk on the graph to all nodes contained in one community before crawling the next. For BFS and DFS a larger fraction of the network has to be crawled to finish one community. Interestingly, BFS perform "closer" to the optimum than DFS. This is because BFS explores the local neighborhood whereas DFS explores the nodes furthest away from the starting node. Thus, the "chance" of BFS to visit all nodes of one community earlier than in DFS is higher.

The proposed crawling method performs reasonably better than BFS and DFS in terms of crawling along the community structure. For P in values larger 0.3, the order in which the nodes are traversed fulfills our requirements. However, P in values smaller than 0.5 somehow define negative communities in terms of the definition and therefore a BFS approach by chance performs better.

Community Detection

We already demonstrated empirically that our method crawls communities of a graph one after another. In order to detect communities while crawling the graph, traces of the reference score of visited nodes can be analyzed. Figure 3 shows the trace of reference scores performed on the example graph (figure 1) starting from node 0. As mentioned earlier the proposed method always selects the next node to visit having the highest reference score (line 8 in algorithm 1). Hence the reference scores inside communities should always increase or stay roughly the same while traversing the graph. When detecting a node that is interconnecting communities, a large number of links of this node are ended in the previously unknown community. Therefore, its reference score will be smaller than the ones of nodes connected to this in the current community. As this node is selected as the last one, a drop can be observed in the trajectory of reference scores of visited nodes. Figure 3 shows five major drops of the score. Those drops in Step s of the algorithm the reference score of the chosen nodes reflect the creation of new communities. We define the difference between the next reference score to the previous one as ∆ref score. During traversing the graph, all nodes are added to the same community as long as ∆ref score is large enough. If the score decreases a new community can be created. To prevent the creation of single node communities, we found that the drop in the reference score should be at least half the difference between the maximum S max and the minimum S min of the reference score in this community. By using this method, the Mutual Friend Crawling is creating six communities on the sample graph having the community assignments as indicated by different colors in figure 1 One problem however still remains: a possibly incorrect classification of certain nodes during the first visit of a new community. In case neighbors of the starting node as well as neighbors of the first node of a community have the same degree as the visited node, a node of a different community could be assigned incorrectly. Such misclassification is exemplified for the case of three equally- sized, fully-connected communities which are pairwise connected through one node as shown in figure 4. In this case when starting in one clique, all nodes of this clique are added to the first community. When reaching one of the 3 nodes connecting communities [START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] or 21 in figure 4) the score drops, a new community is generated and all following nodes are added to this community. When reaching for example node 10, the reference score for the 2 peers (11 and 21) is the same. One of them is chosen to be next node to visit. But now, (e.g., by visiting node 11) 2 links towards the third node are discovered doubling its score. Having a higher score than all other neighbors of 11, 21 will be added to the same community as 11. Afterwards one of 11's or 21's neighbors are visited where the reference score drops again leaving 11 and 21 in one community. all other nodes afterwards are correctly classified. Our solution is to check for this kind of misclassification by iterating through all nodes in a already discovered community checking if a node has more connections with another community then inside the "own" community. If so this node is merged to the connected community. As this procedure is raising the density in the community the node is merged to, the modularity value is increasing as stated in Trajanovski [START_REF] Trajanovski | Maximum Modular Graphs[END_REF].

To prove the correctness of Mutual Friend Crawling in terms of community detection, we compare the results of community assignments to existing approaches. However, as the variety of community detection algorithms is too large to compare against, we chose algorithms which (with slight modifications) can be used to identify communities while crawling. This means we are comparing against algorithms which iteratively assign nodes to communities without having the knowledge about the whole graph.

The chosen methods are:

1. Newman and Clauset's fast and greedy modularity maximizing method [START_REF] Clauset | Finding community structure in very large networks[END_REF] 2. Pons & Latapy's random walk method [START_REF] Latapy | Computing communities in large networks using random walks[END_REF] the Louvain(-la-Neuve) method by Blondel et al. [START_REF] Blondel | Fast unfolding of community hierarchies in large networks[END_REF] As all mentioned approaches are not directly providing a map of community ids to node ids we chose the partition resulting from the merges of nodes leading to a maximum of modularity. This partition is then compared to the output of our algorithm. For the given example graph in figure 1, all community detection algorithms found the same result as indicated by the colors in figure 1.

A comparison of the mentioned methods on some selected datasets is given in the following table 1. The datasets we compared against contain "Zachary's karate club" [START_REF] Zachary | An Information Flow Model for Conflict and Fission in Small Groups[END_REF], Girvan and Newman's "American College football games" [START_REF] Girvan | Community structure in social and biological networks[END_REF] and the network of all Digg users as described in Tang et. al. [START_REF] Tang | Digging in the Digg Social News Website[END_REF]. As given in table 1, our method is comparable to existing and well known procedures when compared in terms of the P in value and modularity. Except for the last dataset, a large scale directed network of all users of Digg.com where the number of detected communities is higher than given by the Louvain(-la-Neuve) or fast and greedy method.

However, this could be based on the resolution limit of modularity, as described in Fortunato and Barthélemy [START_REF] Fortunato | Resolution limit in community detection[END_REF]. A partition having a high modularity could lead to a relatively small number of large communities which is not reflecting the real community structure. The communities found by Mutual Friend Crawling are smaller than the ones found by the other methods still having the same properties like a power law shaped community size distribution. Also the number of users in a group given by our method is reasonable. The largest community found by Mutual Friend Crawling has a size of 9443 users whereas the largest one found by the Louvain method contains 186271 users. Without further investigation one may arguments for both numbers to be better than the other one. Therefore we leave this question to be solved by further research.

As the P in value and the modularity are global values which cannot be used to compare two partitions directly the Jaccard similarity index may be used. As mentioned earlier, if pairs of nodes are assigned to the same community this similarity will have a high value. Table 2. Comparison of the partitions discovered by our method to other community detection algorithms on the college football dataset [START_REF] Girvan | Community structure in social and biological networks[END_REF] using the Jaccard similarity index.

Table 2 shows the similarity of node assignment into communities between the different community detection algorithms. While this metric is not very sensitive to the number of communities it shows that our approach is equally good as well known methods. A more complete analysis of the Jaccard similarity index is given in van Kester [START_REF] Van Kester | Efficient Crawling of Community Structures in Online Social Networks[END_REF].

Conclusion and Outlook

In this paper we presented Mutual Friend Crawling, an algorithm to crawl a large scale OSN in such a way that the community structure of the network is detected and communities are crawled one after another. To our knowledge this is the first analysis directing a crawling process towards community structure. We showed that our method crawls communities one after another. Especially when obtaining large scale networks, researchers could begin to analyze datasets based on communities while the crawling process is still running.

Further work is needed if the community consists of overlapping groups as the partition of a large scale network into clearly separated communities does not make sense in most Online Social Networks. Also the application of standard metrics (like modularity or the used P in value) to compare partitions to real world community structure should be the focus of additional, future research.

Fig. 1 .

 1 Fig. 1. A simple example graph. Nodes are labeled by the order of traversal during the crawling process. Different colors denote different communities.

Fig. 2 .

 2 Fig. 2. Crawling communities. Depicts the percentage of nodes that have to be visited in order to crawl a full community.

Fig. 3 .

 3 Fig. 3. Plot of reference scores versus the number of visited nodes.

Fig. 4 .

 4 Fig. 4. Example graph where a misclassification may occur when visiting node 11.

Table 1 .

 1 Comparison of Mutual Friend Crawling to well known community detection procedures on different datasets.

	Dataset	Method	Number of communities Pin Modularity
	Karate club	original partition	2	0.86	0.36
		Louvain method	4	0.74	0.42
		Fast and greedy method	3	0.74	0.38
		Random walk method	5	0.63	0.35
		Mutual friend crawling	2	0.86	0.36
	Football	original partition	12	0.64	0.554
		Louvain method	10	0.708	0.604
		Fast and greedy method	5	0.746	0.544
		Random walk method	9	0.726	0.603
		Mutual friend crawling	9	0.736	0.57
	Digg	Louvain method	26646	0.94	0.478
		Fast and greedy method	37591	0.92	0.393
		Mutual friend crawling	78308	0.83	0.142

In this context, optimistic means that no mechanisms against crawling or screen scraping are enforced.

Acknowledgements: We thank Wynand Winterbach and Stojan Trajanowski for useful discussions. This project was partially supported by the Transsector Research Academy for Complex Networks and Services (TRANS).


El Moatez

Billah Nagoudi
email: e.nagoudi@lagh-univ.dz

Jérémy Ferrero
email: jeremy.ferrero@imag.fr

Didier Schwab
email: didier.schwab@imag.fr

LIM-LIG at SemEval-2017 Task1: Enhancing the Semantic Similarity for Arabic Sentences with Vectors Weighting

This article describes our proposed system named LIM-LIG. This system is designed for SemEval 2017 Task1: Semantic Textual Similarity (Track1). LIM-LIG proposes an innovative enhancement to word embedding-based model devoted to measure the semantic similarity in Arabic sentences. The main idea is to exploit the word representations as vectors in a multidimensional space to capture the semantic and syntactic properties of words. IDF weighting and Part-of-Speech tagging are applied on the examined sentences to support the identification of words that are highly descriptive in each sentence. LIM-LIG system achieves a Pearsons correlation of 0.74633, ranking 2nd among all participants in the Arabic monolingual pairs STS task organized within the Se-mEval 2017 evaluation campaign.

Introduction

Semantic Textual Similarity (STS) is an important task in several application fields, such as information retrieval, machine translation, plagiarism detection and others. STS measures the degree of similarity between the meanings of two text sequences [START_REF] Agirre | Semeval-2015 task 2: Semantic textual similarity, english, spanish and pilot on interpretability[END_REF]. Since SemEval 2013, STS has been one of the official shared tasks. This is the first year in which SemEval has organized an Arabic monolingual pairs STS. The challenge in this task lies in the interpretation of the semantic similarity of two given Arabic sentences, with a continuous valued score ranging from 0 to 5. The Arabic STS measurement could be very useful for several areas, including: disguised plagiarism detection, word-sense disambiguation, la-tent semantic analysis (LSA) or paraphrase identification. A very important advantage of SemEval evaluation campaign, is enabling the evaluation of several different systems on a common datasets. Which makes it possible to produce a novel annotated datasets that can be used in future NLP research.

In this article we present our LIM-LIG system devoted to enhancing the semantic similarity between Arabic sentences. In STS task (Arabic monolingual pairs) SemEval 2017, the LIM-LIG system propose three methods to measure this similarity: No weighting, IDF weighting and Partof-speech weighting Method. The best submitted method (Part-of-speech weighting) achieves a Pearsons correlation of 0.7463, ranking 2nd in the Arabic monolingual STS task. In addition, we have proposed another method (after the competition) named Mixed method, with this method, the correlation rate reached 0.7667, which represent the best score among the different submitted methods involved in the Arabic monolingual STS task.

Word Embedding Models

In the literature, several techniques are proposed to build word-embedding model.

For instance, [START_REF] Collobert | A unified architecture for natural language processing: Deep neural networks with multitask learning[END_REF] have proposed a unified system based on a deep neural network architecture. Their word embedding model is stored in a matrix M ∈ R d * |D| , where D is a dictionary of all unique words in the training data, and each word is embedded into a d-dimensional vector. [START_REF] Mnih | A scalable hierarchical distributed language model[END_REF] have proposed the Hierarchical Log-Bilinear Model (HLBL). The HLBL Model concatenates the n -1 first embedding words (w 1 ..w n-1 ) and learns a neural linear model to predicate the last word w n . Mikolov et al. (2013aMikolov et al. ( , 2013b) ) have proposed two other approaches to build a words representations in vector space. The first one named the continuous bag of word model CBOW (Mikolov et al., 2013a), predicts a pivot word according to the context by using a window of contextual words around it. Given a sequence of words S = w 1 , w 2 , ..., w i , the CBOW model learns to predict all words w k from their surrounding words (w k-l , ..., w k-1 , w k+1 , ..., w k+l ). The second model SKIP-G, predicts surrounding words of the current pivot word w k (Mikolov et al., 2013b). Pennington et al.( 2014) proposed a Global Vectors (GloVe) to build a words representations model, GloVe uses the global statistics of wordword co-occurrence to calculate the probability of word w i to appear in the context of another word w j , this probability P (i/j) represents the relationship between words.

3 System Description

Model Used

In Mikolov et al. (2013a), all the methods [START_REF] Collobert | A unified architecture for natural language processing: Deep neural networks with multitask learning[END_REF], [START_REF] Turian | Word representations: a simple and general method for semi-supervised learning[END_REF], [START_REF] Mnih | A scalable hierarchical distributed language model[END_REF], (Mikolov et al., 2013c) have been evaluated and compared, and they show that CBOW and SKIP-G are significantly faster to train with better accuracy compared to these techniques. For this reason, we have used the CBOW word representations for Arabic model 1 proposed by Zahran et al. (2015). To train this model, they have used a large collection from different sources counting more than 5.8 billion words including: Arabic Wikipedia (WikiAr, 2006), BBC and CNN Arabic corpus (Saad and Ashour, 2010), Open parallel corpus [START_REF] Tiedemann | Parallel data, tools and interfaces in opus[END_REF]), Arabase Corpus (Raafat et al., 2013), Osac corpus (Saad and Ashour, 2010), MultiUN corpus [START_REF] Chen | Multiun v2: Un documents with multilingual alignments[END_REF], KSU corpus (ksucorpus, 2012), Meedan Arabic corpus [START_REF] Meedan | Meedan's open source arabic english[END_REF] and other (see Zahran et al. 2015).

Words Similarity

We used CBOW model in order to identify the near matches between two words w i and w j . The similarity between w i and w j is obtained by comparing their vector representations v i and v j respectively. The similarity between v i and v j can be evaluated using the cosine similarity, euclidean distance, manhattan distance or any other similarity measure functions. For example, let " " 1 https://sites.google.com/site/mohazahran/data (university), " " (evening) and " " (faculty) be three words. The similarity between them is measured by computing the cosine similarity between their vectors as follows:

sim( , ) = cos(V ( ), V ( )) = 0.13 sim( , ) = cos(V ( ), V ( )) = 0.72
That means that, the words " " (faculty) and " " (university) are semantically closer than " " (evening) and " " (university).

Sentences similarity

Let S 1 = w 1 , w 2 , ..., w i and S 2 = w 1 , w 2 , ..., w j be two sentences, their words vectors representations are (v 1 , v 2 , ..., v i ) and (v 1 , v 2 , ..., v j ) respectively. There exist several ways to compare two sentences. For this purpose, we have used four methods to measure the similarity between sentences. Figure 1 illustrates an overview of the procedure for computing the similarity between two candidate sentences in our system.

Figure 1: Architecture of the proposed system.

In the following, we explain our proposed methods to compute the semantic similarity among sentences.

No Weighting Method

A simple way to compare two sentences, is to sum their words vectors. In addition, this method can be applied to any size of sentences. The similarity between S 1 and S 2 is obtained by calculating the cosine similarity between V 1 and V 2 , where:

V 1 = i k=1 v k V 2 = j k=1 v k
For example, let S 1 and S 2 be two sentences:

S1 = "
" (Joseph went to college).

S2 = "

" (Joseph goes quickly to university).

The similarity between S 1 and S 2 is obtained as follows:

Step 1: Sum of the word vectors

V1 = V ( ) + V ( ) + V ( ) V2 = V ( ) + V ( ) + V ( ) + V ( )
Step 2: Calculate the similarity The similarity between S 1 and S 2 is obtained by calculating the cosine similarity between V 1 and

V 2 : sim(S 1 , S 2 ) = cos(V 1 , V 2 ) = 0.71
In order to improve the similarity results, we have used two weighting functions based on the Inverse Document Frequency IDF [START_REF] Salton | Termweighting approaches in automatic text retrieval[END_REF] and the Part-Of-Speech tagging (POS tagging) [START_REF] Schwab | Approche hybride-lexicale et thématique-pour la modélisation, la détection et lexploitation des fonctions lexicales en vue de lanalyse sémantique de texte[END_REF] [START_REF] Lioma | Part of speech based term weighting for information retrieval[END_REF].

IDF Weighting Method

In this variant, the Inverse Document Frequency IDF concept is used to produce a composite weight for each word in each sentence. The idf weight serves as a measure of how much information the word provides, that is, whether the term that occurs infrequently is good for discriminating between documents (in our case sentences). This technique uses a large collection of document (background corpus), generally the same genre as the input corpus that is to be semantically verified. In order to compute the idf weight for each word, we have used the BBC and CNN Arabic corpus2 (Saad and Ashour, 2010) as a background corpus. In fact, the idf of each word is determined by using the formula: idf (w) = log( S W S ), where S is the total number of sentences in the corpus and W S is the number of sentences containing the word w. The similarity between S 1 and S 2 is obtained by calculating the cosine similarity between V 1 and V 2 , cos(V 1 , V 2 ) where:

V 1 = i k=1 idf (w k ) * v k V 2 = j k=1 idf (w k ) * v k
and idf (w k ) is the weight of the word w k in the background corpus.

Example: let us continue with the sentences of the previous example, and suppose that IDF weights of their words are: 0.27 0.37 0.31 0.29 0.22 0.34

Step 1: Sum of vectors with IDF weights

V1 = V ( ) * 0.31 + V ( ) * 0.37 +V ( ) * 0.27 V2 = V ( ) * 0.34 + V ( ) * 0.22 + V ( ) * 0.29 +V ( ) * 0.37
Step 2: Calculate the similarity The cosine similarity is applied to computed a similarity score between V 1 and V 2 . sim(S 1 , S 2 ) = cos(V 1 , V 2 ) = 0.78 We note that the similarity result between the two sentences is better than the previous method.

Part-of-speech weighting Method

An alternative technique is the application of the Part-of-Speech tagging (POS tag) for identification of words that are highly descriptive in each input sentence [START_REF] Lioma | Part of speech based term weighting for information retrieval[END_REF]. For this purpose, we have used the POS tagger for Arabic language proposed by G. Braham et al. (2012) to estimate the part-of-speech of each word in sentence. Then, a weight is assigned for each type of tag in the sentence. For example, verb = 0.4, noun = 0.5, adjective = 0.3, preposition = 0.1, etc.

The similarity between S 1 and S 2 is obtained in three steps [START_REF] Ferrero | Using Word Embedding for Cross-Language Plagiarism Detection[END_REF] as follows:

Step 1: POS tagging In this step the POS tagger of G. Braham et al. ( 2012) is used to estimate the POS of each word in sentence.

P os tag(S 1 ) = P os w 1 , P os w 2 , ..., P os w i P os tag(S 2 ) = P os w 1 , P os w 2 , ..., P os w j

The function P os tag(S i ) returns for each word w k in S i its estimated part of speech P os w k .

Step 2: POS weighting At this point we should mention that, the weight of each part of speech can be fixed empirically. Indeed, we based on the training data of SemEval-2017 (Task 1)3 to fix the POS weights.

V 1 = i k=1 P os weight(P os w k ) * v k V 2 = j k=1 P os weight(P os w k ) * v k
where P os weight(P os w k ) is the function which return the weight of POS tagging of w k .

Step 3: Calculate the similarity Finally, the similarity between S 1 and S 2 is obtained by calculating the cosine similarity between V 1 and V 2 as follows:

sim(S 1 , S 2 ) = cos(V 1 , V 2 ).

Example:

Let us continue with the same example, and suppose that POS weights are:

verb noun noun prop adj prep 0.4 0.5 0.7 0.3 0.1

Step 1: Pos tagging The function P os tag(S i ) is applied to each sentence.

P os tag(S 1 ) = verb noun prop noun P os tag(S 2 ) = noun prop verb adj noun

Step 2: Sum of vectors with POS weighting

V1 = V ( ) * 0.5 + V ( ) * 0.7 + V ( ) * 0.4 V2 = V ( ) * 0.5 + V ( ) * 0.3 + V ( ) * 0.4 + V ( ) * 0.7
Step 3: Calculate the similarity sim(S 1 , S 2 ) = cos(V 1 , V 2 ) = 0.82

Mixed weighting

We have proposed another method (after the competition), this method propose to use both IDF and the POS weightings simultaneously. The similarity between S 1 and S 2 is obtained as follows:

V1 = i k=1 idf (w k ) * P os weight(P osw k ) * v k V2 = j k=1 idf (w k ) * P os weight(P os w k ) * v k
If we apply this method to the previous example, using the same weights in Section 3.2 and 3.3, we will have:

Sim(S 1 , S 2 ) = Cos(V 1 , V 2 ) = 0, 87.
4 Experiments And Results

Preprocessing

In order to normalize the sentences for the semantic similarity step, a set of preprocessing are performed on the data set. All sentences went through the following steps: 1. Remove Stop-word, punctuation marks, diacritics and non letters. 2. We normalized to and to .

3. Replace final followed by with . 4. Normalizing numerical digits to N um.

Tests and Results

To evaluate the performance of our system, our four approaches were assessed based on their accuracy on the 250 sentences in the STS 2017 Monolingual Arabic Evaluation Sets v1.1 4 . We calculate the Pearson correlation between our assigned semantic similarity scores and human judgements. The results are presented in These results indicate that when the no weighting method is used the correlation rate reached 59.57%. Both IDF-weighting and POS tagging approaches significantly outperformed the correlation to more than 73% (respectively 73.09% and 74.63%). We noted that, the Mixed method achieve the best correlation (76.67%) of the different techniques involved in the Arabic monolingual pairs STS task.

Conclusion and Future Work

In this article, we presented an innovative word embedding-based system to measure semantic relations between Arabic sentences. This system is based on the semantic properties of words included in the word-embedding model. In order to make further progress in the analysis of the semantic sentence similarity, this article showed how the IDF weighting and Part-of-Speech tagging are used to support the identification of words that are highly descriptive in each sentence. In the experiments we have shown how these techniques improve the correlation results. The performance of our proposed system was confirmed through the Pearson correlation between our assigned semantic similarity scores and human judgements. As future work, we are going to combine these methods with those of other classical techniques in NLP field such as: n-gram, fingerprint and linguistic resources.

Table 1 .

 1

	4 http://alt.qcri.org/semeval2017/task1/data/uploads
	/sts2017.eval.v1.1.zip

Table 1 :

 1 Correlation results

https://sourceforge.net/projects/ar-text-mining/files /Arabic-Corpora/

http://alt.qcri.org/semeval2017/task1/data/uploads/

Acknowledgments

This work was carried out as part of a PNE scholarship funded by Ministry of Higher Education and Scientific Research of Algeria, with an international collaboration between two research laboratories: LIM Laboratoire d'Informatique et de Mathmatiques Laghouat, Algeria and LIG Laboratoire d'Informatique de Grenoble (GETALP Team), France.