SuperAPI AI 工具集

algo-net-influence

数据与分析

查看项目

更新于 10-15 20:07

技能介绍

用途:在给定网络与扩散模型下,选出 k 个种子节点以最大化预期信息传播范围,适用于病毒式营销选种子用户、固定预算下最大化传播、对比不同选种策略(度排序、贪心、随机)。

主要能力:支持独立级联(每条边一个概率)与线性阈值(每个节点一个阈值)两种扩散模型;采用带惰性评估的贪心算法(CELF),利用子模性跳过不必要的评估,相比朴素贪心可获约 700 倍加速;用蒙特卡洛模拟估计边际增益;输出种子集合、预期传播量及与随机、top-k 度、top-k PageRank 等基线的对比。

使用方式:先构建网络图,选择扩散模型,设定 k 与传播概率;初始化种子集 S 为空,对候选节点用蒙特卡洛(R=10000 次)估计边际增益 σ(S∪{v})-σ(S),选增益最高者加入 S,CELF 复用先前边际增益、仅在上界超过当前最优时重新评估,重复至 |S|=k;随后与基线对比验证,最后返回种子集、预期传播量与对比结果。输出为 JSON,含 seeds(节点、边际增益、选择顺序)、expected_spread、baselines 与 metadata(k、模型、模拟次数、节点数)。

适用场景:社交网络选种子、预算受限的传播最大化、策略对比。不适用于测量已有影响力(应用中心性指标)或社区结构分析(应用社区发现)。

限制与注意:问题为 NP-hard,贪心仅有 (1-1/e)≈63% 近似保证;蒙特卡洛存在方差,R=1000 时约 5% 波动,比较接近候选时建议 R=10000 以上;IC 与 LT 会产生不同最优种子集;真实边概率通常未知,常用均匀(p=0.01-0.1)、按入度倒数加权或从级联数据学习;即使有 CELF,百万级节点仍需 IMM、TIM+ 等草图近似方法。k=1 时选个体传播最高节点;k 超过社区数时每社区一个种子更优;极稀疏图传播量普遍很小。