Page 238 - 《软件学报》2020年第11期

尹子都 等:基于采样的在线大图数据收集和更新 3553

进一步地,我们根据公式(6)计算了上述对比方法与 HD-QMC 在各个数据集下的有效性指标(S A ),见表 2.不
难看出,由于 HD-QMC 能够更精确地计算子空间的重要性,因此所有数据集上获得了最高的 S A ,并取得了最好
的数据收集效果.DFS 方法由于无法在微博数据集上运行,表 2 中对应值未列出.

Table 2 S A of different methods for data collection
表 2 不同数据收集方法的 S A

数据集 Sequence Random Snowballing DFS BB-QMC HD-QMC
Wiki-data 53.45 50.02 50.62 50.48 56.45 59.27
Ber-stan 49.99 51.06 45.12 44.36 56.44 57.50
Facebook 21.51 18.23 21.30 19.13 22.83 22.99
微博 505.54 401.04 471.53 N/A 488.31 550.73

(2) EPP 算法有效性测试
我们用 2 个典型的数据集测试 EPP 算法的有效性:第 1 个是时间跨度 2 周、约 11 000 个用户的真实微博
数据集,第 1 周数据作为已收集数据,第 2 周数据作为新数据;第 2 个是由扩展的 LFR 方法 [28] 生成的 LFR 数据
集,以此来测试当社交媒体中存在极端变化时,EPP 的数据更新效果.与 HD-QMC 的测试相似,我们测试了不同
[9]
方法的目标信息覆盖度,包括本文提出的 EPP、基于统计的方法(Statistic) 和基于结构的方法(structure-
based) [22] ,如图 10(a)、图 10(b)所示.其中,基于统计的方法通过统计并计算历史数据中对象变化的概率进行数据
更新,基于结构的方法通过计算对象间不同连接结构的变化概率进行数据更新.

EPP
1.0 Statistic 1.0
Structure-Based
目标信息覆盖度 0.5 目标信息覆盖度 0.5 EPP

Statistic
0.0
0.0
Structure-Based
0 2000 4000 6000 8000 10000 12000 14000 0 2000 4000 6000 8000 10000 12000 14000
已收集对象数 已收集对象数
(a) 微博 (b) LFR
Fig.10 Target information coverage of different methods for data updating
图 10 不同数据更新方法的目标信息覆盖度

根据公式(6),以上 3 种方法的有效性指标(S A )见表 3.
Table 3 S A of different methods for data updating
表 3 不同数据更新方法的 S A
数据集 Statistic Structure-based EPP
微博 41.03 10.99 42.17
LFR 115.62 90.49 109.78

结合图 10 和表 3 可以看出,对于真实的微博数据集,EPP 比其他方法能够更好地发现增量,但是基于统计的
方法在 LFR 数据集上取得了更好的数据更新效果.
我们进一步用 F1 值测试 EPP 针对数据更新的有效性.
2 Pr Re⋅ ⋅
F 1 = (14)
Pr + Re
其中,Pr 和 Re 分别表示 Precision 值和 Recall 值,Precision 是 EPP 发现的增量与其预测增量的比值,Recall 是 EPP
发现的增量与真实增量的比值.测试结果如图 11(a)、图 11(b)所示,可以看出,EPP 在微博和 LFR 数据集上优于