第4期 杨宇迪，等：异质信息网络中基于网络嵌人的影响力最大化 ·761· 种模型作为扩散模型，在SR模型实验中，感染概 1)最大感染率。 率y设为0.8，恢复概率0设为0.5，种子集大小设 由于存在随机性，每次实验中被感染节点的 为1~100：在线性阈值模型实验中，其阈值设置为 数量通常不同，因此本实验将每组种子集在SIR 0.5,种子集大小设为050。 模型上运行50次，取平均感染率作为该组种子集 3.1.3对比算法 的感染率。图4显示了不同算法的top-k个不同 采用DC、PageRank、Entropy-based、MPIE和 类型的影响力节点获得的感染率。 MNE-D算法作为对比算法，验证IMNE算法实现 80 HN中影响力最大化的有效性。其中DC、PageR- ank算法是常见的影响力最大化中选择种子集的 70 方法；Entropy-based算法是同质网络中不仅考 虑直接影响和间接影响，还考虑影响力扩散的一 60 种方法，有助于对比异质信息对种子集选择的影 -DC 50 响；其次，IMNE算法除了实现HN中的影响力最 -◆-PageRank -IMNE-D 大化，还可以度量HN中节点的社会影响力，而 -Entropy-based -◆MNE 0 20 40 60 80 100 MPIE算法是基于元路径度量HN中节点影响力 top-k 的方法，因此，本文还选择MPE算法作为对比 (a)Yelp 算法，分析MNE算法在HN中度量节点社会影 80 响力的效果。 在实验中，DC、PageRank和Entropy-.based方 70 法将忽略HN中节点和链接的异质性，直接在整 60 书中十个◆中+、 个网络(4-area、Yelp和Amazon)上运行，实验结 0 果包含各种不同类型的节点。MNED是IMNE算 -o-DC 法的变体，主要通过计算节点的直接影响力来选 0 -◆-PageRank -4-IMNE-D -Entropy-based --IMNE 择种子集，未考虑非直接相连的节点间的影响，有 30 20 40 60 80 100 助于对比间接影响力对影响力最大化的作用。特别 top-k 地，基准算法中的参数均选择实验结果最优参数。 (b)4-area 3.1.4评估指标 1)在SIR模型实验中，将感染率(Infection rate)和感染时间(nfection time)作为评估指标验 40 有◆◆身◆身之文 证MNE算法的性能，其中感染率表示种子集在 -0-00=0 SIR模型下感染节点占所有节点的比例；感染时 30 间代表种子集在SIR模型下达到最大感染率所需 -0-DC -◆-PageRank -IMNE-D 时间，验证IMNE算法是否在SIR扩散模型下使 --Entropy-based -◆-MNE 得影响力扩散范围在较短时间内达到最大。令 20 0 0 60 80100 I表示在影响力扩散过程中从易感染状态转变 top-k (c)Amazon 为感染状态的节点数量，IW表示整个HN包含的 节点数量，则感染率定义为 图4不同算法的topk影响力节点的感染率比较 infection rate-NI Fig.4 Comparison of infection rate of different methods (7) ☑ with different top-k influential nodes 通常情况下，感染率越大、感染周期越短，算 首先，从图4可以看出，IMNE算法得到的感 法性能越强。 染率优于基线算法(DC、PageRank和Entropy- 2)在线性阈值模型实验中，将使用种子节点 based),这表明不同类型节点之间具有影响且这些 激活的其他节点数目来评估不同算法的性能，激 异质信息有益于影响力最大化。其次，由于不同 活的节点数量越多，表示该影响力最大化算法的 数据集数据的分布情况不同，相同的方法在不同 性能越强。 的数据集上具有不同的感染率。特别地，DC和 3.2IMNE算法在SIR模型下的性能 PageRank更加依赖于数据的分布情况，例如4area 本节将从感染率和感染时间两个方面分析 中节点度的差异比Amazon和Yelp更明显，因 IMNE算法在SR模型下的有效性。 此，在4-area中PageRank的性能比在Amazon和γ θ 种模型作为扩散模型，在 SIR 模型实验中，感染概 率 设为 0.8，恢复概率 设为 0.5，种子集大小设 为 1~100；在线性阈值模型实验中，其阈值设置为 0.5，种子集大小设为 0~50。 3.1.3 对比算法 采用 DC、PageRank、Entropy-based、MPIE 和 IMNE-D 算法作为对比算法，验证 IMNE 算法实现 HIN 中影响力最大化的有效性。其中 DC、PageR￾ank 算法是常见的影响力最大化中选择种子集的 方法；Entropy-based 算法[11] 是同质网络中不仅考 虑直接影响和间接影响，还考虑影响力扩散的一 种方法，有助于对比异质信息对种子集选择的影 响；其次，IMNE 算法除了实现 HIN 中的影响力最 大化，还可以度量 HIN 中节点的社会影响力，而 MPIE 算法是基于元路径度量 HIN 中节点影响力 的方法，因此，本文还选择 MPIE 算法[18] 作为对比 算法，分析 IMNE 算法在 HIN 中度量节点社会影 响力的效果。 在实验中，DC、PageRank 和 Entropy-based 方 法将忽略 HIN 中节点和链接的异质性，直接在整 个网络 (4-area、Yelp 和 Amazon) 上运行，实验结 果包含各种不同类型的节点。IMNE-D 是 IMNE 算 法的变体，主要通过计算节点的直接影响力来选 择种子集，未考虑非直接相连的节点间的影响，有 助于对比间接影响力对影响力最大化的作用。特别 地，基准算法中的参数均选择实验结果最优参数。 3.1.4 评估指标 NI |V| 1) 在 SIR 模型实验中，将感染率 (Infection rate) 和感染时间 (Infection time) 作为评估指标验 证 IMNE 算法的性能，其中感染率表示种子集在 SIR 模型下感染节点占所有节点的比例；感染时 间代表种子集在 SIR 模型下达到最大感染率所需 时间，验证 IMNE 算法是否在 SIR 扩散模型下使 得影响力扩散范围在较短时间内达到最大。令 表示在影响力扩散过程中从易感染状态转变 为感染状态的节点数量， 表示整个 HIN 包含的 节点数量，则感染率定义为 infection rate = NI |V| (7) 通常情况下，感染率越大、感染周期越短，算 法性能越强。 2) 在线性阈值模型实验中，将使用种子节点 激活的其他节点数目来评估不同算法的性能，激 活的节点数量越多，表示该影响力最大化算法的 性能越强。 3.2 IMNE 算法在 SIR 模型下的性能 本节将从感染率和感染时间两个方面分析 IMNE 算法在 SIR 模型下的有效性。 1) 最大感染率。 k 由于存在随机性，每次实验中被感染节点的 数量通常不同，因此本实验将每组种子集在 SIR 模型上运行 50 次，取平均感染率作为该组种子集 的感染率。图 4 显示了不同算法的 top- 个不同 类型的影响力节点获得的感染率。 80 70 60 50 40 20 40 60 80 100 top-k (a) Yelp 感染率/% DC PageRank Entropy-based IMNE-D IMNE 80 70 60 50 30 40 1 20 1 1 40 60 80 100 top-k (b) 4-area 感染率/% DC PageRank Entropy-based IMNE-D IMNE 50 40 30 20 20 40 60 80 100 top-k (c) Amazon 感染率/% DC PageRank Entropy-based IMNE-D IMNE 图 4 不同算法的 top-k 影响力节点的感染率比较 Fig. 4 Comparison of infection rate of different methods with different top-k influential nodes 首先，从图 4 可以看出，IMNE 算法得到的感 染率优于基线算法 (DC、PageRank 和 Entropy￾based)，这表明不同类型节点之间具有影响且这些 异质信息有益于影响力最大化。其次，由于不同 数据集数据的分布情况不同，相同的方法在不同 的数据集上具有不同的感染率。特别地，DC 和 PageRank 更加依赖于数据的分布情况，例如 4-area 中节点度的差异比 Amazon 和 Yelp 更明显，因 此，在 4-area 中 PageRank 的性能比在 Amazon 和 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·761·