logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 11: 110104(2017) https://doi.org/10.1007/s11432-017-9243-7

Integrating a weighted-average method into the random walk framework to generate individual friend recommendations

More info
  • ReceivedAug 15, 2017
  • AcceptedSep 8, 2017
  • PublishedOct 13, 2017

Abstract

Friend recommendation is a fundamental service in both social networks and practical applications, and is influenced by user behaviors such as interactions, interests, and activities. In this study, we first conduct in-depth investigations on factors that affect recommendation results. Next, we design Friend+, a hybrid multi-individual recommendation model that integrates a weighted average method (WAM) into the random walk (RW) framework by seamlessly employing social ties, behavior context, and personal information. In Friend+, the first plus signifies recommending a new friend through network features, while the second plus stands for using node features. To verify our method, we conduct experiments on three social datasets crawled from the Sinamicroblog system (Weibo). Experimental results show that the proposed method significantly outperforms six baseline methods in terms of recall, precision, F1-measure, and MAP. As a final step, we describe a case study that demonstrates the scalability and universality of our method. Through discussion, we reach a meaningful conclusion: although common interests are more important than user activities in making recommendations, user interactions may be the most important factor in finding the most appropriate potential friends.


Acknowledgment

This work was supported by National High Technology Research and Development Program of China (863 Program) (Grant No. 2015AA124102), Hebei Natural Science Foundation of China (Grant No. F2015203280), Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing (Grant No. 214125), National Natural Science Foundation of China (Grant No. 61303130), Graduate Innovation Funded Program of Yanshan University (Grant No. 2017XJSS028), and Innovation Zone Project Program for Science and Technology of China's National Defense (Grand No. 2017-0001-863015-0009).


References

[1] Doina A D, Simone S. Using context to get novel recommendation in internet message streams. In: Proceedings of the 24th International Conference on World Wide Web. New York: ACM, 2015. 783--786. Google Scholar

[2] Cai Y, Leung H, Li Q. Typicality-based collaborative filtering recommendation. IEEE Trans Knowl Data Eng, 2014, 26: 766-779 CrossRef Google Scholar

[3] Erheng Z, Nathan L, Yue S, et al. Building discriminative user profiles for large-scale content recommendation. łinebreak In: Proceedings of the the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2015. 2277--2286. Google Scholar

[4] Yang Z, Tang J, Zhang J, et al. Topic-level random walk through probabilistic model. In: Proceedings of Asia-Pacific Web Conference and Web-Age Information Management. Berlin: Springer-Verlag, 2009. 162--173. Google Scholar

[5] Wang C, Tang J, Sun J, et al. Dynamic social influence analysis through time-dependent factor graphs. In: Proceedings of the 2011 International Conference on Social Networks Analysis and Mining. New York: ACM, 2011. 239--246. Google Scholar

[6] Gong J B, Gao X X, Song Y Q, et al. Individual friends recomme dation based on random walk with restart in social networks. In: Proceedings of Chinese National Conference on Social Media Processing. Berlin: Springer-Verlag, 2016. 123--133. Google Scholar

[7] Oh H, Kim J, Kim S, et al. A probability-based trust prediction model using trust-message passing. In: Proceedings of the 22nd International Conference on World Wide Web. New York: ACM, 2013. 161--162. Google Scholar

[8] Wang P, Xu B W, Wu Y R, et al. Link prediction in social networks: the state-of-the-art. Sci China Inf Sci, 2017, 58: 011101. Google Scholar

[9] Paul S, Boutsidis C, Magdon-Ismail M, et al. Random projections for linear support vector machines. ACM Trans Knowl Discov Data, 2014, 8: 1--25. Google Scholar

[10] Chen W L, Chen Y X, Mao Y, et al. Density-based logistic regression. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2013. 140--148. Google Scholar

[11] Gong J B, Wang L L, Sun S T. iBole: A Hybrid Multi-Layer Architecture for Doctor Recommendation in Medical Social Networks. J Comput Sci Technol, 2015, 30: 1073-1081 CrossRef Google Scholar

[12] Tran V, Michael G. A spatial LDA model for discovering regional communities. In: Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York: ACM, 2013. 162--168. Google Scholar

[13] Hakan B, Pinar K. Context-aware friend recommendation for location based social networks using random walk. In: Proceedings of the 25th International Conference on World Wide Web. New York: ACM, 2016. 531--536. Google Scholar

[14] Yao L, Wang L, Pan L. Link Prediction Based on Common-Neighbors for Dynamic Social Network. Procedia Comp Sci, 2016, 83: 82-89 CrossRef Google Scholar

[15] Bagci H, Karagoz P. Context-aware location recommendation by using a random walk-based approach. Knowl Inf Syst, 2016, 47: 241-260 CrossRef Google Scholar

[16] Page L, Brin S, Motwani R, et al. The Pagerank Citation Ranking: Bringing Order to the Web. Technical Report 66. 1999. Google Scholar

[17] Li R-H, Yu J X, Huang X, et al. Random-walk domination in large graphs. In: Proceedings of IEEE 30th International Conference on Data Engineering, Chicago, 2014. 736--747. Google Scholar

[18] Chen H, Jin H, Cui X. Hybrid followee recommendation in microblogging systems. Sci China Inf Sci, 2017, 60: 012102 CrossRef Google Scholar

[19] Tang J, Zhang J. A discriminative approach to topic-based citation recommendation. In: Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin: Springer-Verlag, 2009. 572--579. Google Scholar

[20] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information. Eur Phys J B, 2009, 71: 623-630 CrossRef ADS arXiv Google Scholar

[21] Zhang C Y, Liang H W, Wang K. Trip recommendation meets real-world constraints: POI availability, diversity, and traveling time uncertainty. ACM Trans Inf Syst, 2016, 35: 1--28. Google Scholar

[22] Sheng Y L, Jin R M. Learning personal social latent factor model for social recommendation. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012. 1303--1311. Google Scholar

[23] Bisio F, Meda C, Zunino R, et al. Real-time monitoring of Twitter traffic by using semantic networks. In: Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York: ACM, 2013. 966--969. Google Scholar

[24] Yang X W, Harald S, Liu Y. Circle-based recommendation in online social networks. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012. 1267--1275. Google Scholar

[25] Liu Q, Li Z G, Lui J C, et al. PowerWalk: scalable personalized pagerank via random walks with vertex-centric decomposition. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2016. 195--204. Google Scholar

[26] Cheng H, Zhou Y, Yu J X. Clustering large attributed graphs: a balance between structural and attribute similarities. ACM Trans Knowl Discov Data, 2011, 5: 12. Google Scholar

[27] Dong Y X, Tang J, Wu S, et al. Link prediction and recommendation across heterogeneous social networks. In: Proceedings of IEEE 12th International Conference on Data Mining. Washington: IEEE Computer Society, 2012. 181--190. Google Scholar

[28] Wu S-H, Chien H-H, Lin K-H, et al. Learning the consistent behavior of common users for target node prediction across social networks. In: Proceedings of the 31st International Conference on Machine Learning, Beijing, 2014. 32: 298--306. Google Scholar

[29] Benedikt L, Katja H, Jürgen Z. Blended recommending: integrating interactive information filtering and algorithmic recommender techniques. In: Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems. New York: ACM, 2015. 975--984. Google Scholar

[30] Chen W, Hsu W, Mong L. Modeling user's receptiveness over time for recommendation. In: Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2013. 373--382. Google Scholar

[31] Wang Z Y, Zhou Y, Tang J, et al. The prediction of venture capital co-investment based on structural balance theory. IEEE Trans Knowl Data Eng, 2016, 28: 1568--1569. Google Scholar

[32] Tang J, Jin R M, Zhang J. A topic modeling approach and its integration into the random walk framework for academic search. In: Proceedings of IEEE International Conference on Data Mining. New York: ACM, 2008. 1055--1060. Google Scholar

[33] Ye J H, Cheng H, Zhu Z, et al. Predicting positive and negative links in signed social networks by transfer learning. In: Proceedings of the 22nd International Conference on World Wide Web. New York: ACM, 2013. 1477--1488. Google Scholar

[34] Huang J, Huangfu X, Sun H. Backward Path Growth for Efficient Mobile Sequential Recommendation. IEEE Trans Knowl Data Eng, 2015, 27: 46-60 CrossRef Google Scholar

[35] Song D J, Meyer D A, Tao D C. Efficient latent link recommendation in signed networks. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2015. 1105--1114. Google Scholar

  • Figure 1

    (Color online) Architecture of Friend+.

  • Figure 2

    Results for user behavior statistics.

  • Figure 3

    Analysis results for DS1, DS2, and DS3. (a) Results of IN analysis; (b) results of IA analysis; (c) results of ID analysis.

  • Figure 4

    Trend of $\alpha$ for $u_{1}$, $u_{2}$, and $u_{3}$.

  • Figure 5

    Trends of MAP, Recall, and F1-Measure with changes in weight $a\_{\rm weight}$ in (a) DS1, (b) DS2, and (c) DS3.

  • Figure 6

    Values of Macro-average F1-Measure on DS1, DS2, and DS3.

  • Figure 7

    (Color online) Screenshots and descriptions of Xunweiyou whose Chinese meaning is “Looking for Weibo friends".

  • Figure 8

    (Color online) Results of Xunweiyouapplication.

  •   

    Algorithm 1 Random-walk-with-restart algorithm

    $\tilde{W}\Leftarrow $ The normalized matrix;

    $r_{0}\Leftarrow $ the initial vector;

    ${\rm iterator} = 0.000001$;

    M$ \Leftarrow $ the state transition matrix;

    Initialize $r_{\left ( k \right )}^{\left ( 0 \right )}=\left ( r_{\left ( 1 \right )}^{\left ( 0 \right )},r_{\left ( 2 \right )}^{\left ( 0 \right )},\ldots, r_{\left ( n \right )}^{\left ( 0 \right )} \right )$ , $m$=1;

    for $i=1,2,\ldots, N$

    $\phi _{i}^{(m-1)}=\frac{r_{i}^{(m-1)}}{ \| r_{i}^{(m-1)} \|}_{1}$;

    $A^{(m-1)}\Leftarrow$ the aggregation matrix;

    $(A^{(m-1)})_{ij}=\phi_{i}^{m-1}M_{ij}e_{j}$;

    $\zeta ^{(m-1))}\Leftarrow $ characteristic vector;

    $\zeta ^{(m-1))}=\zeta^{(m-1)}A^{(m-1)}+c_{1\times N}$ (constant vector);

    if $r^{(m)}_{(k)}-r^{(m-1)}_{(k)}$)$\leq$ iterator then

    $r^{(m)}_{(k)}=(\zeta ^{(m-1)}_{1}\phi^{{(m)}}_{1}, \zeta ^{(m-1)}_{2}\phi^{{(m)}}_{2}, \times , \zeta ^{(m-1)}_{N}\phi^{{(m)}}_{N})$;

    else

    $m \Leftarrow m+1$;

    end if

    end for

    $ r \Leftarrow $Stationary distribution probability;

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1