·762· 智能系统学报 第16卷 Yelp更稳定。同时，还可观察到，当k值较小时， 最广，还要求在短时间内达到影响力扩散范围最 在Yelp数据集中，Entropy-based优于IMNE算 广，因此，本实验从感染时间验证MNE算法的性 法，但是随着k值的增加，IMNE算法的感染率逐 能。图5显示了不同模型的top-k影响力节点达 渐优于Entropy-based, 到最大感染率的周期（周期即种子完成一次感染 其次，关于IMNE-D,其与IMNE的主要区别 和恢复所需时间)，可以看出MNE算法在3个数 在于影响力度量组件，IMNE-D仅考虑了直接链 据集上的影响力传播过程中，尤其是Yelp和 接节点之间的影响，忽略了社交网络中朋友的朋 Amazon,IMNE达到最大感染率的时间均小于其 友之间的某种间接影响。根据结果(IMNE> 他基线算法，表示IMNE算法能在较短的时间内 IMNE-D),可以发现间接影响力对改善影响力的 达到较大的感染率，即IMNE算法具有效性。在 传播范围具有重要意义。 4-area数据集中，当k值超过60时，尽管IMNE- 2)达到最大感染率的时间。 D感染时间小于IMNE,但此时从图4可以发现 影响力最大化不仅要求种子节点的影响范围 IMNE算法的感染率大于IMNE-D。 --IMNE-D =3-DC -IMNE -◆-PageRank -◆-Entropy-based 2 -o-DC --DC -◆-PageRank -+-IMNE-D -◆-PageRank --IMNE-D Entropy-based =◆-MNE --Entropy-based -◆-IMNE 20 4060 80100 20 40 60 80100 204060 80100 top-k top-k top-k (a)Yelp (b)4-area (c)Amazon 图5不同算法的top-k影响力节点感染时间比较 Fig.5 Comparison of infection time of different methods with different top-k influential nodes 综上所述，通过分析最大感染率和达到最大 响范围。 感染率所需时间，可以发现，MNE算法相较于其 从图6可看出，MNE算法的影响范围均大 他基准算法能在更短的时间实现影响力最大化。 于同质网络中的方法(DC、Entropy-based和 3.3MNE在线性阈值模型下的性能 PageRank),这表明IMNE算法在LT模型下也能 为了更好地验证IMNE算法的有效性，本实 较好地实现影响力最大化。其次，IMNE算法的 验也验证了IMNE算法在线性阈值模型下的有效 影响范围接近MPIE算法，这表明IMNE算法可 性。图6显示了在4-area和Yelp数据集上不同算 以在不指定特定的元路径的情况下也能较为有效 法的k=(5,10,20,30,40,50)个有影响力作者的影 地度量HN中节点的社会影响力。 300 1500 DC 250 二车 2 1250 PageRank Entropy-based 1000 MPIE IMNE-D 150 IMNE ·DC 750 100 -◆·PageRank pp-aed 500 50 -◆IMNE-D 250 出◆ -◆.MNE 10 20 30 8 10 20 30 40 50 top-k top-k (a)4-area (b)Yelp 图6不同算法的top-k影响力节点影响范围 Fig.6 Comparison of the range of top-k influential nodes of different methods 3.4计算效率 力耗费的时间。 本实验主要从节点社会影响力的计算时间分 首先，从表1可以看出，由于不同数据集的数 析IMNE算法的效率。表1展示了不同算法在4 据分布情况不同，不同算法在不同数据集上的计 area、Yclp和Amazon数据集上计算节点社会影响 算时间不同，IMNE算法和其他基准算法在k k Yelp 更稳定。同时，还可观察到，当 值较小时， 在 Yelp 数据集中，Entropy-based 优于 IMNE 算 法，但是随着 值的增加，IMNE 算法的感染率逐 渐优于 Entropy-based。 其次，关于 IMNE-D，其与 IMNE 的主要区别 在于影响力度量组件，IMNE-D 仅考虑了直接链 接节点之间的影响，忽略了社交网络中朋友的朋 友之间的某种间接影响。根据结 果 (IMNE> IMNE-D)，可以发现间接影响力对改善影响力的 传播范围具有重要意义。 2) 达到最大感染率的时间。 影响力最大化不仅要求种子节点的影响范围 k 最广，还要求在短时间内达到影响力扩散范围最 广，因此，本实验从感染时间验证 IMNE 算法的性 能。图 5 显示了不同模型的 top-k 影响力节点达 到最大感染率的周期（周期即种子完成一次感染 和恢复所需时间），可以看出 IMNE 算法在 3 个数 据集上的影响力传播过程中，尤其是 Yelp 和 Amazon，IMNE 达到最大感染率的时间均小于其 他基线算法，表示 IMNE 算法能在较短的时间内 达到较大的感染率,即 IMNE 算法具有效性。在 4-area 数据集中，当 值超过 60 时，尽管 IMNE￾D 感染时间小于 IMNE，但此时从图 4 可以发现 IMNE 算法的感染率大于 IMNE-D。 4 3 2 1 0 1 40 60 80 100 20 top-k (a) Yelp 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 5 4 3 2 1 0 1 40 60 80 100 20 top-k (b) 4-area 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 4 3 2 1 0 1 40 60 80 100 20 top-k (c) Amazon 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 图 5 不同算法的 top-k 影响力节点感染时间比较 Fig. 5 Comparison of infection time of different methods with different top-k influential nodes 综上所述，通过分析最大感染率和达到最大 感染率所需时间，可以发现，IMNE 算法相较于其 他基准算法能在更短的时间实现影响力最大化。 3.3 IMNE 在线性阈值模型下的性能 k = (5,10,20,30,40,50) 为了更好地验证 IMNE 算法的有效性，本实 验也验证了 IMNE 算法在线性阈值模型下的有效 性。图 6 显示了在 4-area 和 Yelp 数据集上不同算 法的 个有影响力作者的影 响范围。 从图 6 可看出，IMNE 算法的影响范围均大 于同质网络中的方法 (DC、 Entropy-based 和 PageRank)，这表明 IMNE 算法在 LT 模型下也能 较好地实现影响力最大化。其次，IMNE 算法的 影响范围接近 MPIE 算法，这表明 IMNE 算法可 以在不指定特定的元路径的情况下也能较为有效 地度量 HIN 中节点的社会影响力。 300 250 200 150 100 50 0 5 20 30 40 50 10 top-k (a) 4-area 影响力传播 DC PageRank Entropy-based IMNE-D IMNE MPIE 1 500 1 250 1 000 750 500 250 0 5 20 30 40 50 10 top-k (b) Yelp 影响力传播 DC PageRank Entropy-based IMNE-D IMNE MPIE 图 6 不同算法的 top-k 影响力节点影响范围 Fig. 6 Comparison of the range of top-k influential nodes of different methods 3.4 计算效率 本实验主要从节点社会影响力的计算时间分 析 IMNE 算法的效率。表 1 展示了不同算法在 4- area、Yelp 和 Amazon 数据集上计算节点社会影响 力耗费的时间。 首先，从表 1 可以看出，由于不同数据集的数 据分布情况不同，不同算法在不同数据集上的计 算时间不同， IMN E 算法和其他基准算法 在 ·762· 智 能 系 统 学 报 第 16 卷