Abstract Recommending friends is an important mechanism for social networks to enhance their vitality and attractions to users. The huge user base as well as the sparse user relationships give great challenges to propose friends on social networks. Random walk is a classic strategy for recommendations, which provides a feasible solution for the above challenges. However, most of the existing recommendation methods based on random walk are only weighing the forward search, which ignore the significance of reverse social relationships. In this paper, we proposed a method to recommend friends by integrating reverse search into random walk. First, we introduced the FP-Growth algorithm to construct both web graphs of social networks and their corresponding transition probability matrix. Second, we defined the reverse search strategy to include the reverse social influences and to collaborate with random walk for recommending friends. The proposed model both optimized the transition probability matrix and improved the search mode to provide better recommendation performance. Experimental results on real datasets showed that the proposed method performs better than the naive random walk method which considered the forward search mode only.

References

[1] Bagci H. and Karagoz P., “Context-Aware Friend Recommendation for Location Based Social Networks Using Random Walk,” in Proceedings of the 25th International Conference Companion on World Wide Web, Montreal, pp. 531-536, 2016.

[2] Brin S. and Page L., “Anatomy of a Large-Scale Hypertextual Web Search Engine,” in Proceedings of the 7th International World Wide Web Conference, Brisbane, pp.107-117, 1998.

[3] Broder A., Kumar R., Maghoul., Raghavan P., Rajagopalan S., Stata R., Tomkins A., and Wiener J., “Graph Structure in the Web,” Computer Networks, vol. 33, no. 1-6, pp. 309- 320, 2000.

[4] Chin A., “Finding Cohesive Subgroups and Relevant Members in the Nokia Friend View Mobile Social Network,” in Proceedings of International Conference on Computational Science and Engineering, Vancouver, pp. 278- 283, 2009.

[5] Faisal M., Daud A., and Akram A., “Expert Ranking using Reputation and Answer Quality of Co-Existing Users,” The International Arab Journal of Information Technology, vol. 14, no. 2, pp. 118-126, 2017.

[6] Gyongi Z., Garcia-Molina H., and Pedersen J., “Combating Link Spam with Trustrank,” in Proceedings of 30th International Conference on Very Large Databases, Toronto, pp. 576-587, 2004.

[7] Han J., Pei J., Yin Y., and Mao R., “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery, vol. 8, no. 1, pp. 53-87, 2004.

[8] Huang W., Kataria S., Caragea C., Mitra P., and Giles L., “Recommending Citations: Translating Papers into References,” in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, Hawaii, pp. 1910-1914, 2012.

[9] Kandhway K. and Kuri J., “Using Node Centrality and Optimal Control to Maximize Information Diffusion in Social Networks,” IEEE Transactions on Systems, Man, and Cybernetics System, vol. 47, no. 7, pp. 1099- 1110, 2017.

[10] Konstas I., Stathopoulos V., and Jose J., “On Social Networks and Collaborative Recommendation,” in Proceedings of the 32nd International ACM SIGIR Conference on Incorporating Reverse Search for Friend Recommendation with Random Walk 297 Research and Development in Information Retrieval, Boston, pp. 195-202, 2009.

[11] Le T. and Zhang D., “DBLPminer: A Tool for Exploring Bibliographic Data,” in Proceedings of the 16th IEEE International Conference on Information Reuse and Integration, San Francisco, pp. 435-442, 2015.

[12] Li H., He K., Wang J., and Peng Z., “A Friends Recommendation Algorithm Based on Formal Concept Analysis and Random Walk in Social Network,” Journal of Sichuan University (Engineering Science Edition), vol. 47, no. 6, pp. 131-138, 2015.

[13] Likavec S., Osborne F., and Cena F., “Property- based Semantic Similarity and Relatedness for Improving Recommendation Accuracy and Diversity,” International Journal on Semantic Web and Information Systems, vol. 11, no. 4, pp. 1-40, 2015.

[14] Liu J., Zhu Y., and Zhou T., “Improving Personalized Link Prediction by Hybrid Diffusion,” Physica A: Statistical Mechanics and its Applications, vol. 447, pp. 199-207, 2016.

[15] Lo S. and Lin C., “WMR-A Graph-Based Algorithm for Friend Recommendation,” in Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, Hongkong, pp. 121-128, 2006.

[16] Massa P. and Bhattacharjee B., “Using Trust in Recommender System: An Experimental Analysis,” in Proceedings of the 2nd International Conference on Trust Management, Oxford, pp. 221-235, 2004.

[17] Mourchid F. and Koutbi M., “LBRW: A Learning based Random Walk for Recommender Systems,” International Journal of Information Systems and Social Change, vol. 6, no. 3, pp. 15-34, 2015.

[18] Nie D., Fu Y., Zhou J., Liu Z., Zhang Z., and Liu C., “A Personalized Recommendation Algorithm Via Biased Random Walk,” in Proceedings of the 11th International Joint Conference on Computer Science and Software Engineering, Chon Buri, pp. 292-296, 2014.

[19] Page L., Brin S., Motwani R., and Winograd T., “The PageRank Citation Ranking: Bringing order to the Web,” Technical Report, Stanford InfoLab, 1999.

[20] Shen D., Sun J., Yang Q., and Chen Z., “Latent Friend Mining from Blog Data,” in Proceedings of the 6th International Conference on Data Mining, Hongkong, pp. 552-561, 2006.

[21] Simpson M., Srinivasan V., and Thomo A., “Clearing Contamination in Large Networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 6, pp. 1435-1448, 2016.

[22] Wang P., Zhao J., Lui J., Towsley D., and Guan X., “Unbiased Characterization of Node Pairs over Large Graphs,” ACM Transactions on Knowledge Discovery from Data, vol. 9, no. 3, pp. 22, 2015.

[23] Wang Y., Li J., Liu Q., and Ren Y., “Prediction of Purchase Behaviors Across Heterogeneous Social Networks,” The Journal of Supercomputing, vol. 71, no. 9, pp. 3320-3336, 2015.

[24] Wang Z., Tan Y., and Zhang M., “Graph-based Recommendation on Social Networks,” in Proceedings of the 12th International Asia- Pacific Web Conference, Busan, pp. 116-122, 2010.

[25] Xia F., Chen Z., Wang W., and Li J., “MVCWalker: Random Walk-Based Most Valuable Collaborators Recommendation Exploiting Academic Factors,” IEEE Transactions on Emerging Topics in Computing, vol. 2, no. 3, pp. 364-375, 2015.

[26] Xu L. and Gulliver T., “Performance Analysis for M2M Video Transmission Cooperative Networks Using Transmit Antenna Selection,” Multimedia Tools and Applications, vol. 76, no. 22, pp. 23891-23902, 2017.

[27] Xu L., Wang J., Zhang H., and Gulliver T., “Performance Analysis of IAF Relaying Mobile D2D Cooperative Networks,” Journal of the Franklin Institute, vol. 354, no. 2, pp. 902-916, 2017.

[28] Yan M., Sang J., Mei T., and Xu C., “Friend Transfer: Cold-start Friend Recommendation with Cross-Platform Transfer Learning of Social Knowledge,” in Proceedings of the International Conference on Multimedia and Expo, San Jose, pp. 1-6, 2013.

[29] Ying J.J.C., Kuo W., Tseng V., and Lu E., “Mining User Check-In Behavior with a Random Walk for Urban Point-of-Interest Recommendations,” ACM Transactions on Intelligent Systems and Technology, vol. 5, no. 3, pp. 40, 2014.

[30] Zheng Y., Chen Y., Xie X., and Ma W., “GeoLife2.0: A Location-Based Social Networking Service,” in Proceedings of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware, Taipei, pp. 357-358, 2009. 298 The International Arab Journal of Information Technology, Vol. 17, No. 3, May 2020 Qing Yang is an associate professor at Guilin University of Electronic Technology, China. Her research interests include intelligent information processing, social network analysis, and large-scale data processing optimization. Haiyang Wang is a M.S., born in 1981. His research interests includes personalized recommendation and applications. Mengyang Bian is a M.S, born in 1992. His research interests include data mining and recommendation optimization. Yuming Lin is an associate professor at Guilin University of Electronic Technology, China. He obtained his Ph.D from East China Normal University, China in 2013. His research interests include sentiment analysis, Web data mining and knowledge graph. Jingwei Zhang is an associate professor at Guilin University of Electronic Technology, China. He obtained his Ph.D from East China Normal University, China in 2012. His research interests include massive data management, distributed computing framework and big data analytics for emerging applications.