پیش بینی پیوند در شبکه‌های اجتماعی به وسیله تخصیص درجه‌ی همسایگی به رئوس در گراف‌های بدون جهت

نویسندگان
حدیث بشیری 1
غلامحسین دستغیبی‌فرد 2
1 دانشجوی کارشناسی ارشد، مهندسی کامپیوتر،دانشکده برق و کامپیوتر، دانشگاه شیراز، شیراز، ایران
2 دانشیار، مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه شیراز، شیراز، ایران
چکیده
امروزه شبکه‌های اجتماعی مثل فیس‌بوک، گوگل‌پلاس، اینستاگرام و غیره در زندگی افراد تأثیر بسزایی دارند. در این شبکه‌ها برای پیشنهاد افراد به یکدیگر از الگوریتم‌های پیش‌بینی پیوند استفاده می‌شود و یکی از موضوعات چالش‌برانگیز و پرکاربرد می‌باشد. محققین الگوریتم‌های مختلفی برای پیش‌بینی پیوند ارائه کرده‌اند، اما مشکل عمده الگوریتم‌های موجود، دقت پایین آن‌هاست. با توجه به اینکه درصد ارتباطات در شبکه‌های اجتماعی متفاوت است، در این مقاله با استفاده از وزن‌دار کردن یال‌ها و تخصیص درجه‌ی همسایگی، الگوریتمی برای تشخیص دوستان صمیمی ارائه داده‌ایم. آزمایش الگوریتم پیشنهادی بر روی سه مجموعه داده Facebook و Hamster و Email صورت گرفته است و در مقایسه با الگوریتم‌های جاری به ترتیب 0.4 ، 2.4 و 6.9  درصد بهبود دقت داشته‌ایم.

کلیدواژه‌ها

  • [1] M. Zuckerberg, “facebook,” 2017. [Online]. Available: https://www.facebook.com/zuck?fref=ts. [Accessed: 01-Jan-2017].
  • [2] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” J. Assoc. Inf. Sci. Technol., vol. 58, no. 7, pp. 1019–1031, 2007.
  • [3] Y. Dhote, N. Mishra, and S. Sharma, “Survey and analysis of temporal link prediction in online social networks,” in Advances in Computing, Communications and Informatics (ICACCI), International Conference on, pp. 1178–1183, 2013.
  • [4] A. K. Menon and C. Elkan, “Link prediction via matrix factorization,” in Joint european conference on machine learning and knowledge discovery in databases, pp. 437–452, 2011.
  • [5] G. Kossinets, “Effects of missing data in social networks,” Soc. Networks, vol. 28, no. 3, pp. 247–268, 2006.
  • [6] J. Zhang, X. Kong, and S. Y. Philip, “Predicting social links for new users across aligned heterogeneous social networks,” in Data Mining (ICDM), IEEE 13th International Conference on, pp. 1289–1294, 2013.
  • [7] E. A. Leicht, P. Holme, and M. E. J. Newman, “Vertex similarity in networks,” Phys. Rev. E, vol. 73, no. 2, p. 26120, 2006.
  • [8] “facebook,” 2017. [Online]. Available: www.facebook.com.
  • [9] “google plus,” 2017.
  • [10] W. Sherchan, S. Nepal, and C. Paris, “A survey of trust in social networks,” ACM Comput. Surv., vol. 45, no. 4, p. 47, 2013.
  • [11] P. Jaccard, “Étude comparative de la distribution florale dans une portion des Alpes et des Jura,” Bull Soc Vaudoise Sci Nat, vol. 37, pp. 547–579, 1901.
  • [12] M. E. J. Newman, “Clustering and preferential attachment in growing networks,” Phys. Rev. E, vol. 64, no. 2, p. 25102, 2001.
  • [13] L. A. Adamic and E. Adar, “Friends and neighbors on the web,” Soc. Networks, vol. 25, no. 3, pp. 211–230, 2003.
  • [14] L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, 1953.
  • [15] A. Papadimitriou, P. Symeonidis, and Y. Manolopoulos, “Fast and accurate link prediction in social networking systems,” J. Syst. Softw., vol. 85, no. 9, pp. 2119–2132, 2012.
  • [16] R. N. Lichtenwalter, J. T. Lussier, and N. V Chawla, “New perspectives and methods in link prediction,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 243–252, 2010.
  • [17] H. A. Deylami and M. Asadpour, “Link prediction in social networks using hierarchical community detection,” in Information and Knowledge Technology (IKT), 7th Conference on, pp. 1–5, 2015.
  • [18] J. Pei, X. Liu, P. M. Pardalos, W. Fan, S. Yang, and L. Wang, “Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain,” Int. J. Adv. Manuf. Technol., vol. 70, no. 1–4, pp. 335–348, 2014.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 1
بهار و تابستان
بهار 1398