An efficient method to find the optimal social trust path in contextual social graphs

Guanfeng Liu*, Lei Zhao, Kai Zheng, An Liu, Jiajie Xu, Zhixu Li, Athman Bouguettaya

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

3 Citations (Scopus)

Abstract

Online Social Networks (OSN) have been used as platforms for many emerging applications, where trust is a critical factor for participants’ decision making. In order to evaluate the trustworthiness between two unknown participants, we need to perform trust inference along the social trust paths formed by the interactions among the intermediate participants. However, there are usually a large number of social trust paths between two participants. Thus, a challenging problem is how to effectively and efficiently find the optimal social trust path that can yield the most trustworthy evaluation result based on the requirements of participants. In this paper, the core problem of finding the optimal social trust path with multiple constraints of social contexts is modelled as the classical NP-Complete Multi-Constrained Optimal Path (MCOP) selection problem. To make this problem practically solvable, we propose an efficient and effective approximation algorithm, called T-MONTE-K, by combining Monte Carlo method and our optimised search strategies. Lastly we conduct extensive experiments based on a real-world OSN dataset and the results demonstrate that the proposed T-MONTE-K algorithm can outperform state-of-the-art MONTE K algorithm significantly.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication20th International Conference, DASFAA 2015, Proceedings, Part II
EditorsMatthias Renz, Cyrus Shahabi, Xiaofang Zhou, Muhammad Aamir Cheema
Place of PublicationCham
PublisherSpringer, Springer Nature
Pages399-417
Number of pages19
Volume9050
ISBN (Electronic)9783319181233
ISBN (Print)9783319181226
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: 20 Apr 201523 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9050
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
CountryViet Nam
CityHanoi
Period20/04/1523/04/15

Fingerprint Dive into the research topics of 'An efficient method to find the optimal social trust path in contextual social graphs'. Together they form a unique fingerprint.

Cite this