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;

  • Table 1   Definition of variables
    Symbol Description
    U Set of target users
    C Set of candidate users
    E Set of relationships among users
    $P_{i,j}$ Probability of moving from point i to point j
    P State transition probability matrix
    $\bar{P}_{i,j}^{k}$ Column vector of matrix P
    $\bar{R}_{u,\_}^{*}$ Row vector of matrix P
    $\tilde{R}$ Reflects the target user's rating of a user
    $\tilde{W}$ Adjacency matrix
    $e_{j}$ An initial vector
    $R_{t}$ Probability distribution vector after t iterations
    $w(i,j)$ User i's interactive value to user j
    ${c(i,j)}$ Number of mutual friends between user i and user j
    $t_{i}$ Number of days ago that an interaction took place
    ${m(t)}$ Interaction time between i and j during the last five days
    $\phi(t)$ The time attenuation function
    $k_{j}$ Degree of recommended user j
  • Table 2   Experimental setup
    Dataset No. Real size Random selection Alias Characteristic
    Dataset1 300000 160000 DS1 Dense network
    Dataset2 165001 160000 DS2 High activities
    Dataset3 212064 160000 DS3 High common interests
  • Table 3   Performance of Friend+
    Dataset MAP Recall F1-Measure
    DS1 87.4 0.8327 0.8747
    DS2 71.5 0.8186 0.5087
    DS3 80.6 0.8121 0.7263
  • Table 4   Comparative evaluation results
    Dataset Method P@5 P@10 P@15 Recall MAP F1-Measure
    Friend+ 80.0 51.4 27.1 0.9327 87.4 0.8747
    RW 77.1 47.1 26.4 0.5938 85.5 0.5759
    LDAS 65.7 44.3 25.0 0.5129 73.4 0.2597
    DS1 RWCFR 39.1 32.6 25.4 0.2156 51.3 0.2146
    CN 79.6 51.2 27.8 0.9315 87.2 0.8663
    Jaccard 74.1 53.5 21.8 0.7624 79.2 0.7412
    AA 76.1 48.7 19.6 0.7845 74.6 0.6687
    Friend+ 71.4 44.3 24.3 0.9186 71.5 0.5087
    RW 65.0 40.0 22.5 0.8014 65.5 0.6736
    LDAS 51.4 38.6 22.9 0.6324 66.0 0.5222
    DS2 RWCFR 41.3 38.7 26.2 0.1835 60.8 0.1864
    CN 57.2 40.6 23.1 0.8124 68.1 0.5123
    Jaccard 62.3 43.5 19.8 0.7528 71.2 0.4658
    AA 54.8 37.9 15.4 0.7233 65.4 0.5315
    Friend+ 81.4 50.0 26.4 0.8721 80.6 0.7263
    RW 51.4 42.9 21.4 0.6036 63.1 0.6993
    LDAS 47.5 36.3 21.3 0.7623 54.1 0.3696
    DS3 RWCFR 28.3 20.4 15.8 0.2016 41.9 0.2423
    CN 54.6 46.2 22.7 0.7884 67.6 0.6543
    Jaccard 49.8 47.9 19.6 0.7249 69.5 0.6915
    AA 58.4 46.5 15.7 0.7461 64.5 0.5748
  • Table 5   Performance comparison based on MAE and RMSE using real datasets
    Method MAE RMSE
    Friend+ 0.21768$\pm$ (0.00248) 0.20743$\pm$ (0.00267)
    RW 0.25381 0.26865
    LDAS 0.24543$\pm$ (0.00372) 0.31542$\pm$ (0.00198)
    RWCFR 0.26452$\pm$ (0.00312) 0.35315$\pm$ (0.00287)
    CN 0.23152$\pm$ (0.00265) 0.25523$\pm$ (0.00325)
    Jaccard 0.24316$\pm$ (0.00242) 0.26847$\pm$ (0.00147)
    AA 0.25982$\pm$ (0.00226) 0.28648$\pm$ (0.00184)

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

京ICP备18024590号-1