Monthly Archives: February 2022

图挖掘

社交网络之间的帐号映射

Leave a comment

帐号映射的整体介绍

在现实生活中，用户通常会同时使用多个社交网络，例如国外的 Twitter，Instagram，Facebook，也可能使用微信，QQ，微博等国内的产品。基于这些产品的不同定位，用户自身的社交网络会有很大的差异，那么如何通过机器学习算法找到一个人的社交网络帐号就成为了一个有趣的问题。在学术界，有学者对开源的 Facebook，Twitter 等社交网络数据进行了研究，设计了一套帐号映射的技术方案。

帐号映射这个课题有很多的别名，例如：

  • Social identity linkage；
  • User identity linkage；
  • User identity resolution；
  • Social network reconciliation；
  • User account linkage inference；
  • Profile linkage；
  • Anchor link prediction；
  • Detecting me edges；

帐号映射的目的就是将社交网络上这些看似不同的帐号映射到自然人：帐号（user accounts）-> 真实的自然人（real natural person）。令社交网络 \mathcal{G}=\mathcal{G}(\mathcal{U},\mathcal{E}) 是一个图，顶点是帐号 \mathcal{U}=\{u_{1},\cdots,u_{n}\}, 边是由帐号之间的连线 \mathcal{E}\subseteq \mathcal{U}\times\mathcal{U} 所构成的。

帐号映射（User Identity Linkage）的定义是：给定两个社交网络 \mathcal{G}^{s}=(\mathcal{U}^{s},\mathcal{E}^{s}) 和 \mathcal{G}^{t}=(\mathcal{U}^{t},\mathcal{E}^{t}), 其目标是找到一个函数 \mathcal{F}:\mathcal{U}^{s}\times\mathcal{U}^{t}\rightarrow\{0,1\} 使得，
\mathcal{F}(u^{s},u^{t})=\begin{cases}1,\text{ if } u^{s} \text{ and } u^{t} \text{ belong to same person,}\\ 0, \text{ otherwise.} \end{cases}
其中 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}.

上述函数 \mathcal{F} 就是模型需要学习的目标函数，进一步地，对于 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}, 学习得到的预测函数 \mathcal{\hat{F}}(u^{s},u^{t})=p\in [0,1] 表示两个帐号属于同一个自然人的概率值。

一个帐号在社交网络的属性包括很多方面，例如：

画像属性（Profile Features）内容属性（Content Features）社交网络属性（Network Features）
ID（社交网络的唯一标识）时间戳（timestamp）关注，被关注，好友关系（Friendship）
身份证 ID（identity card）语音（speech）点赞（like）
手机号（phone）视频（video）评论（comment）
昵称（username）图片（image）@（at）
头像（head image）文本（text）收藏（collect）
性别（gender）设备信息（device）消息（message）
年龄（age）wifi 信息（wifi）回复（reply）
邮箱（email）地理位置（gps）
个人网页（url）
职业（occupation）
常见的社交网络数据

一般情况下，

  1. 画像属性：绝大多数帐号都会有基础的画像信息；
  2. 内容属性：不活跃的帐号较难获取；
  3. 社交网络属性：线上的社交网络关系并不代表线下的社交网络关系，存在一定的噪声数据。

帐号映射的技术框架可以基于特征工程来做，然后使用有监督算法，无监督算法，或者半监督算法来进行帐号对之间的训练和预测。

帐号映射的技术框架

帐号映射的特征工程

帐号的画像特征

对于社交网络 \mathcal{G}=\mathcal{G}(\mathcal{U},\mathcal{E}) 中的一个帐号 u\in\mathcal{U} 而言，用 \overrightarrow{p_{u}}=(p_{u}^{1},\cdots,p_{u}^{m}) 来表示画像特征向量，其中 m\geq 1 表示画像属性特征的个数。对于两个社交网络 \mathcal{G}^{s},\mathcal{G}^{t} 的帐号 u^{s},u^{t} 而言，可以得到相应的画像特征向量 \overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}}, 然后可以用基于距离（distance-based）或者基于频率（frequence-based）的方法来获得向量的距离或者相似性。换句话说，就是通过加权平均算法来获得结果：

sim(\overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}})=\sum_{1\leq i\leq m}w_{i}\cdot sim(p_{u^{s}}^{i},p_{u^{t}}^{i}), 或者

dis(\overrightarrow{p_{u^{s}}},\overrightarrow{p_{u^{t}}})=\sum_{1\leq i\leq m}w_{i}\cdot dis(p_{u^{s}}^{i},p_{u^{t}}^{i}),

其中 sim 表示相似度，dis 表示距离。

基于距离的方法（distance-based）的方法很多，例如：

  1. 文本（text field）之间的距离可以考虑用 Jaro-Winkler distance，Jaccard similarity，Levenshtein distance 等方法；
  2. 图像（visual field）之间的距离可以考虑用 mean square error，dot product，angular distance，peak signal-to-noise ratio，Levenshtein distance 等方法；

基于频率的方法（frequence-based）可以考虑 bag-of-word model，TF-IDF model，Markov-chain model 等方法；

帐号的内容特征

帐号所产生的内容数据包括三个部分：

  1. 时间上的数据（temporal）：时间戳的数据；
  2. 空间上的数据（spatial）：帐号的设备数据，IP 数据，WIFI 数据，地理位置数据等等；
  3. 内容上的数据（post）：帐号所产生的内容数据，包括但不限于视频，文本，语音，图片等。

用数学公式来描述就是 \overrightarrow{c_{u}}=\{(t_{1},s_{1},p_{1}), \cdots,(t_{m},s_{m},p_{m})\}, 其中 t_{i},s_{i},p_{i}(1\leq i\leq m) 分别表示时间戳，空间数据，内容数据。

在某个时间段内，帐号所产生的内容特征可以提炼出用户在社交网络上的行为数据和内容数据，形成一个行为序列。通过这个行为序列，可以得到用户的内容特征。

  1. 基于兴趣的特征（Interest-based）：可以基于内容数据判断帐号对哪些内容更感兴趣；
  2. 基于风格的特征（Style-based）：基于内容数据得到帐号的写作风格，例如常用词语等；
  3. 基于轨迹的特征（Trajectory-based）：基于帐号的行为轨迹数据，包括设备，IP，WIFI，地理位置以及相应的时间戳，得到帐号的足迹（footprint）。

帐号的社交网络特征

社交网络包括两种：

  1. 局部社交网络（local network）：查看帐号的邻居（关注，被关注，好友关系）等诸多数据；
  2. 全局社交网络（global network）：查看帐号在全局数据中的位置情况；

对于帐号的社交网络特征，包括以下两种常见形式：

  1. 基于邻居的特征（Neighborhood-based）：共同好友数，共同邻居个数，Jaccard Coefficient，Overlap Coefficient，Dice Coefficient，Adamic/Adar score；
  2. 基于嵌入的特征（Embedding-based）：通过计算帐号在相应的社交网络的嵌入特征，然后计算特征之间的距离或者相似性。

帐号映射的建模思路

机器学习的常见算法包括有监督算法（supervised model），无监督算法（unsupervised model）和半监督算法（semi-supervised model）。

基于上面的特征工程，加上合适的权重之和可以得到一个分数（score），也就是：

\mathcal{F}(u^{s},u^{t})=\alpha \cdot sim_{p}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}})+\beta\cdot sim_{c}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}})+\gamma\cdot sim_{n}(\overrightarrow{p_{u^{s}}}, \overrightarrow{p_{u^{t}}}),

其中 sim_{p}, sim_{c}, sim_{n} 分别表示画像（profile），内容（content），社交网络（network）之间的相似度。

如果有样本的话，全体样本是 \mathcal{Q}=\{(u^{s},u^{t}),\forall u^{s}\in\mathcal{U}^{s},\forall u^{t}\in\mathcal{U}^{t}\}, 那么正样本是 \mathcal{M}=\{(u^{s},u^{t}),u^{s}\in\mathcal{U}^{s},u^{t}\in\mathcal{U}^{t}, u^{s} \text{ and } u^{t} \text{ belong to the same person}\}, 负样本 \mathcal{N}=\mathcal{Q}-\mathcal{M}. 在实际使用的时候，要注意采样的比例和负样本的选择方法。

帐号映射的评价指标

对于 u^{s}\in\mathcal{U}^{s}, u^{t}\in\mathcal{U}^{t}, 假设
\mathcal{Q}=\{(u^{s},u^{t}),\forall u^{s}\in\mathcal{U}^{s},\forall u^{t}\in\mathcal{U}^{t}\} 是所有的帐号对，
\mathcal{M}=\{(u^{s},u^{t}),u^{s}\in\mathcal{U}^{s},u^{t}\in\mathcal{U}^{t}, u^{s} \text{ and } u^{t} \text{ belong to the same person}\} 是所有属于相同自然人的帐号对，
\mathcal{N}=\mathcal{Q}-\mathcal{M} 是所有属于不同自然人的帐号对。
令\mathcal{A}= {被算法映射成相同自然人的帐号对}，\mathcal{B}= {被算法映射成不同自然人的帐号对}；用 TP, TN, FN, FP 来描述就是：

  • True Positive（TP）：|\mathcal{A} \cap \mathcal{M}|;
  • True Negative（TN）：|\mathcal{B}\cap\mathcal{N}|;
  • False Negative（FN）：|\mathcal{B}\cap\mathcal{M}|;
  • False Positive（FP）：|\mathcal{A}\cap\mathcal{N}|;

那么，Precision = TP / (TP + FP)=|\mathcal{A}\cap\mathcal{M}|/|\mathcal{A}|, Recall = TP / (TP + FN)= |\mathcal{A}\cap\mathcal{M}|/|\mathcal{M}|.

另外，F1=2\cdot Precision \cdot Recall / (Precision + Recall), Accuracy=(TP+TN)/(TP+TN+FP+FN).

部分论文细节

  1. Liu, Jing, et al. “What’s in a name? An unsupervised approach to link users across communities.” Proceedings of the sixth ACM international conference on Web search and data mining. 2013. 本篇文章主要是基于用户的名字来识别跨网络的用户的，提取用户的特征之后，使用 SVM 分类器来进行识别；
  2. Riederer, Christopher, et al. “Linking users across domains with location data: Theory and validation.” Proceedings of the 25th International Conference on World Wide Web. 2016. 本篇文章主要是基于用户的内容特征来进行建模；
  3. Labitzke, Sebastian, Irina Taranu, and Hannes Hartenstein. “What your friends tell others about you: Low cost linkability of social network profiles.” Proc. 5th International ACM Workshop on Social Network Mining and Analysis, San Diego, CA, USA. 2011. 本篇论文是根据社交网络中的用户邻居数据，来判断用户之间相似性的。

参考文献

  1. Shu, Kai, et al. “User identity linkage across online social networks: A review.” Acm Sigkdd Explorations Newsletter 18.2 (2017): 5-17.
  2. Liu, Jing, et al. “What’s in a name? An unsupervised approach to link users across communities.” Proceedings of the sixth ACM international conference on Web search and data mining.
  3. Riederer, Christopher, et al. “Linking users across domains with location data: Theory and validation.” Proceedings of the 25th International Conference on World Wide Web. 2016.
  4. Labitzke, Sebastian, Irina Taranu, and Hannes Hartenstein. “What your friends tell others about you: Low cost linkability of social network profiles.” Proc. 5th International ACM Workshop on Social Network Mining and Analysis, San Diego, CA, USA. 2011.
Advertisement