Online Social Network (OSN) has been used to enhance service provision and service selection, where trust is one of the most important factors for the decision making of service consumers. Thus, a significant and challenging problem is how to effectively and efficiently find those social trust paths that can yield trustworthy trust evaluation results based on the requirements of a service consumer particularly in contextual OSNs which contains social contexts, like social relationships and social trust between participants, and social positions of participants. In this paper, we propose a new concept called Strong Social Graph (SSG), consisting of participants with strong social connections. We also propose an approach to identify SSGs, and propose a novel index method and a graph compression method for SSG. Then based on the compressed SSG and indices, we propose a new efficient and effective approximation algorithm, called SSG-MCBA by adopting the Monte Carlo method and our optimization search strategies. The experiments conducted onto two real social network datasets illustrate that SSG-MCBA greatly outperforms the state-of-the-art method in both efficiency and effectiveness.
- Service provider selection
- Social network