In Online Social Networks (OSNs), the important participants, the trust relations between participants, and the interaction contexts between participants greatly impact a participant's decision-making in many applications, such as service provider selection and crowdsourcing service invocation. However, predicting the trust between two unknown participants based on the whole large-scale social network can lead to very high computation costs. Thus, prior to trust prediction, extracting a small-scale sub-network containing the important participants and the corresponding contextual information with a high density could make the trust prediction more efficient and effective. However, extracting such a sub-network has been proved to be an NP-Complete problem. To address this challenging problem, we propose a strong social component-aware trust sub-network extraction model, So-BiNet, to search for near-optimal solutions effectively and efficiently. Our method can extract a trust sub-network without any decompression, which can in turn greatly save the search time of trust sub-network extraction. The experiments, conducted on four social network datasets, demonstrate that our approach can efficiently extract sub-networks covering important participants and contextual information while keeping a high density. Our approach is superior to the state-of-the-art approaches in terms of the quality of the sub-networks extracted within the same execution time.

Online Social Networks (OSNs) have become an integral part of daily life in recent years. OSNs contain important participants, the trust relations between participants, and the contexts in which participants interact with each other. All of these have a great influence on the prediction of the trust between a source participant and a target participant, which is important for a participant's decision-making process in many applications, such as seeking service providers. However, predicting the trust from a source participant to a target one based on the whole social network is not really feasible. Thus, prior to trust prediction, the extraction of a small-scale sub-network containing most of the important nodes and contextual information with a high density rate could make trust prediction more efficient and effective. However, extracting such a sub-network has been proved to be an NP-Complete problem. To address this challenging problem, we propose BiNet: a social context-aware trust sub-network extraction model to search for near-optimal solutions effectively and efficiently. In this model, we first capture important factors that affect the trust between participants in OSNs. Next, we define a utility function to measure the trust factors of each node in a social network. At last, we design a novel binary ant colony algorithm with newly designed initialization and mutation processes for sub-network extraction incorporating the utility function. The experiments, conducted on two popular datasets of Epinion and Slash dot, demonstrate that our approach can extract sub-networks covering important participants and contextual information while keeping a high density rate. Our approach is superior to the state-of-the-art approaches in terms of the quality of extracted sub-networks within the same execution time.

Online social networks have been used for a variety of rich activities in recent years, such as investigating potential employees and seeking recommendations of high quality services and service providers. In such activities, trust is one of the most critical factors for the decision-making of users. In the literature, the state-of-the-art trust prediction approaches focus on either dispositional trust tendency and propagated trust of the pair-wise trust relationships along a path or the similarity of trust rating values. However, there are other influential factors that should be taken into account, such as the similarity of the trust rating distributions. In addition, tendency, propagated trust and similarity are of different types, as either personal properties or interpersonal properties. But the difference has been neglected in existing models. Therefore, in trust prediction, it is necessary to take all the above factors into consideration in modeling, and process them separately and differently. In this paper we propose a new trust prediction model based on trust decomposition and matrix factorization, considering all the above influential factors and differentiating both personal and interpersonal properties. In this model, we first decompose trust into trust tendency and tendency-reduced trust. Then, based on tendency-reduced trust ratings, matrix factorization with a regularization term is leveraged to predict the tendency-reduced values of missing trust ratings, incorporating both propagated trust and the similarity of users' rating habits. In the end, the missing trust ratings are composed with predicted tendency-reduced values and trust tendency values. Experiments conducted on a real-world dataset illustrate significant improvement delivered by our approach in trust prediction accuracy over the state-of-the-art approaches.

Online trading takes place in a very complex environment full of uncertainty in which deceitful service providers or sellers may strategically change their behaviors to maximize their profits. The proliferation of deception cases makes it essential and challenging to model the dynamics of a service provider and predict the trustworthiness of the service provider in transactions. Recently, probabilistic trust models have been used to assist decision making in computing environments. Although the typical Hidden Markov Model (HMM) has been used to model a provider's behavior dynamics, existing approaches focus only on the outcomes or ignore the hidden characteristics of the HMM model. In this paper, we model the dynamic trust of service providers concerning a forthcoming transaction in light of as much information as we can consider, including the static features, such as the provider's reputation and item price, and the dynamic features, such as the latest profile changes of a service provider and price changes. Based on a service provider's historical transactions, we predict the trustworthiness of the service provider in a forthcoming transaction. In addition, the Mutual Information theories and the Principle Component Analysis method are leveraged to eliminate redundant information and combine essential features to form lower dimensional feature vectors. Furthermore, by adopting Vector Quantization techniques, we apply the discrete HMM in a more powerful way, in which all the features extracted from both contextual information and the rating of each transaction are treated as observations of HMM. We evaluate our approach empirically in order to study its performance. The experiment results illustrate that our approach significantly outperforms the state-of-the-art probabilistic trust methods in accuracy in the cases with complex changes.

We study distributed task-allocation problems where cooperative agents need to perform some tasks simultaneously. Examples are multi-agent routing problems where several agents need to visit some targets simultaneously, for example, to move obstacles out of the way cooperatively. In this paper, we first generalize the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks. Second, we show how agents can construct and approximate reaction functions in a distributed way. Third, we show how reaction functions can be used by an auctionlike algorithm to allocate tasks to agents. Finally, we show empirically that the team costs of our algorithms are substantially smaller than those of an existing state-of-the-art allocation algorithm for complex tasks.

We study the distributed allocation of tasks to cooperating robots in real time, where each task has to be assigned to exactly one robot so that the sum of the latencies of all tasks is as small as possible. We propose a new auction-like algorithm, called Sequential Incremental-Value (SIV) auction, which assigns tasks to robots in multiple rounds. The idea behind SIV auctions is to assign as many tasks per round to robots as possible as long as their individual costs for performing these tasks are at most a given bound, which increases exponentially from round to round. Our theoretical results show that the team costs of SIV auctions are at most a constant factor larger than minimal.

One of the main applications of mobile robots is coverage: visiting each location in known terrain. Coverage is crucial for lawn mowing, cleaning, harvesting, search-and-rescue, intrusion detection, and mine clearing. Naturally, coverage can be sped up with multiple robots. However, we show that solving several versions of multirobot coverage problems with minimal cover times is NP-hard, which provides motivation for designing polynomial-time constant-factor approximation algorithms. We then describe multirobot forest coverage (MFC), a new polynomial-time multirobot coverage algorithm based on an algorithm by Even et al. [Min-max tree covers of graphs. Oper. Res. Lett., vol. 32, pp. 309-315, 2004] for finding a tree cover with trees of balanced weights. Our theoretical results show that the cover times of MFC in weighted and unweighted terrain are at most about a factor of 16 larger than minimal. Our simulation results show that the cover times of MFC are close to minimal in all tested scenarios and smaller than the cover times of an alternative multirobot coverage algorithm.

We study task-allocation problems where cooperative robots need to perform tasks simultaneously. We develop a distributed negotiation procedure that allows robots to find all task exchanges that reduce the team cost of a given task allocation, without robots having to know how other robots compute their robot costs. Finally, we demonstrate empirically that our negotiation procedure can substantially reduce the team costs of task allocations resulting from existing task-allocation procedures, including sequential single-item auctions.

In this paper, we study how multiple robots can cover known terrain quickly. We extend Multi-Robot Forest Coverage, a state-of-the-art multi-robot coverage algorithm, from terrain with uniform traversability to terrain with nonuniform traversability, which is nontrivial. We prove that its cover times are at most about sixteen times larger than minimal and demonstrate experimentally that they are significantly smaller than those of an alternative multi-robot coverage algorithm.

We study how to improve sequential single-item auctions that assign targets to robots for exploration tasks such as environmental clean-up, space-exploration, and search and rescue missions. We exploit the insight that the resulting travel distances are small if the bidding and winner-determination rules are designed to result in hillclimbing, namely to assign an additional target to a robot in each round of the sequential single-item auction so that the team cost increases the least. We study the impact of increasing the lookahead of hillclimbing and using roll-outs to improve the evaluation of partial target assignments. We describe the bidding and winner-determination rules of the resulting sequential single-item auctions and evaluate them experimentally, with surprising results: larger lookaheads do not improve sequential single-item auctions reliably while only a small number of roll-outs in early rounds already improve them substantially

One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. Terrain coverage is crucial for lawn mowing, cleaning, harvesting, search-and-rescue, intrusion detection and mine clearing. Naturally, coverage can be sped up with multiple robots. In this paper, we describe multi-robot forest coverage, a new multi-robot coverage algorithm based on an algorithm by Even et al. (2004) for finding a tree cover with trees of balanced weights. The cover time of multi-robot forest coverage is at most eight times larger than optimal, and our experiments show it to perform significantly better than existing multi-robot coverage algorithms.