todo314 @ ウィキ
todo314 @ ウィキ

Real-time Topic-aware Influence Maximization Using Preprocessing

todo314 @ ウィキ内検索 / 「Real-time Topic-aware Influence Maximization Using Preprocessing」で検索した結果

検索 :
  • Online Topic-Aware Influence Maximization
    ... Queries, Real-time Topic-aware Influence Maximization Using Preprocessingの後続研究 トピック分布$$ \mathbf{\gamma} $$とシードサイズ$$ k $$がもらえるので、良いやつを返す MIAベースの手法 その場で木を構成するのはダルすぎるので、上限をいい感じに計算して、余分な頂点を枝刈りする $$ \epsilon(1-1/e) $$近似の中身 下限と上限を使って良さげな頂点集合があれば即座に終了 (今のi頂点)∪(候補のk-i頂点) 基本的にはごちゃごちゃ頑張るだけ VLDB 影響最大化 2017/09/20
  • Real-time Topic-aware Influence Maximization Using Preprocessing
    Real-time Topic-aware Influence Maximization Using Preprocessing Wei Chen, Tian Lin, Cheng Yang CSoNet 2015 概要 トピックモデルで重みがクエリで高速影響最大化 手法1 実は単一トピックと考えて答えてもよさ気 手法2 影響拡散の増分を少し真面目に考える 実験の結果，マイクロ秒で返答 問題 $$ p_i(u,v) $$ トピックiに関する辺(u,v)の確率 クエリ$$ I=(\lambda_1, \lambda_2, \ldots, \lambda_2) $$ 辺確率$$ p(u,v) = \sum_i \lambda_i p_i(u,v) $$で影響最大化 ...
  • 論文一覧
    ...ト広告 Real-time Targeted Influence Maximization for Online Advertisements VLDB 2015 Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret VLDB 2015 Revenue Maximization in Incentivized Social Advertising VLDB 2017 疎化・粗大化 Sparsification of Influence Networks Fast Influence-based Coarsening for Large Networks 予測 Prediction of Informa...
  • 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...
  • Real-Time Influence Maximization on Dynamic Social Streams
    Real-Time Influence Maximization on Dynamic Social Streams Yanhao Wang, Qi Fan, Yuchen Li, Kian-Lee Tan VLDB 2017 概要 クエリ Stream Influence Maximization sliding windowモデルで考える Influential Checkpoints 途中途中で結果をとっておいて ε-近似 Sparse Influential Checkpoints チェックポイントの数が多すぎるので、対数個くらいにまで減らす (log N)/β個で、ε(1-β)/2-近似 問題定式化 行動 $$ a_t = \langle...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • Online Topic-aware Influence Maximization Queries
    Online Topic-aware Influence Maximization Queries Cigdem Aslay, Nicola Barbieri, Francesco Bonchi, Ricardo Baeza-Yates Yahoo Labs Barcelona EDBT 2014 概要 トピック付き影響最大化クエリ アイテム毎にトピックの重みが付いている 少量のクエリに対する答えを索引にしておく 問題定義 p_e^z トピックzに対する辺の確率 γ_i アイテムiに対するトピックの重みベクトル アイテムiのベクトルは p^i = Σ_z γ^z*p^z アイテム毎に確率が変わるけど，その上で影響最大化 枠組み H ...
  • 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)...
  • 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)でアクティベーションが成功する これは一回だけ ...
  • 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...
  • 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...
  • 気になった論文
    ...dates for Real-time Story Identification best paper Truss Decomposition in Massive Networks k-truss VLDB 2013 ✔Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation FastPPV 逐次的に精度を改善する手法 Efficient SimRank-based Similarity Join Over Large Graphs VLDB 2014 Toward a Distance Oracle for Billion-Node Graphs ...
  • On Approximation of Real-World Influence Spread
    On Approximation of Real-World Influence Spread Yu Yang, Enhong Chen, Qi Liu, Biao Xiang, Tong Xu, Shafqat Ali Shad 中国科学技術大学 In PKDD 2012 概要 influenceの計算を近似+反復計算で p_v~Σp_uv*p_u．これをガウスザイデル p_v=1-Π(1-p_u*p_uv)はちゃんとしてる 嘘でした これに加えてヒューリスティクスでちょっと収束速めている アルゴリズム SSSbyStep ↑に書いた式で近似 GSbyStep 線形系で近似 SSSの簡易版 行列で表されるので、ガウス...
  • 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アルゴリズ...
  • 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,...
  • Efficient Influence Maximization in Social Networks
    Efficient Influence Maximization in Social Networks Wei Chen, Yajun Wang, Siyu Yang In KDD 2009 概要 Wei Chen 劇場の始まりっぽい influence maximization のアルゴリズムを2つ提案 greedy based algorithm の高速化 ヒューリスティックによるinfluence spreadの近似 アルゴリズム NewGreedyIC seedを選ぶためにグラフをR=20000個作る Sから到達可能なノードは省く vから到達可能なノード数を計算、これがmarginに相当 これの計算は自明ではないが論文ではlinearでできると...
  • Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
    Maximizing Influence in an Ising Network A Mean-Field Optimal Solution Christopher W. Lynn, Daniel D. Lee NIPS 2016 概要 Isingモデル上の影響最大化 意見＝スピン、外部影響＝外部磁場、影響力＝J 相互作用の反復による意見の「平衡」状態 平均場近似で解く 外部磁場に対して滑らかかつ凹になる十分条件 平均場の安定非負定常分布の存在に関する条件 実験もしたよ 問題定式化 Ising influence maximization $$ \Pr[\sigma_i(t+1) \mid \sigma(t)] = \frac{\exp\Bigl( \...
  • Influence Maximization in Dynamic Social Networks
    Influence Maximization in Dynamic Social Networks Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, Xiaoming Sun ICDM 2013 概要 influence max.の動的グラフ版を考える 現実的設定で、どこの頂点をprobeし直せば良いかを問題とする b頂点だけ更新できる influence spreadのずれがでかそうな頂点を頑張って計算する 実験の結果ベースラインよりかなり良かった 問題設定 G^t 時刻tでのグラフ b probeできる頂点数 b頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい ...
  • 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 ...
  • 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を以下で近似 $$ ...
  • 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 ...
  • Efficient influence spread estimation for influence maximization under the ...
    Efficient influence spread estimation for influence maximization under the linear threshold model Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang Computational Social Networks 2014 概要 LTモデルの影響拡散を厳密or精度良く計算 4hop以内の影響について厳密計算 4hopはRandom walkで近似 性質 $$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$ P(S) = S内の頂点から出てる単...
  • 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「に」伝搬する頂点を選んでいることに等しい ...
  • 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
  • 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...
  • Computing and maximizing influence in linear threshold and triggering models
    Computing and maximizing influence in linear threshold and triggering models Justin T. Khim, Varun Jog, Po-Ling Loh NIPS 2016 概要 影響拡散の上下限を新たに作ったよ！ LTモデルとTriggeringモデル 下限は単調劣モジュラなので、最大化できて良い解になる 主結果 LTモデル 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$ An Upper Bound based Greed...
  • CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social ...
    CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social Networks Amit Goyal, Wei Lu, Laks V.S. Lakshmanan 何かよく見るな名前 WWW 2011 CELF++ CELFを速くしたよ！！！ 頂点uは→を持つ u.mg1, u.prev_best, u.mg2, u.flag mg1 Sに対するマージン prev_best u以前に見た中でbest mg2 S+prev_bestに対するマージン flag 最後にmg1が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
  • Efficient algorithms for influence maximization in social networks
    Efficient algorithms for influence maximization in social networks Yi-Cheng Chen, Wen-Chih Peng, Suh-Yin Lee KAIS 2012 概要 CDH Community and Degree Heuristic CDH-KcutとCDH-SHRINK Heat diffusion model (HDM) 熱拡散（物理現象） f_i(t) 時刻tでのv_iの熱 初期状態t=0が与えられる 近傍からΔtの間影響を受ける iの変化量 = αΣ_j [f_j(t)-f_i(t)] 熱がθを超えたらアクティブになったとする シードに対してf(t_0)=h_0とセットする...
  • 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回ループ 各辺を割り当てられた確率に応じて消す...
  • 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • Revisiting the Stop-and-Stare Algorithms for Influence Maximization
    Revisiting the Stop-and-Stare Algorithms for Influence Maximization Keke Huang, Sibo Wang, Glenn S. Bevilacqua, Xiaokui Xiao, Laks V. S. Lakshmanan VLDB 2017 概要（だけ） SSAとD-SSA間違ってたよ～(´；ω；｀) ちょっと計算のオーバーヘッドが増えるけど、直しました 再実験したら、kが大きい時にIMMより速かったよ 結局、辺確率は1/入次数 まとめ (´Д｀)ﾊｧ… VLDB 影響最大化 2017/10/02
  • 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...
  • 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´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
  • Influence Maximization in Undirected Networks
    Influence Maximization in Undirected Networks Sanjeev Khanna Brendan Lucier SODA 2014 難しいので概要だけ 無向グラフでのinfluence maximizationでは、貪欲アルゴリズムは1-1/eよりも良い近似比が保証できるという話 1-1/e+c cはタイトな値は示さずfuture work 直感的な例 p12=1/2, p13=1/2のグラフを考える 有向グラフだと、貪欲解={1,2}、最適解={2,3}で競合比が酷いことになる 無向グラフだと、貪欲解={2,3}、最適解={2,3}で一致する こういうのを考慮すると良いらしい XYZ Lemma x,y,zが確率pで...
  • 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：サンプリング回数θを...
  • 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)で求めている？ 何でこんなことをしたのか若干謎
  • 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) =...
  • 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 実験 ...
  • 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...
  • Mining Social Networks Using Heat Diffusion Processes for Marketing ...
    Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King CIKM 2008 概要 熱拡散過程によるモデリング 3つの拡散モデル，3つのアルゴリズム 製品採択に時間を入れる クラスタ（係数）を反映 正負の意見を伝える 熱拡散モデル 当然，物理現象 分類，次元削減とかに使われている 開発者・ターゲットは熱源として振る舞い，一杯熱を持ってる で，どんどん広がっていく f_t(x,t)=Δf(x,t) f(x,t) 時刻t...
  • Dynamic Influence Maximization Under Increasing Returns to Scale
    Dynamic Influence Maximization Under Increasing Returns to Scale Haifeng Zhang, Ariel D. Procaccia, Yevgeniy Vorobeychik AAMAS 2015 概要 時間が動的な設定 予算投入を途中で行う 活性化頂点 時間に従い適当に増える，指数とか多項式とか 予算 時間に従い指数的に増える 適当な設定では，ある時点に一斉投入（使い切る）のが最適 そうでない場合はヒューリスティクス 導入 ICモデルは劣モジュラ 最近は適応的劣モジュラ最大化もある しかし，Bassモデルのような古典的なモデルはS-shaped Curve ここはミスリーディングで，劣...
  • 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] 辺を含んだ集合関数 ...
  • 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 Extent of Spread in a Dynamic Network
    Maximizing the Extent of Spread in a Dynamic Network Habiba, Tanya Y. Berger-Wolf ? 2007 概要 動的ネットワークでinfluence maximizationやるお！ 問題定義 Dynamic Network G_t = (V_t, E_t)の列 特定の時点のものだから，辺は消えたりする Independent Cascade Modelの拡張 uが時刻tでactiveだったら(u_t, v_t)なv_tを伝播確率でactivate 成功したらvは時刻t+1でactiveになる 一旦activeになったらずっとactive 他の時刻で辺があったらまた試行できる ...
  • Probabilistic Solutions of Influence Propagation on Networks
    Probabilistic Solutions of Influence Propagation on Networks Miao Zhang, Chunni Dai, Chris Ding, Enhong Chen 色々いるし名前を知らん CIKM 2013 概要 新しいinfluence spreadの計算方法 包除原理？ 実験もしてオリジナルより速くなったよ！ Exact influence spread n=3,4,5について、頑張ってinfluence spreadを厳密計算する 3頂点について 1がseed パターンを全部考えて、2、3がactiveになる確率を求めた でも、もっと簡単にできる 1から2がactiveにな...
  • Cost-aware Targeted Viral Marketing in Billion-scale Networks
    Cost-aware Targeted Viral Marketing in Billion-scale Networks Hung T. Nguyen, Thang N. Dinh, My T. Thai INFOCOM 2016 概要 新しい問題 Cost-aware Targeted Viral Marketing ユーザ毎に最初の費用が違う ユーザ毎に影響させた事による効果が違う いい感じにすれば$$ 1-1/\sqrt{e} $$近似が可能 効率的アルゴリズム BCT：CTVMにもInfMaxにも適用可能 LISA [CSoNet 15]の後続 Cost-aware Targeted Viral Marketing 費用$$c(u)$$、利益$$b(u)$$、予算$...
  • On minimizing budget and time in influence propagation over social networks
    On minimizing budget and time in influence propagation over social networks Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan Social Network Analysis and Mining (SNAM) 2012 MINTSS (minimum target set selection) 入力 閾値η 出力 σ(S)≧ηなる最小サイズのS 提案手法 貪欲算法 σ(S)＜η-εの間，増量（min{σ(S+t),η}で考える）が最大の頂点をSに追加 定理1 貪欲算法で双基準近似 σ(S)≧η-ε |S|≦(1+ln(n/ε))OPT 関...
  • Influence Maximization in Big Networks: An Incremental Algorithm for ...
    Influence Maximization in Big Networks An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li Gao IJCAI 2015 概要 小さい部分グラフに分割する 頂点を共有しうるが辺は互いに素 挑戦 部分グラフ間のシミュレーションが重なる 提案手法 M=シミュレーション回数 N=分割個数 $$ (V_i)_i $$ Vの被覆 $$ (E_i)_i $$ Eの分割 X_r = コインフリッピング結果rを表す01値ベクトル ...
  • Revenue Maximization in Incentivized Social Advertising
    Revenue Maximization in Incentivized Social Advertising Çigdem Aslay, Francesco Bonchi, Laks V. S. Lakshmanan, Wei Lu VLDB 2017 概要 Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret VLDB 15の続き感 Incentivized ユーザにも収入の分け前を上げる設定 単調劣モジュラ最大化 with 分割マトロイド制約 (for 広告-シード配置) and 劣モジュラナップサック制約 (for 各広告主の予算) 2つの近似手法を提案して、RISで高速化 定式化 ...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • @wiki全体から「Real-time Topic-aware Influence Maximization Using Preprocessing」で調べる

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