グラフクラスタリングを用いた影響最大化問題のための新しいアルゴリズムフレームワーク

グラフでモデル化されたソーシャルネットワークを考慮した場合、影響最大化問題の目的は、拡散プロセスを通じてアクティブな頂点の数を最大化するk個の頂点を見つけることです。この拡散には線形閾値モデルが考慮されます。クラスターグリーディと呼ばれる新しいアルゴリズムが、影響最大化問題を解決するために提案されています。クラスターグリーディアルゴリズムは、元のノードの集合を小さな部分集合（クラスター）に分 partitionし、各部分集合によって誘導されたサブグラフにシンプルグリーディアルゴリズムを適用し、整数線形計画を解くことで各クラスターのシードセットの組み合わせからシードセットを取得します。このアルゴリズムは、拡散関数のサブモジュラリティ特性を探索することでさらに改善されます。実験結果は、クラスターグリーディアルゴリズムが、ワッツ–ストロガッツのランダムグラフに対して、平均してシンプルグリーディアルゴリズムよりも高い影響の広がりと低い実行時間を提供することを示しています。