A Novel C2C E-Commerce Recommender System Based on Link Prediction: Applying Social Network Analysis

Social network analysis emerged as an important research topic in sociology decades ago, and it has also attracted scientists from various fields of study like psychology, anthropology, geography and economics. In recent years, a significant number of researches has been conducted on using social network analysis to design e-commerce recommender systems. Most of the current recommender systems are designed for B2C e-commerce websites. This paper focuses on building a recommendation algorithm for C2C e-commerce business model by considering special features of C2C e-commerce websites. In this paper, we consider users and their transactions as a network; by this mapping, link prediction technique which is an important task in social network analysis could be used to build the recommender system. The proposed tow-level recommendation algorithm, rather than topology of the network, uses nodes features like: category of items, ratings of users, and reputation of sellers. The results show that the proposed model can be used to predict a portion of future trades between users in a C2C commercial network.

INTRODUCTION
In recent years, moving from mass production toward mass customization has been an important factor for success of companies in global markets. In other words, diversity and customization of products have replaced long life time and standardized products. The emersion of electronic commerce has facilitated their movement toward personalization of products. In order to expand personalization, companies need to increase the amount of information that users should process before choosing their ideal items. This phenomenon which is known as Information overload problem, was the main reason of developing recommender systems in e-commerce [1].
Recommendation based on best-selling items, demographic information of users, and user's past behavior analysis, are samples of techniques used by Recommender systems in ecommerce websites [2]. These techniques can be considered as different types of personalization, since they help the website to adapt itself to the customers. Although most of commercial websites use B2C e-commerce, some of them support C2C ecommerce. Ebay.com, Bizrate.com, etc. are instances of websites in which customers can be buyer and seller at the same time. Current recommendation algorithms (e.g. collaborative filtering, content based algorithms, and hybrid algorithms) can be most useful for B2C e-commerce websites. Since these algorithms only concentrate on items and consumers (but not sellers), there is a lack of recommender systems for C2C e-commerce websites [3].
The solution proposed in this paper for the mentioned problem is based on social network analysis. Social network analysis emerged as an important research topic in sociology decades ago, and its first studies was focused on the adoption of medical and agricultural innovations [4]. It is a vast field of research that has attracted researchers from anthropology, economics, psychology, biology and geography, just to mention a few. Link prediction which is an important task in social network analysis, is the problem of predicting the existence of a link between two nodes in a graph where prediction is based on the attributes of the nodes and other observed links [5].
In this paper, we are going to design a recommender system which can be used in commercial networks. A commercial network is a graph which its nodes represent users of a C2C ecommerce website and edges represent the transactions between these users. If we presume transactions between users as edges of a graph, link prediction approaches can be used to design the recommender system. But before using link prediction techniques, the nature of network should be identified and analyzed. Since the context of links in commercial networks are different from links in common social networks, we must adapt link prediction approaches to our problem. So far, several nodes proximity measures are introduced for link prediction in common social networks (e.g. Adamic-Adar, FOAF, etc. [6]) but as we will discuss in section III, many of them are not applicable for being used in our model.
The main goal of this paper is to propose a model for predicting future trades between users in a commercial network. If G1(U,E1) is the transactions graph in time t1 (U is the set of nodes and E1 is the set of graph edges in time t1). We are going to predict edges of the graph in time t2 (t1<t2). So we should predict the graph G2(U,E2) in time t2 where the difference between G1 and G2 is in their edges. Predicting these new links and using them in a recommender system could have two benefits: first, such recommender system can accelerate formation of trades between users and this can benefit all involving parties, i.e. buyers and sellers and third parties. Second, recommending a user to buy an item from another user can end up to a trade that was not going to happen in future at all. Another goal that we are going to seek is to predict items sold in future trades. Since the ultimate goal of this paper is recommending items of sellers to target users, we should choose the most appropriate item of the sellers to increase the probability of accepting recommendations.
The rest of the paper is organized as follows: In section II, we briefly review some of previous works on link prediction problem in social networks and recommendation algorithms for C2C websites. Section III contains our proposed methodology for solving the problem ahead. In section IV we discuss the experiments we performed and the data used in experiments. Results are presented in section V, and finally in section VI we present conclusions and future works.
II. RELATED WORK So far, plenty of research has been done in the field of link prediction and item recommendation in common social networks, but just a few of them has focused on commercial networks. In [7], a recommendation model for C2C online trading is proposed. The author divides user's behaviors in a C2C website into four categories: browse, attention, bidding, and purchase. Based on these criteria, a users' preference matrix is built. Afterwards, similarity between current active users and other users is calculated. Finally Top-N recommendation list is built for each user based on most important items for his neighbors. Three-dimensional collaborative filtering is another method for recommending items in C2C commercial networks which is introduced in [8]; They extended the traditional collaborative filtering technique to solve the recommendation problem in C2C e-commerce websites. Their proposed recommender system firstly calculates seller similarities using seller features, and fills the rating matrix based on seller similarities. Then it calculates the buyer similarities using historical ratings, and defines neighbors of each user to predict unknown ratings. Eventually, the system recommends the seller and product combinations with the highest prediction ratings to the target user.
In, Arazy et al. [9] proposed a framework for improving social recommender systems using behavioral theories of advice-taking. They identified four factors that impact a user's decision when he receives a recommendation: Homophily, Trust, Reputation, and Tie strength. After computing these relationship factors, the system should calculate a weighted average of them in order to rate each recommendation source. Then these sources could be used to recommend items to users. In [10], Guy et al. studied personalized recommendation of social software items, including bookmarked web-pages, blog entries, and communities. They focused on recommendations that are derived from the user's social network. In their proposed model, Social network information is collected and aggregated across different data sources. A group recommendation system is proposed In [11]. The system makes recommendations based on supervised entropy, association rules and D-Tree classification method.
Unlike item recommendation in C2C commercial networks, a large number of researches has been done on link prediction and link recommendation in common social networks. Some works have used only network's topology for predicting new links. Nowell et al. in [5], state that link prediction could be done just by using topological features. They used three different methods to predict missing links: Methods Based on Node Neighborhoods, Methods Based on the Ensemble of All Paths, and Higher Level Approaches. In [6], de Sá et al. investigated the effect of using supervised learning approaches on weighted graphs. They used pairs of nodes as instances of binary classification problem in which the predictor attributes were metrics computed from the network topology, and the target attribute was the presence or absence of a link between the nodes in future. Link prediction using hybrid approaches is investigated in many of prior works. Yin et al. [12] proposed a framework for link recommendation based on attribute and structural properties in a social network. They enumerated six criteria for link recommendation: homophily, rarity, Social influence, common friendship, social closeness, and preferential attachment. In [13], Chen et al. compared the performance of different people recommendation in predicting and recommending potential friends. The comparison was between four algorithms: content matching, content plus link, friend of a friend, and SONAR.
To the best of our knowledge, except [8], none of the previous researches about item recommendation in C2C ecommerce websites are focused on choosing appropriate seller for target users, and this is one of the main difference between this work and previous works. Besides, this paper uses link prediction technique for recommending items in C2C ecommerce websites, an approach that has not been used in previous researches about C2C e-commerce recommender system.

III. PROPOSED MODEL
In general, link prediction approaches are divided into three categories: methods based on structural measures in the network, methods based on the content or attribute similarity between nodes, and methods based on probabilistic models. In this paper, measures based on structure of network and attributes of nodes are used for link prediction task. This choice is according to the results of previous works which state the more features of social network we use, the stronger predictions we can make [13], [12]. Our proposed model for link recommendation (i.e. recommendation of buying items from sellers) in commercial networks is shown in Fig. 1. These are the assumptions that we made to design the model:  There is a network of users in which some users are just seller, some are just buyer, and some are both.
 After every transaction, buyers can rate sellers according to four aspects: overall satisfaction, quality of goods, delivery time, and seller support.
 Each item belongs to a certain category (number of categories are limited).
As you can see in Fig. 1, the recommendation model consists of six stages. It should be noted that stage 2, 3 and 4 can be done in parallel, but other stages must be performed in specified order. A. Computing structural similarity The first stage of our model is computing similarity of each pair of nodes according to network structural metrics. Considering definition of the problem, we cannot directly use these metrics. Because unlike common social networks, there is no clear evidence that having more common neighbors or being close to each other in graph, increases the probability of forming a link between two nodes. So in this stage, a different approach must be used. SimRank is a similarity measures proposed for directed graphs. This measure which is proposed by Jeh & Widom in [14], computes similarities based on an intuitive concept: two objects are similar if they refer to similar objects or they are referred by similar objects. Like PageRank algorithm [15], SimRank computes similarity of graph nodes using their input and output edges. The first step is to calculate user similarities according to SimRank measure. We use Eq.
(1) to calculate similarity of target users to other users in transactions graph.
In Eq. (1), u and v are sample users, S (u,v) is the similarity of u and v, C is the damping factor, I(u) is the list of sellers that user u have purchased items from and I(v) is the list of sellers that user v have purchased items from. After computing similarity of each target user like u to other users in graph, there will be a list of n similar users to u. We use the list of similar users to specify candidate sellers; for this purpose, we choose sellers that have sold items to users in u's similarity list (but u has bought nothing from them) as candidate sellers. Assume the graph in Fig. 2 as a commercial network. Nodes on the left are buyers and nodes on left are sellers. Considering n=1 (size of u's similar users list), candidate sellers for u in this graph would be d and e.

B. Computing Category Scores
Each item in the network belongs to a certain category. So we can calculate proximity of users according to the categories in which they have sold or bought items. I.e. we have a vector of non-numeric values for each user. There are bunch of algorithms for measuring similarity of such vectors. Here, the significant note is the importance of different categories for each user. For considering the importance of each category for each user, we used two factors: In Eq. (2), Lu(a) is the importance of category a in user's local network, a is a sample category, and N(u) is the list of u's adjacent nodes . A(v,a) is equal to 1 if both u and v have bought or sold an item in category of a, and 0 otherwise; If u and v does not have any category in common, Lu(a) is equal to 1. Finally, we calculate ultimate score of each category for each user using Eq. (3) in which Qu(k) and Pu(k) are respectively number and price of item k, and Lu(a) is computed using Eq. .
Now we can use similarity measures like Jaccard's coefficient to compute the score of candidate sellers for the target user according to category of items. Eq. (4) is the adapted form of Jaccard's coefficient for our problem, Where Scategory(u,v) is the category score between u and v, c is a category that both u and v have traded in, A(u) is the list of categories that user u have traded in, and wu(a) is the category score of attribute a according to user u:

C. Computing Reputation Scores
Reputation is a quantity derived from the prior interactions of individuals to others in a community which is globally visible to all members of the network. Although the reputation of sellers is not the most important factor of increasing number of sales, but it is one of the effective factors for buying items from them [16], [17]. So we should consider the reputation of sellers in recommending items to target users. In commercial networks, the information about previous transactions can be used to calculate the reputation of users [18]. Generally, reputation systems are divided into two categories: centralized and distributed; In centralized reputation systems, a central authority is responsible for saving ratings or complaints and computing reputation of users, unlike distributed ones which there is no centralized authority for computing reputations [19]. The type of reputation system in our model is centralized but unlike common centralized reputation systems, every seller may have a different value of reputation form the viewpoint of different users. To compute reputation of each seller, four factors are considered: seller ratings from prior transactions, monetary value of each transaction, total number of seller's transactions, and importance of categories to target user. Eq.
(5) shows how we calculate a seller's reputation from perspective of a target user. total sales number of user v, Rs(v,i) is the average value of item quality, responsiveness, shipment cost, and shipment time rating that seller v have received in transaction i (a number between [-1,1]). D(v,i) is the monetary value of user v's sales in transaction i. L (u,g(i)) is the importance of category in which user v have sold an item and is computed similar to Lu(a) in Eq.
(2); If u has not traded in category g(i), L(u,g(i)) value will be equal to 1.

D. Computing Ratings Scores
The other metric that can be used to find best sellers, is similarity between candidate sellers and prior sellers that have sold items to users, in terms of ratings they have gained. We assume that buyers rate sellers after each transaction, regarding to the overall satisfaction, quality of goods, delivery time, and seller support. These rating vectors can be used to choose best sellers for target users. Several metrics have been proposed in order to compute similarity of two numeric vectors. Cosine similarity [20] and Pearson correlation [21] are the most common ones. Here is the adopted version of cosine similarity we used to compute rating scores: In Eq. (6), Srating is the similarity of seller v to sellers of user u according to their ratings, I(v) is the list of sellers that user u has bought items from, w is each user who has sold items to user u, j is a rating component, and R is total number of rating components (which is equal to 4 in our problem), MR(v,j) is the average rating of user v according to rating component j in all of his sales, and MR(w,j) is the average rating of user w according to rating component j in all of his sales.

E. Computing Total Score of Candidates
The List of best sellers for a target user is built using three metrics we discussed before (Category score, Ratings score, and Reputation score). Before using these 3 scores, they should be normalized into a number between [0,1]. Eventually, total score of each candidate is calculated by combining the scores from previous stages: Stotal(u,v) is the total score of seller v for recommending his items to user u, α is category score coefficient, β is ratings score coefficient, ϒ is reputation score coefficient, Scat(u,v) is category score of user v according to user u, Srat(u,v) is rating score of user v according to user u, and Srep(u,v) is reputation score of user v according to user u. α, β and ϒ must be chosen in range of [0,1] so that α+β+ϒ=1. By changing value of these coefficients, one can change the influence of each score in building best sellers list.

F. Choosing items from sellers
After creating list of sellers for each user, we must choose one item from each seller's selling items. Online stores use several strategies for recommending items to users. These strategies include suggestion of random items, suggestion of best-selling items, using association rules (using algorithms like A-priori), collaborative filtering (using ratings of items), content based filtering (using textual information of items), demographic filtering (using age, gender, job, living area) and so on.
We could not use the last three methods listed above Hence users' demographic information, textual information about data, and ratings of users to items were not available in our dataset. So in our experiments, we used these methods to perform the last stage of our model: choosing best-selling items, choosing random items, and using association rules for item selection. In random item suggestion, a random item from selling items of a seller is selected and in Best-selling item suggestion, we select the best selling item of the seller. For applying association rules, we use the list of items that users have purchased so far. So we use a-priori algorithm to find strong rules and considering these rules, we select items from selling items each seller; If no rules could be used for item selection, we use random selection for suggesting items. The simplest form of recommendation is suggesting a single item. A single item would increase the chance that the customer will accept the suggestion. But most of the recommender systems provide a list of suggestions for customers. A list of items can increase the probability that user's desired item shows up in the list of items [22]. In our experiments, we select one item from each seller in order to shorten the final recommendation list.

IV. DATA AND EXPERIMENTS
The best datasets that could be used for our experiments is the transaction data of users in C2C e-commerce websites. So we used a dataset of Bizrate.com to evaluate the performance of our proposed model. The dataset contains information about 2066 transactions between sellers and buyers. Each record of transaction includes: sellerID, buyerID, itemID, category, price, and ratings that seller has received from buyer. The ratings include four parameters: overall satisfaction, quality of goods, delivery time, and seller support. The graph of sellersbuyers graph has an average degree of 1.3, density of 0.001, maximum in-degree of 17 (i.e. purchases), and maximum outdegree of 167 (i.e. sales).
Precision and recall are the most common measures for evaluating prediction algorithms. Precision of a prediction algorithm is the number of truly predicted links divided by total number of predictions, and recall is the number of truly predicted links divided by total number of true links that can be predicted [12]. According to some studies in the field of information retrieval, as the level of precision increases, the level of recall decreases (and wise-versa). F-measure which is the harmonic mean of precision and recall, can be used to balance the two measures [23]. In order to compute precision, recall and F-measure, we used 10-fold cross validation [24]. So the data is partitioned into 10 nearly equally sized folds and 10 iterations of training and validation is performed. In each iteration, a different fold is held-out for validation (validation set) and the other 9 folds are used for learning (training set). The similarity of nodes and different scores (discussed in section III) are computed using the training set. The average value of precision, recall and F-measure obtained from these iterations is considered as estimated values of these measures on unseen data. To compute precision, recall and F-measure in each iteration 50 nodes that have least one edge in validation set are randomly selected and for each node, 1 to 25 predictions is made.
V. RESULTS AND DISCUSSION We measured precision, recall and F-measure at two levels: the first level, is to predict whether two users will show up in a same transaction in future or not (as buyer and seller); the second level is to predict sold items in future transactions. In other words, the first level is evaluating the model without performing stage 6. Obviously, size of precision, recall and Fmeasure of the model at stage 6 cannot be more than size of these metrics at stage 5. Fig. 3, Fig. 4 and Fig. 5 shows the percentage of precision, recall and F-measure of the model at user level (M1). In M2, the scores computed at stage 2, 3 and 4 are not used; instead, random sellers are selected from candidate list created at stage 1 to form prediction list for target users. As you see in Fig. 5, for M1, the level of F-measure decreases as the number of recommendations for each user increases. This can be a result of low number of missing link for each target user; in our experiments, this value was at least of 1 and at most 3 for each sample user. let Consider the number of missing edges of a sample node is equal to 2; If we assume that all of its missing links are truly predicted at the point of 5 prediction for the user, any other predictions for this user will decrease the overall precision of the system, because there is no more missing links for the user to be recovered.   The final form of the recommendation, is a list of items from different sellers, so we should measure the performance of model at predicting items too. Table I shows the f-measure of proposed model at item prediction using the three methods discussed in section III. As you see in the table, best-selling items method is having the best performance among others. But this method lacks personalization in recommending items to users. The performance of association rules method is being weak and almost close to random prediction method. The reason for this weak performance can be the weakness of extracted rules. VI. CONCLUSION AND FUTURE WORK Online stores need an efficient e-marketing strategy. Modeling users' behavior and recommending items based on their interests is one of the most efficient strategies in ecommerce. Over time, recommender systems are becoming an inseparable component of e-commerce websites. But unfortunately, most of the current recommendation models could only be used in B2C e-commerce websites. In this paper, we proposed a recommender system for C2C e-commerce websites using prior transactions of users, categories of items, rating of users, and reputation of sellers. The goal of the system is recommending items from most appropriate sellers to target customers.
The Results of our experiments show that the proposed model can predict some of the missing links in commercial networks. The portion of predicted links by our model may seem to be low, but one should consider that even this low percent can end up to a big number of new transactions in large scale commercial networks. It should be noted that using different datasets for experiments may have significant effects on results, as the scale of our dataset was too large. Similar to other recommendation models, a challenge for our model is recommending items to new users (cold start). There are several ways to deal with this problem: recommending items from sellers who have sold most items in the network, sellers who have best reputation in the network and recommending items from random sellers are some common solutions for the problem.
The proposed model can be improved in several ways. The results of related works shows that considering time element in recommendations, can improve performance of recommender systems [10], [9]. So investigating the effect of using time in predictions is one of the future works. As the effect of using weight of links in a graph for link prediction is not deterministic yet [25], other possible future work can be using the weight of links between users for computing similarities at the stage of creating candidates list.


extfieldsofstudy:
Computer Science
Mathematics

text:
Entropy NAND: Early Functional Completeness in Entropy Networks

An observer increases in relative entropy as it receives information from what it is observing. In a system of only an observer and the observed, an increase in the relative entropy of the observer is a decrease in the relative entropy of the observed. Linking together these directional entropy disequilibriums we show that NAND and NOR functionality arise in such networks at very low levels of complexity.

description of negentropy [1, (eq. 3)] for an observer which remains isothermal by radiating the entropy increase as thermal energy. The negentropy principal builds on previous work (Szilard [2] and others) stating that the entropy of the observer is negative as entropy is transferred to the observer's environment.
Instances of the generation and transfer of entropy through observation can be linked together to produce an observation network model which we illustrate in figure 1. Entropy network structures have been investigated previously [8,13,14]. A description of entropy transfer can be found in the Schreiber transfer entropy [3] which has been thermodynamically characterized by Prokopenko, Lizier & Price [15]. We describe a discrete entropy transfer between two idealized elements which are entropy containers.
Networks constructed from observations can be functionally complete, which we show in this article by constructing a NAND gate from entropy transfers.

Observers
We propose our version of an observer as a discrete element which can change. By discrete we mean having no relation with any other element, except through the relationship type which we describe as an observation. We define element to be that which generates 1 nat of entropy in the observer when observed. The element is the prototype for possible thermodynamic disequilibrium, initially without internal differentiation. The interior of our prototypical element is homogeneous, having no features to compare and so having no internal information, and no entropy. The first differentiation in an element is the instantiation of disequilibrium that is a directed transfer of entropy. As stated previously, entropy creation from observation has been described to have a minimum limit [1,10,11,12] of k B T ln 2. We can set an appropriate temperature so that k B = 1 which simplifies the description of the entropy of the observer to: where m is the quantity of states of the observer. Before observation, m = 1, through observation m = 2 at least momentarily until the entropy is transferred into the environment. We can represent this element as a pattern that has no features, illustrated in figure 1.a as a circle where m = 1; and as a divided circle where m=2. Our small model system is shown in figure 1 and 2. We illustrate the element as a pattern that has no features in figure 1.a as a circle. An element in internal entropy disequilibrium as represented as a circle split into parts, figure 1.b labeled b1, b2, illustrated with lines drawn through the circle enumerating the component states of disequilibrium. An example shows two states and the simplest entropy disequilibrium in figure 1.b.

Observation of an object
Our version of observation of an object is a process in which the observer gains at least one bit of information, and which is an entropy change. In a system of only the observer and the observed, this relative entropy change is described by 1 nat. We can find a physical description of the relation (measuring temperature T, S is total summed entropy) as S=E/T as stated by Brillouin [1, (eq. 40)] where the total entropy increase from a single observation is described.
We equate the smallest entropy increase to the simplest differentiation of a discrete element, resulting in an entropy increase of 1 nat. The entropy increase we describe as a split of the observer into two states which we can describe as "before observation" and "after observation".
In the course of observation the complexity of the element is momentarily increased, which increases its entropy in relation to those observers which observe it. This entropy must be dissipated to the environment if the element is to remain isothermal, we represent the environment as another discrete element as defined previously, this is illustrated in the transfer network in figure 1.c The graph of binary entropy H(p) shows entropy peaks between the beginning and ending states in a system of one bit expressing a state change. This graph can be verified experimentally on a statistical basis. In this article we describe a "before" and an "after" state, and propose that the transition between these states follows the binary entropy graph through time, yielding maximum entropy at the theoretical midpoint of the transition. The transition between states for our simple element model is a momentary peak at maximum entropy, which we describe as a Kronecker delta function that is 1 only at 0 (0 being the theoretical midpoint of the transition). For illustrative purposes we also describe in section 3 a physical example using ice cubes as entropy containers, in which the transition would need to occur over a longer span of time.

Entropy transfer
The minimum entropy transfer on observation is 1 nat which is a relative entropy reduction for the observed: Minimum Entropy Transfer = 1 nat Minimum Energy Required = k B Temperature ln 2 (Joules) At stable temperatures (isothermal conditions, in Joules) [10] this defines the minimum energy required to transfer one bit of information. For an isothermal system, if entropy has increased, such entropy must be absorbed by the environment, otherwise the system is not isothermal. When we model this transfer with the Kronecker delta, the absorption of new entropy appears to occur instantly for elements which are connected directly (with a network distance of 1)

Entropy of erasure
If the system in which a bit is changed is small enough, and it has no memory, then changing a bit is deleting information. This deletion of information by the Landauer principle will require the dissipation of heat of at least k B T ln 2 of heat per lost bit [13]. This dissipation interacts with the environment of the observer. In a small system where the environment is composed of only a single discrete element (figure 1.c), the dissipated entropy must be absorbed by this single element.
In the following diagrams we describe the creation of an element's relationships with other elements.
These elements are an accounting device which we can use to trace entropy transfer. An element can split into two elements (before and after) in the creation of a nat of entropy, which is an observation and the simplest relationship.
Entropy before observation is Temperature ln 1 =0, as there are no relationships in the system (figure

Entropy transfer classes
We can classify entropy network structures according to their entropy transfer directionality. This can be a simple means to classify simple patterns through entropy networks.
Entropy networks are diverse. Entropy-driven organization occurs at least at the molecular scale [17].
Entropy is directed by people, ubiquitous in the practice of thermodynamic industry. People are sensitive to entropy at large scales [18] and directly through sensory perception in the course of pattern recognition.
These areas all express entropy networks, while a common classification of entropy network components throughout these systems is lacking. Classification by total entropy [19], has been examined [20] to search for information. But using a measure of total entropy tells us nothing about what the net connects to and how it is formed. Classification by connectivity has been carried out historically in the practice of geometry and related studies. Unsurprisingly, there are several basic transfer patterns from which other patterns can be built. We classify them by how they transfer entropy, by linking together instances of observation.
We describe two classes, which we label first order and second order, the order is an indication of the quantity of observations that compose the network. We stop at two. The first order contains only one pattern of observation, the single observation. The second order contains four patterns, which are all possible patterns for two observations. In the second order, the only difference between networks is the directionality of entropy transfer.

A first order classification (all possible patterns for one observation)
1) The single observation. This is the simplest discrete entropy transfer describing a single element splitting into two states on observation of another element, creating entropy disequilibrium of 1 nat.

A second order classification (all possible patterns for two observations)
This second order of classification is all possible patterns for two observations. The patterns have equal complexity but each transfers entropy differently. NAND state (inputs:11; output:0 ) is shown by the s < pattern shown in figure 2.c, which has two elements being observed and so has lower relative entropy while their observer, being split through before and after states has higher entropy.
NAND state (inputs:00; output:1) is shown in the e > pattern ( figure 2.b), in which the central e element is of low relative entropy because it is being observed by two other elements of higher relative entropy.
The next two NAND states are represented by the two other possibilities that exist for the sequential, train-like observation patterns that are (inputs:01; output:1) and (inputs:10; output:1). We can note that these last two patterns, being sequential, can only be distinguished (front to back or back to front) if the NAND gate is embedded within another network, which is appropriate because a logic gate requires input and output to be a gate. In the following expressions we use the caret notation (a hat) to represent that an element is the observation of another element, for example = 1 means that is the observation of 1 . > = = 1 ; ≥ T ln 2 = 2 ; ≥ T ln 2 = T ln 1

Discussion
To physically embody this NAND system would require the embodiment of elements which can contain entropy. In our simple example we use discrete elements which have discrete entropy values, these values are controlled by the direction of entropy transfer between elements. A macro-scale implementation of this could be constructed, but would become statistical as the thermodynamic transfers would be of higher energies and not discrete observations. In a possible experimental implementation our simple elements could be embodied by ice cubes which are thermodynamic heat reservoirs, and entropy transfer could be arranged by heat pumping, thermally conductive paths between the reservoirs. Two ice cubes are inputs which are connected to a central ice cube by a thermal pump, and the central ice cube is a NAND output. For our macro-scale implementation, the thermal coupling must be a directionally controllable entropy pump, which could be implemented as a heat pump (thermal transfer engine).
The three elements that compose our NAND gate are then three ice cubes. Entropy increase, considering constant volume and pressure would then be a temperature increase, and high entropy ice cubes would melt. Low entropy ice cubes would be solid. In the two-link (two observation) network that we have described, if we are to drain the entropy from two ice cubes ( figure 2.b), the central ice cube (represented in figure 2.b as element e) must absorb the entropy, and melt. If we are to drain the entropy from the central ice cube into the other two ( figure 2.b), they must increase in entropy and melt while the central ice cube (e) freezes.
We note that within a quantity of exactly 2 observations, NAND is possible with output thresholded so that the logical false ≤ ½ and logical true > ½. NOR is possible with a slight modification of this threshold. AND, OR, XAND and XOR are unreachable with two observation networks, they require more than 2 observations for implementation. That discrete observation entropy networks can attain functional completeness almost instantly may be but a curiosity. However, the statistical, thermodynamic NAND/NOR produces the same functionality in the macro scale, and the thermodynamic gate would share in the physical ubiquity of thermodynamic transfer.
The energy associated with a single observation and it's relation to relative entropy in quantum models was already noted by Brillouin in 1953. It has been increasingly accounted for in quantum collapse models [21][22]. Huaiyu Zhu [23] and others have described the entropy of photon-mass absorption, and though this description is a larger scale entropy transfer than that in the observation networks model presented here, photon-mass entropy transfer might allow an experimentally feasible micro-scale characterization of entropy transfer at the quantum scale. Entropy reduction is a collapse of multiple states to fewer states. This feature of collapse, in conjunction with entropy NAND perhaps points to the possibility of fine grained computational style structures with physical results.
The thermodynamic NAND which follows from entropy NAND points to the existence of scale invariant computationally functional entropy transfer networks and proposes ubiquitous computation occurring throughout such networks.

Conclusions
Thermodynamic entropy networks are ubiquitous. Our simple characterization of entropy networks shows that at a very early stage of complexity functional completeness can be produced. As noted in the introduction, the thermodynamic NAND gate is trivial to construct, and because of this simplicity it may be present in nature.

Conflicts of Interest
The authors declare no conflict of interest.


s2fieldsofstudy:
Computer Science
Linguistics

text:
Overview of Stemming Algorithms for Indian and Non-Indian Languages

Stemming is a pre-processing step in Text Mining applications as well as a very common requirement of Natural Language processing functions. Stemming is the process for reducing inflected words to their stem. The main purpose of stemming is to reduce different grammatical forms / word forms of a word like its noun, adjective, verb, adverb etc. to its root form. Stemming is widely uses in Information Retrieval system and reduces the size of index files. We can say that the goal of stemming is to reduce inflectional forms and sometimes derivationally related forms of a word to a common base form. In this paper we have discussed different stemming algorithm for non-Indian and Indian language, methods of stemming, accuracy and errors.

I. INTRODUCTION
Many natural languages like Dravidian languages (Tamil, Telugu, Malayalam and Kannada), Finno-Ugric languages (Finnish, Estonian, Hungarian, Turkish), Indo-Aryan languages (Hindi, Bengali, Marathi, Gujarati) are inflected. In such languages several words sharing the same morphological invariant (root) can be related to the same topic. The ability of an Information Retrieval (IR) system to conflate words allows reducing index and enhancing recall. In most cases, morphological variants of words have similar semantic interpretations and can be considered as equivalent for the purpose of IR applications. For this reason, a no of stemmers have been developed, which attempt to reduce a word to its stem or root form. Each algorithm attempts to convert the morphological variants of a word like 'playing', 'played', 'plays' etc. to get mapped to the word 'play'. Thus, the key terms of a query or document are represented by stems rather than by the original words.

II. STEMMING ALGORITHMS FOR INDIAN LANGUAGE
Many Indian languages are in highly inflected form. Indian languages are Tamil, Malayalam, Gujarati, Marathi, Hindi, Bengali etc.
A. Assamese stemming Navanath Saharia, Utpal Sharma and Jugal Kalita [6], they adopt suffix stripping approach along with a rule engine that generates all possible suffix sequences. They used two approaches. In first approach, they manually collected all possible suffixes and describe the suffix stripping approach.
B. Gujarati Stemming Pratikkumar Patel Kashyap Popat and Pushpak Bhattacharyya [1], they have used the EMILLE corpus for training and hand-crafted suffixes. Their approach is based on Goldsmith's take-all-splits method. They try to obtain the optimal split position for each word present in the Gujarati word list provided for training. Kartik Suba, Dipti Jiandani and Pushpak Bhattacharyya [4], they present two stemmers for Gujarati -a lightweight inflectional stemmer based on hybrid approach and a heavyweight derivational stemmer based on a rule-based approach. For inflectional stemmer, they used POS based stemming and suffix stripping based on linguistic rules and used take-all-spilt method to obtain optimal split position of words. For derivational stemmer, they used suffix stripping, substitution and orthographic rules. Juhi Ameta, Nisheeth Joshi, Iti Mathur [9], they present implementation of rule based stemmer of Gujarati. They have shown the creation rule for stemming and verifying it with human expert. The process of this stemmer is strips the suffixes based on the longest match.
C. Hindi Stemming Ananthakrishnan Ramanathan and Durgesh D Rao [8], present a lightweight stemmer for Hindi, which conflates terms by suffix removal. The suffix list was developed. The stemmer is implemented by simply removing from each word the longest possible suffix from suffix list. They have evaluated our stemmer by computing the number of understemming and over-stemming errors for a corpus of documents. Upendra Mishra and Chandra Prakash [2], present the Hybrid approach which is combination of brute force and suffix removal approach and reduces the problem of over-stemming and under-stemming.

III. STEMMING ALGORITHM FOR NON-INDIAN LANGUAGE
A. Arabic stemming Haidar Harmanani et al's [5] proposed an extensible method for natural languages indexing and search. The method is based on a rule engine that allows the system to be adapted to a variety of natural language without the need to develop a specialized IR system. The proposed method used full-text indexing and ranks terms according to their degree of relevance.

B. English stemming
The first popular and effective stemmer for English is proposed by Lovins in 1968. The Lovins stemmer is a single pass stemmer, context sensitive and longest match stemmer. Lovins stemmer maintains a list of most frequent suffixes, and removes the longest suffix. Porters stemming algorithm is as of now one of the most popular stemming methods. It is based on the idea that the suffixes in the English language (approximately 1200) are mostly made up of a combination of smaller and simpler suffixes. It has five steps, and within each step, rules are applied until one of them passes the conditions. The rule looks like the following: <condition> <suffix> → <new suffix> C. Farsi / Persian stemming The Farsi stemmer uses a Deterministic Finite Automata (DFA). The DFA is input string is obtained by reversing the stemmer is input string. It matches words with a set of suffixes and use multiple phases conforming to the rules of suffix stacking. .  It is based on a set of steps composed by a collection of rules

IV. CONCLUSION
We have presented a comparative study of various stemming algorithms for Indian and non-Indian language. In this we studied that stemming significantly increases the retrieval results for both rule based and statistical approach. It is also useful in reducing the size of index files as the number of words to be indexed are reduced to common forms or so called stems. Most of stemming algorithms are based on rule based approach. The performance of rule based stemmer is superior to some well known method like brute force. Dictionary-based algorithms, including natural language processing approaches, allow integration with other applications, for example, for interactive query expansion or machine translation. Of course, they require constant updates to dictionaries due to language evolution, but this task is constantly performed by publishers and scientific groups. Also, growing computers power makes natural language processing approaches more feasible.


extfieldsofstudy:
Physics
Computer Science

text:
Consensus reaching in swarms ruled by a hybrid metric-topological distance

Recent empirical observations of three-dimensional bird flocks and human crowds have challenged the long-prevailing assumption that a metric interaction distance rules swarming behaviors. In some cases, individual agents are found to be engaged in local information exchanges with a fixed number of neighbors, i.e. a topological interaction. However, complex system dynamics based on pure metric or pure topological distances both face physical inconsistencies in low and high density situations. Here, we propose a hybrid metric-topological interaction distance overcoming these issues and enabling a real-life implementation in artificial robotic swarms. We use network- and graph-theoretic approaches combined with a dynamical model of locally interacting self-propelled particles to study the consensus reaching pro- cess for a swarm ruled by this hybrid interaction distance. Specifically, we establish exactly the probability of reaching consensus in the absence of noise. In addition, simulations of swarms of self-propelled particles are carried out to assess the influence of the hybrid distance and noise.

Introduction
One of the paradigmatic examples of emergent behavior in complex systems is given by awe-inspiring collective animal behaviors such as birds flocking, fish schooling, locusts marching, amoebae aggregating and humans crowding [1][2][3]. Over the past two decades, research into collective phenomena has rapidly expanded. Initially the aim was to gain insight into the elementary rules governing such phenomena [2,4,5]. More recently, following a biomimetic approach and free from some of the inherent constraints encountered in biological systems, a host of artificial swarming behaviors have been designed either with actual robots [6,7] or in a simulated environment [2].
The basic mechanistic functioning of collective motion is now well understood as being the result of multiple uncoordinated local interactions between individuals. The central importance of these local interactions have led scientists to experiment very many different local interaction rules, often with the aim to reproduce fine details of some of the very specific behaviors associated with different species of swarming agents [2,5]. However, two broad groups of local interaction rules can be discerned, each based on the definition of a specific interaction distance thereby defining the so-called neighborhood of interaction. The first group based on a metric distance, was the first considered and has attracted a tremendous amount of attention (see Ref. [2] and references therein). In the metric Send offprint requests to: neighborhood framework, each swarming agent exchanges information with all other agents located at a fixed and given distance-assumed to be the same for all [8][9][10]. The metric distance was only recently challenged following the analysis of empirical data for the dynamics of flocks of starlings [11] as well as results from the dynamics of human crowds [12,13]. For instance, in the topological distance framework, each and every agent interacts with a fixed number of neighbors regardless of the distance separating them.
Essentially, both distances are associated with distinct physiological (resp. technological) limitations of living (resp. artificial) agents. Specifically, the metric neighborhood of interaction finds its origin in the limited sensory range of individuals. Indeed, a fish in a school can only interact with other fish it can perceive either through vision or lateral line sensing [14,15]. On the other hand, the topological neighborhood of interaction stems from the limited information-processing capabilities of individuals. All living or artificial agents possess limited cognitive and information-processing capabilities enabling them to socially interact with a fixed number of other agents [16,17]. However, in real-life situations and depending on their positions within the swarm, individuals may found themselves limited either by their sensory apparatuses or by their internal information-processing system. Therefore, a purely metric or purely topological distance is unable to account for this inhomogeneity in limiting factors within the group.
Here, we address the shortcomings associated with all models based on a purely metric or topological distance. We propose a hybrid interaction distance that integrates both limitations in terms of sensory range as well as information processing. Our framework is different from the hybrid metric-topological interaction model proposed by Niizato & Gunji [18], in which cognitional ambiguity is accounted for by a constant switching between class and collection cognition, thereby overcoming the problem of neighbor selection. Very recently, a thorough comparison between the metric model and the topological one-based on an interaction with the seven nearest neighbors-has been carried out by Barberis & Albano [19]. Remarkably, in Ref. [19], the authors show through extensive simulations that both models share some common features, e.g. the order parameter-scalar quantity measuring the global consensus level within the flock-using both models has approximately the same scaling exponent with respect to time, and the final cluster size distributions of the flock have a similar power-law behavior.
It is worth mentioning here some influential theoretical frameworks dealing with consensus of Vicsek-like models in the absence of noise [20,21]. However, these works usually impose quite strong (sometimes unrealistic from the natural swarming standpoint) conditions on the system. Two typical assumptions are: i) some sort of connectivity (e.g., recurrent connectedness or the possession of spanning trees) of the underlying interaction network, and, ii) the required balance condition, i.e., the out-degree equals the in-degree for each agent, when the network is directed. As will be shown in the sequel, these restrictions do not apply to our approach.
In the present framework, using network-and graphtheoretic approaches combined with the linear dynamical model by Komareji & Bouffanais [22], we prove mathematically that the achievement of global consensus is primarily influenced by the metric component of our hybrid interaction neighborhood in the absence of noise. Furthermore, small swarms ruled by this hybrid interaction distance are simulated using a self-propelled particles model to investigate the influence of three key parameters: noise level, metric radius and number of topological neighbors within that metric radius.

Hybrid metric-topological interaction distance
Consider a group of N interacting agents moving in a √ N × √ N square area. Each agent i is described by its velocity v i = v 0 cos θ ix + v 0 sin θ iŷ , where v 0 is the constant speed and θ i ∈ [0, 2π) is the velocity direction for 1 ≤ i ≤ N . Therefore, the density of the agents is equal to the unity for any size N of the swarm. We assume that each agent can connect to its at most k nearest neighbors via directed information interaction within a physical distance R > 0. In other words, an agent is connected to at most k neighbors within a disk with radius R centered about itself. Thus the dynamical model for an individual agent i can be described aṡ where θ j , θ j+1 , · · · , θ j+ki−1 represent the velocity directions of agent i's k i -nearest neighbor within distance R and k i ≤ k [22,23]. The above described k i -nearest neighbor rule allows us to locally identify the links between agents. The resulting network, through a bottom-up assembly of the interagent links, is called the swarm signaling network [22,24], for which the specific value of k has a direct impact on its connectivity character. As stressed in our recent work [23], the dynamics of this directed swarm signaling network is intricately connected to the dynamics of the agents in the physical space. Signaling network structure/topology and information dynamics change on the same time scale and are strongly interwoven. Throughout the complete dynamical process, the signaling network maintains a constant number of nodes and some edges are broken while new ones are being created following the hybrid interaction rule-an agent is connected to at most k neighbors within a disk with radius R centered about itself. The rate at which network edges are changing is governed by the pace of the physical dynamics of the swarm. Hence, contrary to the static topology of the network models considered by Aldana et al. [25], we consider here the more general case of switching networks of interaction. Such switching events intrinsically occur at nonuniform time intervals. As detailed in Ref. [23], we can assume without loss of generality that those switching events are evenly distributed in time with the time interval between switching events corresponding to the decorrelation time scale τ of the matrix of correlations C ij = s i · s j for the normalized velocity s i = v i /v 0 . As all agents move at constant speed v 0 , the decorrelation time scale is therefore strictly equivalent to the spatial decorrelation time scale, which given our hybrid interaction rule is directly related to the values of k and R.
By considering the underlying swarm signaling network, the dynamics (1) of the agents is recast aṡ where Θ(t) = [θ 1 (t), · · · , θ N (t)] T and L(t) is the timedependent outdegree Laplacian graph of the swarm signaling network. Our following analysis is formally built on the framework of hybrid (k, R)-nearest neighbor digraph model. Switching networks are generally modeled using a dynamic graph G s(t) parameterized with a switching signal s(t) that takes its values in an index set {1, · · · , m} [26]. That is equivalent to choosing τ = 1, thereby imposing one specific choice of the unit of time of the swarm dynamics. Following that approach, let G(N, k, R) denote the hybrid (k, R)-nearest neighbor digraph model by placing N agents randomly and uniformly on a √ N × √ N square. If R ≥ √ N , the model reduces to the random nearest neighbor digraph [27][28][29]. We randomly choose a sequence G 1 , G 2 , · · · , G m , · · · in G(N, k, R), and generate a dynamical random network G(t) as Let 1 = (1, · · · , 1) T ∈ R N . We want to show the following result reaches a consensus with probability at least Proof. Since reaching consensus of system (4) is a monotone increasing property with respect to the number of edges of G(t) [30], it suffices to show the case k = 1. Let ξ ij (t) be a random variable representing the directed connection from agent i to agent j at time t. More specifically, P (ξ ij (t) = 1) = (πR 2 k)/(N (N − 1)) and By the law of large numbers, we have where we have used the variance of ξ ij (m) as which tends to 1 as M → ∞. Now define a graphG of order N whose adjacency matrix (a ij ) is given by Note that M 0 ξ ij (t)dt = M m=1 ξ ij (m). Thus, Eq. (6) implies thatG is a completely connected digraph for almost all sequences G 1 , G 2 , · · · , G m , · · · .
For each agent i, we estimate the probability q k that there are at least k other agents within distance R from it. We have In the following, we assume that there are at least one other agent within distance R from each agent. From the comment below Eq. (7), we see that each agent i is within distance R from any other agent infinitely many times. We fix any such sequence G 1 , G 2 , · · · , G m , · · · , we will show that the consensus can be reached for the system (4) where Note that this new vector still satisfies the equatioṅ except that the matrix L(t) now is a result of conjugation transform made by some permutation matrix at time t. In Eq. (10) we still write it as L(t) for simplicity. It is clear thatφ 1 . Therefore, φ 1 (t) and φ N (t) are monotonic and bounded functions. We obtain as t → ∞ for some φ * 1 and φ * N . Define Ψ (t) = [ψ 1 (t), · · · , ψ N (t)] T . Recall that k = 1. Then the outdegree of any vertex in G(t) is equal to 1. Hence, it is easy to see that there exists a diagonal matrix B with diagonal elements equal to 1 or −1 such that andψ i (t) ≥ 0 for all i. Since ψ i (t) ≤ |φ N (0)| (i.e., bounded), ψ i (t) converges for all i. It follows from Eq. (12) that φ i (t) also converges. We write Next, we claim that θ i (t) converges for i = 1, · · · , N . This can be seen as follows. Note that there exists an ε 0 > 0 such that for any ε < ε 0 , any pair of intervals in the family is either coincident or disjoint. For such ε there exists T > 0 such that for t > T , by invoking Eq. (13). Since θ i (t) is continuous, for any t 1 , t 2 > T we obtain |θ i (t 1 ) − θ i (t 2 )| < 2ε. Therefore, by the Cauchy convergence criterion we have for some θ * i (i = 1, · · · , N ). Finally, we need to show that all the above θ * i are equal. From Eq. (4) we havė In the following we will use the method of proof by contradiction. Without loss of generality, we assume that θ * j0 > θ * i0 . Then there exists some T > 0 such that holds for any t > T . Using Eqs. (16) and (17) we obtain It then follows from the definition (7) that a i0j0 = 0, and hence {i 0 , j 0 } is not an edge inG. This yields a contradiction since we know thatG is a complete digraph. Therefore, we have θ * 1 = · · · = θ * N , which is the final consensus value of the agents. ✷ As mentioned earlier, the swarm signaling network considered in our model switches independently at each time instant with the characteristic time scale τ = 1. In other words, it follows a Markovian process of order "zero". More realistic models should take into account the velocity/position co-evolution since there are several features of self-propelled particle models that depend crucially on the fact that motion in space is linked to local order [12,[31][32][33]. This simple yet tractable model is adopted here as a very first step in understanding collective behavior ruled by a hybrid interaction distance. A possible improvement to the model is to consider a continuoustime Markovian system. Formally, the random network G(t) in (3) switches among m topologies G 1 , · · · , G m in G (N, k, R), and G(t) = G i if and only if the switching signal s(t) = i ∈ M := {1, · · · , m}. The random process {s(t), t ≥ 0} is ruled by a Markov process with state space M and infinitesimal generator Γ = (γ ij ) given by P(s(t + h) = j|s(t) = i) = γ ij h + o(h), when s(t) jumps from i to j, Here, P is the concerned probability measure, γ ij is the transition rate from state i to state j with γ ij ≥ 0 if i = j, γ ii = − j =i γ ij , and o(h) represents an infinitesimal of higher order than h. For practical implementation, we may set γ ij large (thus more likely) if G i and G j differ only locally, while set γ ij small (thus less likely) if G i and G j differ violently. The multiagent dynamical systems driven by the above Markovian switching networks have been studied in control theory intensively during the past few years to generate consensus behaviors; see e.g. [34][35][36].
One of the common restrictive assumptions in these work again turns out to be the balance condition. Clearly, these existing results do not directly apply here. Above we assumed that the speed v 0 for each agent i is kept the same and only the heading θ i is evolving.
Let v x i = v 0 cos θ i and v y i = v 0 sin θ i . In the following, we seek consensus of the velocity v i = (v x i , v y i ) of each agent i. Similarly as in Eq. (1), the dynamical model for an individual agent i can be described aṡ with α = x or y and where v α j , v α j+1 , · · · , v α j+ki −1 represent theα-component of velocities of agent i's k i -nearest neighbors within distance R and k i ≤ k. Denote by T and L(t) the time-dependent outdegree Laplacian graph of the swarm signaling network as before. The dynamics (19) of the agents can be recast asΓ (t) = (I 2 ⊗ diag(1/k 1 , · · · , 1/k N )(−L))Γ (t). (20) We have the following result Theorem B. Assume that k ≥ 1. For all random sequences G 1 , G 2 , · · · , G m , · · · in G(N, k, R), the switching systeṁ Γ (t) = (I 2 ⊗ diag(1/k 1 , · · · , 1/k N )(−L(t)))Γ (t) (21) reaches a consensus with probability at least 1 − e −R 2 π , as N → ∞. Here L(t) is the corresponding (outdegree) Laplacian matrix of G(t), and Γ (t) is given by Proof. This result can be proved similarly as Theorem A. Note that instead of the rearrangement (9) we will assume Similarly as in Eq. (10), we havė Since the x-system and y-system are decoupled, we can prove v x i → v x * and v y i → v y * (∀ i = 1, · · · , N ), respectively, for them as in the proof of Theorem A. ✷

Self-propelled particles subjected to the hybrid interaction distance
Up to this point, our analysis of the swarm dynamics was limited to the ideal case of dynamics in the absence of any noise source-stimulus and response noises [16]. With both a metric and topological distance, it is well known that an increasing level of extraneous noise triggers a second-order phase transition [2,22]. For very low noise levels, a consensus is guaranteed and after a certain transient the swarm is globally aligned. On the contrary, beyond a certain critical noise level no global consensus can be achieved. The consensus level within the swarm is measured by the following order parameter with v j the velocity of agent j in complex notation. In the particular case of self-propelled particles, the order parameter ϕ represents the alignment of the collective. At this stage it is worth highlighting that there exists a vast range of models of self-propelled particles reported in the literature, all stemming from the original Vicsek's model [37]. Our objective here is not to provide an exhaustive list of those models-many of which can be found in the following review [2]-but instead a representative samples of some of the key developments in relation with the present work. Alternative ways of imposing noise have been considered in Ref. [33], and the inclusion of cohesive forces reported in Refs. [31,32], while also considering the effects of the ambient fluid in Ref. [31]. Pure topological interactions have been reported in Refs. [19,22,23], while a topological density invariant rule based on Voronoi neighbors has been considered in Refs. [32,33], with a particular emphasis on metric-free interactions that can be found in Ref. [12]. Very recently, the effects of limited information flow due to limitations in the bandwidth of the signaling network have been reported in Ref. [38].
We now turn to the simulations of the dynamics of a swarm of N = 100 agents initially evenly distributed in a square domain of size L = √ N so as to have a unit density as considered in Sec. 2. We intentionally consider the dynamics of small-size swarms as our interest lies in artificial swarms [6,7] and some other natural collectives [39,40] with swarmers numbering in the tens to a few hundreds maximum. Given the value of N considered here, some strong small-size effects are expected and in particular, the phase transitions-from a disordered state to collective motion when reducing the ambient noise level-will appear to be continuous (i.e. of second-order type) while they are actually discontinuous (i.e. of first-order type) as proved in several studies [31,33,41].
For simplicity, we focus on the constant speed case corresponding to v 0 = 0.1 that falls into the typical range of values used for such simulations [2]. Noise can generally be assumed to be random fluctuations with a normal distribution [16]. In the sequel, the background noise is considered to have a normal distribution fully characterized by its noise level, η. Specifically, starting from the continuous-time equation (1), the presence of noise leads to the following discrete-time equation governing the dynamics of agent i: where ∆θ i is a random number chosen with a uniform probability from the interval [−η/2, η/2]. The agents po- ..,N are updated according to the discretetime kinematic rule with v i having the same definition as previously introduced in Sec. 2. As for the time advance, the canonical value ∆t = 1 is considered throughout [2].The neighborhood of interaction for this swarm model being given by the hybrid metric-topological one, three independent parameters-namely the metric radius R, the maximum number of topological neighbors k within the radius R and the noise level η-influence the emergence of order. Figure 1 displays the variations of the order parameter ϕ with the square of the normalized metric radius ρ 2 = (R/L) 2 as hinted from Theorem A. The results gathered in Fig. 1 allow us to draw several interesting comments. First, as expected from the mathematical results in Sec. 2, an increase in the metric radius R systematically yields an increase in the alignment of the swarm for all values of k and of the noise level considered. Second, for any given value of R and for all three noise levels considered, the order parameter is found to increase with k with a dramatic jump in ϕ when k goes from 3 to 10 but with a minute and yet noticeable increase when k goes from 10 to N − 1. Note that the case k = N − 1 corresponds to the extreme case of an all-to-all connectivity of the swarm interaction network; in other words each agent interacts with all the others which amounts to what is probably the most cost-ineffective mode of swarming. This case k = N − 1 also corresponds to a pure metric interaction while the case ρ = 1 corresponds to the purely topological one. This second result is in complete agreement with the analysis of the influence of the value of k on the consensus reaching dynamics by Shang & Bouffanais [23].
To further appreciate the transition between the topological and the metric component of the hybrid interaction distance, one may compare k with the actual number n * (k) of neighbors typically found within the metric disk of radius R centered about the agent. For a given value of the density ν = N/L 2 of the swarmers, one finds n * (k) ≃ νπR 2 . On the one hand, when k > n * (k) it is expected that the topological component becomes ineffective and therefore the hybrid interaction reduces to a purely metric one. Since we investigate the constant density ν = 1 case, this situation is bound to happen for small values of R, or equivalently ρ. On the other hand, when k < n * (k), the topological component takes over the hybrid interaction. This indeed is the case for the largest possible value for R, namely R = L or equivalently ρ = 1. This analysis is consistent with the results shown in Fig. 1 and the related discussion above. The influence of the noise level is better appreciated when turning to the results reported in Fig. 2. An increase in the noise η systematically translates into a reduction of the swarm alignment. As anticipated, the phase transition from an aligned state to a disordered one occurs much earlier for smaller values of R. This observation also holds for smaller values of k. However, the cases k = 10 and k = N − 1 yield extremely close results for not too large values of R and at any given noise level η. Furthermore, the phase transitions associated with the rapid decay of the order parameter ϕ with noise level η, for different values of (k, ρ) shown in Fig. 2 are qualitatively consistent with those reported by Barberis & Albano [19]. Note that the comparison can only be qualitative owing to the fact that the time update rule used in Ref. [19] is slightly different from the one considered in the present study, namely Eq. (26). The exact same comment also applies to the comparison of our results gathered in Fig. 2 with those obtained by Niizato & Gunji [18] with yet another time update rule and another framework for their hybrid metric-topological interaction distance.

Conclusions
A combined computational and theoretical analysis of the dynamics of swarms of self-propelled agents subjected to a hybrid metric-topological neighborhood of interaction has been performed. The hybrid interaction distance is devised to overcome fundamental issues associated with inherent limitations in the sensory range and informationprocessing capabilities encountered in real-life natural and artificial complex systems. The results reported in this article allow us to formulate the following important conclusions: (i) When the agent density in the field is constant (here the unity), the consensus dynamics is exclusively dominated by the metric component R of our hybrid model. As long as k ≥ 1, one can always observe the emergence of consensus with some positive probability in the absence of noise. This result is further extended to the case of agents having non-constant speeds. (ii) For large swarms and still in the absence of noise, the probability of emergence of consensus is approximately proportional to R 2 . (iii) Similarly to swarms subjected to a purely metric or a purely topological distance, a collapse of the swarm alignment is observed in the presence of a sufficientlyhigh noise level using our hybrid model. Furthermore, our results confirm the ineffectiveness of the purely metric model which yields a marginally higher alignment at the expense of a very large number of social interactions as compared to the case k = 10 [23].
Furthermore, our initial observations reveal that the number of topological neighbors k solely affects the speed with which consensus is reached as observed in the purely topological distance case [23]. However, this last point requires a more thorough investigation to provide a clear picture of the consensus reaching dynamics for a swarm ruled by a hybrid interaction distance.

Acknowledgments
We thank Dr. Mohammad Komareji for fruitful and stimulating conversations.