Fast Trust Computation in Online Social Networks

Safi-Ullah NASIR  Tae-Hyung KIM  

IEICE TRANSACTIONS on Communications   Vol.E96-B   No.11   pp.2774-2783
Publication Date: 2013/11/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.2774
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Progress in Information Network Science)
social networks,  trust,  min-max trust propagation,  landmarks,  

Full Text: PDF>>
Buy this Article

Computing the level of trust between two indirectly connected users in an online social network (OSN) is a problem that has received considerable attention of researchers in recent years. Most algorithms focus on finding the most accurate prediction of trust; however, little work has been done to make them fast enough to be applied on today's very large OSNs. To address this need we propose a method for fast trust computation that is suitable for very large social networks. Our method uses min-max trust propagation strategies along with the landmark based method. Path strength of every node is pre-computed to and from a small set of reference users or landmarks. Using these pre-computed values, we estimate the strength of trust paths from the source user to in-neighbors of the target user. The final trust estimate is obtained by aggregating information from most reliable in-neighbors of the target user. We also describe how the landmark based method can be used for fast trust computation according to other trust propagation models. Experiments on a variety of real social network datasets verify the efficiency and accuracy of our method.