todo314 @ ウィキ
todo314 @ ウィキ

Efficient Location-Aware Influence Maximization

todo314 @ ウィキ内検索 / 「Efficient Location-Aware Influence Maximization」で検索した結果

検索 :
  • 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でできると...
  • 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ベースの手法 その場で木を構成するのはダルすぎるので、上限をいい感じに計算して、余分な頂点を枝刈りする ...
  • 論文一覧
    ... 2011 Efficient Influence Maximization in Social Networks KDD 2009 StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization CIKM 2013 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ... ICDM 2013 An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ... WWW 2014 Extracting Influential Nodes for Informa...
  • A Novel and Model Independent Approach for Efficient Influence Maximization ...
    ...roach for Efficient Influence Maximization in Social Networks Hemank Lamba, Ramasuri Narayanam WISE 2013 概要 influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!! sparsificationするよ！ 精度を落とさずに数倍高速化 提案手法 ある頂点の近傍のスコアを出す スコアの出し方 色々な基準を大量に持ってくる 適当に重みを計算して足し合わせる スコアの大きい近傍をdeg(i)^eだけ残す 0 =e =1 実験 基準 次数とか共通近傍とかJaccard係数...
  • 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とセットする...
  • Personalized Influence Maximization on Social Networks
    ... Efficient Local Greedy Algorithm (ELGA) wから逆にたどれば、各頂点から到達可能かをまとめて計算できる O(kD(m+m*)) Local Cascade Algorithm (LCA) 最短路木っぽいのを持っておく？ オンライン向けらしい 実験 比較対象 次数、ランダム、最大次数の近傍 データセット Epinions、Wikipedia（何で？） WPは(2M,5M) 結果 まぁよいよね LGAは重すぎるらしい ELGAも1000secくらい？ まとめ この問題だとまぁ早くしやすいわな 特定個人に注目するのはいいんだけど...
  • 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´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
  • 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • 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)...
  • 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...
  • 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...
  • 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...
  • 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内の頂点から出てる単...
  • ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
    ...mpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復では、既に選んだシードの貢献を無視した差分を計算 CELF++より6--8倍速くて、TIMよりメモリ消費が1/200だよ まとめ 単純経路は本当に出来るのかな？重複しそう WWW 影響最大化 2017/10/01
  • 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 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 ...
  • 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
  • Competitive Influence Maximization in Social Networks
    Competitive Influence Maximization in Social Networks Shishir Bharathi, David Kempe, Mahyar Salek WINE 2007 概要 モデル 辺uvが試行成功したら指数分布の遅延時間T_{uv}が発生する bプレイヤがサイズk_i以下の集合S_iを選択する 複数人が選択した頂点はランダムに誰かの頂点になる これでカスケードをしていく 純粋戦略ナッシュ均衡は無い（？） 混合戦略ナッシュ均衡は有る 戦略 もし，他の人の戦略が固定されていたら 自分の戦略に対するσは単調かつ劣モジュラ First Mover Strategies Influence Max...
  • 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：サンプリング回数θを...
  • 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...
  • 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)につい...
  • 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頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい ...
  • 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...
  • 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...
  • 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 ...
  • 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アルゴリズ...
  • Diversified Social Influence Maximization
    Diversified Social Influence Maximization Fangshuang Tang, Qi Liu, Hengshu Zhu, Enhong Chen, Feida Zhu ASONAM 2014 概要 影響最大化に人の多様性を導入 影響を受けた人の多様性 シードの多様性（緩和） 影響拡散と多様性の線形結合を最大化 単調・劣モジュラ（文書要約っぽい） Don t put all your eggs in one basket. 全部の卵を一つの篭に入れるな／一つのことにすべてを賭けるな 問題定義 $$ F(S) = (1-\gamma)\sigma(S) / \sigma + \gamma D(\mu^S) / D...
  • On Budgeted Influence Maximization in Social Networks
    On Budgeted Influence Maximization in Social Networks Huy Nguyen, Rong Zheng JSAC 2013 概要 頂点に単一でないコストがついた影響最大化 貪欲アルゴリズムをちょっと変形して1-1/√e近似 σを効率良く求めるためにDAGを作って信念伝搬っぽいことをやる Budgeted Influence Maximization 情報拡散モデルはIC max σ(S) s.t. c(S)≦b c(S)はc(u)(u∈S)の総和 [σ(S+v)-σ(S)]/c(v)で貪欲に選ぶと近似比が任意に悪くなる Leskovecのでも説明してたな… Improved Greedy ↑...
  • Simpath: An Efficient Algorithm for Influence Maximization under the Linear ...
    Simpath An Efficient Algorithm for Influence Maximization under the Linear Threshold Model Amit Goyal, Wei Lu, Laks V. S. Lakshmanan ICDM 2011 LTモデルの性質 $$ \sigma(S) = \sum_{v \in V} \Upsilon_{S,v} $$ Υ_S,v = Sがvを活性化させる確率 $$ \Upsilon_{s,t} = \sum_{\pi \in \text{Path}(s,t)} \Pr[\pi] $$ By definition of the ``live-edge model と簡単に言うが… ※結局はσ({s})はsを始点とす...
  • Stability of Influence Maximization
    Stability of Influence Maximization Xinran He, David Kempe KDD 2014 動機付け 影響最大化の高速手法と確率推定の手法は沢山研究されている でも，ノイズは無視できない！ もし，推定確率でのσと真の確率でのσの差がでかかったら， 推定σで影響最大化しても意味が無い 確率を摂動しても安定かを判定する問題を定式化しよう Influence Difference Maximization p_uv 推定した確率 I_uv = [l_uv, r_uv] 摂動する範囲 $$ \max_S \max_{p \in P} | \sigma_p(S) - \sigma_{p }(S) | $$ 摂動させた中で一番...
  • 気になった論文
    ... Oracles Efficient Dynamic Algorithms for the Steiner Tree. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC 2016 Simpler Analysis and Enumeration of Parametric Minimum Cuts David Karger Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithmic Barrier for Truthful Co...
  • 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)でアクティベーションが成功する これは一回だけ ...
  • 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を以下で近似 $$ ...
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • 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
    ...の経路全体 Efficient influence spread estimation for influence maximization under the ...と一部かぶっている 最悪時には全然駄目、下限=1.5、上限=(n+2)/4 適当に仮定を置いて下限/上限をバウンドしようとしている Triggeringモデル 何かそれっぽいやつ その他性質 下限はすごく特殊な場合（近傍しか見てない）には、単調劣モジュラ 実験 目的：上下限がそれ程タイトか？貪欲アルゴリズムはどれくらい良いか？ データ：Erdős–Rényi、Preferential attachment、Gridで全て小さめ シードの選び方はシミュレーション回数が全体的に雑 まと...
  • 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) =...
  • 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 (Chen+)
    Robust Influence Maximization Chen+ Robust Influence Maximization Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou KDD 2016 概要 最悪時比を最大化したい 解依存バウンド パラメタ空間をいい感じに狭めるサンプリング手法提案 実際、パラメタ空間が大きいと解が良くないので提案手法が効果的 問題定式化 パラメタ空間 $$ \Theta = \times_{e \in E}[l_e, r_e] $$ 頑健比 $$ g(\Theta, S) = \min_{\theta \in \Theta}\frac{\sigma_\theta(S)}{\sigma_\...
  • 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...
  • 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回ループ 各辺を割り当てられた確率に応じて消す...
  • Online Influence Maximization
    Online Influence Maximization Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, Pierre Senellart KDD 2015 概要 辺確率情報はたいてい不完全か利用不可 確率の学習と影響伝播を同時に施行 今の情報からシード選択 宣伝開始 反応から確率更新 Explore-Exploit戦略 動機付け オフライン 辺確率が事前にわかっている 行動ログ自体が入手容易でない それでも何とか影響最大化できるか？ オンライン影響最大化問題 提案手法 不確かな影響グラフ 入力 $$G=(V,E,p)$$ $$N...
  • 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...
  • 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が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
  • Maximizing the Long-term Integral Influence in Social Networks Under the ...
    Maximizing the Long-term Integral Influence in Social Networks Under the Voter Model Chuan Zhou, Peng Zhang, Wenyu Zang, Li Guo WWW 2014 companion ポスター 概要 Voter Modelにおける影響最大化 long-term integralを最大化したい 問題+提案手法 モデルはInfluence Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[...
  • 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 complex networks through optimal percolation
    Influence maximization in complex networks through optimal percolation Flaviano Morone, Hernán A. Makse Nature 2015 概要 頂点を削除して最大の連結成分を最小化したい 強影響力頂点抽出，immunization，コミュニティ検出 既存手法…ヒューリスティクス 本手法 最適化問題 ある種の貪欲アルゴリズム 輪郭 最適パーコレーション 固有値の最小化問題 上を解く 最適パーコレーション $$ \nu_i $$の計算
  • Extracting Influential Nodes for Information Diffusion on a Social Network
    Extracting Influential Nodes for Information Diffusion on a Social Network Masahiro Kimura, Kazumi Saito, Ryohei Nakano AAAI 2007 概要 influence maximizationの高速アルゴリズム ICとLT 提案手法 ICもLTもランダムグラフを考えればいい σの増加量を効率的にもとめる 事前にランダムグラフを作っておく シード集合 A Aから到達可能な頂点を除く 頂点uについて，↑で出来たグラフでuから到達可能な頂点数Fをもとめる uと同じ連結成分に入っている頂点vについて，σ_i(A∪{v})=σ_i(A)+Fとする ...
  • @wiki全体から「Efficient Location-Aware Influence Maximization」で調べる

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