基于手机上网记录数据的个体相遇预测

doi:10.11959/j.issn.1000-0801.2017249

摘要/Abstract

摘要：

随着反映个体位置信息的数据大量涌现，人类移动行为的研究引起了业界学者的广泛关注。针对个体相遇预测问题，使用用户手机终端上网产生的会话数据进行分析。首先基于用户相遇关系进行复杂网络建模，然后分析了网络拓扑结构特征，同时引入了用户移动性特征和上网行为特征，构造基于随机森林的预测模型，进行个体相遇预测。实验结果表明，相比于传统的网络拓扑结构特征，通过引入用户移动性特征和上网行为特征，能够显著地提升预测性能。

关键词: 相遇预测, 移动互联网, 复杂网络, 随机森林

Abstract:

Studies on human movement behavior have drawn much attention with the availability of unprecedented amount of records with high accuracy involving individuals’ trajectories.The encounter prediction problem based on the session data generated by users’ mobile terminal was studied when users accessed the internet for data usage.Firstly,the network based on the encounter relations between users was constructed.Secondly,the network topology features were analyzed and user mobility characteristics and user internet behavior characteristics were introduced.Finally,the prediction model based on random forest was applied.The experimental results show that compared with the traditional network topology features,the prediction performance can be significantly improved by introducing the user mobility characteristics and user internet behavior characteristics.

Key words: encounter prediction, mobile internet, complex network, random forest

中图分类号:

TP393

李倩,江昊,杨锦涛. 基于手机上网记录数据的个体相遇预测[J]. 电信科学, 2017, 33(10): 115-123.

Qian LI,Hao JIANG,Jintao YANG. Individual encounter prediction based on mobile internet record data[J]. Telecommunications Science, 2017, 33(10): 115-123.

图/表 11

表1

网络结构特征"

网络结构特征	计算式	基本思想
共同邻居CN指标	$C N (u, v) = \| Γ (u) \cap Γ (v) \|$	若u和v的共同邻居数量越多，则两者有连边的可能性越大
Salton指标	$S a l t o n (u, v) = \frac{\| Γ (u) \cap Γ (v) \|}{\sqrt{k (u) \times k (v)}}$	在CN的基础上，考虑了两个节点度的乘积对相似性的作用
Jaccard指标	$J a c c a r d (u, v) = \frac{\| Γ (u) \cap Γ (v) \|}{\| Γ (u) \cup Γ (v) \|}$	在u或v的邻居节点集里，随机选择一个节点，它是u和v的共同邻居的概率
Sorenson指标	$S o r e n s o n (u, v) = \frac{2 \| Γ (u) \cap Γ (v) \|}{k (u) + k (v)}$	从CN指标发展而来的，它加入考虑了u和v的度之和对相似性的影响
大度节点有利指标HPI	$H P I (u, v) = \frac{\| Γ (u) \cap Γ (v) \|}{min {k (u), k (v)}}$	HPI指标的分母为两个节点度中较小的值
大度节点不利指标HDI	$H D I (u, v) = \frac{\| Γ (u) \cap Γ (v) \|}{max {k (u), k (v)}}$	选取两个节点度中的较大值作为分母，用来抑制大度节点对相似性的影响
LHN-I指标	$L H N - I (u, v) = \frac{\| Γ (u) \cap Γ (v) \|}{k (u) \times k (v)}$	若 u 和 v 拥有共同邻居数越多，两者之间的相似性就越高，同时纳入考虑了节点度乘积
优先链接指标PA	$P A (u, v) = k (u) \times k (v)$	只考虑两个节点的度，节点 u 和 v 之间有连边的可能性与两个节点度的乘积成正比
Adamic-Adar指标	$A A (u, v) = \sum_{z \in Γ (u) \cap Γ (v)} \frac{1}{\lg k (z)}$	共同邻居节点的度越小，它对相似度的作用越大，由此将度的对数取倒数
资源分配指标RA	$R A (u, v) = \sum_{z \in Γ (u) \cap Γ (v)} \frac{1}{k (z)}$	从网络资源分配的角度提出的，假设有若干资源从u传送到v，两者的共同邻居当作传送的媒介，并将资源均匀分发给邻居节点，则u和v的相似度定义为v接收的资源数

表1

图1

表2

表3

图2

图3

表4

图4

表5

图5

图6

参考文献 23

[1]	卢卫, 陆希玉 . 4G时代移动互联网的发展趋势[J]. 电信科学, 2014,30(5): 51-54.
	LU W , LU X Y . Mobile internet trends in 4G era[J]. Telecommunications Science, 2014,30(5): 51-54.
[2]	林金桐, 许晓东 . 第五代移动互联网[J]. 电信科学, 2015,31(5): 7-14.
	LIN J T , XU X D . The 5th generation of mobile internet[J]. Telecommunications Science, 2015,31(5): 7-14.
[3]	中国互联网络信息中心. 第39次中国互联网络发展状况统计报告[R]. 2017.
	China Internet Network Information Center. The 39th China statistical report on internet development[R]. 2017.
[4]	SONG C , BARABáSI A L . Limits of predictability in human mobility[J]. Science, 2010,327(5968): 1018-1021.
[5]	LU X , WETTER E , BHARTI N ,et al. Approaching the limit of predictability in human mobility[J]. Scientific Reports, 2013,3(10): 2923.
[6]	AN N T , TU M P . A Gaussian mixture model for mobile location prediction[C]// International Conference on Research,Innovation and Vision for the Future (RIVF),February 12-14,2007,Okamoto,Kobe,Japan. New Jersey:IEEE Press, 2007: 914-919.
[7]	NOULAS A , SCELLATO S , LATHIA N ,et al. Mining user mobility features for next place prediction in location-based services[C]// International Conference on Data Mining,December 10-13,2012,Brussels,Belgium. New Jersey:IEEE Press, 2012: 1038-1043.
[8]	MONREALE A , PINELLI F , TRASARTI R ,et al. Wherenext:a location predictor on trajectory pattern mining[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,June 28-July 1,2009,Paris,France. New York:ACM Press, 2009: 637-646.
[9]	苏孝强, 倪宏 . 基于概率的移动用户移动模型[J]. 微计算机信息, 2011,27(6): 1-3.
	SU X Q , NI H . Probability-based mobility model for mobile users[J]. Microcomputer Information, 2011,27(6): 1-3.
[10]	程贤亮, 徐小良 . 基于序列挖掘的用户移动位置预测[J]. 工业控制计算机, 2013,26(3): 70-72.
	CHENG X L , XU X L . Location prediction based on sequential mining[J]. Industrial Control Computer, 2013,26(3): 70-72.
[11]	刘震, 付俊辉, 赵楠 . 基于移动通信数据的用户移动轨迹预测方法[J]. 计算机应用和软件, 2013,30(2): 10-17.
	LIU Z , FU J H , ZHAO N . Users mobile track prediction method based on mobile communication data[J]. Computer Applications and Software, 2013,30(2): 10-17.
[12]	GONG Y , LI Y , JIN D ,et al. A location prediction scheme based on social correlation[C]// Vehicular Technology Conference,May 15-18,2011,Yokohama,Japan. New Jersey:IEEE Press, 2011: 1-5.
[13]	ZHANG D , ZHANG D , XIONG H ,et al. Nextcell:predicting location using social interplay from cell phone traces[J]. IEEE Transactions on Computers, 2015,64(2): 452-463.
[14]	SUN L , AXHAUSEN K W , LEE D H ,et al. Understanding metropolitan patterns of daily encounters[J]. Proceedings of the National Academy of Sciences of the United States of America, 2013,110(34): 113774-13779.
[15]	SOCIEVOLE A , DE RANGO F , MARANO S . Link prediction in human contact networks using online social ties[C]// Third International Conference on Cloud and Green Computing,September 30-October 2,2013,Karlsruhe,Germany. New Jersey:IEEE Press, 2013: 305-312.
[16]	SCHOLZ C , ATZMUELLER M , STUMME G . On the predictability of human contacts:influence factors and the strength of stronger ties[C]// International Conference on Privacy,Security,Risk ＆ Trust,September 3-5,2012,Amsterdam,Netherlands. New Jersey:IEEE Press, 2012: 312-321.
[17]	吕琳媛 . 复杂网络链路预测[J]. 电子科技大学学报, 2010,39(5): 651-660.
	LV L Y . Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010,39(5): 651-660.
[18]	GONZáLEZ M C , HIDALGO C A , BARABáSI A L . Understanding individual human mobility patterns[J]. Nature, 2008,453(7196): 779-782.
[19]	ZHOU T , LV L , ZHANG Y C . Predicting missing links via local information[J]. European Physical Journal B, 2009,71(4): 623-630.
[20]	LV L , ZHOU T . Link prediction in weighted networks:the role of weak ties[J]. Europhys Lett, 2010,89(1): 18001.
[21]	BREIMAN L . Random forests[J]. Machine Learning, 2001,45(1): 5-32.
[22]	王铮, 任华, 方燕萍 . 随机森林在运营商大数据补全中的应用[J]. 电信科学, 2016,32(12): 7-12.
	WANG Z , REN H , FANG Y P . Application of random forest in big data completion[J]. Telecommunications Science, 2016,32(12): 7-12.
[23]	LIBEN-NOWELL D , KLEINBERG J . The link-prediction problem for social networks[J]. Journal of the Association for Information Science ＆ Technology, 2007,58(7): 1019-1031.

记录数据	规模
记录数/个	42 023 038
用户数/个	1 614 291
基站数/个	10 787
数据集起止时间	2014年11月21日—12月14日

字段名	含义
Uid	加密后的用户ID
Longitude	经度
Latitude	纬度
Stime	数据流起始时间
Duration	数据流持续时间/s
Download	下行流量/MB
Upload	上行流量/MB

网络	节点数/个	边数/条	群聚系数
G_train	6 039	9 086	0.419
G_train 最大连通子图	2 368	5 269	0.533
G_test	6 233	9 399	0.423
G_test最大连通子图	2 159	4 899	0.547