todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Non-monotone Adaptive Submodular Maximization」で検索した結果

• Non-monotone Adaptive Submodular Maximization
  Non-monotone Adaptive Submodular Maximization Alkis Gotovos, Amin Karbasi, Andreas Krause IJCAI 2015 概要 これまでは単調だけ 非単調でも応用はあるので，1-1/e近似アルゴリズム作って実験 適応的な設定とは？ アイテムsの状態$$y_s$$が選択して初めて分かる 繰り返し アイテム選択 状態観測 状態$$\phi V \rightarrow \mathcal{Y}$$ 事前分布$$ p(\phi) $$は既知 観察$$\psi = \{(s_1, y_1), \ldots, (s_\ell, y_\ell)\}$$ $$ p(\phi ...
• 気になった論文
  ...ontinuous Non-monotone Submodular and DR-Submodular Maximization Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization Adversarially Robust Optimization with Gaussian Processes Stefanie Jegelka Sublinear Time Low-Rank Approximation of Distance Matrices Found Graph Data and Planted Vertex Covers Jon Kleinberg Do Less, Get More Strea...
• On Bisubmodular Maximization
  On Bisubmodular Maximization Ajit P. Singh, Andrew Guillory, Jeff Bilmes AISTATS 2012 概要 双劣モジュラ関数最大化問題を考える センサ配置・特徴選択への応用 単純双劣モジュラ $$ f 2^{2V} \to \mathbb{R} $$が単純双劣モジュラ$$ \iff $$ $$ f(A,B) + f(A ,B ) \geq f(A \cup A , B \cup B ) + f(A \cap A , B \cap B ) $$ NOTE 定義域がdisjointで無い g(S) = f(abs(S ∩ V1, S ∩ V2)) とかいう感じで書けるので、結構解ける $$ |A...
• Budgeted stream-based active learning via adaptive submodular maximization
  Budgeted stream-based active learning via adaptive submodular maximization Kaito Fujii, Hisashi Kashima NIPS 2016 概要 ブール型能動学習→ストリーム型能動学習 適応的劣モジュラ→この研究 問題定式化 オンラインの適応的劣モジュラ最大化 方策適応的劣モジュラ性 ストリーム・秘書設定での定数競合比アルゴリズム 動機づけ ラベルを手に入れるのにコストがかかる…スパムフィルタとか 能動学習 どのサンプルにラベルをつけるか決めたい ブール型…ラベルなしサンプル全体が既知 今回の設定=ストリーム型…1つずつ（メモリ制限も加味） 例 スパム、監...
• Maximizing Submodular Set Function with Connectivity Constraint: Theory and ...
  Maximizing Submodular Set Function with Connectivity Constraint Theory and Application to Networks Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai Research Center for Information Technology Innovation（資訊科技創新研究中心） National Tsing Hua University（國立清華大學） INFOCOM 2013 概要 ワイヤレスネットワークのルーターの設置問題 submodular関数で表せる さらにルーターは連結であるという制約を追加 この設定でも近似アルゴリズムが設計できる 1...
• 論文一覧
  ...r ... Non-monotone Adaptive Submodular Maximization IJCAI 2017 Robust Quadratic Programming for Price Optimization International Conference on Artificial Intelligence and Statistics AISTATS 2012 On Bisubmodular Maximization AISTATS 2018 Random Warping Series A Random Features Method for Time-Series Embedding International Workshop on Internet a...
• How to Influence People with Partial Incentives
  How to Influence People with Partial Incentives Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghadam WWW 2014 概要 今までのinfluence maximizationは二者択一だった 実際には中間があるので，そういうモデルを作ったよ 分数版は積分版との違い モデル 積分影響モデル(integral influence model) Mossel and Rochの提案 f_v 2^V→[0,1] 辺を含んだ集合関数 ...
• Stochastic Submodular Maximization: The Case of Coverage Functions
  Stochastic Submodular Maximization The Case of Coverage Functions Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2017 概要 確率的劣モジュラ最大化のための新しい手法を提案 まずは、被覆関数から 連続拡張をさらに緩和した問題を直接解いてから元に戻す 問題 目的関数 $$ f(S) = \mathbb{E}_{\gamma \sim \Gamma}[f_\gamma(S)] $$ 影響最大化なら、影響グラフからサンプルしたグラフ上で到達可能な頂点数 線形連続拡張 $$ F(\bm{x}) = \mathbb{E}...
• Risk-Sensitive Submodular Optimization
  Risk-Sensitive Submodular Optimization Bryan Wilder AAAI 2018 概要 確率的連続劣モジュラ関数のCVaR最大化 非凹なので大変だが1-1/e近似可能 集合上のポートフォリオを構築できます アルゴリズム 問題 $$ \max_{\vec{x}, \tau} \tau - \frac{1}{\alpha}\mathbb{E}_y[ [\tau-F(\vec{x},y)]^+ ] $$ 難しさ F(*,y)がxについて凹なら、CVaRは凹最適化 劣モジュラ（2階微分が非正）の場合、そんなことはない だけど、非負方向に凹（up-concave性） Frank-Wolfは使えるの？ 今の勾...
• Streaming Submodular Maximization: Massive Data Summarization on the Fly
  Streaming Submodular Maximization Massive Data Summarization on the Fly Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbas, Andreas Krause KDD 2014 概要 ストリーム設定の単調劣モジュラ関数最大化 ワンパスで1/2-ε近似 関数評価も無作為標本で近似 実験で爆速 アルゴリズム1 最適値$$ \texttt{OPT} $$を知っている $$ \alpha \texttt{OPT} \leq v \leq \texttt{OPT} $$ $$ \textbf{for } i = 1 \textbf{ to } n $$ ...
• Time Constrained Influence Maximization in Social Networks
  Time Constrained Influence Maximization in Social Networks Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng ICDM 2012 ※Wei ChenのTime-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Processとは独立らしい 概要 時間制限付きinfluence maximizationを提案 NP-hardだけどmonotoneかつsubmodular Influence Spreading Pathという速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• Word Alignment via Submodular Maximization over Matroids
  Word Alignment via Submodular Maximization over Matroids Hui Lin, Jeff Bilmes ACL-HLT 2011 概要だけ 単語アラインメント：単語対応をとる よくある制約はマトロイド制約で表せる 英語 $$ e_1, \ldots, e_I $$ 仏語 $$ f_1, \ldots, f_J $$ $$ E=\{1,\ldots,I\}, F=\{1,\ldots,J\} $$ 欲しい割り当て $$ A \subseteq = V = E \times F $$ E--Fの二部グラフのようなもの 制約 $$f_j$$には高々$$k_j$$単語しか割り当てない $$ |A \cap ...
• Influence Maximization in Social Networks When Negative Opinions May Emerge ...
  Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan SDM 2011 概要 商品の質が低かったらdisる人も出るよねーをモデル化 質をパラメータに含めたNegative Opinion付き positiveな人数が目的関数ならsubmodularは保たれる 速い手法を作って実験してみたよ Independent Cascade Mode...
• Time-Critical Influence Maximization in Social Networks with Time-Delayed ...
  Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process Wei Chen, Wei Lu, Ning Zhang AAAI 2012 概要 ICモデルは時間制限を設けないからダメ 締切＋時間の遅延付きモデルを考案 高速(?)アルゴリズムも提案して実験 Independent Cascade with Meeting events 遭遇確率 m(u,v) 伝搬確率 p(u,v) 各ステップtで、アクティブな頂点uは非アクティブな頂点に確率m(u,v)で遭遇する 一回目の遭遇において確率p(u,v)でアクティベーションが成功する これは一回だけ ...
• Influence Maximization with Viral Product Design
  Influence Maximization with Viral Product Design Nicola Barbieri, Francesco Bonchi SDM 2014 概要 製品設計も考えた情報拡散LTモデル 同じアイテムでも特徴が違うとσが変わる 頂点+特徴の選択が必要 提案モデルF-TMの学習手法 最適化アルゴリズムを頑張る share-of-choice (SoC)問題 u_{f,l}^i 人i，特徴f，レベルlについてその効果 負もありうる 各人iについて Σ_fΣ_l x_{f,l} u_{f,l}^i ≧ h_i ならiはこの製品を採用する x_{f,l}は0-1変数，これを決定するのが問題 fe...
• Maximizing Social Influence in Nearly Optimal Time
  Maximizing Social Influence in Nearly Optimal Time Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier first author有名？ SODA 2014 概要 influence maximization(IC model)の近似アルゴリズム 今までみたいに、各ノードからの到達可能ノード数や確率を求めるんじゃない 逆に考える 探索するノードの数をほぼ線形にboundしても良い解が出てくることを保証できる 提案手法 逆グラフを作る ノードをランダムに選び、逆グラフ上でシミュレートする v「に」伝搬する頂点を選んでいることに等しい ...
• Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
  Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy NIPS 2016 概要 Joint M-best-diverse labeling 問題をパラメトリック劣モジュラ最小化問題に帰着して解く 動機づけ・問題定式化 2値画像のノイズ除去・画像分割 エネルギー関数最小化として定式化 エネルギー関数 データ項= 「入力と出力の近さ」＋平滑化項=「出力の滑らかさ」 例 $$ E(y) = \sum_{v \in V}b_v [x_v \neq y_v] + ...
• StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
  StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng In CIKM 2013 ArXiv 2012 概要 実は今までのMonte-Carloは間違っていた！ 毎回ランダムグラフを作っているのが問題 そのせいで莫大な試行回数が要求される 俺が最強のMonte-Carloアルゴリズムを提案するぜ！ ランダムグラフを使いまわす Rは1/100に減った StaticGreedy R回ループ 各辺を割り当てられた確率に応じて消す...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 Parameterized Algorithms influence maximizati ICDM KDD AAAI k-means SCG SODA nearest neighbor IJCAI VLDB clustering coefficie random walk WWW STOC SIGMOD quasi-clique NIPS ICML SDM PNAS JMLR information diffusio triangle I/O-efficient algori Econometrica SCC streaming algorithm JEA ALENEX graph partitioning spectral clustering causality t...
• Influence Blocking Maximization in Social Networks under the Competitive ...
  Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Xinran He, Guojie Song, Wei Chen, Qingye Jiang SDM 2012 概要 Competitive Linear Threshold モデルを考えたよ 目的関数は自分の最大化じゃなくて，相手の最大化だよ そうするとこのモデルではsubmodularだよ 目的関数の計算が大変なのでPMIAっぽいものを作った Competitive Linear Threshold Model 各辺には2つの重みw+とw-がある 各頂点の閾値も2つθ+とθ- 状態はin...
• Sparsification of Influence Networks
  Sparsification of Influence Networks Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, Antti Ukkonen KDD 2011 概要 Yahoo! Research, Barcelonaの方々 尤度最大化という観点で辺をk本残す問題を提案 近似がNP-hard 最適解は頑張ってDPできる 貪欲アルゴリズムを提案（最適解に近い） 実験したら最強 influence maximizationにも使えるよ！ モデル とりあえず，トレースから確率を推定したい カスケードのトレースは頂点と時刻のペアの列とする (v,t)につい...
• Maximizing the Spread of Cascades Using Network Design
  Maximizing the Spread of Cascades Using Network Design Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David Shmoys, William Allen, Ole Amundsen, William Vaughan UAI 2010 We apply our model to a sustainability problem that is part of an ongoing collaboration with The Conservation Fund to optimize the conservation of ...
• Random-walk domination in large graphs: problem definitions and fast solutions
  Random-walk domination in large graphs problem definitions and fast solutions Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng CoRR 多分KDDに出した？ 概要 2種類ランダムウォーク支配問題、というものを考えた ソーシャルネットワーク上にアイテムを配置したり、色々なアプリケーションがある どの頂点からも長さLのランダムウォークによるヒッティングタイムが短い 長さLのランダムウォークがターゲットノードに到達する確率が高い DPベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
• Influence Maximization in Near-Linear Time: A Martingale Approach
  Influence Maximization in Near-Linear Time A Martingale Approach Youze Tang, Yanchen Shi, Xiaokui Xiao SIGMOD 2015 概要 TIMInfluence Maximization Near-Optimal Time Complexity Meets Practical Efficiencyから更に改善しました 直接最適値の下限を推定するよ！ TIMよりめっちゃ速くなった TIMの問題点 最悪時には下限が最適値よりn/k倍悪い 下限の計算自体が結構（シード選択段階よりも）遅い 提案手法 Influence Maximization via Martingales (IMM)...
• Maximizing Influence in a Competitive Social Network: A Follower's Perspective
  Maximizing Influence in a Competitive Social Network A Follower s Perspective Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen ICEC 2007 概要 既に敵対するカスケードが広がっている時に，自分はどうシード集合を選択するか 2つのモデルを提案 NP-hardだけど1-1/e近似可能 モデル Aが自分で，Bが敵 I_B すでにBのシード集合 σ(I_A | I_B)が最大となるI_Aを選びたい ベースはICモデルと同じランダムグラフを考える E_a 残った辺 カスケードの仕...
• Topic-aware Social Influence Propagation Models
  Topic-aware Social Influence Propagation Models Topic-aware Social Influence Propagation Models Nicola Barbieri, Francesco Bonchi, Giuseppe Manco Yahoo! Research Barcelona ICDM 2012 概要 トピックを考慮したモデルにICとLTを拡張 期待値最大化でパラメータを見積もる 上のモデルは大変なので，ちょっとパラメータ数を減らしたモデルを考案 実験して普通のICより良かった Topic-awareモデル Topic-aware Independent Cascade Model (TIC) z...
• Simulated Annealing Based Influence Maximization in Social Networks
  Simulated Annealing Based Influence Maximization in Social Networks Qingye Jiang, Guojie Song, Cong Gao, Yu Wang, Wenjun Si, Kunqing Xie In AAAI 2011 概要 influence maximizationに対する初の焼きなましベースアルゴリズム influence spreadを高速に近似計算 アルゴリズム SA based 適当にseed setを変更するだけ SAEDV (Expected Diffusion Value) Aによりactivateされるノード数の期待値は $$ |A| + \sum_{v \in N^{o...
• Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...
  Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks Wei Chen, Chi Wang, Yajun Wang In KDD 2010 概要 MIAモデルというのを使ってinfluence maximizationを高速化 アルゴリズム maximum influence paths (MIP) v- uへの伝搬は最短経路だけを考える しきい値θ以下の伝搬は無視する Dijkstraの途中で打ち切る maximum influence arborescence model influence spreadを以下で近似 $$ ...
• Optimizing Budget Allocation Among Channels and Influencers
  Optimizing Budget Allocation Among Channels and Influencers Noga Alon, Iftah Gamzu, Moshe Tennenholtz WWW 2012 概要 最適予算配分問題の定式化 二部グラフ的な広告マーケティングを広告媒体視点と顧客視点のそれぞれでモデル化 ポイント 予算の配分という概念，今までは頂点を選ぶだけだった 影響の伝播は扱わない，予算の配分が主眼だから hardnessを解析 影響モデル G=(S,T,E) Sはソース，Tはターゲット，Eは辺集合 c_s (s∈S) 整数容量 B 予算 各ソースsに0以上c_s以下の整数予算b_sを割り当てる ...
• Influence maximization in complex networks through optimal percolation
  Influence maximization in complex networks through optimal percolation Flaviano Morone, Hernán A. Makse Nature 2015 概要 頂点を削除して最大の連結成分を最小化したい 強影響力頂点抽出，immunization，コミュニティ検出 既存手法…ヒューリスティクス 本手法 最適化問題 ある種の貪欲アルゴリズム 輪郭 最適パーコレーション 固有値の最小化問題 上を解く 最適パーコレーション $$ \nu_i $$の計算
• A Novel and Model Independent Approach for Efficient Influence Maximization ...
  A Novel and Model Independent Approach for Efficient Influence Maximization in Social Networks Hemank Lamba, Ramasuri Narayanam WISE 2013 概要 influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!! sparsificationするよ！ 精度を落とさずに数倍高速化 提案手法 ある頂点の近傍のスコアを出す スコアの出し方 色々な基準を大量に持ってくる 適当に重みを計算して足し合わせる スコアの大きい近傍をdeg(i)^eだけ残す 0 =e =1 実験 ...
• Efficient Location-Aware Influence Maximization
  Efficient Location-Aware Influence Maximization Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, Wen-Syan Li SIGMOD 2014 概要 位置を考慮した影響最大化 Foursquareとか クエリは領域とk 2つの手法を提案 1-1/e近似 expansion-based assembly-based それでも遅いのでさらに2手法 ε(1-1/e)近似 bound-based hint-based 問題定式化 vの位置は二次元座標(x,y) 情報拡散モデルはICモデル クエリ Q=(R,...
• Online Topic-Aware Influence Maximization
  Online Topic-Aware Influence Maximization Shuo Chen, Ju Fan, Guoliang Li, Jianhua Feng, Kian-lee Tan, Jinhui Tang VLDB 2015 概要（だけ） Online Topic-aware Influence Maximization Queries, Real-time Topic-aware Influence Maximization Using Preprocessingの後続研究 トピック分布$$ \mathbf{\gamma} $$とシードサイズ$$ k $$がもらえるので、良いやつを返す MIAベースの手法 その場で木を構成するのはダルすぎるので、上限をいい感じに計算して、余分な頂点を枝刈りする ...
• Nonnegative Spectral Clustering with Discriminative Regularization
  Nonnegative Spectral Clustering with Discriminative Regularization Yi Yang, Heng Tao Shen, Feiping Nie, Rongrong Ji, Xiaofang Zhou AAAI 2011 概要（だけ） よくあるクラスタリング手法 どの要素がどのクラスタに属するかを表すindicator matrixで目的関数を表現 そのままだと解けないので{0,1}から緩和する 固有値分解をココらへんで使う 頑張って解く ±混ざっている {0,1}にする 何が問題？ 混合符号の行列がもらえた時にそれを量子化する簡単な方法が無い EM-like / k-means / spe...
• Scalable Influence Maximization in Social Networks under the Linear ...
  Scalable Influence Maximization in Social Networks under the Linear Threshold Model Wei Chen, Yifei Yuan, Li Zhang In ICDM 2010 概要 LTモデル用の高速アルゴリズム LTモデルでのσの計算は#P-hard DAGをとってきて、それの上で高速計算 #P-hardness 基本は単純経路の数え上げからの帰着 アルゴリズム LTモデルからlive-edge graphを考える eはw_eの確率で残ると書いてあるが、本当だろうか…？ Kempeのではもっと複雑なことをしていた こうすると、random graph上でのreacha...
• Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
  Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang WSDM 2013 概要 voter modelを拡張 元はunsigned network signed networkにした 味方とは同じ意見（色） 敵とは違う意見（色） 最初の色の分布を与えた時の挙動を解析（面白い） このモデルでinfluence maximization ある意味で簡単 確率的振舞を計算するのが超大変 Voter ...
• CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in ...
  CINEMA Conformity-Aware Greedy Algorithm for Influence Maximization in Online Social Networks Hui Li, Sourav S Bhowmick, Aixin Sun EDBT 2013 Contribution conformity-aware cascade model(c^2 model) の提案 mag-list というデータ構造 CINEMA (Conformity-aware INfluEnce MAximization) 部分グラフに分割する←a novel approach ??? 何が問題なの？ ぶっちゃけよく分からん とにかく普通のIC・LTモデルはダメでconfo...
• A Data-Based Approach to Social Influence Maximization
  A Data-Based Approach to Social Influence Maximization Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan VLDB 2012 概要 Data-Basedの意味：伝播確率をデータから推定するのではなく、直接σを推定する Credit Distribution Modelというモデルを提案 NP-hardでsubmodular σ_CDでの最大化が良いし速い！！ 何でこんなことになったのか いろんなモデルを使って実験してみよう weighted cascade model trivalency model uniform IC model EMアルゴリズ...
• The complexity of influence maximization problem in the deterministic linear ...
  The complexity of influence maximization problem in the deterministic linear threshold model Zaixin Lu, Wei Zhang, WeiliWu, Joonmo Kim, Bin Fu Journal of Combinatorial Optimization 2012 概要だけ linear threshold modelのしきい値を固定したバージョンを考える 近似の難しさ しきい値を固定するとσは多項式時間で求められる 当たり前。なぜO(n^2)で求めている？ 何でこんなことをしたのか若干謎
• IRIE: Scalable and Robust Influence Maximization in Social Networks
  IRIE Scalable and Robust Influence Maximization in Social Networks Kyomin Jung, Wooram Heo, Wei Chen In ICDM 2012 概要 Influence maximizationを超高速に求めるアルゴリズムを開発 しかもロバストに良い解を発見する アルゴリズム $$ \sigma(S \cup \{v\}) - \sigma(S) $$を次で近似する $$ r(v) = (1-AP_S(v))\left[ 1+\alpha \sum_{vu}p_{vu}r(u) \right] $$ AP_S(v) Sがvをactivateする確率 $$ AP_S(v) - \sum_{s \in ...
• Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study
  Debunking the Myths of Influence Maximization An In-Depth Benchmarking Study SIGMOD 2017 概要だけ 提案されたきた影響最大化の手法は本当に効率的なのか？ 比較手法 CELF, CELF++, TIM+, IMM, PMC, StaticGreedy, LDAG, SIMPATH, EaSyIM, IRIE, IMRANK 徹底的な実験を決行 個々の論文の著者の主張は間違っている！！ • PMC [39] PMC establishes itself as the only technique that consistently provides high spread and scales for bot...
• Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
  Influence Maximization Near-Optimal Time Complexity Meets Practical Efficiency Youze Tang, Xiaokui Xiao, Yanchen Shi SIGMOD 2014 概要 RIS (SODA 14)を実用的に改良するよ！ 提案手法 TIM, TIM+ サンプリング回数をいい感じにしました。 $$ O(\epsilon^{-2}(k+\ell)(n+m)\log n) $$時間 ヒューリスティックで更に効率改善→TIM+ triggeringモデルにも拡張したよ 提案手法 Two-phase Influence Maximization (TIM) フェーズ1：サンプリング回数θを...
• Robust Influence Maximization (Lowalekar+)
  Robust Influence Maximization (Lowalekar+) Meghna Lowalekar, Pradeep Varakantham, Akshat Kumar AAMAS 2016 概要だけ 最大後悔最小化する頂点集合が欲しい Robust Influence Maximization (He-Kempe) Robust Influence Maximization (Chen+)とだいたい同じ サンプリングの方法だとかアルゴリズムを提案 貪欲と比較しました～ 2ページなので良く分からず AAMAS 影響最大化 頑健最適化 2017/10/02
• Real-time Targeted Influence Maximization for Online Advertisements
  Real-time Targeted Influence Maximization for Online Advertisements Yuchen Li, Dongxiang Zhang, Kian-Lee Tan VLDB 2015 概要だけ Keyword-Based Targeted Influence Maximization トピックつきのモデル キーワード集合Tとシードサイズkが与えられる Tによって、頂点の重みが変わる(TF-IDFに基づいた奴)、Tに関して線形な感じ $$ \phi(v,T) = \sum_{w \in T}\mathrm{tf}_{w,v} \cdot \mathrm{idf}_w $$ if_wvはユーザvのワードwへの嗜好 だから"targeted...
• IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks
  IMGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks Mo Li, Zhenjiang Li, Longfei Shangguan, Shaojie Tang, and Xiang-Yang Li TPDS 2014 概要 influence maximizationのGPUを取り入れたよ 既存手法の60倍速くなったよ IMGPU Bottom-Up Traversal Algorithm (BUTA) 元のグラフから沢山ランダムグラフを作る 各頂点のレベルを定義 末端までの最長距離 レベルで並列化するよ SCC内は全部同じなのでつぶすよ σ_S(u) =...
• Cost-effective Outbreak Detection in Networks
  Cost-effective Outbreak Detection in Networks Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance KDD 2007 概要 outbreak detection問題を考える 色々あるけど目的関数はsubmodularになるのが多い 貪欲アルゴリズムで近似だ！ しかもsubmodularityを活かした高速化手法+online boundも考案 安定のLeskovecといったところか Outbreak detection モチベーション グラフ上でのカスケードを検知したい！ 水質汚染 ...
• ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
  ASIM A Scalable Algorithm for Influence Maximization under the Independent Cascade Model Sainyam Galhotra, Akhil Arora, Srinivas Virinchi, Shourya Roy WWW 2015 概要だけ 当時最強のTIMはメモリ消費がやばいので、新しいアルゴリズムを作ったよ！ アルゴリズム Simpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復...
• Scalable and Parallelizable Processing of Influence Maximization for ...
  Scalable and Parallelizable Processing of Influence Maximization for Large-Scale Social Networks Jinha Kim, Seung-Keol Kim, Hwanjo Yu 浦項（ぽはん）工科大学校 In ICDE 2013 概要 並列化可能なアルゴリズム 競技相手はPMIA 質はCELF並、PMIAより良い 速度はPMIAより速い 提案手法 Independent Path Algorithm(IPA) 経路を指定したらそれを使う確率は全部かければ良い グラフがもらえた 有るノードからtraverseして木っぽくパスを広げる（同じ頂点がいくつかある...
• Holistic Influence Maximization: Combining Scalability and Efficiency with ...
  Holistic Influence Maximization Combining Scalability and Efficiency with Opinion-Aware Models Sainyam Galhotra, Akhil Arora, Shourya Roy SIGMOD 2016 概要 新しいモデル opinion-cum-interaction 高速アルゴリズム OSIM：OI用 EaSyIM：普通の影響最大化用 5%くらい質が悪いけど、良いよ！ モデル 省略します 　　,r´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
• Information Propagation Game: a Tool to Acquire Human Playing Data for ...
  Information Propagation Game a Tool to Acquire Human Playing Data for MultiPlayer Influence Maximization on Social Networks Hung-Hsuan Chen, Yan-Bin Ciou, Shou-De Lin KDD 2012 概要だけ アプリケーションの話だったでござる competitiveなモデル 交互に頂点を選んで行ったり，先手がk頂点選んでから後手がk頂点選ぶとか こういうのをゲームのアプリケーションとして色々やってみる 特に面白い点は無かった KDD 影響最大化 情報拡散 2014-06-18 17 17 19 (Wed)
• @wiki全体から「Non-monotone Adaptive Submodular Maximization」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索