ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. DOI: 10.13203/j.whugis20190180
Citation: ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. DOI: 10.13203/j.whugis20190180

A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data

Funds: 

The National Key Research and Development Program of China 2016YFB0502300

the National Natural Science Foundation of China 41471336

More Information
  • Author Bio:

    ZHANG Zheng, PhD candidate, specializes in geographic information visualization and geographic information service, spatial data mining, pan spatial information system. E-mail: giser_zzy@163.com

  • Corresponding author:

    JIANG Nan, PhD, professor. E-mail: 13653802609@163.com

  • Received Date: April 28, 2020
  • Published Date: April 04, 2022
  •   Objectives  With the continuous popularity of social network products and applications, there are more and more ways to obtain location check-in data. The judgement of friendship based on check-in data is one of the most popular research directions of location based social networks (LBSN). However, social network data is often difficult to obtain in advance. In order to solve the problem of friend relationship judgement based on location check-in data only, this paper proposed a friend relationship judgment method based on an improved gravity model.
      Methods  Firstly, the information gain was used to calculate the influence of different feature parameters on friendship judgment, and two feature parameters, residence distance and spatial temporal co-occurrence zone, were selected as consequences. Secondly, the gravity model was improved according to the selected feature parameters, and the model's value range was mapped from 0 to 1 by using Sigmoid function, to facilitate the judgement of friend relationship and calibration of model parameters. Finally, the parameters of the model were calibrated by logistic regression, and the prediction of friend relationship was realized on the Gowalla and Brightkite datasets.
      Results  Multiple experiments were conducted. Part of check-in data were selected to test the validity of feature parameters. The AUC (area under the curve) value of the spatial temporal co-occurrence zone parameter on the Gowalla dataset was 0.710, and the AUC value in the Brightkite dataset was 0.760. The residence distance parameter on the Gowalla dataset got an AUC value of 0.634, and 0.647 on the Brightkite dataset. By setting different degrees of balance, the improved gravity model was used to conduct friend relationship prediction experiments. As the data imbalance increased, the accuracy increased, while the recall rate and F-value decreased. However, the model still had a high accuracy and recall rate even with an imbalance of 1∶150. The accuracy rate was 0.846 1 and the recall rate was 0.788 5 when the Gowalla dataset as the training dataset while the test was performed on the Brightkite dataset. The accuracy rate was 0.859 1, and the recall rate was 0.853 7 when the Brightkite dataset as the training dataset while the test was performed on the Gowalla dataset. The contrast experiment with the friend relationship probability model shows that the recall rate of the contrast model dropped from 0.75 to almost 0 with the increase of the threshold. The experimental results above show that the selected feature parameters and the proposed model have a good predictive effect on the judgment of friend relationship.
      Conclusions  The proposed method can realize friend relationship judgment under the condition of only relying on location check-in data. The model has better stability between datasets from different sources, and the overall performance of this method is significantly higher than that of the comparison method.
  • [1]
    王家耀. 时空大数据时代的地图学[J]. 测绘学报, 2017, 46(10): 1226-1237 doi: 10.11947/j.AGCS.2017.20170308

    Wang Jiayao. Cartography in the Age of SpatioTemporal Big Data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1226-1237 doi: 10.11947/j.AGCS.2017.20170308
    [2]
    龚健雅, 耿晶, 吴华意. 地理空间知识服务概论[J]. 武汉大学学报·信息科学版, 2014, 39(8): 883-890 doi: 10.13203/j.whugis20140119

    Gong Jianya, Geng Jing, Wu Huayi. Geospatial Knowledge Service: A Review[J]. Geomatics and Information Science of Wuhan University, 2014, 39(8): 883-890 doi: 10.13203/j.whugis20140119
    [3]
    李德仁. 从测绘学到地球空间信息智能服务科学[J]. 测绘学报, 2017, 46(10): 1207-1212 doi: 10.11947/j.AGCS.2017.20170263

    Li Deren. From Geomatics to Geospatial Intelligent Service Science[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1207-1212 doi: 10.11947/j.AGCS.2017.20170263
    [4]
    陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5): 665-672 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201405002.htm

    Lu Feng, Liu Kang, Chen Jie. Research on Human Mobility in Big Data Era[J]. Journal of Geo-Information Science, 2014, 16(5): 665-672 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201405002.htm
    [5]
    罗惠, 郭斌, 於志文, 等. 基于网络拓扑和地理特征融合的朋友关系预测模型[J]. 计算机科学, 2014, 41(6): 43-47 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406009.htm

    Luo Hui, Guo Bin, Yu Zhiwen, et al. Friendship Prediction Based on Fusion of Network Topology and Geographical Features[J]. Computer Science, 2014, 41(6): 43-47 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406009.htm
    [6]
    Leskovec J, Lang K J, Dasgupta A, et al. Statistical Properties of Community Structure in Large Social and Information Networks[C]// The 17th International Conference on World Wide Web, Beijing, China, 2008
    [7]
    Wakita K, Tsurumi T. Finding Community Structure in Mega-Scale Social Networks: Extended Abstract[C]//The 16th International Conference on World Wide Web, Banff, Alberta, Canada, 2007
    [8]
    Kwak H, Choi Y, Eom Y H, et al. Mining Communities in Networks: A Solution for Consistency and Its Evaluation[C]//The 9th ACM SIGCOMM Conference on Internet Measurement Conference, Chicago, Illinois, USA, 2009
    [9]
    Ye M, Yin P F, Lee W C. Location Recommendation for Location-Based Social Networks[C]//The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, California, USA, 2010
    [10]
    Cho E, Myers S A, Leskovec J. Friendship and Mobility: User Movement in Location-Based Social Networks[C]//The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 2011
    [11]
    Eagle N, Pentland A, Lazer D. Inferring Friendship Network Structure by Using Mobile Phone Data[J]. PNAS, 2009, 106(36): 15274-15278 doi: 10.1073/pnas.0900282106
    [12]
    Li R H, Liu J Q, Yu J X, et al. Co-occurrence Prediction in a Large Location-Based Social Network[J]. Frontiers of Computer Science, 2013, 7(2): 185-194 doi: 10.1007/s11704-013-3902-8
    [13]
    Crandall D J, Backstrom L, Cosley D, et al. Inferring Social Ties from Geographic Coincidences[J]. PNAS, 2010, 107(52): 22436-22441 doi: 10.1073/pnas.1006155107
    [14]
    Shannon C E. A Mathematical Theory of Communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423 doi: 10.1002/j.1538-7305.1948.tb01338.x
    [15]
    Mitchell T M. Machine Learning[M]. New York: The McGraw-Hill Companies, 1997
    [16]
    Scellato S, Noulas A, Lambiotte R, et al. SocioSpatial Properties of Online Location-Based Social Networks[C]//The 5th International Conference on Weblogs and Social Media, Barcelona, Catalonia, Spain, 2011
    [17]
    Liben-Nowell D, Novak J, Kumar R, et al. Geographic Routing in Social Networks[J]. PNAS, 2005, 102(33): 11623-11628 doi: 10.1073/pnas.0503018102
    [18]
    Backstrom L, Sun E, Marlow C. Find me if You Can: Improving Geographical Prediction with Social and Spatial Proximity[C]//The 19th International Conference on World Wide Web, Raleigh, North Carolina, USA, 2010
    [19]
    Lambiotte R, Blondel V D, De Kerchove C, et al. Geographical Dispersal of Mobile Communication Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2008, 387(21): 5317-5325 doi: 10.1016/j.physa.2008.05.014
    [20]
    Hu Y Q, Wang Y G, Li D Q, et al. Possible Origin of Efficient Navigation in Small Worlds[J]. Physical Review Letters, 2011, 106(10): 108701 doi: 10.1103/PhysRevLett.106.108701
    [21]
    马春来, 单洪, 马涛, 等. 一种基于随机森林的LBS用户社会关系判断方法[J]. 计算机科学, 2016, 43(12): 218-222 doi: 10.11896/j.issn.1002-137X.2016.12.040

    Ma Chunlai, Shan Hong, Ma Tao, et al. Random Forests Based Method for Inferring Social Ties of LBS Users[J]. Computer Science, 2016, 43(12): 218-222 doi: 10.11896/j.issn.1002-137X.2016.12.040
    [22]
    Cranshaw J, Toch E, Hong J, et al. Bridging the Gap Between Physical Location and Online Social Networks[C]//The 12th ACM International Conference on Ubiquitous Computing, New York, USA, 2010
    [23]
    常晓猛, 乐阳, 李清泉, 等. 利用位置的虚拟社交网络地理骨干网提取[J]. 武汉大学学报·信息科学版, 2014, 39(6): 706-710 doi: 10.13203/j.whugis20140105

    Chang Xiaomeng, Yue Yang, Li Qingquan, et al. Extracting the Geographic Backbone of LocationBased Social Network[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 706-710 doi: 10.13203/j.whugis20140105
    [24]
    李雯静, 李少宁, 龙毅, 等. 利用重力模型进行GIS点群选取[J]. 武汉大学学报·信息科学版, 2013, 38(8): 945-949 http://ch.whu.edu.cn/article/id/2716

    Li Wenjing, Li Shaoning, Long Yi, et al. Point Cluster Selection in GIS Using Gravity Model[J]. Geomatics and Information Science of Wuhan University, 2013, 38(8): 945-949 http://ch.whu.edu.cn/article/id/2716
    [25]
    徐睿, 梁循, 齐金山, 等. 极限学习机前沿进展与趋势[J]. 计算机学报, 2019, 42(7): 1640-1670 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201907012.htm

    Xu Rui, Liang Xun, Qi Jinshan, et al. Advances and Trends in Extreme Learning Machine[J]. Chinese Journal of Computers, 2019, 42(7): 1640-1670 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201907012.htm
    [26]
    付仲良, 杨元维, 高贤君, 等. 利用多元Logistic回归进行道路网匹配[J]. 武汉大学学报·信息科学版, 2016, 41(2): 171-177 doi: 10.13203/j.whugis20150112

    Fu Zhongliang, Yang Yuanwei, Gao Xianjun, et al. Road Networks Matching Using Multiple Logistic Regression[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 171-177 doi: 10.13203/j.whugis20150112
  • Related Articles

    [1]ZHONG Heping, TANG Jinsong, MA Mengbo, WU Haoran. Complex Image Registration Algorithm and Its Optimization for Interferometric Synthetic Aperture Sonar in Shared Memory Environment[J]. Geomatics and Information Science of Wuhan University, 2019, 44(8): 1169-1173. DOI: 10.13203/j.whugis20180051
    [2]WANG Hongyan, GUAN Xuefeng, WU Huayi. A Collaborative Parallel Spatial Interpolation Algorithmon Oriented Towards the Heterogeneous CPU/GPU System[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1688-1695. DOI: 10.13203/j.whugis20150361
    [3]ZHONG Heping, ZHANG Sen, TIAN Zhen, TANG Jinsong. A Fast Quality-guided Phase Unwrapping Algorithmin Heterogeneous Environment[J]. Geomatics and Information Science of Wuhan University, 2015, 40(6): 756-760. DOI: 10.13203/j.whugis20130518
    [4]ZHU Jianfeng, CHEN Min. Supply Chain Knowledge Collaboration Based on Ontologyin Semantic Heterogeneous Environment[J]. Geomatics and Information Science of Wuhan University, 2014, 39(1): 123-126.
    [5]CHEN Jing, XIANG Longgang, ZHU Xinyan. Integrated Management of Distributed Heterogeneous Raster Spatial Data[J]. Geomatics and Information Science of Wuhan University, 2011, 36(9): 1094-1096.
    [6]FU Xiaojing, ZHANG Guoyin, MA Chunguang. An Identity-based Authenticated Key Agreement Sheme for Heterogeneous Sensor Networks[J]. Geomatics and Information Science of Wuhan University, 2010, 35(5): 582-586.
    [7]MA Chunguang, CHU Zhenjiang, WANG Jiuru, WANG Huiqiang. A Framework for Key Management in Heterogeneous Sensor Networks[J]. Geomatics and Information Science of Wuhan University, 2010, 35(5): 509-511.
    [8]SHA Zongyao, LI Xiaolei. Algorithm of Mining Spatial Association Data Under Spatially Heterogeneous Environment[J]. Geomatics and Information Science of Wuhan University, 2009, 34(12): 1480-1484.
    [9]WU Mengquan, SONG Xiaodong, CUI Weihong. On Ontology-Driven Heterogeneous Geographic Data Set Integration[J]. Geomatics and Information Science of Wuhan University, 2007, 32(10): 915-918.
    [10]Li Yong. Research of Process Real-time Communication Based on Heterogeneous Networks[J]. Geomatics and Information Science of Wuhan University, 1999, 24(4): 362-366.

Catalog

    Article views (587) PDF downloads (41) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return