影響最大化（貪欲法・劣モジュラ性）

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：閾値モデル・情報カスケード・固有ベクトル中心性とPageRank　|　関連：拡散と感染症モデル（SI・SIS・SIR）

要点（BLUF）

影響最大化：予算 $k$ 個のシードを選んで、拡散の最終的な広がり（期待波及数）を最大にする組合せ最適化問題。
厳密解は NP困難。だが影響関数 $\sigma(S)$ は単調・劣モジュラなので、貪欲法が $(1-1/e)\approx 0.63$ の近似保証を持つ（Kempe–Kleinberg–Tardos）。
「最も波及する $k$ 人」は単純な次数トップ $k$ とは限らない（重複・冗長を避ける必要がある）。応用＝口コミマーケはマーケへ。

概念：誰を起点にすれば最も広がるか

予算は限られています。インフルエンサー5人にだけ新製品を渡せるなら、誰に渡せば最も広く拡散するか。これが影響最大化。単に次数トップ5を選ぶと、彼らの影響圏が重なって無駄が出ることがあります。最適なシード集合を選ぶこの問題は組合せ的に難しい一方、美しい数学的構造（劣モジュラ性）のおかげで実用的な近似が効きます。応用としての口コミマーケティングはマーケのturf — ここでは最適化の数理を扱います。

数式：影響関数と劣モジュラ性

シード集合 $S$ から拡散モデル（独立カスケード等）で最終的に活性化するノード数の期待値を影響関数 $\sigma(S)$ とします。目標は

\max_{|S| \leq k} \sigma(S)

この $\sigma$ は2つの良い性質を持ちます。

単調性： $S \subseteq T \Rightarrow \sigma(S) \leq \sigma(T)$ （シードを足せば波及は減らない）
劣モジュラ性（収穫逓減）： $S \subseteq T$ のとき、任意の $v$ について

\sigma(S \cup \{v\}) - \sigma(S) \;\geq\; \sigma(T \cup \{v\}) - \sigma(T)

「同じノードを加える価値は、既存シードが多いほど小さい」。

Nemhauser の定理より、単調・劣モジュラ関数の貪欲法（毎回、限界利得が最大のノードを1つずつ足す）は最適値の $(1-1/e)\approx 63\%$ 以上を保証します。NP困難な問題に対する、保証付き近似です。

コードで確認

import networkx as nx
import numpy as np

def ic_spread(G, seeds, p, seed, runs=100):
    """独立カスケードの期待波及数（モンテカルロ）"""
    rng = np.random.default_rng(seed)
    totals = []
    for _ in range(runs):
        active = set(seeds); frontier = set(seeds)
        while frontier:
            nxt = set()
            for u in frontier:
                for v in G.neighbors(u):
                    if v not in active and rng.random() < p:
                        nxt.add(v)
            active |= nxt; frontier = nxt
        totals.append(len(active))
    return np.mean(totals)

G = nx.barabasi_albert_graph(300, 2, seed=7)
p, k = 0.1, 5

# 貪欲法：限界利得が最大のノードを1つずつ
greedy = []
for _ in range(k):
    best, best_gain = None, -1
    for v in G.nodes():
        if v in greedy: continue
        g = ic_spread(G, greedy + [v], p, seed=42)
        if g > best_gain:
            best_gain, best = g, v
    greedy.append(best)

topk = [v for v, _ in sorted(G.degree(), key=lambda x: -x[1])[:k]]
rng = np.random.default_rng(1)
rand = list(rng.choice(list(G.nodes()), k, replace=False))

print(f"貪欲法     {greedy} → 期待波及 {ic_spread(G, greedy, p, 123):.1f}")
print(f"次数トップ{k}         → 期待波及 {ic_spread(G, topk, p, 123):.1f}")
print(f"ランダム{k}個         → 期待波及 {ic_spread(G, rand, p, 123):.1f}")

実行結果：

貪欲法     [1, 0, 11, 28, 30] → 期待波及 21.4
次数トップ5         → 期待波及 21.5
ランダム5個         → 期待波及 9.0

賢いシード選び（貪欲法・次数トップ）は、ランダム選択の約2.4倍の波及を達成。このスケールフリーグラフでは貪欲法と次数トップがほぼ並ぶ — ハブの影響が支配的だからです。ただし一般のネットワーク（影響圏が重なる構造）では、貪欲法が冗長を避けて次数トップを上回り、しかも理論保証を持つ点が強みです。

数式の直観的意味

劣モジュラ性は「収穫逓減」、つまり「もう十分カバーした領域に、似たノードをもう1人足しても価値が薄い」という直観の数式化です。次数トップ $k$ を選ぶと、ハブ同士の影響圏が重なって2人目以降の限界利得が下がる。貪欲法は毎回「まだカバーできていない領域に最も効くノード」を選ぶので、自然に冗長を避けます。 $(1-1/e)$ という保証は、この「毎ステップ残りギャップの一定割合を埋める」性質から導かれます。固有ベクトル中心性やPageRank（固有ベクトル中心性とPageRank）は高速なシード候補のヒューリスティクスとして使えます。

⚠️ よくある誤解・落とし穴

次数トップ $k$ が最適とは限らない：影響圏が重なると冗長。貪欲法は限界利得で選ぶので重なりを避けます。
影響関数の評価が重い： $\sigma(S)$ はモンテカルロ推定が必要で計算コスト大。CELF など劣モジュラ性を使った高速化があります。
$(1-1/e)$ は近似比であって誤差ではない：最適の63%以上を保証するのであって、誤差が37%という意味ではありません。実際はもっと良いことが多い。

対応シミュレーション

本文のコードがそのまま検証用です。口コミの応用はマーケティングへ（薄リンク）。