刘鑫哲 方勇 贾鹏 寇蒋恒 范希明 周小涵 潘睿 朱旭
摘 要：
群体竞争影响力识别是社交网络分析领域的一个必要研究，其任务是识别社交网络中任意两群体节点在相互竞争条件下的影响力，在舆情分析等实际场景中具有重要意义. 在过去的几年里，许多研究集中在没有竞争对手的群体影响力识别. 然而，竞争普遍存在于真实的社交网络中，因此研究群体竞争影响力识别任务十分必要. 与非竞争场景下的群体影响力识别相比，群体竞争影响力识别存在竞争数据集的构建和群体对嵌入聚合等挑战. 图表示学习（GRL）在社交网络分析领域取得了巨大的成功，可以将图结构表示成具有结构信息的低维嵌入，能够更好的反应节点之间的相互作用，提供比传统方法更丰富的信息. 本文开创性的使用GRL 来解决竞争场景下的群体影响力识别问题，并提出了一个基于GRL 的框架. 为了解决竞争数据集的构建问题，本文提出了一种基于影响力多样性的群体对构建方法. 为了解决竞争群体对嵌入聚合问题，本文提出了一种基于求和相减的方法来聚合竞争群体对中节点的嵌入. 本文在7 个真实的社交网络上进行了大量实验来分析所提框架的有效性. 实验结果表明所提框架优于基线方法.
关键词：
群体竞争影响力识别；
社交网络分析；
深度学习；
图神经网络
中图分类号：
TP391. 1 文献标志码：
A DOI：
10. 19907/j. 0490-6756. 2024. 033006
1 引言
社交网络通常可以表示为G = （V， E ），其中V 表示社交网络中的节点，E 表示节点之间的边.竞争是社交网络的普遍特征，准确识别社交网络内群体的影响力意义重大，而这需要同时考虑群体本身及其竞争对手的特征. 假设S 和C 是两组相互竞争的节点，（S， C ） 称为群体对，其中S ∈ V，C ∈ V，S ∩ C = ?. 群体竞争影响力识别任务的目标就是识别社交网络中群体S 在存在竞争群体C时的影响力，这在分析企业传播策略的有效性、预测投票趋势和抑制舆论传播等领域具有实际应用价值. 现有的群体影响力研究主要集中在无竞争场景，主要的方法有3 类：基于路径分析的方法、基于贪心算法的方法和基于中心性的方法.
基于路径分析的方法通过分析节点组与其他节点之间的路径信息计算影响力. 然而，这些方法只能分析一些特定的路径，无法分析所有节点之间的所有路径，导致结果精确度不高. 基于贪心算法的方法需要大量的蒙特卡罗模拟，计算成本高昂，所以无法扩展到大型网络［1］. 基于中心性的方法比基于路径分析和基于贪心算法的方法更高效. 然而，现有方法通常只考虑一个或几个特定的结构［2，3］，或者从几个单独节点的结构信息分析节点组的影响力，没有考虑多个节点之间的相互作用，例如影响的重叠，导致结果并不准确.
此外，这些方法都没有考虑到社交网络中普遍存在的竞争因素. 因此，在竞争场景下直接使用这些方法来识别群体影响力会产生较大误差. 如何在考虑竞争因素的情况下准确评估群体的影响力是社交网络分析领域的挑战之一.
图表示（Graph Representation Learning，GRL）是一种针对图数据的处理方法［4］，可以将节点、边、子图或整个图处理为低维向量表示，以供下游具体任务使用. GRL 在自然语言处理［5］、社交网络分析［6］、物理建模［7］和药物设计［8］等许多研究领域有着广泛应用并取得了巨大成功. 群体的整体分布特征是处理群体级任务的重要信息，但现有的GRL 模型并不能很好的获取此类信息，所以不能直接用于群体竞争影响力识别任务.
在本文中，我们提出了一个基于GRL 的框架来解决群体竞争影响力识别问题. 我们工作的主要贡献如下：（1） 我们将群体竞争影响力识别视为群体层面的回归任务，并提出了一个基于GRL 的框架来解决这一问题. 据我们所知，这是第一个从这样的角度来处理群体竞争影响力识别任务的工作.（2） 我们提出了一个基于求和-相减的群体对嵌入聚合方法，该方法可以有效捕捉群体之间的竞争关系和同群体内的合作关系，解决群体对嵌入表示的问题. 该方法还通过计算群体内节点的邻居重叠度来削减重叠影响问题.（3） 针对社交网络数据分布不平衡问题，我们提出了一个基于影响力多样性的群体对构建方法.（4） 本文在7 个真实社交网络数据集上进行了一系列实验，证明所提框架的性能优势和所提方法的有效性.
2 相关工作
目前尚无关于社交网络群体竞争影响力识别的研究，因此我们希望从社交网络群体影响力识别的现有研究中获得经验. 研究人员已经提出了许多方法来评估社交网络中群体的影响力，这些方法通常可以分为3 类：基于贪心算法的方法、基于路径分析的方法和基于中心性的方法. 此外，图表示学习（GRL）作为近期的研究热点，被越来越多的研究者研究并应用. 因此，本文参考了大量基于贪心算法、基于路径分析、基于中心性的群体影响力识别方法和GRL 相关文献.
2. 1 基于贪心算法的方法
该方法主要使用蒙特卡洛模拟来估计群体影响力，并通过构建贪心算法来优化模拟过程. 其中，Leskovec 等人［9］提出了CELF 算法，通过利用影响估计优先级队列和懒惰转发策略来提高简单贪心算法的效率. Goyal 等人［10］基于CELF 提出了CELF++算法，其核心是将贪心算法的两个连续迭代的影响扩散同时计算. 另外，Zhou 等人［11］提出了UBLF 算法，该算法限制了每个节点的模拟上限，从而减少了第一轮节点选择的模拟次数.Cheng 等人［12］提出了一种静态贪心算法，该算法严格保证影响力扩散的亚模态性，从而提高组影响力模拟的速度. 而Ohsaka 等人［13］则引入了PrunedBFS 来加速蒙特卡洛模拟的过程. 然而，由于以上基于贪心算法的方法需要大量的蒙特卡洛模拟来估计节点影响力，因此效率较低且难以扩展到大规模社交网络. 因此，不建议使用这类方法来识别群体竞争影响力.
2. 2 基于路径分析的方法
该方法通过分析节点之间的路径结构信息来评估群体影响力. 其中，Chen 等人［14］提出了最大影响路径（Maximum Influence Path，MIP）的概念，用于表示从一个节点到另一个节点的影响力，并通过合并多个节点的影响路径来估计群体影响力. Gong 等人［1］提出了一种局部影响估计方法来近似群体影响力. Lu 等人［15］则通过计算节点之间的可达概率，利用递归方式估计群体影响力，并提出了3 种策略来提高计算效率. 然而，由于节点之间路径的复杂性，以上基于路径分析的方法通常无法考虑完整的路径信息，导致结果不准确. 考虑到本文要研究的群体竞争影响力识别问题会分析大量节点，且包含大量路径信息，为了确保结果的准确性，不建议使用以上基于路径分析的方法.
2. 3 基于中心性的方法
基于中心性的方法根据各种中心性计算节点的重要性，进而识别群体影响力. Kundu 等人［16］将社区结构与中心性结合，通过计算每个节点所属社区的总体中心性来近似节点的影响力，进而计算群体影响力. Jia 等人［3］在度中心性的基础上将节点的度重新定义为出度和入度，并提出了一个可调整的参数α 来调整出度与入度之间的相对权重，以适应不同场景的群体影响力识别. Ullah 等人［17］提出了一种局部全局中心性方法，该方法综合考虑了局部信息和全局信息来评估节点的影响力，从而识别群体影响力. 不同的中心性可以从不同的角度反应节点的影响力，以上基于中心性的方法多从单一中心性角度分析节点影响力后扩展到群体影响力，对节点分析不全面，且没有考虑影响力重叠问题，所以此类方法也不适用于本文所研究的群体竞争影响力问题.
2. 4 基于图表示学习的方法
图嵌入技术可以将高维图数据如节点、边、图等映射为低维向量，为后续的节点级、边级和图级任务提供丰富的信息. 社交网络是一种天然的图数据，近年来，越来越多的研究人员使用图嵌入技术进行社交网络分析. 例如，Zhao 等人［18］提出了InfGCN 模型，该模型结合了节点特征和网络结构信息来识别社交网络中有影响力的节点. Huang等人［19］提出的SDGNN 模型则考虑了平衡理论和地位理论，并重新设计了聚合方法和损失函数，能更好地学习符号有向图的嵌入表示. Cao 等人［20］提出的MuGNN 模型用于实体对齐任务，该模型通过多个通道学习两个知识图谱的嵌入，解决了不同网络结构的异质性问题. Chen 等人［21］提出了一个新的多级图卷积网络框架（MGCN），用于社交网络链路预测任务. 该框架同时考虑局部和超图级的卷积信息来学习网络嵌入，能捕捉更丰富的网络信息. Jia 等人［22］提出了SRFA-GRL 框架，通过子图重建来捕捉群体的分布，并提出了一种新的特征聚合方法来聚合群体特征. Kou 等人［23］引入了一种包含邻域特征的多头注意力回归模型，以提高节点影响识别的准确性。
这些研究都表明，使用GRL 可以有效地解决社交网络中的具体问题，并且优于传统方法. 这启发我们使用GRL 来解决组竞争影响力评估问题.
3 本文方法
3. 1 概述
在本节中，我们提出了一个基于GRL 的框架，用于识别社交网络中群体的竞争影响力. 所提框架的总体结构如图1 所示，它包含以下几个部分.
（1） 准备工作.（a）IC 仿真［25］：我们计算社交网络中每个节点的IC 值以获取节点的传播能力特征；
（b）特征提取：我们提取了社交网络中每个节点的多种特征，详见4. 2. 1 节.