Ana S Fernandes

Pedro Alves

Ian H Jarman
email: i.h.jarman@ljmu.ac.uk

Terence A Etchells
email: t.a.etchells@ljmu.ac.uk

José M Fonseca

Paulo J G Lisboa
email: p.j.lisboa@ljmu.ac.uk

A Clinical Decision Support System for Breast Cancer Patients

Keywords: Breast cancer, survival analysis, decision support systems

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

Introduction

Prognostic assessments as well as clinical indicators are the key issues to guide clinical oncologists to better define the treatments and to better assess the impact of prognostic factors on survival of operable breast cancer patients.

This paper presents a web decision support system for clinical oncologists, where three different survival models are considered: the commonly used NPI (Nottingham Prognostic Index), Proportional Hazards Modelling and PLANN-ARD (Partial Logistic Artificial Neural Network with Automatic relevance determination), such that each model provides an independent prognostic index. The prognostic indices (PI) for each of the models are derived from prognostic factors and allow stratification of patients by survival outcome. A patient stratification methodology is also introduced to separate the population into significantly different survival risk groups In addition, these risk groups can be characterized using explanatory rules obtained from the prognostic factors used in the analysis. Both, the patient's risk group and the explanatory rules can be incorporated in the Web decision support system. It is important to mention that the aim of the proposed decision support system is to enhance the oncologists' current practices, rather than to replace them. Therefore, all the previous models are incorporated in the web interface.

Section 2 explains the current study's contribution to technical innovation, section 3 gives a description of the data set used to train the model and defines the predictive variables chosen for the analysis. Section 4 presents the prognostic models and the methodologies used for patient stratification into different survival groups and Section 5 presents the Web decision support system followed by the conclusions.

Contribution to Technical Innovation

The present work makes an important contribution to both technical innovation and clinical application as several important novelties were added or changed to current practice. [START_REF] Jarman | An integrated framework for risk profiling of breast cancer patients following surgery[END_REF] have already presented a web decision support system as a relevant innovation [START_REF] Jarman | An integrated framework for risk profiling of breast cancer patients following surgery[END_REF]; this study improves upon this system by resolving and improving, some particular issues. Currently there are several survival models which are in use, such as NPI and other Cox proportional hazards models. It is intended to augment NPI by adding more variables considered to be important in the prognostic model, which selection is explained in section 4. Moreover, it was intended to define a prognostic model to become predictive rather than explanatory as well as modelling non-linear dependences, with PLANN-ARD. Previous research [START_REF] Fernandes | Missing data imputation in longitudinal cohort studies -application of PLANN-ARD in breast cancer survival[END_REF] on the dataset used for this study and mentioned on section 3, showed missing data to be missing at random (MAR): hence, it can be successfully imputed. Therefore this work also takes account of missing data and censorship within principled frameworks [START_REF] Fernandes | Missing data imputation in longitudinal cohort studies -application of PLANN-ARD in breast cancer survival[END_REF], applying multiple imputation in combination with neural network models for time-to-event modelling, where a new PI was also considered. It is important to note that survival models must take account of censorship, which occurs when a patient drops out of the study before the event of interest is observed or if the event of interest does not take place until the end of the study. Moreover a new stratification methodology was developed, based on decision trees, which adds a more robust path to identify the patient's risk group and the explanatory rules that characterize risk group membership, based on patient's characteristics. Finally, a new web decision support system contributes to technical innovation as it implements both the previously mentioned models, where all can be compared.

Data Description

The data set comprise 931 consecutive series of female patients recruited by Christie Hospital in Wilmslow, Manchester, UK, during 1990-94. The current study is specific to early operable breast cancer patients filtered using the standard TNM (Tumour, Nodes, Metastasis) staging system as tumour size less than 5 cm, node stage less than 2 and without clinical symptoms of metastatic spread. The event of interest is death to any cause, being a single risk model, where the study period for analysis is 5 years and the time-to-event was measured in months from surgery. All patients in this study were censored after 5 years of follow-up. 16 explanatory variables in addition to outcome variables were acquired for all patient records.

This study will only focus on Histological type lobular and ductal, therefore some records were withdrawn. Also, two of the 931 records in the training data were identified as outliers and removed. Finally, at the end of the analysis the data set ended up with 743 subjects. Missing data is a common problem in prediction research. After analysing the data set, information has been considered to be Missing at Random (MAR) where a new attribute may be created to denote missing information or the missing values can be imputed. The latter has been shown to be effective [START_REF] Clark | Developing a prognostic model in the presence of missing data an ovarian cancer case study[END_REF]. Therefore, the missing covariates were imputed following the method indicated in [START_REF] Clark | Developing a prognostic model in the presence of missing data an ovarian cancer case study[END_REF] and repeated 10 times. The choice of this number is a conservative one, as several studies have shown that the required number of repeated imputations can be as low as three for data with up to 20% missing information.

Breast Cancer Prognostic Models and Stratification Methods

This section explains both, the different prognostic models and the stratification methodology which were included in the web decision system. The following detailed methods bridge the gap between individual predictions for single patients and allocations of patients into risk groups.

Breast Cancer Prognostic Models

It is important to mention that historically, the purpose of prognostic models was to stratify patients into cohorts with distinct survival. The most widely used index is TNM, which is purely clinical, as it depends only on clinical investigations and palpation and takes account of metastatic spread of the disease but is not sufficiently detailed for early breast cancer. The Nottingham prognostic index (NPI) [START_REF] Haybittle | A prognostic index in primary breast cancer[END_REF], a clinical prognostic index for breast cancer patients has been widely applied to inform the choice of adjuvant therapy. It is an indicator of breast cancer outcome and its score is calculated using the following formula: NPI=0.2×pathological size + histological grade + nodes involved .

(

Subsequently, from their NPI patients are allocated into prognostic groups from excellent prognostic group to poor prognostic group based on the cutpoints: <2.41; <3.41; <5.41 and ≥5.41. Predictive prognostic inference for individual patients was also introduced by the web-based interface for clinical oncologists which has expanded the covariate basis for prognostic inference. www.Adjuvantonline.com [START_REF] Ravdin | Computer Program to Assist in Making Decisions about Adjuvant Therapy for Women with Early Breast Cancer[END_REF] is an interface format that appears to be readily accepted by practicing clinicians. This model has the advantage to infer the potential effect of different treatment choices and since its publication on the web, there is greater interest in making individualised predictions of survival. However, its predictions do not include confidence intervals, yet are likely to be subject to substantial uncertainties for particular groups of patients. Advances in therapy, detection technologies and health policy have skewed the patient population and additional prognostic indicators can be added to increase the predictive power of NPI. Consequently, the other two prognostic models are included and compared in this study.

In the survival analysis field, the proportional hazard model, also known as Cox regression is widely used. Cox regression factorises dependence on time and the covariates, where the hazard rate is modelled for each patient with covariates x p at time t k , as follows:

h(x p ,t k ) 1-h(x p ,t k ) = h 0 (t k ) 1-h 0 (t k ) .exp( bx i i=1 N i ∑ ) . ( 2
)
where h 0 is the baseline hazard function and x i are the patient variables. Here the prognostic score is defined by the traditional linear index βx. However, for this study 10 imputed data sets were used, which means that the final prognostic score for each patient was determined as the mean of the 10 prognostic indices identified, Model selection was carried out through Cox regression (proportional hazards) [START_REF] Fernandes | Missing data imputation in longitudinal cohort studies -application of PLANN-ARD in breast cancer survival[END_REF], where six predictive variables were identified: age at diagnosis, node stage, histological type, ratio of axillary nodes affected to axilar nodes removed, pathological size (i.e. tumour size in cm) and oestrogen receptor count. All variables are binary coded as 1-from-N.

The Partial Logistic Artificial Neural Network is a predictive model, rather than an explanatory model, such as the proportional hazards regression and also has the capability of capturing interactions between covariates as well as fitting the time dependence of the hazard function. It has a strong regularisation framework which has been added to avoid overfitting, using the method of Automatic Relevance Determination, hence the acronym PLANN-ARD [START_REF] Lisboa | A Bayesian neural network approach for modelling censored data with an application to prognosis after surgery for breast cancer[END_REF]. For a single risk, such as overall mortality, this model has the structure of a multi-layer perceptron with a single hidden layer and sigmoidal activations in the hidden and output layer nodes. The number of hidden nodes was determined using cross-validation that is several networks were trained, each one with different hidden nodes and validated with crossvalidation. It was concluded that 8 hidden nodes were sufficient to train the network and not lead to over-fitting.

Covariates and discrete time (monthly time increments) are introduced in the network as inputs, where the output is the hazard for each patient and for each time. Estimating the weights requires a likelihood term for the status of one patient at time t k , by using an indicator when the patient status is observed alive at time t k (labeled as 0) or have died (label as 1). The papers cited in [START_REF] Lisboa | A Bayesian neural network approach for modelling censored data with an application to prognosis after surgery for breast cancer[END_REF] make a strict theoretical correspondence between this neural network model and classical statistical time-toevent models for censored data. To obtain patient information, that is appropriate to their prognostic risk group, it is important to define first this risk group as well as the relevant prognostic score, appropriated for non-linear models, as with the previous mentioned prognostic models. Therefore, the following expression is proposed: PI(x p ) = (-ln(1 -CCI(t))) = ln(-ln(S(t))).

(

) 3
where the CCI is the crude cumulative incidence, identified as the probability of the occurrence of a specific event of interest and S(t) is the estimated survival at the end of follow up. As a consequence of imputation, PLANN-ARD was computed 10 independent times, one to each imputed data set, which resulted in 10 different trained networks. The mentioned time independent PI was also computed for the 10 networks and averaged for each patient, producing a final PI.

Group Risk Stratification

In a clinical environment stratification of patients, in different risk groups, based on survival models is frequently used in the evaluation of treatments or to assess the impact of prognostic factors on survival. Therefore, a stratification methodology needs to be defined in order to separate the different patients in statistically significant risk groups by overall mortality. Previous studies [START_REF] Fernandes | Stratification methodologies for neural networks models of survival[END_REF] presented a comparison between different stratification methodologies, such as the bootstrap log-rank aggregation based on the log-rank test and a regression tree, based on CART algorithm [START_REF] Breiman | Classification and Regression Trees[END_REF], where the PI is now the target for regression using a rule-tree. The bootstrap log-rank aggregation was considered in order to diminish the log-rank cutpoints overestimation [START_REF] Etchells | Stratification of severity of illness indices: a case study for breast cancer prognosis[END_REF]. All stratification methodologies were applied to both survival models: PLANN-ARD, a neural network for time-to-event data and Cox proportional hazards. However, a concern of many clinicians is the 'black box' nature of artificial neural networks (ANN) [START_REF] Lisboa | A review of evidence of health benefit from artificial neural networks in medical intervention[END_REF] which raises the important issue of explaining individual inferences by the network. This is a key stage in evaluating the clinical plausibility of inferences made by analytical models to enable clinicians to apply these inferences with confidence. Consequently, the regression tree can be a very well accepted stratification method in a clinical environment, as it gives simple explanatory rules, based on the predictive variables for all the risk groups considering all the existent possibilities, as it can be observed in figure 1. This figure represents the final regression tree, where, thanks to the pruning method, the final leafs define different risk groups. Each risk group is characterized by different rules based on the patient's characteristics which are defined by each branch of the regression tree.

Framework for Integrated Decision Support System

All the prognostic models, combined with the stratification methods described above can be integrated with decision supports for clinicians and patients, being used for personalized patient information systems. Figure 2 represents the framework web home page, where the three prognostic models can be computed and the output compared for a single patient. The framework's main goal is to assist the clinicians and patients in defining the appropriate information to their prognostic risk group, by way of a cross-matching matrix for all the different methodologies. The interface combines a group score (the NPI index) with two statistical models (one linear and one non-linear) to estimate breast cancer specific mortality. This provides a 'second opinion' for current users of Adjuvant! but using a single data-based model and hence with the potential to provide not just point estimates of survival but also theoretically derived confidence intervals for those estimates. The Kaplan Meier survival curves can also be available for each cell of the matrix in order to discover heterogeneity within a prognostic risk group. It is important to mention that the basis of this framework is to detail the prognosis risk group using different methodologies, rather then replacing one for another. The same idea of cross-tabulation can be extended to a scatter plot of the PI. It can also inform if some patients are outliers of the model or in the borderline between groups. Patient's characteristics are submitted and the risk scores as well as risk groups are calculated. These are displayed in the web page, figure 3. The cross-matching can be visualized in two dimensional and three dimensional plots. As an example, figure 3 represents in the ordinate the currently used clinical risk score, namely the Nottingham Prognostic Index (NPI), while the abscissa is the PI derived from the PLANN-ARD. The result is that patients in NPI group 3 are shown in the plot to be stratified into different risk groups. Finally, this Web clinical decision support system also allows clinical oncologists to collect and save their patients prognosis as well as their clinical data. Therefore, supported by patient history, clinical oncologists have the possibility to compare prognosis and treatments and improve their medical decisions.

Conclusions

This paper presents a web decision support system for breast oncology, which shows the value of the new prognostic models and stratification methodology in discriminating patients by mortality risk. This tool, after introducing patient variables, identifies the risk group allocation for the three prognostic models presented in this paper (NPI, Cox proportional hazards, PLANN-ARD) and consequently the rules that explain each risk group. A cross-matching matrix of grouped survival and the position a patient resides within the matrix it is also presented, leading to better insights if the risk group allocation for a specific prognostic model is more accurate. Moreover, as Adujantonline is gaining clinical support, a link to this web tool has been placed in the presented web decision support system. Future work on the prognostic model will include a detailed validation of the prognostic predictions by application to out-ofsample data collected by the British Columbia Cancer Agency. This is the same data set that was used to evaluate the Adjuvantonline system, thus enabling benchmarking. In order to improve the presented tool, for future work the different treatment choices for the data base used for training the prognostic model.

Fig. 1 .

 1 Fig. 1. Final regression tree, indicating the risk groups belonging for all the patients with different predictive variables, using the proportional hazards model as a prognostic model.

Fig 2 .

 2 Fig 2. Home page of a patient information system for breast cancer patients with the possibility to choose a 2D or 3D cross-matching visualisation for different risk group allocation.

Fig 3 .

 3 Fig 3. User interface for breast cancer oncology, showing the risk group belonging for PLANN-ARD model and NPI PI and a visualisation of the patient data.

Acknowledgments. The authors gratefully acknowledge Mr. R. Swindell from Christie Hospital for making the anonymised modelling data set available for this study and members of the BC Cancer Agency's Breast Cancer Outcomes Unit for assembling the British Columbia data. This study was partially funded by the European Network of Excellence Biopattern (FP6/2002/IST/1-508803) and by Fundação para a Ciência e Tecnologia, through the POS_C(SFRH/BD/30260/2006).


Petar Ćurković
email: petar.curkovic@fsb.hr

Bojan Jerbić
email: bojan.jerbic@fsb.hr

Dual-Arm Robot Motion Planning Based on Cooperative Coevolution

Keywords: co-evolution, path planning, multi-objective optimization

This paper presents a cooperative coevolutionary approach to path planning for two robotic arms sharing common workspace. Each arm is considered an agent, required to find transition strategy from given initial to final configuration in the work space. Since the robots share workspace, they present dynamic obstacle to each other. To solve the problem of path planning in optimized fashion, we formulated it to multi-objective optimization domain and implemented co-evolutionary algorithm to simultaneously optimize four conflicting objectives. End-effector trajectory length, end-effector velocity distribution, total rotate angle and number of collisions are the objectives to be optimized. Simulation results for two 2-R type robots are presented.

Introduction

Over the last two decades, evolutionary algorithms have been applied in a variety of fields, namely: robotics, scheduling, construction engineering, speech recognition, space engineering, image processing etc. An augmentation of evolutionary computation, coevolutionary computation, drives the inspiration from natural processes of coevolution between different (animal) species. The main difference between coevolutionary and standard evolutionary algorithms is in the nature of individuals' fitness evaluation. While the former uses a static fitness function for evaluation of individuals from a single population, the latter employs non-stationary fitness function for evaluating individuals from multiple populations, based on their interactions with individuals from other populations [START_REF] Paredis | Coevolutionary Computation[END_REF].

Coordinated path planning for multiple robots is difficult because the problem is NP-complete, whose complexity grows exponentially as the number of DOF increases [START_REF] Lavalle | Planning Algorithms[END_REF] [START_REF] Canny | The Complexity of Robot Motion Planning[END_REF]. Required is to plan not only for the paths of individual robots, but also for the order of their consecutive movements, in order to prevent the robots from colliding with one another. The path planning problem for multiple manipulators sharing common work space have been studied for some time now [START_REF] Erderman | On multiple moving objects[END_REF].

Contribution to Technological Innovation

Current industrial control approaches are on the edge of becoming obsolete. While the processes inducted by the globalization have opened the door for a worldwide market, at the same time, competition is additionally boosted. In this context, traditional, deterministic automation approaches are cost ineffective, inflexible and unreliable in the conditions of short-termed business opportunities.

In this line of thought, employing dual-arm robots in decentralized control fashion, for solving complex assembly tasks receives recent attention in the first line in research community. Such robots should be able to decompose complex assembly tasks to several simpler ones, simultaneously change end effectors, reduce facilities costing, total assembly time and spare area.

However, theory about motion planning of this type of robots is not perfect. The problem is twofold; from the one hand, feasible collision free paths between two intermediate points should be calculated prior the movement of each robot begins. From the other hand, it is difficult to achieve synchronization of the two hands in context of industrial communication protocols, i.e. fast Ethernet, due to its stochastic nature and time delays.

This work was motivated bearing in mind that the two hands of the robots could be to some extent autonomous, being controlled by two controllers in decentralized fashion. Each controller should be governed by one evolutionary algorithm, and the communication between the two controllers should take place at the time controllers are checking for collisions, for the case when the objective is to find collision free paths.

Some of the technological benefits of the proposed approach: assembly speedup and efficiency increase due to asynchronous and parallel computation. Scalability -it should be possible to add additional agents and represent them in form of new coevolving population. Modularity and cost reduction, it is easier and most cost effective to rearrange system that is based on decentralized control principles.

Problem of synchronization of the two hands at the level of execution of complex tightly coupled assembly tasks is beyond the scope of this paper and considered for future work.

Related Literature

Many important contributions to the problem of path planning in recent years have been made, each one possessing its own merits and disadvantages. Comprehensive survey can be found in [START_REF] Latombe | Robot Motion Planning[END_REF]. Practical multi-robot motion planning problems are often decoupled in the sense that the robots trajectories are planned for only one robot at a time in priority order. Then in the second phase, velocities are modulated so that collisions between the robots are avoided. If a problem of path planning is represented as an optimization problem, robust optimization techniques, such as evolutionary algorithms have proven suitable for finding solution for such formulated problems. Rana and Zalzala [6] [7] propose an evolutionary planner to evolve near time-optimal collision-free trajectories for multi-arm robot manipulators. In this study, planning is carried out in joint space of the manipulator, and the path is represented as a string of via points connected by cubic polynomial splines. Davidor [START_REF] Davidor | Genetic Algorithm and Robotics; A Heuristic Strategy for Optimization[END_REF] also applies evolutionary algorithms to the trajectory generation by searching the inverse kinematics solutions to pre-defined end effector robot paths. Pires, Machado and Oliveira [START_REF] Solteiro Pires | Robot Trajectory Planning Using Multi-objective Genetic Algorithm Optimization[END_REF] employ multi objective genetic algorithm to evolve joint-space strings of manipulator configurations. Five indices, namely manipulator joints travelling distance, joint velocity, cartesian distance, cartesian velocity and energy are used to qualify the evolving trajectories. Toyoda and Yano [START_REF] Toyoda | Optimizing Movement of A Multi-Joint Robot Arm with Existence of Obstacles Using Multi-Purpose Genetic Algorithm[END_REF] used multi-purpose genetic algorithm to optimize movement of multi-joint robotic arms in presence of stationary obstacles. Optimum solutions with smooth trajectories and minimal joint rotation were obtained. Venegas and Marcial-Romero [START_REF] Venegas Montes | An Evolutionary Path Planner for Multiple Robot Arms[END_REF] present preliminary results of Constructive Solid Geometry based approach to path planning of multiple robot arms. They used two phase genetic algorithm to obtain a plan for the robotic arms by using a strategy that combines the exploration of the free collision space while looking for the target position from each previously explored area.

Majority of papers dealing with evolutionary -based path planning consider either single agent operating in an environment without presence of obstacles, or in an environment containing static, point obstacles. The problem then boils down to finding suitable set of interior points, to be interpolated to formulate the polynomial of given order representing the trajectory.

The method presented in this paper considers concurrent development of robot trajectories for two 2R type robots sharing common work space. Each robot is considered an agent that is to find appropriate strategy for moving from given initial to final configuration. Since one agent presents dynamical obstacle to the other, and vice versa, often it is necessary for the agents to detour away from optimal, shortest paths, to find feasible strategies. It is also necessary to check for collisions between the links of the two robots in each consecutive time step.

Cooperative coevolutionary algorithms (CEAs) offer great potential for concurrent multiagent domains. Two populations, each representing set of configurations of one robot in joint space, co-evolve to minimize number of collisions between interacting individuals, at the same time minimizing distance traveled, total joint rotation angle, and equalizing end-effector velocity profile. Best collaborators are sought and preserved to achieve memory effect in subsequent populations, and to bias coevolutionary search for optimal strategies.. The paper is organized as follows: In section 2, impact on technological innovation is discussed. Section 3 presents related literature and recent work, with focus on implementation of evolutionary algorithms to path planning. Problem and proposed algorithm are discussed in the section 4. Section 5 presents simulation and result for one given scenario. In section 5 some coevolutionary modifications are described. Finally, we discuss results and give insights for future work in sections 6 and 7.

Problem and Algorithm Formulation

In this paper, two 2-R type robots with two links and two joints are considered. The end-effector is considered to move in the horizontal plane. The configuration spaces of the two robots are:

C q q R = × ∈
for the first robot and

Individual Representation

An individual in a population is encoded as real-valued vector in the joint space:

( ) ( ) { } ( ) ( ) { } ( ) ( ) ( ) ( ) { } , , 2 , 2 , 2 , 2 , 11 11 11
,.., , ,.., ,.., ,..,

t G t G t G t G n t G n t G ij ij ij q q q q q q ∆ ∆ ∆ ∆ -∆ -∆     (1)
Where i denotes the robot i=1,2, j is the number of DOF, t ∆ is sampling time between two consecutive configurations, q is angle between the link and positive x axis, G is current generation. At the beginning of the evolutionary process, joint values are randomly initialized, whereby the initial and final configurations are not encoded into the string because they remain constant throughout the search process. Without the lost of generality, adopted is normalized sampling time with 0.1 t ∆ = s.

Operators of the Coevolutionary Algorithm

The algorithm starts with random initialization of two populations, each representing set of configurations for one robot. The performance of each robot's configuration depends on the current state of the robots from other population, since the two must coordinate the motion, to achieve continuous collision free movement. In the canonical CCEA, each individual from the first population should be evaluated by all individuals from other population, what is extremely time-consuming. To speed-up the evolution process, modified co-evolution is considered. In the modified version, each individual is evaluated by a finite set of the top collaborators from the other population, based on scores from previous generation. In this study, we evaluated the top 10 % of the populations, which is a modification of the approach proposed by the Sims [START_REF] Sims | Evolving 3D Morphology and Behavior by Competition[END_REF], where "…the most "interesting" results occurred when the all vs. best competition pattern was used". The sizes of both populations were same and set to 60 individuals. In what concerns the selection operator, the successive generations are reproduced on the basis of roulette wheel selection. Standard single point crossover operator is used. The mutation operator replaces one allele with a given probability using the equation, where rand gives random number from the given interval:

( ) ( ) ( ] ( ) , 1 , , 1 0, / 5 t G t G t G ij ij ij rand q q q π π ∆ + ∆ ∆ + ∈ = + < (2)

Fitness Criteria

Fitness criteria should take into account number of collisions between the two robotic arms, trajectory length, velocity profile, and total rotate angle. The most important criterion is the collision number, since collisions should be avoided at all costs. To check for collisions, in each time step t ∆ , linear system is solved that describes current positions of all links of the two robots.

Collision Penalty

Collision penalty depending on collision between Robot 1 and Robot 2 in corresponding configurations is given by:

2 1 1 1 min , k n k k C C C = - = = → ∑ (3)
where:

1 if R1 and R2 collide in i generation 0 otherwise.

th k C =    (4)
It is important to note that the evaluation of the eq. 3 needs representatives from other co-evolving population and here is where cooperative coevolution makes contribution.

Total Distance of the End-Effector Movement

Total Rotation Angle

Since the robots are redundant systems even in this simple form of 2 DOF, resulting in possibilities of reaching the same point in the space in elbow-up and elbow-down configurations, criterion of minimizing the total distance is not enough. Additionally, it is necessary to minimize the total rotation angle, to ensure no oscillations between the elbow-up and elbow-down configurations occur. Following expression defines total angle for one joint of one robot. Each robots' total angle should be minimized:

3 1 1 min n i i i C α α - = = → - ∑ (6)
where i α is the angle between the limb of the robot and positive horizontal axis.

End-effector Velocity Distribution

To ensure even distribution of passing points along the robots' trajectory, the distance between two adjoining points in unit time should be equal:

( ) ( ) { } 4 1 1 max min min , , j j j j C dist p p dist p p - - = → - (7)
Optimal value for C 4 is equal to 0, what means that all passing points are equally distant from each other.

Objective Function Calculation

Objective (fitness) function for each candidate is calculated as weighted linear combination of above equations.

( )

1 1 2 2 3 3 4 4 min F w C w C w C w C f → = ⋅ + ⋅ + ⋅ + ⋅ (8)
Where values of weight factors w i are constants. Values of weight constants have significant impact on the overall behavior of the algorithm. Namely, since objective criteria are in conflict, i.e. shortest distance criterion conflicts collision penalty criterion, proper tuning of these parameters is very tedious and time demanding. We are considering implementing non-linear functional relationships in weight parameters in the future. To address this problem in this paper, we implement dynamic weight factors and show the effectives of proposed approach.

Simulation Results

Several experiments were conducted to test the performance of the proposed algorithm. It was observed that, beside the parameters of the fitness function, the success ratio of the algorithm depends on the initial and final configurations of the robots. The easiest scenario is when configurations of the robots result with no collisions. Most difficult scenarios occurred for configurations when significant detouring from shortest paths was necessary, (to ensure collision free motion). Fig. 1 shows evolved motions for two robots sharing work space. In the above case, all lengths of robot links are 1 m, and the distance between bases of the robots is set to 1.5 m. The algorithm successfully evolved trajectories for given start and end configurations of the robots. Trajectory of the left robot could be further optimized in terms of length, since it is obvious that end-effector performs arc motion, while linear motion would result in reduced trajectory length.

Operation of the coevolutionary algorithms is very complex and theoretical background is still developing in the research community [START_REF] Bucci | Emergent Geometric Organization and Informative Dimensions in Coevolutionary Algorithms[END_REF] [START_REF] Panait | Archive-based Cooperative Coevolutionary Algorithms[END_REF]. For example, it is not possible to employ simple elitist function to the coevolutionary algorithm, as it is in the case of standard algorithm. The reason is that each individual from one population is, in canonical case, evaluated by each individual from coevolving population. The consequence is that performance of the individuals from first population depends on the structure of the other population(s). That means that individual, that had high fitness value and was good in one generation, may suddenly become not so good in the next generation. The fitness vs. time function is not monotonously growing in that case.

Modified Coevolution

Standard evaluation each individual by each individual from other populations is time consuming. To speed up the evolutionary process, we save top 10% individuals from both populations and evaluate them by each individual from other population. By doing so, we hope to only increase the speed of the convergence, without hindering the ability of the algorithm for finding solutions near Pareto front. Other issue is biasing coevolutionary search towards optimal solutions. Taking in consideration the nature of the problem, we introduce dynamic fitness function. Since it is very difficult to find proper combination of weight factors, we employ following procedure:

The search starts with weight parameters having initial values chosen either by random or by some previous experience. Afterwards, number of collisions is monitored for the pair of individuals we call best collaborators -the pair receiving the highest fitness value. Since the most important criterion is to find collision free trajectories, weight w 1 is increased and simultaneously all other weight values start to decay. This way, importance is given to part of the fitness function responsible for finding collision free paths. After best collaborators have no more collisions, opposite process starts and other three weight factors start to increase, whereas w 1 starts to decay, as shown by If, in any moment, best collaborators start to collide, the first process begins, increasing the importance of avoiding collisions.

Such way, after individuals are evolved, which generally do not collide with each other, they are fine-tuned afterwards. If stationary fitness function is used, it is very difficult to evolve satisfactory strategies for the robots. There are numerous possibilities to improve this process of tuning fitness function. For example, we monitor only best collaborators i.e. one individual from the first and one individual from the second population to determine when to change fitness function. At the other hand, gradients of the growth of weight factors are chosen after several experiments were conducted. It is very important parameter, whose behavior should be determined with more care.

Discussion

As it is already mentioned, there are many possibilities to improve presented approach. There are two critical factors: speed of the convergence and completeness of the solution i.e. number of satisfying configurations developed by the algorithm before stopping criterion is matched. In what concerns speed of the convergence, it is proposed to evaluate a finite representative set from each population. This way, number of evaluations of the algorithm is decreased, but some, possibly good combinations of individuals might get lost. In what concerns completeness of solution, we propose dynamic weight factors for the fitness function. In such way, we are able to adapt the evolutionary process according to current state in the population. It is rather rough idea, how the process should look like, since only two individuals are monitored, and based on their interaction it is decided on the values of the weight factors. Simple method for changing fitness factors is adopted, namely, they are increased or decayed by adding or subtracting some fixed increment. The values of the increments remain fixed over the evolutionary process, but are different for each weight factor.

Conclusion and Future Work

Our long-term goal is to develop a framework based on described principles and implement it to a pair of real robots, probably of SCARA configuration. To do so, many important questions should be answered. First of all, algorithm should be further optimized in terms of speed of execution, although off-line planning with combination of machine learning is possible. No real physical properties of the robot are taken into consideration in this work, i.e. maximal acceleration etc. what is another important issue. At the level of execution of the algorithm, problem of synchronization of two hands based on Ethernet protocols is issue for itself and beyond the scope of this paper, but certainly an issue to be cleared before implementation to real robots would be possible.

  The two manipulators are to move from given initial to a given final configuration. The lengths of all links are set to 1 m, with distance between the robots of 2.1 m. The links are free to rotate in the range [ ] 0, rad π .

  robot's intermediate end-effector position. In the case where no obstacles are present in the environment, optimal value of the function is length of the straight line connecting initial and final end-effector position. For all other cases

Fig. 1 .

 1 Fig. 1. Trajectories evolved for two robots simultaneously. Trajectories are optimized in terms of length, end-effector velocity distribution, total rotation angle, and number of collisions.

  Fig 2.

Fig. 2 .

 2 Fig. 2. Non-stationary weight factors over generations.

Acknowledgments. The author kindly acknowledge Croatian Ministry of Science, Education and Sports for the Grant No. 120-1201948-1941, Autonomous Multiagent Assembly.


Khrystyna Nordheimer
email: nordheimer@wifo.uni-mannheim.de

Thimo Schulze
email: schulze@wifo.uni-mannheim.de

Daniel Veit

Trustworthiness in networks: A simulation approach for approximating local trust and distrust values

Keywords: Trust network, local trust values, trust properties, trust and distrust propagation, connection probability, Monte Carlo method

Trust is essential for most social and business networks in the web, and determining local trust values between two unfamiliar users is an important issue. However, many existing approaches to calculating these values have limitations in various constellations or network characteristics. We therefore propose an approach that interprets trust as probability and is able to estimate local trust values on large networks using a Monte Carlo simulation method. The estimation is based on existing indirect trust statements between two unfamiliar users. This approach is then extended to the SimTrust algorithm that incorporates both trust and distrust values. It is implemented and discussed in detail with examples. Our main contribution is a new approach which incorporates all available trust and distrust information in such a way that basic trust properties are satisfied.

Introduction

Today, many different networks shape the Internet and serve as platforms for various kinds of interaction between unfamiliar people and businesses. The bestknown examples of such platforms include eBay, Amazon, Facebook, MySpace and LinkedIn. Due to their open nature, trust between users is essential to the successful continuation of these networks. Therefore, most of them provide their own rating systems which allow users to assign trust ratings as an expression of their direct trustworthiness to other people.

Knowing this kind of information can be very useful for aggregating, filtering, and ordering data in many domains [START_REF] Kuter | SUNNY: a new algorithm for trust inference in social networks using probabilistic confidence models[END_REF]. Furthermore, the consideration of trust relationships between users is becoming a new trend for recommender systems. Trust information can be used as part of the recommendation process, especially as a means to reduce the sparsity problem [START_REF] O'donovan | Trust in recommender systems[END_REF] and thus improve the quality of recommendations [START_REF] Avesani | A trust-enhanced recommender system application: Moleskiing[END_REF].

However, in a community with dozens of millions of users, direct trust statements are only made to a limited subset of users. For example, on Facebook with 350 million active members and with a very simple rating system, the average user has about 130 friends [START_REF]Facebook[END_REF]. This may be interpreted as 130 explicit trust statements. Because of missing direct ratings among the majority of users, there is a huge lack of trust information in most online communities. Thus, the question arises whether the existing indirect trust ratings between two unacquainted people could be used to infer and predict trust between them.

In this paper, we deal with this question and present a new approach that estimates the local trust value between any two users in a network using a Monte Carlo simulation method. The contributions of our work are as follows: At first, we propose an approach, called MoCaTrust, for computing trust inferences mentioned above. Thereby, we consider networks with rating systems where only positive trust statements from a specific range can be made. This reflects the situation considered by many research works in this area [START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF][START_REF] Richardson | Trust Management for the Semantic Web[END_REF]. However, experience with real trust systems like eBay and Epinions shows that distrust is at least as important as trust [START_REF] Guha | Propagation of trust and distrust[END_REF]. Thus, we take our approach a step further and present a new algorithm, called SimTrust, which incorporates distrust in the estimation process. To our knowledge, there are only a few works that consider distrust in the computation of local trust values. [START_REF] Guha | Propagation of trust and distrust[END_REF] use a different approach incorporating various matrix operations to evaluate atomic propagations of trust. [START_REF] Massa | Controversial users demand local trust metrics: an experimental study on Epinions.com community[END_REF] present the Moletrust algorithm for computing trust values between two users. It also allows distrust statements but ignores most of them in the calculation.

The remainder of the paper is organized as follows: In Section 2, we discuss issues like trust definition, trust properties, and trust elicitation. Section 3 describes our MoCaTrust approach and takes a look at some example calculations. In Section 4, we extend our approach and describe the SimTrust algorithm which incorporates distrust. Section 5 provides details for an implementation and points out opportunities for further optimization. The conclusion and opportunities for future work are presented in Section 6.

Background

In this paper, we consider the following situation: There is an online platform where users interact with each other with respect to specific interests. They assign trust values according to the platform-specific rating system. All assigned trust statements build a trust network represented as a directed weighted graph (see Figure 1). Users are shown as nodes and a directed edge between nodes indicates that one user (truster) made trust statement about another user (trustee). The corresponding trust value conveys how much this user trusts the other one. All trust statements are given about the same context and range from 0 to 1. The prior knowledge and experiences of the truster form the basis for trusting decisions [START_REF] Luhmann | Trust and Power[END_REF]. In general, many of other factors exist which influence the decision about the trustworthiness of a user -such as subjective opinions of the actions the person has taken, recommendations from friends, psychological factors, rumors, etc. Marsh [START_REF] Marsh | Formalising Trust as a Computational Concept[END_REF], for example, analyzes these factors and then, based on them, formalizes and computes trust values. This issue is a complex field and is not the scope of our work. We rather take the ratings as they exist and use them to estimate trust between two people where direct trust values are not available. However, to compute with trust, it is important to be aware of its notion and properties, the rating system for assigning trust values, and their interpretation.

Notion of trust

Considering the notion of trust, there is a variety of different understandings of its meaning in the scientific literature. Since trust is used in various ways in different disciplines, there is no standard interdisciplinary definition. In particular, social trust is a diffuse term, its properties are fuzzy, and it is not yet well understood from a computational perspective [START_REF] Kuter | SUNNY: a new algorithm for trust inference in social networks using probabilistic confidence models[END_REF]. For this reason, beside the studies of trust in sociological and psychological theories [START_REF] Sztompka | Trust: A Sociological Theory[END_REF][START_REF] Luhmann | Familiarity, Confidence, Trust: Problems and Alternatives[END_REF][START_REF] Coleman | Foundations of Social Theory[END_REF][START_REF] Falcone | Social trust: a cognitive approach[END_REF][START_REF] Williamson | Calculativeness, Trust, and Economic Organization[END_REF] it has recently become an emerging research topic in computer science [START_REF] O'donovan | Trust in recommender systems[END_REF][START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF][START_REF] Guha | Propagation of trust and distrust[END_REF][START_REF] Massa | Controversial users demand local trust metrics: an experimental study on Epinions.com community[END_REF][START_REF] Abdul-Rahman | Supporting Trust in Virtual Communities[END_REF][START_REF] Massa | Using Trust in Recommender Systems: An Experimental Analysis[END_REF][START_REF] Golbeck | Computing with Social Trust[END_REF]. Here we make use of existing research results.

Sztompka, in [START_REF] Sztompka | Trust: A Sociological Theory[END_REF], understands trust as follows: "Trust is a bet about the future contingent actions of others". Golbeck, in [START_REF] Golbeck | Trust and nuanced profile similarity in online social networks[END_REF], adopts this definition and sees trust in a person as "a commitment to an action based on a belief that the future actions of that person will lead to a good outcome". Thus, trust seems to express the subjective expectation that the trusted person will behave in an appropriate manner.

Proceeding from that, trust has been identified with a subjective "probability that [the trustee] will perform an action that is beneficial or at least not detrimental to [the truster] " [START_REF] Gambetta | Can We Trust Trust?[END_REF]. However, opinions diverge on the question of whether trust can be modeled as a mathematical probability. While some authors reject the notion of trust as a subjective probability [START_REF] Abdul-Rahman | Supporting Trust in Virtual Communities[END_REF][START_REF] Castelfranchi | Trust Is Much More than Subjective Probability: Mental Components and Sources of Trust[END_REF], others use a probabilistic interpretation [START_REF] Kuter | SUNNY: a new algorithm for trust inference in social networks using probabilistic confidence models[END_REF][START_REF] Richardson | Trust Management for the Semantic Web[END_REF][START_REF] Gambetta | Can We Trust Trust?[END_REF][START_REF] Dasgupta | Trust as a Commodity[END_REF][START_REF] Dubois | Rigorous Probabilistic Trust-Inference with Applications to Clustering[END_REF][START_REF] Gulati | Does Familiarity Breed Trust? The Implications of Repeated Ties for Contractual Choice in Alliances[END_REF]. In our work, we also agree with [START_REF] Gambetta | Can We Trust Trust?[END_REF] and assume that "trust (or, symmetrically, distrust) is a particular level of the subjective probability with which an [user] assesses that another [user] [. . . ] will perform a particular action, both before he can monitor such action [. . . ] and in a context in which it affects his own action".

Properties of trust

Next, we deal with properties that are important for making trust computations. Based on [START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF], we consider three main properties of trust that hold in trust networks. The first very simple and inherent property of trust is asymmetry. It means, if A trusts B at a certain level, it does not necessarily mean that B trusts A at the same level.

The next important property is transitivity, i.e. trust can be passed along a path of trusting users. If A trusts B and B trusts C, it can be inferred that A trusts C at a certain level. However, the transitivity of trust is not perfect in the mathematical sense [START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF]. Considering the relationships along the path A=>B=>C in Figure 1, we cannot follow that A trusts C exactly at 0.9. On the contrary, it is plausible to expect that A's trust in C should be less than 0.9 because of their indirect relationship. Thus, trust degrades along a path of trusting people. Measuring the rate of degradation from empirical data is an interesting topic for further research.

Composability is the third property of trust. It implies that trust information along all available paths between two unknown users must be taken into account for inferring their trust. We consider again the case in Figure 1 where A trusts B and D directly. Both of them also made some trust statements about C. It is reasonable that A should take into account the information from B and D to decide about the trustworthiness of C. Another question is how this information should be composed. An analysis of the two trust networks described in [START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF] showed that higher trusted neighbors tend to agree with a user more than lower trusted neighbors, and that nodes connected by shorter paths tend to agree more than nodes connected by longer paths. Thus, it is reasonable that shorter and more trusted paths should have a much greater contribution to the final trust value than longer and less trusted paths.

In Section 3 and 4 we will show that MoCaTrust and SimTrust and their computational implementation satisfy all of the properties presented above.

Rating system

Another important part of a trust network is an appropriate rating system. As mentioned above, we consider two different schemes for representing trust. The first rating system, used by MoCaTrust, allows users to assign only positive trust values from the real interval (0,1) (see Section 3). In this case, e.g. the trust value of 0.1 means very low but positive trust. An expression of distrust is not possible. In our extended approach SimTrust, users also assign trust values from the interval (0,1) with the difference that trust values close to 0 mean very strong distrust, and values close to 1 represent very strong trust (see Section 4). Here, trust is seen as a point located on a probabilistic distribution of more general expectations, which can take a number of values between 0 and 1 exclusively, and which is centered around a trust threshold point T [START_REF] Gambetta | Can We Trust Trust?[END_REF]. This trust threshold of e.g. 0.5 therefore stands for a neutral evaluation, with expressed distrust below this threshold and expressed trust above the threshold.

Computing trust using the probabilistic interpretation of trust

After the presentation of the background, we return to the main question of this paper: How much should one user trust another one if direct trust statements, based on the prior experience between them, are not available?

As mentioned above, we first assume that a trust network provides a very simple rating system according to which users can make only positive trust statements. Furthermore, the trust value assigned by a truster represents a subjective probability that the trusted person will behave in an expected manner. Each of these values is between 0 and 1 exclusively.

The idea of our approach is to interpret a trust value as the connection probability between two appropriate nodes, i.e. the probability that the start node connects to the target node in a network. The connection probability between nodes connected directly is given by the trust statement made by the truster. If there is no direct trust value between two nodes available, we can compute it as the total connection probability. It describes the probability that there is a path between these nodes in the network [START_REF] Chen | A new algorithm for network probabilistic connectivity[END_REF], i.e. that there exists an indirect connection between them. For finding this probability, we rely on the existing concepts and techniques which have proved their effectiveness in solving similar problems in the network reliability [START_REF] Fishman | Monte Carlo: Concepts, Algorithms, and Applications[END_REF][START_REF] Provan | The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected[END_REF][START_REF] Agrawal | An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks[END_REF].

Underlying concept

The simple way to compute the total connection probability is to use the complete enumeration of all possible states of the network [START_REF] Fishman | Monte Carlo: Concepts, Algorithms, and Applications[END_REF]. Consider the trust network modeled as a directed weighted graph G = (V, E, p) with K nodes and M edges. Users are represented as a node set V = {v 1 , v 2 , . . . , v K } and trust statements as an edge set E = {e 1 , e 2 , . . . , e M }. The appropriate trust values are given as p = (p(e 1 ), p(e 2 ), . . . , p(e M )). Let ȳ = (y 1 , y 2 , . . . , y M ) denote a state of the network where y i = 1 if edge e i operates, and y i = 0 if edge e i fails, e i ∈ E. Let Y denote the set of all the possible states of the network and

P (ȳ, p) = i∈E p yi i (1 -p i ) 1-yi . (1)
Then the quantity

P r(v i , v j ) = ȳ∈Y φ(ȳ)P (ȳ, p) . (2)
is the probability that

v i connects v j with v i , v j ∈ V . The function φ(ȳ) → [0, 1] defined as φ(ȳ) = 1 if v i connects v j when state ȳ occurs 0 otherwise (3)
indicates whether the target node is reachable by the source node through an indirect path when a certain state occurs.

Let us consider Figure 1 and compute how much A should trust C applying the presented method. For the depicted network there are 2 4 possible states. A few of them are listed in Table 1, as well as the respective values of φ and P . The Table 1. Complete enumeration for computing P r(A, C).

Network state ȳ

(AB,BC,AD,DC)

P (ȳ, p) φ(ȳ) (0, 0, 0, 0) (0.9 0 • 0.1 1 ) • (0.9 0 • 0.1 1 ) • (0.2 0 • 0.8 1 ) • (0.7 0 • 0.3 1 ) = 0.0024 0 (0, 0, 0, 1) (0.9 0 • 0.1 1 ) • (0.9 0 • 0.1 1 ) • (0.2 0 • 0.8 1 ) • (0.7 1 • 0.3 0 ) = 0.0056 0 . . . . . . . . . (1, 1, 1, 0) (0.9 1 • 0.1 0 ) • (0.9 1 • 0.1 0 ) • (0.2 1 • 0.8 0 ) • (0.7 0 • 0.3 1 ) = 0.0486 1 (1, 1, 1, 1) (0.9 1 • 0.1 0 ) • (0.9 1 • 0.1 0 ) • (0.2 1 • 0.8 0 ) • (0.7 1 • 0.3 0 ) = 0.1134 1
trust value P r(A, C) calculated as in expression ( 2) is 0.8366. In this simple case it can also be calculated as P r(A, C) = 0.9 • 0.9 + (1 -0.81) • 0.2 • 0.7 = 0.8366. Now, we recall the properties of trust discussed in Section 2.2. The asymmetry of trust holds because the trust network is modeled as a directed graph. Transitivity and composability are satisfied by the calculation rules of this method. The multiplication of trust values along the path lets trust pass from the source node to the target node. Moreover, the transitivity is not perfect because all trust values range between 0 and 1. Thus, as is to be expected, the longer the path, the more trust degrades along it. Computing the total connection probability all the possible paths are aggregated and taken into account. Therefore, the local trust value captures all available information about trust between the start node and the target node. Another effect is that each additional trust path between nodes increases the overall trust value. Above all, the information from shorter and more trusted paths inherently influences the final trust value more than that from longer and less trusted paths.

Unfortunately, the computation of the local trust value between two unacquainted users by the complete enumeration method belongs to the class of #P -complete problems [START_REF] Fishman | Monte Carlo: Concepts, Algorithms, and Applications[END_REF][START_REF] Provan | The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected[END_REF]. The number of all the possible network states is 2 M and it increases exponentially with the number of edges M . This method is thus not applicable for real world networks and we need a useful approximation for the trust value. Monte Carlo sampling emerges as a well-suited solution for this kind of problem. In the next section we briefly describe a Monte Carlo method [START_REF] Fishman | Monte Carlo: Concepts, Algorithms, and Applications[END_REF] that approximates the trust value effectively.

Monte Carlo approximation

The basic idea of a Monte Carlo method is to obtain the required solution by multiple repetitions of random tests and by performing some statistical analysis of the obtained results. In our case, a state of the trust network is generated randomly, and it is determined whether the start node connects to the target node in this state. An estimator for the trust value is then simply obtained by repeating this experiment independently and calculating the mean value of the function φ.

To create a network state ȳ ∈ Y , we generate a (0, 1)-uniform distributed random number for each of the M edges and determine whether the edge operates or fails. We compare the generated number with the respective trust value. The edge fails if the random number is greater than the trust value, and this edge is removed from the graph. If the random number is lower than the trust value, the edge remains intact. Next, for this randomly generated state of the network we evaluate the function φ(ȳ). Finally, after N repetitions of the described simulation step the solution is estimated as follows:

P r(v i , v j ) = 1 N N i=1 φ( ȳi ) . ( 4
)
The generation of uniformly distributed random numbers and comparison of them with the connection probability of the edge ensures that after a sufficient number of simulation steps each edge operates with that probability. Thus, the obtained relative number of existing connections from the source node to the target node is the required total connection probability. The pseudo code in Figure 2 shows how to implement the described method. Note, this algorithm has long been used to solve problems in network reliability theory [START_REF] Fishman | Monte Carlo: Concepts, Algorithms, and Applications[END_REF]. We call this approach of using the Monte Carlo method to trust calculation MoCaTrust. We now apply MoCaTrust on the sample trust network depicted in Figure 1 in order to estimate how much user A should trust user C. Figure 3 shows the simulation process by plotting the estimator of the trust value in each simulation step. It is easy to see that even after a few simulation steps the estimated value converges to the real trust value of 0.8366 calculated in Section 3.1 using the complete enumeration method.

4 SimTrust: Extended approach incorporating trust and distrust

Trust and Distrust

In the previous section, we introduced the MoCaTrust approach to use connection probabilities between nodes in networks to calculate local trust values. The basic approach considers only ratings where every value is treated as trust. However, most existing rating systems also include some form of distrust like a binary rating (e.g. whether a review was helpful or not) or a star ranking with four or five increments (where one star stands for 'strongly disagree').

Many existing rating systems also use distrust for trust propagation. [START_REF] Guha | Propagation of trust and distrust[END_REF] find out that distrust has significant impact on how trust is propagated and that direct distrust propagation offers the most promising results. [START_REF] Ziegler | Propagation Models for Trust and Distrust in Social Networks[END_REF] also use distrust in their models and use a similar approach. The local trust metrics of [START_REF] Massa | Controversial users demand local trust metrics: an experimental study on Epinions.com community[END_REF] and [START_REF] Golbeck | Computing and applying trust in web-based social networks[END_REF] also account for distrust to a certain degree. Therefore, we introduce our algorithm SimTrust, extending the simulation approach explained in Section 3 with a 'trust threshold' and transformation rules in order to account for trust and distrust.

In order to incorporate distrust, a couple of preliminary considerations have to be taken into account. Most of the existing rating systems are not able to account for a detailed and differentiated rating of a person. It is unclear whether a positive binary rating does really mean 100% trust for this person. Consider for example eBay where a vast majority of ratings is positive, and negative or even neutral feedback is hardly given. A five star ranking could be considered as a ranking where '3' stands for indifferent or neutral and '4' and '5' are equidistant values somewhere between 0.5 and 1.0. But other interpretations are also possible which makes it difficult to work with these imprecise values for local trust values.

In this paper, we use a rating system where users assign trust values from the continuous interval (0,1). So, they have the possibility to rate each other in detail. This initial rating scale includes both trust and distrust; therefore a value close to 0 represents very strong distrust, and a value close to 1 means very strong trust. With regards to the meaning and interpretation of existing trust values, they could be transformed to this continuous scale. For example, the 5 star rating could stand for 0.1, 0.3, 0.5, 0.7 and 0.9 to work with our approach.

These continuous trust values cannot be treated as probabilities in networks directly. Intuitively, if the source user A rates the target user B with a trust value below a certain threshold, this rating should reduce the overall local trust value from user A to user B. According to [START_REF] Gambetta | Can We Trust Trust?[END_REF], we call this value 'trust threshold' T . Naturally, this trust threshold would be 0.5 in most cases1 -which is also the trust value issued to individuals where no information is available [START_REF] Gambetta | Can We Trust Trust?[END_REF]. Thus, every value below 0.5 shall reduce the overall trust value, and every value above 0.5 shall increase it respectively. However, as stated earlier, when calculating trust in networks every path from the source user to the target user increases the overall trust value.

Calculating local trust values using trust and distrust

For calculation purposes, we therefore introduce two temporary graphs G trust and G distrust that are calculated separately in order to account for trust and distrust. These two graphs are copies of the original graph G = (V, E, p) where the values of the direct predecessors of the target node are modified. For these direct predecessors of the target node, it is intuitively clear that a low trust value of e.g. 0.1 should reduce the local trust value for this target and a high trust value of e.g. 0.9 improves the local trust value.

For the temporary trust graph, we therefore use the trust threshold T and transform the trust values above this threshold to a new scale ranging from 0 to 1 using a simple linear transformation. The incoming edges of the target node with values below the threshold (p(e i ) < T ) are deleted (setting the probability to zero). Hence, in the temporary trust graph G trust = (V, E , p ), every value p(e i ) of direct predecessors of the target node is transformed according to:

p (e i ) = (p(e i ) -T ) • 1 1-T if p(e i ) ≥ T 0 otherwise (5)
For a trust threshold of T = 0.5 this leads to

p (e i ) = (p(e i ) -0.5) • 2 if p(e i ) ≥ 0.5 0 otherwise (6)
Correspondingly, in the temporary distrust graph G distrust = (V, E , p ), every value p(e i ) of direct predecessors of the target node is transformed according to:

p (e i ) = (T -p(e i )) • 1 T if p(e i ) < T 0 otherwise (7)
And for T = 0.5:

p (e i ) = (0.5 -p(e i )) • 2 if p(e i ) < 0.5 0 otherwise (8)
We only change values of direct predecessors of the target node and do not change the values 'in the middle'. The reasons for not changing these values are given below.

There are many approaches to treat these values. [START_REF] Guha | Propagation of trust and distrust[END_REF] introduce and evaluate some of them. One extreme suggests that the "enemy of your enemy is your friend " [START_REF] Rosenberg | The 1941 Mission of Frank Aiken to the United States: An American Perspective[END_REF] and these values should therefore be inverted. However, such interpretation only holds true in very special circumstances. Other approaches like Moletrust [START_REF] Massa | Controversial users demand local trust metrics: an experimental study on Epinions.com community[END_REF] suggest ignoring all values below a certain threshold completely and deleting the corresponding edges. This approach might lead to a significant reduction of edges in the graph but at the same time significant distrust information might get lost.

We, on the other hand, use the interpretation that even a strong distrust towards a node does not necessarily mean that the judgment of this node is flawed when rating others. For example, a person writing low quality reviews in a product portal might very well be able to rate other reviews. Thus, it is reasonable to consider such ratings to a certain degree. Of course, trust values issued from distrusted nodes should have a much lower effect than those issued by edges where we have a strong trust connection. This property holds for SimTrust if no modification is done to the trust values in the middle at all. You can see that a path including a value like 0.1, indicating strong distrust towards a person, has only a minor effect on the overall local trust values, especially when other trusted paths suggest strong trust or distrust.

It can also be shown that our approach calculates much better values if a trust value along a path is just slightly below the threshold value used for deleting edges in other approaches. E.g., in [START_REF] Massa | Controversial users demand local trust metrics: an experimental study on Epinions.com community[END_REF], changing one trust value just slightly can have significant changes on the overall local trust value if this change moves the value above or below the threshold and there are few paths from source to target. Our approach avoids this harsh cutoff depending on a binary segmentation in trust (which counts fully) and distrust (which is ignored).

For each of the two temporary graphs G trust and G distrust with the transformed values of the direct predecessors of the target nodes, we now run the simulation described in Section 3. This leads to two trust values P r trust (v i , v j ) and P r distrust (v i , v j ). These values are now inversely transformed to get the overall trust value:

P r local (v i , v j ) = D • T + T if D < 0 D • (1 -T ) + T if D ≥ 0 (9)
where D = P r trust (v i , v j ) -P r distrust (v i , v j ). This transformation brings the two values back to the original scale where T is the trust threshold between trust and distrust. The first case is used if the trust value is higher than the distrust value. The overall trust value then lies between T and 1. In the second case, distrust outweighs trust and the overall trust value falls between 0 and T . For a threshold of T = 0.5 the equation is simplified to:

P r local (v i , v j ) = P r trust (v i , v j ) -P r distrust (v i , v j ) 2 + 0.5 . ( 10
)
An implementation of the complete algorithm including procedure, evaluation and results can be found in Section 5.

Implementation

In order to evaluate SimTrust, we have implemented the approach in a simple program. The basic procedure of the approach (as explained in detail in Section 4) can be found in Table 2. We use JUNG 'Java Universal Network/Graph Framework' [31] as a basis for our implementation. The implementation itself is quite straightforward using mostly methods already implemented by JUNG. We use the Dijkstra algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] in order to determine the reachability of target and source nodes during the simulation steps.

Example

We now show an example calculation of the complete SimTrust algorithm using two sample graphs. Figure 4

Evaluation

Complexity. In this section, we will evaluate the complexity of our approach using the Big-O notation; for an introduction, see e.g. [START_REF] Sipser | Introduction to the Theory of Computation[END_REF]. According to graph theory literature, n stands for the number of nodes and m stands for the number of edges in the current graph. Duplicating the graph has a complexity of O(1).

Transforming the graph has a worst case complexity of O(m) if all users rate the target node.

The simulation runs are the most complex parts. Here, checking the reachability (whether the source node connects the target node) is most complex. We use the Dijkstra algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] in our implementation which, using some optimization techniques, has a complexity of O(m + n • log(n)) if all distances are positive and there are less than n 2 edges [34]. Since we do not need to find the shortest path but are only concerned with reachability, there might be more efficient ways to solve the problem. [START_REF] Roditty | A fully dynamic reachability algorithm for directed graphs with an almost linear update time[END_REF] introduce an algorithm with almost linear update time. Among others, [START_REF] Khoussainov | A Dynamic Algorithm for Reachability Games Played on Trees[END_REF][START_REF] Wang | Dual Labeling: Answering Graph Reachability Queries in Constant Time[END_REF] also introduce reachability algorithms that are more efficient than Dijkstra. Since all of them have specific restrictions or limitations, an optimal algorithm depends on the specifics of actual networks. The rest of the SimTrust algorithm works in constant time. Reverse transformation and output both work in O(1).

In summary, the current implementation has a complexity of O(m+n•log(n)). Note that in complexity theory, only the most complex part is used for the total complexity. A constant factor of 1000 simulation steps also does have no effect on the complexity. Approaches to improve the current implementation are given in the next section.

Optimization. As already stated above, our current implementation is only a proof of concept with a few suggestions for efficient algorithms. For an implementation in a real world scenario, there are several possibilities to improve our approach. Some of them are presented below.

First, only paths that have a certain maximum depth could be used. Due to the multiplication of trust values, it can be shown that starting from a certain path length, additional values have little to no effect. The exact depth has to be evaluated depending on real implementations.

Second, our current approach uses a fixed number of simulation steps. In order to improve the runtime, a dynamic number of simulation steps can be used. For this purpose, however, an appropriate convergence diagnostic is needed.

Finally, because of the parallel nature of the SimTrust algorithm (each simulation step does not depend on the result of the previous one), it can be implemented in a parallel environment. Furthermore, if local trust values for more than one target user shall be calculated at the same time, distributing the code between various (virtual) computers might also improve the runtime.

Conclusions and future work

In most online platforms, trust is a prerequisite for successful interaction. The a priori knowledge of how much a user should trust other unfamiliar users can considerably improve its quality. In this paper, we presented two approaches to infer local trust values between unknown users based on their indirect trust statements. We first considered the situation where only positive trust statements could be made and introduced MoCaTrust, an approach for calculating these trust values using a Monte Carlo simulation method. Next, we modified it and presented the SimTrust algorithm in order to account for trust and distrust. Implementation details and examples were given for illustration.

In the future, our intention is to improve the described approach, particularly with regard to the runtime, and evaluate it on real world networks. The latter could not be done yet because of the unavailability of suitable real trust and distrust data.

Fig. 1 .

 1 Fig. 1. A sample trust network.

Fig. 2 .

 2 Fig. 2. Pseudo code of the Monte Carlo simulation method.

Fig. 3 .

 3 Fig. 3. Estimation of the trust value between users A and C in the sample network from Section 2 using the MoCaTrust approach.

2 Find the direct predecessors of the target node 3

 23 Transform both graphs according to the rules in equation (5) and[START_REF] Guha | Propagation of trust and distrust[END_REF] 4Run simulation on G trust and save obtained value in P r trust (vi, vj)5Run simulation on G distrust and save obtained value in P r distrust (vi, vj)6Reverse transform the obtained values using equation (9) 7 Display the output local trust value

  shows a sample graph and the two transformations to G trust and G distrust for the trust threshold T = 0.5. The two simulation runs converge to P r trust (A, F ) = 0.8416 and P r distrust (A, F ) = 0.2272. Inverse transformation leads to the overall trust values of P r local (A, F ) = 0.8072.

  (a) Original graph (b) G trust (c) G distrust

Fig. 4 .

 4 Fig. 4. A sample graph and transformations for T = 0.5.

Figure 5

 5 Figure 5 presents another example where we have two positive and two negative ratings of the target node. The source node A rates the nodes B, C, D, and E with an equal trust value of 0.9. Further, B and C rate the target node F with strong trust while D and E express strong distrust. Intuitively, based on this information neither trust nor distrust can be predicted.

  (a) Original graph (b) G trust (c) G distrust

Fig. 5 .

 5 Fig. 5. A sample graph with trust prediction.

Table 2 .

 2 Procedure of SimTrust algorithm. 1 Duplicate the original graph twice into G trust and G distrust

For certain networks and with respect to real data, other values than 0.5 are possible for T , for example in networks with overall positive ratings the threshold could be set other values like 0.3, 0.7 or 0.9 in order to capture the average or median overall value.