摘要： 用户影响力度量是影响力最大化问题的核心，与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标，其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高，局部性指标通常忽略或弱化了网络中的自环和多边现象，导致对节点影响力的度量不全面，限制信息最终传播范围。结合三度分隔原理，提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象，根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域，使用节点在局部域内的影响力近似其在全局范围内的影响力，并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子，根据重叠比因子决定是否将此候选种子节点选作种子节点，控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明，与MaxDegree、PageRank等算法相比，该算法能有效识别高影响力节点群体，扩大信息传播范围，且具有较低的时间复杂度。

关键词: 影响力最大化, 局部影响力, 全局影响力, 三度分隔, 影响力重叠

Abstract: Measures of user influence are at the core of the influence maximization problem.As these measures relate to network topology, they may be classified as global indicators or local indicators.Global indicators rely on the complete network topology to calculate the influence of nodes, and incur a high time complexity.In contrast, local indicators generally ignore or weaken the self-loop and multilateral phenomena in the network, resulting in an incomplete measurement of the influence of nodes, which affects the final dissemination range of information.Using the principle of three degrees of separation, an influence maximization algorithm based on local domain is proposed in this study.This algorithm first constructs a generated graph by making full use of the edges, starting at and ending with the same interconnected nodes.Then, it generates a local domain for each node and approximates each node's global influence, calculated by the topology of its local domain.Finally, the algorithm conducts seed selection by considering the influence of each node, as well as the influence overlap ratio factor of a seed set.Experimental results on real datasets show that, compared with algorithms such as MaxDegree and PageRank, the proposed algorithm can effectively identify high-influence node groups, improve the scope of information dissemination, and incur lower time complexity.

Key words: influence maximization, local influence, global influence, three degrees of separation, influence overlap

中图分类号: 

• TP393