本节书摘来自华章出版社《移动数据挖掘》一 书中的第1章，第1.2节，作者连德富 张富峥 王英子 袁晶 谢幸，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1.2 概念与定义
前面提到移动数据是移动轨迹的集合，而移动轨迹是移动记录的有序序列。移动记录是〈时间，位置〉对，可以记录诸如用GPS设备等连续采样的数据，也可以记录诸如移动社交网络中签到等事件类型的数据。对于GPS设备采集的连续位置信息存在停留点，用户需要在附近停留一定的时间。因而，停留点是带有位置、到达时间及停留时间信息的点。对于非停留点位置，用户可能只是路过所以并不感兴趣，因而连续的GPS位置数据通常会被处理成停留点的序列。移动社交网络是移动位置服务和社交媒体的结合体，是一种与朋友分享地点访问信息的社交平台，可用于帮助人们更加便利、快捷地探索周边环境和配套设施。其中分享的地点访问信息就是移动社交网络中的签到。在签到时，一般是从兴趣点数据库中选择所访问的兴趣点，加上简短的话语分享感受。如果有更深刻的感触，还可以分享更加丰富的攻略信息甚至有趣的照片等。兴趣点是带有名字、语义信息的地点，比如餐馆、酒店、电影院等。诸如大众点评网和Yelp等本地服务平台纷纷兴起，大众点评网可以对地点进行打分和点评，来说明兴趣地点的好和差。点评信息和攻略信息有些类似，只是攻略信息没有打分。用户的移动历史信息除了可以表示为一个地点序列以外，还可以被处理为一个用户地点访问的二部图，在二部图中，图的顶点被分为两个不相交的子集，一个为用户集，一个为地点集。二部图的边只存在于两个子集之间，表示用户访问了某个地点，边的权重可以表示为访问次数。而子集内的顶点之间，即用户之间和地点之间，则无边相连。假设用户的集合为={u1,…，uM}，地点的集合为={l1，…，lN}，cu,i则表示用户集中的某一个用户u对地点集中的某一个地点i的访问次数，对应于二部图中的边权。众所周知，图可以用矩阵来表示，二部图同样也不例外。假设用矩阵C表示这个二部图，每一行对应每一个用户，每一列表示每一个地点，那么矩阵中的每一个元素cu,i便对应了二部图中的边权。随着城市的发展，可供人们访问的诸如餐馆、酒店、商场等地点是越来越多了。由于每个用户只会访问很少一部分地点，因此这个矩阵便是稀疏的。移动社交网络中的社交网络是由顶点和边组成的图结构，顶点是用户，边表示用户之间的关系，比如是否为朋友关系，或者亲密程度等。如果边表示亲密程度，那么图就是加权网络。如果关系是有方向的，比如微博中的关注关系，那么图就称为有向图。如果用户之间是双向关系，比如Facebook中的关系，那么图就为无向图。由于一个用户的朋友数有限，因此社交关系图就是稀疏的。图可以用矩阵来表示，社交关系图就可以用稀疏方阵来表示。对于双向关系的无向图，对应的稀疏矩阵便是对称的；而对于单向关系的有向图，对应的稀疏矩阵基本上就是非对称的。对于社交网络中的任意节点，其一度朋友是指该节点的直接邻居（朋友），二度朋友则是指该节点的朋友的朋友。随着度的增加，与该节点关联的节点越来越多。针对在线社交网络的研究，可以发现在线社交网络基本上都是小世界网络，满足“小世界理论”。“小世界理论”是指人们和任何一个陌生人之间所间隔的人不会超过6个。因而，达到一定的度之后，每个节点所关联的节点可能就会覆盖整个网络［24］。
