Abstract: Online social network (OSN) has been used to enhance service provision and service selection. However, 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. This paper first presents a contextual social network structure and the NP-complete multiple constrained social trust paths finding problem. To deal with this challenging problem, this paper proposes a new concept called strong social graph (SSG). It also proposes a novel index method for SSG, and based on the indices and Monte Carlo method, it proposes a new efficient and effective approximation algorithm, called strong social graph-Monte Carlo based algorithm (SSG-MCBA). The experiments conducted onto two real datasets illustrate that SSG-MCBA greatly outperforms the previously proposed algorithm in both efficiency and effectiveness.

Key words: social network, trust, service provider selection

摘要： 在线社交网络（online social network，OSN）已经被用于增强服务提供和服务选择。然而，一个关键并且充满挑战的问题便是，如何根据服务消费者的需求有效并且高效地找到那些具有可信任评估结果的社交信任路径，尤其是在包含复杂社会关系的在线社交网络中。首先提出一个包含社交影响因子的社交网络结构。然后提出了一种NP完全的多约束社交信任路径查询问题。为了解决这个极具挑战的问题，提出了一个名为“强社交图”（strong social graph，SSG）的新概念。接着提出了一种基于SSG的新的索引方法。基于SSG索引，通过运用蒙特卡罗方法和相关优化搜索策略提出了一个名为“基于强社交图和蒙特卡罗算法”（strong social graph-Monte Carlo based algorithm，SSG-MCBA）的高效近似算法。两个真实数据集上的实验结果表明SSG-MCBA在准确率和效率上都极大地优于先前的算法。

关键词: 社交网络, 信任度, 服务提供商选择