随着移动通信网络的快速发展和移动终端定位技术的广泛应用，基于位置的服务（location based services, LBS）^[1]影响着人类生产生活的方方面面. 通过LBS应用，移动终端用户构成了庞大的社会网络，产生了大量的位置数据. 群体是指2个及以上的个体由于特定的内在因素（兴趣、目标、利益等）自发或者有组织地聚集在一起形成的集合^[2]. 群体发现是社会网络研究的重要内容^[3]，有助于进一步分析群体用户的行为模式与交互规律，实施舆情引导控制和异常群体监控^[4]. 移动终端用户群体发现是指通过分析用户在使用LBS应用时产生的位置数据，挖掘具有相同内在因素的用户集合.

复杂网络的社团挖掘方法^[5]主要依据用户关系拓扑图进行聚类，忽略了用户的其他属性，难以发现属性特征相似的群体^[2]. 移动终端用户具有较强的位置属性，复杂网络的社团挖掘方法不适用于移动终端用户的群体发现. 在现有的针对位置社交网络（location-based social network, LBSN）的社团挖掘方法中，Hung等^[6]和Boston等^[7]根据位置数据提取用户的移动行为模式，将行为模式相似的用户聚类为一个社团/群体. 但是现实生活中行为模式相似的用户不一定具有社会关系，例如在相同路线经过的上班族、在同一个商圈居住的居民等，所以Boston等^[7]所述方法发现的群体存在不准确性. Jayadevan等^[8]根据位置共现信息估计用户社会关系强度，得到社会关系拓扑图，使用社团挖掘方法发现移动用户群体，但是该方法将共现信息转化为社会关系，弱化了用户的位置属性. 假定场景：给定3个用户（1、2、3）和3个位置（Ⅰ、Ⅱ、Ⅲ）. 用户1频繁出现在Ⅰ和Ⅱ，用户2频繁出现在Ⅰ和Ⅲ，用户3频繁出现在Ⅱ和Ⅲ. 每2个用户通过共现位置建立了社会关系. 从社会关系的角度分析，3个用户可以属于同一个群体；但是从位置属性的角度看，三者没有共同的共现位置，属于不同的群体. Lim等^[9]指出时空叠加关系发现的群体以位置为中心，具有高度的位置相似性. Brown等^[10]根据网络结构图和用户签到的位置信息研究同一网络中线上和线下用户群体的差异性，指出线下用户群体具有位置聚集性. Brown等^[11]和Liu等^[12]利用用户社会关系和签到地点双重信息发现位置社团，根据签到信息计算用户的社会关系强度，将社会关系强度作为社会关系拓扑图中边的权值，删除权值小于阈值的边，用传统社团挖掘算法发现位置社团. 但是Brown等^[11]和Liu等^[12]将位置信息与社会关系相融合，根据社会关系拓扑图发现的群体同样可能存在位置属性不强的问题；同时移动终端上既有社交类应用，也有非社交类应用，在非社交类应用中用户间交流互动较少，无法直接提取用户的社会关系，因此Brown等^[11]和Liu等^[12]的方法在移动终端用户的群体发现中的普适性不强.

综上所述，位置数据不能直接表达用户的社会关系，复杂网络群体发现方法不能直接用于移动用户的群体发现；同时移动用户群体具有社会关系和位置聚集双重属性，现有以复杂网络和位置社交网络为对象的社团挖掘方法难以同时兼顾社会关系和位置属性，所发现群体具有不准确性。为此，以位置信息为对象，提取用户社会关系和位置属性，将前者作为用户关系拓扑图，后者作为用户标签，并通过标签传播算法将两者结合起来，提出一种有效的移动终端用户群体发现方法。

1 基本思路

移动终端用户群体发现的目的是从数量众多的用户中筛选出具有稠密社会关系和相似位置属性的用户群体。一方面，移动用户通常在多个地点签到，具有多个位置标签；另一方面，现实生活中每个用户拥有多种类型的社会关系，可能属于多个群体。同一群体成员的位置标签既有共性，也有差异。用户在某个群体中的标签差异性可能与用户所属的其他群体有关。现有方法不能很好处理上述位置属性多标签与社会关系多群体的问题。本研究提出基于反向标签传播算法（reverse label propagation algorithm, Reverse-LPA）的移动终端用户重叠群体发现方法。根据签到位置信息推断移动终端用户社会关系拓扑图，提取用户的时空共现区作为标签，通过标签初始化得到标签拓扑图。在标签拓扑图上进行反向标签传播，对于节点的每个标签，依据其在邻居节点中的状态，标记其状态为“保留”或“消除”；反复迭代，根据标签的状态将符合条件标签删除，得到稳定状态的用户标签拓扑图；最终在标签拓扑图上根据节点连接关系和标签分布情况提取用户群体。Reverse-LPA的结构如图1所示。

2 位置数据预处理 2.1 社会关系推断

移动终端用户社会关系推断是指根据用户签到位置数据的时间和空间关系判断用户社会关系强度. 目前常用的方法有共现频次法^[13]、轨迹相似法^[14]和特征提取法^[15-17]等. 选取马春来等^[17]提出的方法，根据用户签到位置的总体属性、用户活跃性、位置多样性和位置特殊性等4类特征，使用改进的随机森林算法判断用户是否存在社会关系，在用户社会关系判断的基础上构建用户关系拓扑图.

2.2 时空共现区提取

定义位置数据为 $d = \left\{ {u,p,\left\langle {{\rm{lo}},{\rm{la}}} \right\rangle } \right\}$ ，其中 $u$ 为用户， $p$ 为签到时间， $\left\langle {{\rm{lo}},{\rm{la}}} \right\rangle $ 为经纬度. 时空共现（spatio-temporal co-occurrence）^{[13, 15]}是指用户在一定的时间区间和空间区域相遇的事件，发生时空共现事件的时空区域称为时空共现区. 设 $z_{\rm{t}}^{\rho - \tau }$ 为以时间点 $\rho $ 为起点、时长为 $\tau $ 的时间段， $z_{\rm{s}}^{o - \lambda }$ 为以 $o$ 为圆心、半径为 $\lambda $ 的空间区域， $z_{\rm{c}}^{} = (z_{\rm{t}}^{\rho - \tau },z_{\rm{s}}^{o{\rm{ - }}\lambda })$ 为不同用户在时间段 $z_{\rm{t}}^{\rho - \tau }$ 和空间区域 $z_{\rm{s}}^{o{\rm{ - }}\lambda }$ 内相遇所对应的时空共现区. 使用基于密度峰值的快速聚类算法（clustering by fast search and find of density peaks，CFSFDP）^[18]对位置数据进行聚类，每一个聚类簇为1个时空共现区.

3 反向标签传播算法

标签传播算法（label propagation algorithm, LPA）是一种复杂度较低的社团发现方法^[19]，包括标签初始化、标签传播和传播停止条件3个部分. 将用户时空共现区作为位置属性标签，结合标签初始化与用户社会关系拓扑图，有助于提高移动终端用户群体发现结果的准确性. 因为移动终端用户通常会在多个位置签到，对应多个时空共现区，所以标签初始化后的社会关系拓扑图中的每个用户节点拥有多个标签. 现有LPA大多为1个用户节点初始化1个标签，无法处理多标签的情况，因此本研究对现有的LPA进行改进，提出一种反向标签传播算法.

3.1 标签初始化

设移动终端用户社会关系拓扑图为 $G = \left( {V,\;E} \right)$ ，其中 $V = \left\{ {{v_1},{v_2}, \cdots ,{v_n}} \right\}$ 为用户节点集合，E = $ \left\{ {{e_1},{e_2}, \cdots ,{e_m}} \right\}$ 为节点边集合. 时空共现区集合为 ${Z_{\rm{c}}} = \left\{ {{z_{{{\rm{c}}_1}}},{z_{{{\rm{c}}_2}}}, \cdots ,{z_{{{\rm{c}}_h}}}} \right\}$ ，用户节点 ${v_n}$ 签到的时空共现区为 $z_{\rm{c}}^{{v_n}} = \left\{ {z_{{{\rm{c}}_{\rm{1}}}}^{{v_n}}, \cdots ,z_{{{\rm{c}}_i}}^{{v_n}}, \cdots z_{{{\rm{c}}_{{q_n}}}}^{{v_n}}\left| {z_{{{\rm{c}}_i}}^{{v_n}} \in {Z_{\rm{c}}}} \right.} \right\}$ 并且 $z_{\rm{c}}^{{v_1}} \cup z_{\rm{c}}^{{v_2}} \cup \cdots $ $ \cup z_{\rm{c}}^{{v_n}} = {Z_{\rm{c}}}$ . 标签初始化后得到的标签拓扑图 $ {G_{\rm{c}}} = $ $\left( {V,E,z_{\rm{c}}^V} \right)$ ， $z_{\rm{c}}^V = \left\{ {z_{\rm{c}}^{{v_1}},z_{\rm{c}}^{{v_2}}, \cdots ,z_{\rm{c}}^{{v_n}}} \right\}$ .

3.2 反向标签传播

现有LPA的标签传播是依据邻居节点标签的分布情况，采用一定的策略将节点标签置换为某一邻居节点标签. 节点的标签是算法随机分配的，不表示实际含义，置换标签不改变节点属性. 但是 ${G_{\rm{c}}}$ 中的标签表示节点签到的时空共现区，置换标签意味着变更用户到访的地点集合，与事实不符，因此现有 LPA 不适用于处理标签拓扑图G_c，需要改进标签传播方法.

数据集（见4.1节）上的统计结果显示每个用户的平均签到数量分布范围为 ${10^1} \sim {10^2}$ ，标签拓扑图 ${G_{\rm{c}}}$ 中大部分节点拥有多个标签. 移动终端用户群体的位置聚集性要求群体中每个用户签到地点存在交集. 一般来说，群体中所有节点标签的交集为群体中任意2个节点标签交集的子集. 如果节点 ${v_n}$ 属于任意群体 ${V^{\rm{g}}}$ ， $V_{ - {v_n}}^{\rm{g}} = V_{}^{\rm{g}}\backslash {v_n}$ ， ${v_n}$ 与 $V_{ - {v_n}}^{\rm{g}}$ 中所有节点标签的交集为 $z_{\rm{c}}^{{ \cap _0}}\left( {\left| {z_{\rm{c}}^{{ \cap _0}}} \right| \geqslant 1} \right)$ ，与 $V_{ - {v_n}}^g$ 中单个节点标签的交集分别为 $z_{\rm{c}}^{{ \cap _1}},z_{\rm{c}}^{{ \cap _2}}, \cdots ,z_{\rm{c}}^{{ \cap _r}}, \cdots $ ，那么 $z_{\rm{c}}^{{ \cap _0}} \in z_{\rm{c}}^{{ \cap _r}} \in z_{\rm{c}}^{{v_n}}$ . 令 $z_{\rm{c}}^{{ \cap _{r - 0}}} = z_{\rm{c}}^{{ \cap _r}} - z_{\rm{c}}^{{ \cap _0}}$ ， $z_{\rm{c}}^{{ \cap _{ - 0}}} = z_{\rm{c}}^{{v_n}} - z_{\rm{c}}^{{ \cap _0}}$ ，称 $z_{\rm{c}}^{{ \cap _0}}$ 为 ${v_n}$ 关于群体 ${V^{\rm{g}}}$ 的主标签集合， $z_{\rm{c}}^{{ \cap _{1 - 0}}},z_{\rm{c}}^{{ \cap _{2 - 0}}}, \cdots ,z_{\rm{c}}^{{ \cap _{r - 0}}}, \cdots $ 为 ${v_n}$ 关于 $V_{ - {v_n}}^{\rm{g}}$ 中节点的伴随标签集合.

主标签反映了节点与群体的关系，伴随标签仅仅反映了节点与群体中部分节点的关系，因此改进标签传播方法是根据节点 ${v_n}$ 边的连通关系，通过多次标签传播，逐步找到 ${v_n}$ 与其他节点的伴随标签，确定主标签，将与 ${v_n}$ 拥有相同主标签的节点划为一个群体. 由于伴随标签不会影响节点与群体的关系，可以在标签传播的过程中逐步消除伴随标签，保留主标签. 与现有LPA将节点标签置换为邻居节点标签的方法相反，新的标签传播方法根据邻居节点的标签有选择地消除自身的伴随标签，称为Reverse-LPA. Reverse-LPA标签传播过程的主要步骤如下.

1)　统计标签的节点集合. 统计与任意节点 ${v_n}$ 共享标签 $z_{{{\rm{c}}_i}}^{{v_n}}\left( {1 \leqslant i \leqslant {q_n}} \right)$ 的邻居节点，将满足条件的邻居节点组成集合 $S(z_{{{\rm{c}}_i}}^{{v_n}})\left( {1 \leqslant i \leqslant {q_n}} \right)$ . 令 $S'(z_{{{\rm{c}}_i}}^{{v_n}})$ 记录在标签传播过程中与节点 ${v_n}$ 共享标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的邻居节点集合，并初始化为 $S'(z_{{{\rm{c}}_i}}^{{v_n}}) = S(z_{{{\rm{c}}_i}}^{{v_n}})$ .

2)　标记标签状态. Reverse-LPA中位置标签有2种可标记状态：保留和消除. “保留”状态指在当前节点中标签不需要消除；“消除”状态指在当前节点中标签可以消除. 标签的“保留”和“消除”状态是不断变化的，同一标签在不同的节点或者迭代次数中的状态可能不同. 初始状态为“保留”的标签最终不一定会被保留下来，状态为“消除”的标签需要满足一定的条件才可能被消除. 标记标签状态时，初始化所有标签状态为“保留”. 将标签集合 $z_{{{\rm{c}}_{}}}^{{v_n}}$ 中元素按照邻居节点数量 $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right|$ 升序排列，如果多个标签的 $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right|$ 相同，按标签对应的时空共现区的位置熵^[17]的倒数升序排列. 当 $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right| = 0$ 时， $z_{{{\rm{c}}_i}}^{{v_n}}$ 的标签状态为“消除”；如果标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 满足 $S'(z_{{{\rm{c}}_i}}^{{v_n}}) \subseteq \bigcup\nolimits_{z_{{{\rm{c}}_j}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}} {\left( {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right)} $ 并且 $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right| \leqslant$ $ \left| {S'(z_{{{\rm{c}}_j}}^{{v_n}})} \right|\left( {z_{{{\rm{c}}_j}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}} \right)$ ，标记 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态为“消除”.

3)　传播标签状态. 每个节点向所有邻居节点传播自己的标签状态，并且接收邻居节点的标签状态. 对集合 $ S'(z_{{{\rm{c}}_i}}^{{v_n}})$ 中任意节点 $ v_{n'} $ ，若其与 $ v_n$ 的共享标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态为“消除”，更新 $S'(z_{{{\rm{c}}_i}}^{{v_n}}) = $ $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {v_{n'}}$ .

4)　检查停止条件. 如果所有节点标签满足传播停止条件，停止标签传播，否则返回步骤2.

3.3 传播停止条件

当任意标签 $ z_{{{\rm{c}}_i}}^{{v_n}}$ （ $z_{{{\rm{c}}_i}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}$ ， ${v_n} \in V$ ）的状态不再变化时，停止反向标签传播. 满足传播停止条件时，拓扑图 ${G_{\rm{c}}}$ 的标签达到稳定状态，此时每个节点关于所属群体的熵值最小的主标签状态为“保留”，其他主标签和伴随标签状态为“消除”. 在稳定状态，删除状态为“消除”的标签，保留状态为“保留”的标签，标签相同的用户属于同一个群体. 在稳定状态，单个节点可能拥有多个标签，因为移动终端用户群体建立在用户真实社会关系的基础上，每个用户同时存在家人、同事、朋友等多种社会关系^[20-21]，用户可以属于多个群体，节点可以保留多个群体的主标签. 由此可见，反向标签传播算法是符合移动终端用户群体发现需求的重叠群体发现方法.

Reverse-LPA的伪代码如下.

Reverse-LPA Algorithm

Input：Label graph ${G_{\rm{c}}} = \left( {V,E,z_{\rm{c}}^V} \right)$

Output：Group information matrix Group

1　 For each ${v_n} \in V$ calculate $S(z_{{{\rm{c}}_i}}^{{v_n}})$ , and let $S'(z_{{{\rm{c}}_i}}^{{v_n}}) \leftarrow S(z_{{{\rm{c}}_i}}^{{v_n}})$ ;

2　 Do

3　　 ${\rm{Stop}} \leftarrow {\rm{True}}$ ;

4　　 ${\rm{State}}_{z_{{{\rm{c}}_i}}^{{v_n}}}^{{v_n}} \leftarrow $ The initial state of $z_{{{\rm{c}}_i}}^{{v_n}}$ in ${v_n}$ as 1;

5　　 ${\rm{Sor}}{{\rm{t}}_{{v_n}}} \leftarrow $ Sort $z_{{{\rm{c}}_i}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}$ in ascending order by $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right|$ and the reciprocal of entropy;

6　　 For each $z_{{{\rm{c}}_i}}^{{v_n}}$ by the order stored in the ${\rm{Sor}}{{\rm{t}}_{{v_n}}}$ index

7　　　{If $\left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right| = 0$

8　　　　 ${\rm{State}}_{z_{{{\rm{c}}_i}}^{{v_n}}}^{{v_n}} \leftarrow 0$ ;

9　　　 Else If ( $S'(z_{{{\rm{c}}_i}}^{{v_n}}) \subseteq \bigcup\nolimits_{z_{{{\rm{c}}_j}}^{{v_n}} \in z_c^{{v_n}}} {\left( {S'(z_{{{\rm{c}}_j}}^{{v_n}})} \right)} {\rm and} \left| {S'(z_{{{\rm{c}}_i}}^{{v_n}})} \right| \leqslant$ $ \left| {S'(z_{{{\rm{c}}_j}}^{{v_n}})} \right|\left( {z_{{{\rm{c}}_j}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}} \right)$ )

10　　　　 ${\rm{State}}_{z_{{{\rm{c}}_i}}^{{v_n}}}^{{v_n}} \leftarrow 0$ ;}

11　Propagate label state to neighbor nodes in ${G_{\rm{c}}}$

12　 For each ${v_{n'}} \in S'(z_{{{\rm{c}}_i}}^{{v_n}})$

13　　{If ${\rm{State}}_{z_{{{\rm{c}}_i}}^{{v_m}}}^{{v_{n'}}} = 0$

14　　　{ $S'(z_{{{\rm{c}}_i}}^{{v_n}}) \leftarrow S(z_{{{\rm{c}}_j}}^{{v_n}})\backslash {v_{n'}}$ ; ${\rm{Stop}} \leftarrow {\rm{Flase}}$ ;}}

15　 While ( ${\rm{Stop}} = {\rm{Flase}}$ );

16　Update ${Z_{\rm{c}}} \leftarrow z_{\rm{c}}^{{v_1}} \cup z_{\rm{c}}^{{v_2}} \cup \cdots \cup z_{\rm{c}}^{{v_n}}$ ;

　　　 ${\rm{Group}} \leftarrow {\rm{new}}{\rm{int}} [\left| {{Z_{\rm{c}}}} \right|][\left| V \right|]$ ;

17　 For each ${z_{{{\rm{c}}_h}}} \in {Z_{\rm{c}}}$ // $h$ 为被保留的时空共现区标签索引

18　　{ $l \leftarrow 0$ ；// $l$ 为群体成员索引

19　　 For each $z_{{{\rm{c}}_i}}^{{v_n}} \in z_{\rm{c}}^{{v_n}}$

20　　　{If ${z_{{{\rm{c}}_h}}} = z_{{{\rm{c}}_i}}^{{v_n}}$

21　　　　{ ${\rm{Group}}[h][l + + ] \leftarrow n$ ; break;}}} // $n$ 为节点编号

4 Reverse-LPA可行性证明

Reverse-LPA的标签传播过程与现有的LPA差别比较大，需要证明可行性. Reverse-LPA的主要原理是在节点连接关系上经过多次传播获取标签的稳定状态，保留每个群体熵值最小的主标签. 根据Reverse-LPA的标签传播过程，可以通过证明节点标签稳定状态的存在性论证Reverse-LPA的可行性. 节点标签稳定状态的存在性可以从2个方面进行证明：伴随标签的稳定状态为“消除”；熵值最小主标签的稳定状态为“保留”，其他主标签的稳定状态为“消除”.

问题1可描述为：给定节点 ${v_n}$ 和其关于群体 ${V^{\rm{g}}}$ 的伴随标签 $z_{{{\rm{c}} _i}}^{{v_n}}$ ，在Reverse-LPA的稳定状态中 $z_{{{\rm{c}}_i}}^{{v_n}}$ 被标记为“消除”.

证明：设 $z_{{{\rm{c}}_j}}^{{v_n}}$ 为 ${v_n}$ 关于 ${V^{\rm{g}}}$ 熵值最小的主标签， ${V^{\rm{g}}}$ 中与 ${v_n}$ 共享 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的邻居节点集为 ${S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ，由主标签与伴随标签的定义可知 ${S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}}) \subset {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ . 任取 ${v_{n'}} \in {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ .

情况1：与 ${v_n}$ 、 ${v_{n'}}$ 共享 $z_{{{\rm{c}}_i}}^{{v_n}}$ 、 $z_{{{\rm{c}}_j}}^{{v_n}}$ 的邻居节点全部在群体 ${V^{\rm{{\rm g}}}}$ 内. $S(z_{{{\rm{c}}_i}}^{{v_n}}) = {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ， $S(z_{{{\rm{c}}_j}}^{{v_n}}) = {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ ，由于 ${S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}}) \subset {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ ，标记 ${v_n}$ 的标签状态时，存在标签 $z_{{{\rm{c}} _j}}^{{v_n}}$ 使得 $z_{{{\rm{c}}_i}}^{{v_n}}$ 满足 $S(z_{{{\rm{c}}_i}}^{{v_n}}) \subset S(z_{{{\rm{c}}_j}}^{{v_n}})$ 并且 $\left| {S(z_{{{\rm{c}}_i}}^{{v_n}})} \right| < \left| {S(z_{{{\rm{c}}_j}}^{{v_n}})} \right|$ ，所以 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态被标记为“消除”. 因为 $z_{{{\rm{c}}_j}}^{{v_n}}$ 的标签状态始终为“保留”，所以 $z_{{{\rm{c}}_i}}^{{v_n}}$ 在节点 ${v_n}$ 中的状态始终为“消除”. 同理可得， ${v_{n'}}$ 中的标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的最终状态为“消除”；通过标签传播，在 ${v_n}$ 及共享邻居节点中 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态始终为“消除”，即稳定状态中标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态均为“消除”.

情况2：与 ${v_n}$ 、 ${v_{n'}}$ 共享 $z_{{{\rm{c}}_i}}^{{v_n}}$ 、 $z_{{{\rm{c}}_j}}^{{v_n}}$ 的邻居节点不全部在群体 ${V^{\rm{g}}}$ 内. $S(z_{{{\rm{c}}_i}}^{{v_n}}) \supset {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ， $S(z_{{{\rm{c}}_j}}^{{v_n}}) \supset {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ ，当 ${v_n}$ 与节点集合 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 属于另一个新群体时，如果 $z_{{{\rm{c}}_i}}^{{v_n}}$ 为 ${v_n}$ 关于新群体的主标签， $z_{{{\rm{c}}_i}}^{{v_n}}$ 不需要消除；如果 $z_{{{\rm{c}}_i}}^{{v_n}}$ 为 ${v_n}$ 关于新群体的伴随标签，假设 $z_{{{\rm{c}}_i}}^{{v_n}}$ 在新群体中被消除，通过若干次标签传播 $S(z_{{{\rm{c}}_i}}^{{v_n}}) = S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash \left( {S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})} \right) = {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ，存在标签 $z_{{{\rm{c}}_j}}^{{v_n}}$ 使得 $z_{{{\rm{c}}_i}}^{{v_n}}$ 满足 $S(z_{{{\rm{c}}_i}}^{{v_n}}) \subset {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ 并且 $\left| {S(z_{{{\rm{c}}_i}}^{{v_n}})} \right| < \left| {S(z_{{{\rm{c}}_j}}^{{v_n}})} \right|$ ，所以 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态被标记为“消除”. 同理可得，在 ${v_{n'}}$ 中的标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的最终状态为“消除”. 在稳定状态，标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态为“消除”，称为“消除传播效应”；假设 $z_{{{\rm{c}}_i}}^{{v_n}}$ 在新群体中不被消除，则 $z_{{{\rm{c}}_i}}^{{v_n}}$ 在 ${v_n}$ 中也不能被消除. 根据消除传播效应，如果在 ${G_{\rm{c}}}$ 中有其他标签满足情况1，“消除”状态会在传播的过程中影响更多的标签满足“消除”条件，使得 $z_{{{\rm{c}}_i}}^{{v_n}}$ 在新群体中被“消除”的假设成立，最终稳定状态中标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态为“消除”. 当 ${v_n}$ 与节点集合 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 不属于一个群体时， $z_{{{\rm{c}}_i}}^{{v_n}}$ 为 ${v_n}$ 和 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 关于各自所属群体的伴随标签，根据上文的证明可知，在稳定状态中标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态为“消除”. 问题1得证.

问题2可描述为：给定节点 ${v_n}$ 和其关于群体 ${V^{\rm{g}}}$ 的主标签集合 $z_{\rm{c}}^{{ \cap _0}}$ ，令 $z_{{{\rm{c}}_i}}^{{v_n}} \in z_{\rm{c}}^{{ \cap _0}}$ 为熵值最小的主标签，任取 $z_{{{\rm{c}}_j}}^{{v_n}} \in z_{\rm{c}}^{{ \cap _0}}\backslash z_{{{\rm{c}}_i}}^{{v_n}}$ ，在Reverse-LPA的稳定状态中 $z_{{{\rm{c}}_i}}^{{v_n}}$ 被标记为“保留”， $z_{{{\rm{c}}_j}}^{{v_n}}$ 被标记为“消除”.

证明：设 ${V^{\rm{{\rm g}}}}$ 中与 ${v_n}$ 共享 $z_{{{\rm{c}}_i}}^{{v_n}}$ 、 $z_{{{\rm{c}}_j}}^{{v_n}}$ 的邻居节点集分别为 ${S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 、 ${S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ ，那么 $S(z_{{{\rm{c}}_i}}^{{v_n}}) \supseteq {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ， $S(z_{{{\rm{c}}_j}}^{{v_n}}) \supseteq {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ .

如果 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}}) = \phi $ ，那么 $S(z_{{{\rm{c}}_i}}^{{v_n}}) = {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ ；如果 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}}) \ne \phi $ ，由于节点集合 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 不属于群体 ${V^{\rm{{\rm g}}}}$ ， $z_{{{\rm{c}}_i}}^{{v_n}}$ 为 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 的伴随标签. 根据问题1的描述， $z_{{{\rm{c}}_i}}^{{v_n}}$ 在 $S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})$ 中的稳定状态为“消除”，通过标签状态传播得到 $S(z_{{{\rm{c}}_i}}^{{v_n}}) = $ $ S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash \left( {S(z_{{{\rm{c}}_i}}^{{v_n}})\backslash {S^{\rm g}}(z_{{{\rm{c}}_i}}^{{v_n}})} \right)$ .

同理可知，稳定状态时 $S(z_{{{\rm{c}}_j}}^{{v_n}}) = {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}})$ . 此时 $S(z_{{{\rm{c}}_i}}^{{v_n}}) = {S^{\rm g}}(z_{{{\rm{c}}_j}}^{{v_n}}) = S(z_{{{\rm{c}}_j}}^{{v_n}})$ ， $\left| {S(z_{{{\rm{c}}_i}}^{{v_n}})} \right| = \left| {S(z_{{{\rm{c}}_j}}^{{v_n}})} \right|$ ，因为 $z_{{{\rm{c}} _i}}^{{v_n}}$ 对应的时空共现区的熵值最小，所以排列在 $z_{{{\rm{c}}_j}}^{{v_n}}$ 的升序方向（按标签对应的时空共现区熵值的倒数升序排列）. 按照节点排列次序，在升序方向存在标签 $z_{{{\rm{c}}_i}}^{{v_n}}$ 使得 $z_{{{\rm{c}}_j}}^{{v_n}}$ 满足 $S(z_{{{\rm{c}}_j}}^{{v_n}}) \subseteq S(z_{{{\rm{c}}_i}}^{{v_n}})$ 并且 $\left| {S(z_{{{\rm{c}}_i}}^{{v_n}})} \right| \leqslant $ $ \left| {S(z_{{{\rm{c}}_j}}^{{v_n}})} \right|$ ， $z_{{{\rm{c}}_j}}^{{v_n}}$ 的状态被标记为“消除”. 由于在稳定状态时 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的升序方向没有标签，因此 $z_{{{\rm{c}}_i}}^{{v_n}}$ 的状态被标记为“保留”. 问题2得证.

问题1和问题2的证明结果表明，节点的稳定状态是存在的，Reverse-LPA是可行的.

5 实验及结果分析 5.1 数据集简介

基于Reverse-LPA的移动终端用户群体发现方法，Boston等^[7]和Jayadevan等^[8]提出的对比方法只需要位置信息即可完成群体发现工作，但Liu等^[12]提出的对比方法还需要用户社会关系信息，数据集需要同时具有用户签到位置和社会关系信息. 本研究选取来自社交网站Gowalla、Brightkite和Foursquare上的签到位置数据，通过实验验证Reverse-LPA的有效性. Gowalla、Brightkite数据集来源于Cho等^[22]的研究，数据内容主要包括用户ID、位置、时间和关注关系. Foursquare数据集来源于Bao等^[23]的研究，内容包括用户身份、签到事件、地点和关注关系. 由于Foursquare用户的签到频率比较稀疏，为了保证数据的可用性，选取签到事件不少于8次的用户进行实验. 为了分析Reverse-LPA群体发现的准确性，利用Foursquare数据集相对丰富的用户信息，使用问卷调查获取部分用户的真实群体信息. 根据身份信息和Foursquare网站定位用户的Facebook主页，获取用户的Email并且发送调查问卷. 问卷内容主要包括与用户有关注关系的Foursquare用户的Facebook昵称和社会关系类型选项. 根据问卷结果，将用户身份数据中家庭地址（Home City）一致并且有家人（Family）关系的用户划分为一个群体；将Facebook主页中工作地点（或单位）一致并且有同事（Colleague）关系的用户划分为一个群体. 在49 062个Foursquare用户中获取到Email账号31 049个，回收有效调查问卷648份，成功划分群体154个，涉及1 832个用户，命名为Fsqtrue数据集. 各数据集的统计信息如表1所示.

5.2 评价指标 5.2.1 标准互信息

已知群体背景信息时，使用标准互信息（normalized mutual information，NMI）评价群体发现算法的性能. NMI取值范围为[0, 1.0]，数值越大表明群体发现算法输出结果与群体真实结构越接近，算法性能越好. 给定算法输出结果为 ${G_{\rm{A}}}$ 、群体真实结构为 ${G_{\rm{T}}}$ ，定义NMI为^[24-25]

$\begin{split}{\rm{NMI}}\left( {{G_{\rm{A}}},{G_{\rm{T}}}} \right) =& 2\displaystyle\frac{{H\left( {{G_{\rm{A}}}} \right) + H\left( {{G_{\rm{T}}}} \right) - H\left( {{G_{\rm{A}}},{G_{\rm{T}}}} \right)}}{{H\left( {{G_{\rm{A}}}} \right) + H\left( {{G_{\rm{T}}}} \right)}}=\\& \displaystyle\frac{{2{\mathop{\rm MI}\nolimits} \left( {{G_{\rm{A}}},{G_{\rm{T}}}} \right)}}{{H\left( {{G_{\rm{A}}}} \right) + H\left( {{G_{\rm{T}}}} \right)}}.\end{split}$

(1)

式中： $H\left( \cdot \right)$ 为概率熵， ${\rm{MI}}\left( \cdot \right)$ 为互信息. 设 ${G_{\rm{A}}}$ 和 ${G_{\rm{T}}}$ 的混淆矩阵（confusion matrix）为 ${ \varOmega} {\rm{ = }}{\left[ {{N_{ij}}} \right]_{\left| {{G_{\rm{A}}}} \right| \times \left| {{G_{\rm{T}}}} \right|}}$ （ $\left| {{G_ \cdot }} \right|$ 为 ${G_ \cdot }$ 中群体数量）， ${N_{i_ \cdot }}$ 、 ${N_{ \cdot j}}$ 分别为矩阵第 $i$ 行、第 $j$ 列之和， $N$ 为群体节点总数，则

$\begin{array}{l}H\left( {{G_{\rm{A}}}} \right) = \displaystyle\sum\limits_{i = 1}^{\left| {{G_{\rm{A}}}} \right|} {{N_{i\cdot}} \log\; \left( {\frac{{{N_{i \cdot }}}}{N}} \right)} ,\\H\left( {{G_{\rm{T}}}} \right) = \displaystyle\sum\limits_{j = 1}^{\left| {{G_{\rm{T}}}} \right|} {{N_{\cdot_j}} \log\; \left( {\frac{{{N_{\cdot j}}}}{N}} \right)} ,\\{\rm{NMI}}\left( {{G_{\rm{A}}},{G_{\rm{T}}}} \right) = \displaystyle\sum\limits_{i = 1}^{\left| {{G_{\rm{A}}}} \right|} {\displaystyle\sum\limits_{j = 1}^{\left| {{G_{\rm{T}}}} \right|} {{N_{ij}} \log\; \left( {\frac{{{N_{ij}}N}}{{{N_{i \cdot }}{N_{\cdot_j}}}}} \right)} } .\end{array}$

(2)

5.2.2 综合评价函数

在群体背景信息未知的情况下，可以使用模块度 $Q$ ^[26]衡量非重叠群体划分效果. 为了适应重叠群体的情况，Nicosia等^[27]给出了重叠模块度函数 ${Q_{{\rm{ov}}}}$ ：

${Q_{{\rm{ov}}}}\left( {{G_{\rm{A}}}} \right) = \frac{1}{{2w}}\sum\limits_{G_{\rm{A}}^k \in G_{\rm{A}}^{}} {\sum\limits_{{v_i},{v_j} \in G_{\rm{A}}^{}} {\left( {{r_{ijk}}{w_{ij}} - {s_{ijk}}\frac{{d_i^{}d_j^{}}}{{2w}}} \right)} } . $

(3)

式中： $w$ 为 ${G_{\rm{A}}}$ 中总边数， $G_{\rm{A}}^k$ 为 ${G_{\rm{A}}}$ 中第 $k$ 个群体， ${w_{ij}}$ 为 ${G_{\rm{A}}}$ 的邻接矩阵 $W$ 中的元素， ${d_i}$ 为节点 ${v_i}$ 的度， ${r_{ijk}}$ 为“群体与”符号函数， ${s_{ijk}}$ 为“群体或”符号函数. 如果v_i、v_j同属于 $G_{\rm{A}}^k$ ，那么 ${r_{ijk}}$ 为1，否则为0；如果任一节点v_i、v_j属于 $G_{\rm{A}}^k$ ，那么 ${s_{ijk}}$ 为1，否则为0.

移动终端用户群体中不仅存在重叠现象，还具有位置属性. 如图2(a)所示，以模块度为衡量标准，节点 $\left\{ {1,2,3,4,5,6} \right\}$ 应划分为一个群体，但是加入位置属性后应划分为 $\left\{ {1,2,3,4} \right\}$ 和 $\left\{ {4,5,6} \right\}$ 2个群体，如图2(b)所示. 图2(b)的模块度小于图2(a)，模块度标准不能准确评价移动终端用户群体的划分效果. 由于移动终端用户群体具有位置属性，群体内用户的签到时空共现区相似性高于群体间用户，因此时空共现区的相似性可作为移动终端用户群体划分效果的评价因素. 定义群体结构 ${G_{\rm{A}}}$ 的时空共现区相似性为

${S_{\rm{g}}}\left( {{G_{\rm{A}}}} \right) = \frac{1}{{\left| {{G_{\rm{A}}}} \right|}}\sum\limits_{k=1}^{\left| {{G_{\rm{A}}}} \right|} {{S_{\rm{g}}}\left( {G_{\rm{A}}^k} \right)} ,$

(4)

${S_{\text{g}}}\left( {G_{\text{A}}^k} \right) = \frac{1}{{\left| {G_{\text{A}}^k} \right|\left( {\left| {G_{\text{A}}^k} \right| - 1} \right)}}\sum\limits_{k{\text{ = 1}}}^{\big| {{G_{\text{A}}}^{}} \big|} {\sum\limits_{i = 1}^{\big| {G_{\text{A}}^k} \big|} {\sum\limits_{j = 1,j \ne i}^{\big| {G_{\text{A}}^k} \big|} {\frac{{\left| {z_{\text{c}}^{G_{\text{A}}^k - {v_i}} \cap z_{\text{c}}^{G_{\text{A}}^k - {v_j}}} \right|}}{{\left| {z_{\text{c}}^{G_{\text{A}}^k - {v_i}} \cup z_{\text{c}}^{G_{\text{A}}^k - {v_j}}} \right|}}} } } .$

(5)

式中： $\left| {G_{\rm{A}}^k} \right|$ 为 ${G_{\rm{A}}}$ 中第 $k$ 个群体节点数量， $z_{\rm{c}}^{G_{\rm{A}}^k - {v_j}}$ 为群体 $G_{\rm{A}}^k$ 中节点 ${v_j}$ 签到的时空共现区集合. 由图2可知，在Reverse-LPA的群体划分过程中，存在 ${Q_{{\rm{ov}}}}$ 和 ${S_{\rm{g}}}$ 发展趋势相反的情况. 为了更好地评价背景信息未知时的群体划分效果，结合重叠模块度函数 ${Q_{{\rm{ov}}}}$ 与群体时空共现区相似性 ${S_{\rm{g}}}$ ，定义移动终端用户群体综合评价函数 $F$ 为

$F\left( {{G_{\rm{A}}}} \right) = \frac{{2 {Q_{{\rm{ov}}}}\left( {{G_{\rm{A}}}} \right) {S_{\rm{g}}}\left( {{G_{\rm{A}}}} \right)}}{{{Q_{{\rm{ov}}}}\left( {{G_{\rm{A}}}} \right) + {S_{\rm{g}}}\left( {{G_{\rm{A}}}} \right)}}.$

(6)

5.3 结果分析

实验结果分析包含两部分. 首先在4个数据集上观察评价指标NMI、 ${Q_{{\rm{ov}}}}$ 、 ${S_{\rm{g}}}$ 、F在Reverse-LPA迭代过程中的变化规律，验证Reverse-LPA的可行性；其次通过比较Reverse-LPA与其他算法在数据集上的群体划分指标值，分析Reverse-LPA的有效性.

5.3.1 Reverse-LPA可行性验证

使用Reverse-LPA对4个数据集进行群体划分，在每次迭代中计算评价指标NMI、 ${Q_{{\rm{ov}}}}$ 、 ${S_{\rm{g}}}$ 、F，统计结果如图3所示，图中， $X$ 为Reverse-LPA的迭代次数. 由图可知，Reverse-LPA在不同数据集上的迭代次数不同；在Reverse-LPA迭代的过程中， ${S_{\rm{g}}}$ 逐步提高， ${Q_{{\rm{ov}}}}$ 存在下降的现象， $F$ 随两者的变化而变化，整体呈增长趋势；在数据集Fsqtrue中， ${\rm{NMI}}$ 在迭代过程中保持上升态势， $F$ 与 ${\rm{NMI}}$ 的变化趋势相同.

Reverse-LPA算法流程、数据集特征和实验结果表明Reverse-LPA的迭代次数与用户平均签到次数存在关联关系.由 图3可知，数据集中用户平均签到次数越多，Reverse-LPA需要的迭代次数越多，但是后者的增速较前者慢. 原因是用户平均签到次数越多，初始标签越多，Reverse-LPA需要越多次迭代使所有节点标签达到稳定状态. 同时，初始标签越多，伴随标签越多，较多的伴随标签通过“消除传播效应”加速标签状态的确定，因此迭代次数的增幅低于平均签到次数.

函数 $F$ 可以作为移动终端用户群体划分效果的评价标准. 在Reverse-LPA迭代传播过程中 ${S_{\rm{g}}}$ 逐步提高， ${Q_{{\rm{ov}}}}$ 存在极值，如果单独以 ${S_{\rm{g}}}$ 作为评价标准可能存在划分的群体位置聚集性过强、群体较小、模块度偏低的问题. 一种极端的趋势是每一个用户单独为一个群体，此时 ${S_{\rm{g}}}{\rm{ = 1,}}{\kern 1pt} {\kern 1pt} {Q_{{\rm{ov}}}} = 0$ ；如果单独以 ${Q_{{\rm{ov}}}}$ 为评价标准则可能存在划分群体位置属性较弱的问题，因此不能单独以 ${S_{\rm{g}}}$ 或 ${Q_{{\rm{ov}}}}$ 作为移动终端用户群体划分效果的评价标准. 函数 $F$ 以 ${S_{\rm{g}}}$ 、 ${Q_{{\rm{ov}}}}$ 为变量，能够综合反映位置聚集性和模块度在Reverse-LPA迭代过程中的变化，可以作为移动终端用户群体划分效果的评价标准.

Reverse-LPA能够发现移动终端用户群体. 由图3（a）可知，Reverse-LPA在迭代过程中逐步提高了划分群体的NMI值，算法停止时NMI为0.85，说明Reverse-LPA对数据集Fsqtrue的群体划分结果是有效的. 函数F与 ${\rm{NMI}} $ 保持相似的变化趋势，并且在其他3个数据集上呈现相同的变化趋势，说明Reverse-LPA能够发现移动终端用户的群体结构.

5.3.2 Reverse-LPA有效性分析

为了检验Reverse-LPA的有效性，对比Reverse-LPA和文献[7]、[8]、[12]中所述的基于共现位置轨迹的群体发现方法（group discovery using co-location traces，GDC）、面向位置区域的社会群体发现方法（local social groups discovery, LSGD）、基于位置的标签传播算法（location based label propagation algorithm，LBLPA）在4个数据集上的评价指标NMI、 ${Q_{{\rm{ov}}}}$ 、 ${S_{\rm{g}}}$ 、F，分析Reverse-LPA的群体划分效果. GDC、LBLPA方法在群体发现过程中没有进行用户社会关系推断，Reverse-LPA、LSGD使用各自的方法推断用户社会关系，4者结果不同并且不具备绝对可信性. 为了使比对结果更加准确，统一依据数据集中的社会关系（Friendship）计算4种方法的 ${Q_{{\rm{ov}}}}$ ，依据时空共现区计算 ${S_{\rm{g}}}$ . Reverse-LPA、GDC、LSGD、LBLPA在数据集Gowalla、Brightkite、Foursquare、Fsqtrue上的群体划分结果如表2所示. 表中， $\uparrow $ 表示评价指标在不同方法中的最高值， $ \downarrow $ 则表示最低值. 在4个数据集上，GDC方法的 ${Q_{{\rm{ov}}}}$ 最低， ${S_{\rm{g}}}$ 最高， $F$ 和 ${\rm{NMI}} $ 最低. 这说明根据用户的行为模式划分的用户群体成员具有高度相似的位置属性，但是成员之间的社会关系比较稀疏，不能较好地契合用户真实的社会关系结构，群体划分结果可信性较差. LSGD和LBLPA性能相似，群体划分结果的 ${Q_{{\rm{ov}}}}$ 较好， ${S_{\rm{g}}}$ 较差， $F$ 与 ${\rm{NMI}}$ 中等. LSGD和LBLPA将位置信息转化为社会关系后划分群体，虽然模块度比较好，但是弱化了群体的位置属性，群体发现效果有待提高. Reverse-LPA的 ${Q_{{\rm{ov}}}}$ 与 ${S_{\rm g}}$ 适中， ${\rm{NMI}} $ 优势明显，在数据集Fsqtrue上的NMI比次优者高出8.97%；Reverse-LPA的 $F$ 最高，在4个数据集上比次优者平均高出3.87%. 这说明同时兼顾模块度和位置属性的群体划分方法能够较好地发现移动终端用户的群体结构，社会关系模块度和用户位置聚集性共同影响移动终端用户的群体发现效果，两者不可或缺. 与其他方法相比，Reverse-LPA更加充分地考虑了用户社会关系和位置属性，更充分地满足了移动终端用户群体发现的应用需求.

6 结　语

提出了基于Reverse-LPA的移动终端用户群体发现方法，根据位置数据推断用户社会关系拓扑图，提取用户时空共现区. 以时空共现区为标签标记社会关系拓扑图，在标签拓扑图上进行反向标签传播. 通过反复迭代，逐步消除伴随标签，最终保留每个用户所属群体的主标签. 将拓扑图上拥有相同主标签的用户划分为一个群体，得到移动终端用户群体结构. Reverse-LPA算法较好地考虑了用户社会关系和位置属性，其可行性和有效性在真实数据集上得到了验证，Reverse-LPA的评价指标 ${\rm{NMI}}$ 与 $F$ 分别比次优者平均高出8.97%和3.87%. 今后可在此基础上进一步研究在用户社会关系类型等信息辅助下的移动终端用户群体发现方法.