一篇利用熵来建模社交关系的论文

作者: 6c439605722f | 来源:发表于2020-02-14 16:05 被阅读0次

paper标题为"EBM - An Entropy-Based Model to Infer Social Strength from Spatiotemporal Data",这篇文章发在sigmod 2013，写的比较有意思，适合作为研究共现现象、social tie和时空数据挖掘的入手文章。本文利用共现现象的多样性（diversity）和隐私性（privacy）对用户的social tie进行建模。

check-in数据是非常流行的时空数据，包含<u,l,t>三元信息，即用户u在时间t地点l打卡。从直觉上来说，经常在不同的地方同时出现的人群更有可能是熟人。因此定义：对于用户 $U = (u_1, u_2, u_3,...,u_M)$ , 地点 $L = （l_1, l_2, ..., l_N）$ , 用户i和用户j的共现现象可以用共现向量 $C_{ij} = (c_{ij,1},c_{ij,2},...,c_{ij,M})$ 表示，其中 $C_{ij,l}$ 表示用户i，j在地点l出现的次数。

文章的主要思路如下图所示，diversity由Shannon Entropy建模，但由于coincidence现象的存在，作者用Renyi entropy进行改进，一定程度上规避该现象。地点的隐私性由Location Entropy建模，然后利用location entropy由Weighted Frequency建模共现向量的隐私性。最后将Renyi entropy和weighted frequency合并成一个指标得到social tie。

多样性

从直觉上来说，用户在多个不同的地方同时出现，那么该用户之间social tie会更紧密。因此定义用户i、j在地点l共现的概率：

其中， $R_{i,j}^l$ 表示用户i，j在地点l共现的次数， $R_{i,j}$ 表示用户i，j共现次数总和，因此定义social tie $D_{ij}$ ：

其中

讨论完Shannon entropy后，作者提出对于利用Shannon entropy计算的social tie没有考虑coincidence 现象。例如，用户1，2只在图书馆同时出现了4次，用户1，3只在用户1家中同时出现了4次。这两对用户的Shannon entropy一样，但显然后者社交关系更紧密一些。为了缓解该现象带来了负面影响。作者提出Renyi entropy来重新定义。

隐私性

Renyi entropy的特性体现在参数q的取值：若q > 1，权重会向值较大的 $c_{ij,l }$ 倾斜；若q > 1，权重会向值较小的 $c_{ij,l}$ 倾斜。作者在文章中b把q设为0.5。个人认为原因如下：作者假设越隐私的地方用户之间更难同时出现，也即认为 $c_{ij,l }$ 较小的地方是更隐私的地方。同时，作者也承认该假设还有漏洞，但是声明Renyi entropy比Shannon entropy能更好应对coincidence现象。