Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

An Efficient Method to Find the Optimal Social Trust Path in Contextual Social Graphs

  • Conference paper
  • First Online:

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.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Hang, C., Wang, Y., Singh, M.: Operators for propagating trust and their evaluation in social networks. In: AAMAS 2009, pp. 1025–1032 (2009)

    Google Scholar 

  2. Liu, G., Wang, Y., Orgun, M.A.: Optimal social trust path selection in complex social networks. In: AAAI 2010, pp. 1397–1398 (2010)

    Google Scholar 

  3. Adler, P.S.: Market, hierarchy, and trust: The knowledge economy and the future of capitalism. Organization Science12(12), 215–234 (2001)

    Article  Google Scholar 

  4. Ashri, R., Ramchurn, S., Sabater, J., Luck, M., Jennings, N.: Trust evaluation through relationship analysis. In: AAMAS 2005, pp. 1005–1011

    Google Scholar 

  5. Brass, D.J.: A Socal Network Prespective On Industral/organizational psychology. Industrial/Organizational Handbook (2009)

    Google Scholar 

  6. Dalton, M.: Men Who Manage. Wiley, New York (1959)

    Google Scholar 

  7. Golbeck, J., Hendler, J.: Inferring trust relationships in web-based social networks. ACM Transactions on Internet Technology6(4), 497–529 (2006)

    Article  Google Scholar 

  8. Kunegis, J., Lommatzsch, A., Bauckhang, C.: The slashdot zoo: Mining a social network with negative edges. In: WWW 2009, pp. 741–750

    Google Scholar 

  9. Baase, S., Gelder, A.: Computer Algorithms Introduction to Design and Analysis. Addision Wesley

    Google Scholar 

  10. Christianson, B., Harbison, W.S.: Why isn’t trust transitivie? In: Lomas, M. (ed.) Security Protocols 1996. LNCS, vol. 1189, pp. 171–176. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  11. Mansell, R., Collins, B.: Trust and Crime in Information Societies. Edward Elgar Publishing (2005)

    Google Scholar 

  12. Lin, C., Cao, N., Liu, S., Papadimitriou, S., Sun, J., Yan, X.: Smallblue: Social network analysis for expertise search and collective intelligence. In: ICDE 2009, pp. 1483–1486 (2009)

    Google Scholar 

  13. Miller, R., Perlman, D., Brehm, S.: Intimate Relationships, 4th edn. McGraw-Hill College (2007)

    Google Scholar 

  14. Liu, G., Wang, Y., Orgun, M., Lim, E.P.: A heuristic algorithm for trust-oriented service provider selection in complex social networks. In: SCC, pp. 130–137 (2010)

    Google Scholar 

  15. Liu, G., Wang, Y., Orgun, M.A.: Finding k optimal social trust paths for the selection of trustworthy service providers in complex social networks. In: ICWS 2011, pp. 41–48

    Google Scholar 

  16. Liu, G., Wang, Y., Orgun, M.A., Lim, E.P.: Finding the optimal social trust path for the selection of trustworthy service providers in complex social networks. IEEE Transactions on Services Computing (TSC) (2011)

    Google Scholar 

  17. Liu, G., Wang, Y., Wong, D.: Multiple qot constrained social trust path selection in complex social networks. In: TrustCom 2012

    Google Scholar 

  18. Sakaki, T., Okazaki, M., Matsuo, Y.: Tweet analysis for real-time event detection and earthquake reporting system development. IEEE Transactions on Knowledge and Data Engineering25(4), 919–931 (2013)

    Article  Google Scholar 

  19. Shin, Y., Lim, J., Park, J.: Joint optimization of index freshness and coverage in real-time search engines. IEEE Transactions on Knowledge and Data Engineering24(12), 2203–2217 (2012)

    Article  Google Scholar 

  20. Gentle, J., Hardle, W., Mori, Y.: Handbook of Computational Statistics. Springer (2004)

    Google Scholar 

  21. Wang, G., Wu, J.: Multi-dimensional evidence-based trust management with multi-trusted paths. Future Generation Computer Systems17, 529–538 (2011)

    Article  Google Scholar 

  22. Liu, G., Wang, Y., Orgun, M.A.: Trust transitivity in complex social networks. In: AAAI 2011, pp. 1222–1229

    Google Scholar 

  23. Mccallum, A., Wang, X., Corrada-Emmanuel, A.: Topic and role discovery in social networks with experiments on Enron and academic email. Journal of Artificial Intelligence Research30(1), 249–272 (2007)

    Google Scholar 

  24. Tang, J., Zhang, J., Yan, L., Li, J., Zhang, L., Su, Z.: Arnetminer: Extraction and mining of academic social networks. In: KDD 2008, pp. 990–998 (2008)

    Google Scholar 

  25. Berger, P., Luckmann, T.: The Social Construction of Reality: A Treatise in the Sociology of Knowledge. Anchor Books (1966)

    Google Scholar 

  26. Korkmaz, T., Krunz, M.: Multi-constrained optimal path selection. In: INFOCOM 2001, pp. 834–843

    Google Scholar 

  27. Morton, D., Popova, E.: Monte-carlo simulation for stochastic optimization. Encyclopedia of Optimization, pp. 2337–2345 (2009)

    Google Scholar 

  28. Mislove, A., Marcon, M., Gummadi, K., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: ACM IMC 2007, pp. 29–42 (2007)

    Google Scholar 

  29. Chia, P., Pitsilis, G.: Exploring the use of explicit trust link for filtering recommenders: A study on epinions.com. Journal of Information Processing19, 332–344 (2011)

    Article  Google Scholar 

  30. Chua, F., Lim, E.P.: Trust network inference for online rating data using generative models. In: KDD 2010, pp. 889–898

    Google Scholar 

  31. Lo, D., Surian, D., Zhang, K., Lim, E.P.: Mining direct antagonistic communities in explicit trust networks. In: CIKM 2011, pp. 1013–1018

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Soochow University, Suzhou, 215006, China

    Guanfeng Liu, Lei Zhao, An Liu, Jiajie Xu & Zhixu Li

  2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Jiangsu, China

    Guanfeng Liu, Lei Zhao, An Liu, Jiajie Xu & Zhixu Li

  3. School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, 4072, Australia

    Kai Zheng

  4. School of Computer Science and Information Technology, RMIT University, Melbourne, 3001, Australia

    Athman Bouguettaya

Authors
  1. Guanfeng Liu

    You can also search for this author inPubMed Google Scholar

  2. Lei Zhao

    You can also search for this author inPubMed Google Scholar

  3. Kai Zheng

    You can also search for this author inPubMed Google Scholar

  4. An Liu

    You can also search for this author inPubMed Google Scholar

  5. Jiajie Xu

    You can also search for this author inPubMed Google Scholar

  6. Zhixu Li

    You can also search for this author inPubMed Google Scholar

  7. Athman Bouguettaya

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toGuanfeng Liu.

Editor information

Editors and Affiliations

  1. Universität München, München, Germany

    Matthias Renz

  2. University of Southern California, Los Angeles, USA

    Cyrus Shahabi

  3. University of Queensland, Brisbane, Australia

    Xiaofang Zhou

  4. Monash University, Clayton, Australia

    Muhammad Aamir Cheema

Rights and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Liu, G.et al. (2015). An Efficient Method to Find the Optimal Social Trust Path in Contextual Social Graphs. In: Renz, M., Shahabi, C., Zhou, X., Cheema, M. (eds) Database Systems for Advanced Applications. DASFAA 2015. Lecture Notes in Computer Science(), vol 9050. Springer, Cham. https://doi.org/10.1007/978-3-319-18123-3_24

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp