علوم رایانش و فناوری اطلاعات

روش جـدیـد پیش‌بینی لینک در شبکه‌هـای اجتمـاعی مبتنـی بـر مـدل جستجوی گرانشی

نویسندگان

دانشکده فنی و مهندسی، دانشگاه شاهد، ﺗﻬﺮان، اﻳﺮان

چکیده

ما در این مقاله روش توزیعی مقیاس‌پذیر جدیدی برای پیش‌بینی دقیق لینک در شبکه‌های اجتماعی با استفاده از ویژگی‌های ساختاری آن شبکه‌ها و بدون هیچ نیازی به سابقه‌گیری ارائه می‌دهیم. این روش ضمن مدل‌سازی عامل‌گرای مساله و انتخاب انجمن‌ها، از الگوریتم جستجوی گرانشی برای تشخیص لینک‌های مناسب بین انجمن‌ها بهره می‌برد. نتایج ارزیابی آزمایش‌های تجربی نشان می‌دهد که عملکرد روش پیشنهادی در سناریوهای مجموعه داده‌ای مختلف شبکه، مقیاس‌پذیر و از دقت میانگین 69 درصد و صحت میانگین 68 درصد برخوردار است. ضمنا با داشتن ساختار توزیعی و با برخورداری از پاسخ زمانی مناسب، در صورت انتخاب بهینه عامل‌ها و تخصیص مناسب پردازنده به آن‌ها، با بهبود زمان پاسخ و افزایش قدرت مقیاس‌پذیری عامل‌ها مواجه خواهد شد.

کلیدواژه‌ها

  • [1] B. Furht, Handbook of Social Network Technologies and Applications, Springer, 2010.
  • [2] L. L. desdorff, "The Static And Dynamic Analysis of Network Data using Information Theory," Social Networks, vol. 13, pp. 301-345, 1991.
  • [3] L. Lü, and T. Zhou, "Link Prediction in Complex Networks: A Survey," Physica A: Statistical Mechanics and Its Applications, vol. 390, no. 6, pp. 1150–1170, 2011.
  • [4] D. Liben-Nowell, and J. Kleinberg, "The Link-prediction Problem for Social Networks," Journal of the American Society for Information Science and Technology, vol. 58, no.7, pp. 1019–1031, 2007.
  • [5] D. Yin, L. Hong, and B. D. Davison, "Structural Link Analysis and Prediction in Microblogs," Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pp. 1163-1168, 2011.
  • [6] D. J. Hand, “Measuring Classifier Performance: a Coherent Alternative to the Area Under the ROC Curve,” Machine Learning, vol. 77, pp. 103–123, 2009.
  • [7] M. A. Ahmad, Z. Borbora, J. Srivastava, and N. Contractor, "Link Prediction Across Multiple Social Networks," IEEE International Conference on Data Mining Workshops (ICDMW), pp. 911–918, 2010.
  • [8] A. Socievole, F. De Rango, and S. Marano, "Link Prediction in Human Contact Networks Using Online Social Ties," 3rd International Conference on Cloud and Green Computing (CGC), pp. 305–312, 2013.
  • [9] Z. Jiawei, K. Xiangnan, and S. Yu. Philip, "Predicting Social Links for New Users across Aligned Heterogeneous Social Networks," Proc. 13th IEEE International Conference on Data Mining (ICDM "13), 2013.
  • [10] H. Yu, and et. al., "High-Quality Binary Protein Interaction Map of the Yeast Interactome Network," Science, vol. 322, pp. 104–110, 2008.
  • [11] M. P. H. Stumpf, and et. al., "Estimating the Size of the Human Interactome," Proc. Natl. Acad. Sci.U.S.A., vol. 105, pp. 6959–6964, 2008.
  • [12] L. A. N. Amaral, "A Truer Measure of our Ignorance," Proc. Natl. Acad. Sci. U.S.A. vol. 105, pp. 6795-6796, 2008.
  • [13] J. L. Schafer, and J. W. Graham, "Missing Data: Our View of the State of the Art," Psychological Methods, vol. 7, pp. 147-177, 2002.
  • [14] G. Kossinets, "Effects of Missing Data in Social Networks," Social Networks, vol. 28, no. 3, pp. 247–268, 2006.
  • [15] M. Fire, and et. al., "Link Prediction in Social Networks Using Computationally Efficient Topological Features, Privacy, Security, Risk and Trust," IEEE Third International Conference on Social Computing (SOCIALCOM), pp. 73 –80, 2011.
  • [16] J. Hopcroft, T. Lou, and J. Tang, "Who Will Follow You Back?: reciprocal relationship prediction," Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pp. 1137–1146, 2011.
  • [17] S. Fortunato, "Community Detection in Graph," Physics Reports, vol. 486, pp. 75-174, 2010.
  • [18] X. Feng, J. Zhao, and K. Xu, "Link Prediction in Complex Networks: A Clustering Perspective," Springer Berlin/Heidelberg, vol. 85, no. 1, pp. 1-9, 2012.
  • [19] S. Soundarajan, J. "Hopcroft, Using Community Information to Improve the Precision of Link Prediction Methods," Proceedings of the 21st International Conference Companion on World Wide Web, ser. WWW’12 ompanion, pp. 607-608, 2012.
  • [20] J. Valverde-Rebaza, and A. Lopes, "Link Prediction in Complex Networks Based on Cluster Information," XXI Brazilian Symposium on Artificial Intelligence, ser. SBIA, pp. 92-101, 2012.
  • [21] Y. Dhote, and N. Mishra, "Survey And Analysis of Temporal Link Prediction in Online Social Networks," Advances in Computing, Communications and Informatics, pp. 1178 – 1183, 2013.
  • [22] D. Liben-Nowell, and J. Kleinberg, "The Linkprediction Problem for Social Networks," Journal of the American Society for Information Science and Technology, vol. 58, no. 7, pp. 1019–1031, 2007.
  • [23] L. Getoor, L., and C. P. Diehl, "Link Mining: A Survey," ACM SIGKDD Explorations Newsletter, vol. 7, no. 2, pp. 3–12, 2005.
  • [24] J. L. Gross, and J. Yellen, Handbook of Graph Theory, CRC, 1999.
  • [25] M. Fire, and et. al., "Link Prediction in Social Networks Using Computationally Efficient Topological Features, Security, Risk and Trust (PASSAT)," IEEE 3th International Conference on Social Computing (SocialCom), pp. 73–80, 2011.
  • [26] B. Bollobás, Random Graphs, Cambridge University press, 2001. [27] P. Erdős, and A. Rényi, "On the Evolution of Random Graphs," Publication of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 5, pp. 17–61, 1960.
  • [28] D. Watts, and S. Strogatz, "The Small World Problem," Collective Dynamics of Small-World Networks, vol. 393, pp. 440–442, 1998.
  • [29] B. Bollobás, Modern Graph Theory, Springer Verlag, 1998.
  • [30] M. Girvan, and M. E. J. Newman, "Community Structure in Social and Biological Networks," Proc. National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
  • [31] S. Tsugawa, and H. Ohsaki, "Effectiveness of Link Prediction for Face-to-Face Behavioral Networks," PLoS ONE, vol. 8, no. 12, 2013.
  • [32] A. L. Barabâsi, and et. al., "Evolution of the Social Network of Scientific Collaborations," Physica A: Statistical Mechanics and Its Applications, vol. 311, no. 3, pp. 590–614, 2002.
  • [33] M. E. J. Newman, "Clustering and Preferential Attachment in Growing Networks," Physical Review, vol. 64, no. 2, 2001.
  • [34] T. Murata, and S. Moriyasu, "Link Prediction of Social Networks Based on Weighted Proximity Measures," IEEE/WIC/ACM International Conference On Web Intelligence, pp. 85–88, 2007.
  • [35] G. Salton, and M. J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill Book Co., 1983.
  • [36] L. A. Adamic, and E. Adar, "Friends and Neighbors on the Web," Social Networks, vol. 25, no. 3, pp. 211–230, 2003.
  • [37] T. Sørensen, "A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species and Its Application to Analyses of the Vegetation on Danish Commons," Biol. Skr., vol. 5, pp. 1–34, 1948.
  • [38] E. Ravasz, and et. al., "Hierarchical Organization of Modularity in Metabolic Networks," Science, vol. 297, no. 5586, pp. 1551–1555, 2002.
  • [39] E. A. Leicht, P. Holme, and M. E. J. Newman, "Vertex Similarity in Networks," Physical Review, vol. 73, no. 2, pp. 026120, 2006.
  • [40] T. Zhou, L. Lü, and Y. C. Zhang, "Predicting Missing Links via Local Information," The European Physical Journal B-Condensed Matter and Complex Systems, vol. 71, no. 4, pp. 623–630, 2009.
  • [41] L. Katz, "A New Status Index Derived from Sociometric Analysis," Psychometrika, vol. 18, no. 1, pp. 39–43, 1953.
  • [42] P. Y. Chebotarev, and E. Shamis, "The Matrix-forest Theorem and Measuring Relations in Small Social Groups," Autom. Remote Control, vol. 61, pp. 1424–1450, 2001.
  • [43] R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla, "New Perspectives and Methods in Link Prediction," Proc. 16thACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 243–252, 2010.
  • [44] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi,"GSA: A Gravitational Search Algorithm," Information Sciences, vol. 179, no. 13, pp. 2232-2248, 2009.
  • [45] N. M. Sabri, M. Puteh, and M. R. Mahmood, "A Review of Gravitational Search Algorithm," Int. J. Advance. Soft Comput. Appl, vol. 5, no. 3, 2013.
  • [46] R. J. Stuart, P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2003.
  • [47] B. Brewington, and et. al., "Mobile agents for distributed information retrieval, Intelligent Information Agents," Springer-Verlag, pp. 355-395, 1999.
  • [48] E. Matthew, and G. M. Jardins, "Social Networks and Multi-agent Organizational Performance," American Association for Artificial Intelligence, pp. 32-37, 2004.
  • [49] S. Sucheta, "Using Community Information to Improve the Precision of Link Prediction Methods," 21st international conference companion on World Wide Web, pp. 607-608, 2012.
  • [50] A. H. Mohammad, Link Prediction In Social Networks, Indiana university, Social Network Data Analytics, pp. 243-275, 2011.
  • [51] E. Sherkat, M. Rahgozar, and M. Asadpour, "Ant Colony Approach to Link Prediction in Social Networks," JCSE, vol. 12, no. 1, pp. 1-9, 2014.
  • [52] N. K. Yazdani, "A Gravitational Search Algorithm for Multimodal Optimization," Elsevier, vol. 32, pp. 176-183, 2012.
  • [53] P. Jun, and et. al., "Application of an Effective Modified Gravitational Search Algorithm for the Coordinated Scheduling Problem in a Two-Stage Supply Chain," Springer, vol. 70, pp. 335-348, 2014.
  • [54] D. Mohammad, and H. Nezamabadi-pour, "Channel Assignment in Multi-Radio Wireless Mesh Networks using an Improved Gravitational Search Algorithm," Journal of Network and Computer Applications, vol. 38, pp. 163-171, 2014.
  • [55] T. Niknam, F. Bavafa, and M. Jabbari, "A Novel SelfAdaptive Learning Charged System Search Algorithm for Unit Commitment Problem," Journal of Intelligent and Fuzzy Systems, vol. 26, no. 1, pp. 439-449, 2014.
علوم رایانش و فناوری اطلاعات
دوره 13، شماره 1
بهار و تابستان
اردیبهشت 1394