计算机科学 ›› 2014, Vol. 41 ›› Issue (6): 43-47.doi: 10.11896/j.issn.1002-137X.2014.06.009

• 网络与通信 • 上一篇    下一篇

基于网络拓扑和地理特征融合的朋友关系预测模型

罗惠,郭斌,於志文,王柱,封云   

  1. 西北工业大学计算机学院 西安710072;西北工业大学计算机学院 西安710072;西北工业大学计算机学院 西安710072;西北工业大学计算机学院 西安710072;西北工业大学计算机学院 西安710072
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家重点基础研究发展计划(973计划)(2012CB316400),国家自然科学基金(61222209,3),教育部“新世纪优秀人才支持计划”(NCET-12-0466),教育部高等学校博士学科点专项科研基金(博导类)(20126102110043),陕西省自然科学基础研究计划项目(2012JQ8028),西北工业大学基础研究基金(JC20110267)资助

Friendship Prediction Based on Fusion of Network Topology and Geographical Features

LUO Hui,GUO Bin,YU Zhi-wen,WANG Zhu and FENG Yun   

  • Online:2018-11-14 Published:2018-11-14

摘要: 朋友关系预测已成为基于位置的社交网络(LBSN)的主要研究方向之一。提出一种基于网络拓扑特征和地理融合的面向LBSN的朋友关系预测方法。首先,利用信息增益评估不同特征对朋友关系的影响,最终选取3种重要特征:用户社交拓扑、用户签到地点类型和用户签到地点。然后,提出基于这3种特征融合的朋友关系预测方法,分别采用随机森林、支持向量机和朴素贝叶斯3种分类算法建模实现朋友关系推理。最后通过Foursquare和街旁的实际签到数据验证了特征选取的有效性和朋友关系预测的准确性。

关键词: 基于位置的社交网络,朋友关系预测,信息增益,特征融合 中图法分类号TP39文献标识码A

Abstract: Friendship prediction has become one of the major studies of location based social network (LBSN).This paper proposed an approach for predicting friendship,which fuses the topology network and geographical features of LBSN.We first adopted the information gain to measure the contribution of different features to human friendship,and chose three key features:user social topology,the category of the location where people check in,and check in points.We then presented the friendship prediction method based on the fusion of the selected features.Three different classification models,including Random Forests,Support Vector Machine (SVM),and Naive Bayes,were selected to predict human friendship.Experimental results on the real collected data from Foursquare and JiePang verify the efficacy of the selected features and the accuracy of friendship prediction.

Key words: Location-based social network,Friendship prediction,Information gain,Feature fusion

[1] Leskovec J,Lang K J,Dasgupta A,et al.Statistical properties of community structure in large social and information networks[C]∥Proceedings of the 17th international conference on World Wide Web.2008:695-704
[2] Mislove A,Marcon M,Gummadi K P,et al.Measurement andanalysis of online social networks[C]∥Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement.2007:29-42
[3] Wakita K,Tsurumi T.Finding community structure in Mega-scale social networks[C]∥Proceedings of the 16th International Conference on World Wide Web.2007:1275-1276
[4] Kwak H,Choi Y,Eom Y H,et al.Mining communities in networks:A solution for consistency and its evaluation[C]∥Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference.2009:301-314
[5] 窦炳琳,李澍淞,张世永.基于结构的社会网络分析[J].计算机学报,2012(4):741-753
[6] 谈嵘,顾君忠,杨静,等.移动社交网络中的隐私设计[J].软件学报,2010:298-309
[7] Cho E,Myers S A,Leskovec J.Friendship and mobility:Usermovement in location-based social networks[C]∥KDD 2011.2011:1082-1090
[8] Schwartz M F,Wood D M.Discovering shared interests using graph analysis[J].Communications of the ACM,1993,36(8):78-89
[9] Grob R,Kuhn M,Wattenhofer R,et al.Cluestr:Mobile socialnetworking for enhanced group communication[C]∥Procee-dings of the ACM 2009International Conference on Supporting Group Work.2009:81-90
[10] Sadilek A,Kautz H,Bigham J P.Finding Your Friends and Fol-lowing Them to Where You Are[C]∥Fifth ACM International Conference on Web Search and Data Mining.2012:723-732
[11] Gregory S.An algorithm to find overlapping community structure in networks[C]∥PKDD 2007.2007: 91-102
[12] Ozseyhan C,Badur B,Darcan O N.An Association Rule-Based Recommendation Engine for an Online Dating Site[C]∥Communications of the IBIMA.2012
[13] Li N,Chen G L.Multi-Layered Friendship Modeling for Location-Based Mobile Social Networks[C]∥Int’l.Conf.Mobile and Ubiquitous Systems:Computing,Networking and Services.Toronto,Canada,July 2009:1-10
[14] Cranshaw J,Toch E,Hong J,et al.Bridging the gap between physical location and online social networks[C]∥Ubicomp.2010:119-128
[15] 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661
[16] Liben-Nowell D,Kleinberg J.The link prediction problem forsocial networks[C]∥Journal of the American Society for Information Science and Technology.2007:1019-1031
[17] Zhou T,Lv L Y,Zhang Y.Predicting missing links via local information[J].the European Physical Journal B,2009(10):623-630
[18] Leskovec J,Huttenlocher D,Kleinberg J.Predicting positive and negative links in online social networks[C]∥Proceedings of the 19th International Conference on World Wide Web.2010:641-650
[19] Mitchell T M.Machine Learning[M].The Mc-Graw-Hill Companies,Inc.,1997
[20] Shannon C E.A Mathematical Theory of Communication[J].ACM SIGMOBILE Mobile Computing and Communications Review,2001,5(1):3-55
[21] .https://developer.foursquare.com/docs
[22] .https://dev.twitter.com/docs
[23] .http://dev.jiepang.com
[24] Leskovec J,Backstrom L,Kumar R,et al.Microscopic evolution of social networks[C]∥Proceeding of the ACM KDD.August 2008:462-470
[25] Breiman L.Random forests[M]∥Machine Learning.2001:5-32
[26] Cortes C,Vapnik V.Support-vector network[M]∥MachineLearning.1995:273-297
[27] Zhang H.The Optimality of Naive Bayes[C]∥Proceedings ofthe Seventeenth International Florida Artificial Intelligence Research Society Conference.AAAI Press,2004
[28] Holmes G,Donkin A,Witten I H.Weka:A machine learning workbench[C]∥Proceedings of the 1994Second Australian and New Iealand Conference on Intelligent Information System.Brisbane,QID,1994:357-361
[29] Chang C C,Lin C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011(4)
[30] 翟云,杨炳儒,曲武.不平衡类数据挖掘研究综述[J].计算机科学,2010,7(10):27-31
[31] Weiss G,Provost F.Learning when training data are costly:The effect of class distribution on tree induction[J].Journal of Artificial Intelligence Research,2003,19:315-354

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!