.png){kind=icon}
返回
Influence maximization: a local branching algorithm for solving the positive influence dominating set problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10732-026-09595-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
正影响支配集问题（PIDS）是著名的支配集问题的一个变体。它涉及在一个给定的图G = (V, E)中选择一个顶点子集，使得其余顶点被该子集正影响支配。更正式地，顶点v(i) ∈ V被称为被正影响支配，如果其至少有ρ deg(G)(v(i))比例的邻居属于所选子集，其中deg(G)(v(i))是顶点v(i)的度数，且0 < ρ < 1为影响因子。目标是识别最小的正影响支配子集。该问题在一般图上为NP难问题，且在特定图类上仍计算复杂。本文提出了一种基于局部分支方法并结合CPLEX数学规划求解器的有效算法，特别用于增强强化并生成良好部分解。同时，为保障解的多样性，我们开发了一种破坏-重建贪心启发式方法以探索先前未访问的子空间。我们在不同规模的现实基准实例（包括大规模图）上进行了广泛实验，并与五种现有最先进求解方法进行比较。实验结果表明，所提方法能在合理计算时间内获得高质量解，凸显其在高效求解PIDS方面的性能。
Keyword:
Social network
Local Branching
Destructive-constructive heuristic
Dominating set
Positive influence dominating set
期刊
J
IF:
1.4
论文数:
30
被引数:
1.3K
机构
引用论文
An Improved Greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks.png)
Algorithms
OAAI
AlgorithmsIF0
OAAI分享收藏分享收藏
Minimum positive influence dominating set and its application in influence maximization: a learning automata approachAPPLIED INTELLIGENCE
APPLIED INTELLIGENCEIF3.5
PREAI
分享收藏Finding a Weighted Positive In uence Dominating Set in E-learning Social Networks寻找E-learning社交网络中的加权正向影响支配集OAAI
OAAI分享收藏分享收藏
查看更多内容