todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Approximate Distance Oracle with Constant Query Time」で検索した結果

• Approximate Distance Oracle with Constant Query Time
  Approximate Distance Oracle with Constant Query Time Shiri Chechik STOC 2014 近似率，空間計算量，クエリ時間の3つに焦点 クエリ時間が定数になったのが主な成果っぽい？ STOC 最短路クエリ 2014-10-03 17 46 28 (Fri)
• 気になった論文
  ...rdness of Approximate Hypergraph Coloring How Bad is Selfish Routing? Detecting a Network Failure Fully Dynamic Transitive Closure Breaking Through the O(n2) Barrier The Cover Time, the Blanket Time, and the Matthews Bound Randomized Rumor Spreading FOCS 2001 Online Facility Location Testing Subgraphs in Large Graphs Fast Monte-Carlo Algorithms for Appr...
• 論文一覧
  ...s ... Approximate Distance Oracle with Constant Query Time Zig-zag Sort A Simple Deterministic Data-Oblivious Sorting Algorithm ... Minimum Bisection is Fixed Parameter Tractable IEEE Symposium on Foundations of Computer Science FOCS 2013 https //sites.google.com/site/tcsreading/home/focs2013 The Price of Stability for Undirected Broadcast Network Design with Fai...
• Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with ...
  Denser than the Densest Subgraph Extracting Optimal Quasi-Cliques with Quality Guarantees Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, Maria A. Tsiarli In KDD 2013 http //www.math.cmu.edu/~ctsourak/kdd13.pptx 概要 quasi-clique の評価関数を変えた densest-graphの評価関数 $$ e[S]/|S| $$ はだめ！ 辺密度が低いし（グラフがでかいから）、直径もでかい 辺密度 $$ e[S]/{|S| \c...
• Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...
  Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy STOC 2014 概要 Approximation Algorithms for Regret-Bounded Vehicle Routingについて 30.86近似アルゴリズム 今までO(log n)近似 RVRP 入力 完全グラフ 距離 三角不等式 始点r 整数R rを始点とするパスの集合で次を満たす 全頂点が少なくとも1つに被...
• Distance Constraint Reachability Computation in Uncertain Graphs
  Distance Constraint Reachability Computation in Uncertain Graphs Ruoming Jin, Lin Liu, Bolin Ding, Haixun Wang VLDB 2011 概要 経路長に制限を入れた到達可能性確率計算クエリ 普通のシミュレーションは遅いので，頭のいい方法を考案 最大で1M辺規模で動く 問題定義と動機付け 距離制約到達可能性クエリ (Distance-constraint reachability) 入力 2頂点s,t, uncertainグラフ G, 閾値d 出力 s-t間の最短経路長がd以下である確率$$ R_{s,t}^d(\mathcal{G}) $$は？ P2Pネットワークでの応用例...
• The query-flow graph: model and applications
  The query-flow graph model and applications Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato, Aristides Gionis, Sebastiano Vigna CIKM 2008 概要 query-flow graph q_i→q_j 同セッションで計算されやすいよ！w(q_i,q_j)はその確率 問題 でかい、ノイズ、定式化、あいまい、疎、などつらぽよ 応用 logical session intertwined query chainsを見つける query recommendation Random walk with res...
• Top-K Nearest Keyword Search on Large Graphs
  Top-K Nearest Keyword Search on Large Graphs Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian In VLDB 2013 メモ Jeffrey Xu Yu!! 概要 top-k nearest keyword search 頂点 0個以上のキーワード 辺 長さ クエリ ノード、キーワード、k 出力 キーワードを含みノードに近いkノード top-k nearest keyword search に対するアルゴリズム 最短経路木 2つ提案 kが小さいよう 大きくてもOK 応用 Facebo...
• A Local Search Approximation Algorithm for k-Means Clustering
  A Local Search Approximation Algorithm for k-Means Clustering Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y.Wu In SCG 2002 Symposium on Computational Geometry 概要 k-meansアルゴリズム 多項式時間で(9+ε)-近似 Single-Swap ヒューリスティクス 山登り法 初期状態から状態遷移していき、局所解を答えとする 状態 k個の施設 遷移 k個の施設の内1つを残りのn-k個と交換（だから、Single-...
• Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
  Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs Liam Roditty, Virginia Vassilevska Williams In STOC 2013 メモ Y.Yano 直径2近似O(n+m) BFSして最大の高さ additive approximation Aingworth 2つの組み合わせ 2種類のBFS木の高さの最大値 $$ s \in [1,n] $$ O(ns^2 + (s+n/s)m) 論文の内容 ns^2の項を消したい ↑高々s頂点のBFS N_s^out(v)を求めないで頑...
• Accelerated k-means with adaptive distance bounds
  Accelerated k-means with adaptive distance bounds Jonathan Drake, Greg Hamerly In NIPS? 2012 概要 Lloyd s algoの高速化 ベクトル間の距離の計算を刈る ElkanとHamerlyを混ぜた パラメータで アルゴリズム lower boundについて、b next-closest centersをorderedで持っておく bの値 k/8からk/4の間で調整する 実験 次元の変化 ElkanとHamerlyの間くらい 微妙じゃね？ どちらかには大体負けている… 中位では勝ってたわ 実デ...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• 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 ...
• 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...
• On the Approximability of Influence in Social Networks
  On the Approximability of Influence in Social Networks Ning Chen SODA 2008 メモ程度に モデル 無向グラフG 閾値1≦t(v)≦deg(v) 近傍の内t(v)以上が活性化したら自分も活性化 Target Set Selection 問題 ある割合の頂点数を活性化するためのシードサイズを最小化したい ちょっと違うけどまあ 結果 $$ O(2^{\log^{1-\epsilon}n}) $$で近似できない（仮定のもと） Majority Thresholds 半分以上で活性化 Small Thresholds 小さい定数 Unan...
• Random Warping Series: A Random Features Method for Time-Series Embedding
  Random Warping Series A Random Features Method for Time-Series Embedding Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, Michael Witbrock AISTATS 2018 概要 課題：Gram行列の対角優位と自乗時間 random features approximationを採用 DTW距離 2つの時系列$$x_i, x_j$$に対する任意のalignment $$a$$を考える 対応する各要素対のdissimilarityの和の最小が距離 $$ S(x,y) = \min_{a} \sum_{1 \leq t \leq |a|} \tau(x[a_...
• Approximating the Spectrum of a Graph
  Approximating the Spectrum of a Graph David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant KDD 2018 概要 （正規化）Laplacianのスペクトラムが欲しい！ $$ \exp(O(1/\epsilon)) $$時間：定数！！！ $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$ 性質検査的な話もあるよ！ 提案手法 定数時間にしたいので、出力は[0,2]上の離散分布 $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番...
• 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 Similarity Estimation in Social Networks: Closeness, Node Labels, ...
  Scalable Similarity Estimation in Social Networks Closeness, Node Labels, and Random Edge Lengths Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, Renato F. Werneck COSN 2013 背景 直径が小さいグラフで最短路を求める意味はあるのか？ そこを考えよう！ 概要 最短路ベースの頂点間関連性 RWR, SimRank, Resistance dsitance, … この論文 色々提案して、その計算、既存の関連性との比較 神か A...
• Outward Influence and Cascade Size Estimation in Billion-scale Networks
  Outward Influence and Cascade Size Estimation in Billion-scale Networks]] Hung T. Nguyen, Tri P. Nguyen, Tam N. Vu, Thang N. Dinh SIGMETRICS 2017 （会議） Proceedings of the ACM on Measurement and Analysis of Computing Systems 2017 （ジャーナル） 概要 影響力推定の新しい指標outward influenceを作ったよ！…E[拡散サイズ]-|シードサイズ| 相対誤差を保証するのが難しい 高速アルゴリズムを作ったよ カスケードが小さくなり過ぎようにimportance samplingを...
• A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence ...
  A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence Problem Maxime Crochemore, Costas S. Iliopoulos, Yoan J. Pinzon, James F. Reid IPL(Information Processing Letters) 2001 概要 bit vectorによる爆速LCS、正確にはその長さ 時間 O(nm/w) 空間 O(m/w) w ビット数 事前知識 Σ アルファベット s=|Σ| LCSの時間計算量の下界 Ω(nlogm) 最速 Σサイズ制限無 $$ O(n^2 \log \l...
• 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：サンプリング回数θを...
• 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...
• Social Influence Spectrum with Guarantees: Computing More in Less Time
  Social Influence Spectrum with Guarantees Computing More in Less Time Dinh, Thang and Nguyen, Hung and Ghosh, Preetam and Mayo, Michael CSoNet 2015 概要 新しいアルゴリズムLISA $$k=1,\ldots,n$$について同時に解けるよ！ $$ O(\epsilon^{-2}\ln \frac{2}{\delta} (n+m)) $$時間だよ！ 提案手法 Linear-time Influence Spectrum Algorithm (LISA) 終了条件が重要 $$ \Upsilon_L = 1+4.6\epsilon^{-2}...
• A Dual-tree Algorithm for Fast k-means Clustering with Large k
  A Dual-tree Algorithm for Fast k-means Clustering with Large k Ryan R. Curtin SDM 2017 概要だけ Lloydのアルゴリズムと同じ結果を出力するk-means高速化アルゴリズム 基本戦略 点集合と中心集合をそれぞれ木（kd-木、cover tree等）で管理する 点部分集合と中心部分集合の対の関係をまとめて見る 枝刈りをまとめて行える（各点の属する中心の更新とか） 枝刈り条件が沢山ある（一応強そう） 計算時間 結構色々な仮定の下O(N+klogk)時間 expansion constant, related quantityの多項式が掛かってくる 実際には速い 実験;...
• 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回ループ 各辺を割り当てられた確率に応じて消す...
• Faster Random Walks By Rewiring Online Social Networks On-The-Fly
  Faster Random Walks By Rewiring Online Social Networks On-The-Fly Zhuojie Zhou, Nan Zhang, Zhiguo Gong, Gautam Das ICDE 2013 概要 ランダムウォークでサンプリングしたい！ Third party（全データが無いのでAPIとかでとってくる でも、変なところにはまりやすい（孤立したコミュニティっぽいところ 辺を消したり付け替えたりして、conductanceを大きくする ランダムウォークなので、今見てる頂点の近傍だけから操作を行う 定常状態に速く収束する！（mixing timeが小さい 貢献 グラフトポロジーを変化させ、サンプリングを効率的にする、という「問題...
• Co-clustering documents and words using Bipartite Spectral Graph Partitioning
  Co-clustering documents and words using Bipartite Spectral Graph Partitioning Inderjit S. Dhillon KDD 2001 概要 文書と単語の共クラスタリング カット最小化として妥当な問題設定 スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和 後はk-meansすると大体上手い 問題設定 $$ G=({\cal D}, {\cal W}, E) $$ 文書と単語の二部グラフ 辺重みが謎… 単語・文書クラスタリングの関係 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える というわけで、k...
• A Fast and Provable Method for Estimating Clique Counts Using Turan's Theorem
  A Fast and Provable Method for Estimating Clique Counts Using Turán s Theorem Shweta Jain, C. Seshadhri CoRR 概要 k-クリークの個数の数え上げ サンプリングでの精度を上げるために、元のグラフをclique shadowと言うものに分解し、その上でサンプリング shadowの良さをTuránの定理を使って与える←辺密度がある値以上 構築はクリーク探索の再帰的アルゴリズムを途中打ち切り shadowの大きさは上手くバウンドできないけど、実際的にはかなり小さく上手く行く Turán s theorem k-cliqueの密度 $$ \rho_k(G) = |C_k(G)|/{|V| ...
• From Machu_Picchu to rafting the urubamba river: Anticipating information ...
  From Machu_Picchu to "rafting the urubamba river" Anticipating information needs via the Entity-Query Graph Ilaria Bordino, Gianmarco De Francisci Morales, Ingmar Weber, Francesco Bonchi WSDM 2013 概要 今見ているwebページの内容から非自明かつ偶察力を有する少数かつ多様な検索クエリを提示 手法 ページ内容をWikipediaエンティティで表現 エンティティとクエリからなるグラフ上でPersonalized PageRank PageRankスコアの高いクエリを出力 実験 提...
• 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)...
• Minimum-Risk Maximum Clique Problem
  Minimum-Risk Maximum Clique Problem Maciej Rysz, Pavlo A. Krokhmal, and Eduardo L. Pasiliao Dynamics of Information Systems Algorithmic Approaches 2013 概要 最小危険最大クリーク問題 各頂点には費用／損失を表す確率変数 同時分布は既知 特定の危険尺度で危険最小のクリークを見つけたい 尺度の単調性から最適解は極大クリークになる Erdős–Rényiグラフで実験 導入 状況 頂点 が不確かさを持つ 危険回避グラフ理論的問題 Xi 頂点iに紐づく確率変数 Xiの同時分布は分かる...
• Why approximate when you can get the exact? Optimal Targeted Viral Marketing ...
  Why approximate when you can get the exact? Optimal Targeted Viral Marketing at Scale Xiang Li, J. David Smith, Thang N. Dinh, My T. Thai INFOCOM 2017 概要 普通に厳密解目指すんで、オレ。 RR集合をサンプルしてからMaxCover部分を整数計画ソルバで解く 得られた結果の精度を保証するのがミソ 普通の いわゆるtwo-stage stochastic programmingを使った場合 各サンプルがO(m)サイズ 信頼区間だけなのが嫌だ $$(\epsilon,\delta)$$近似を保証するサンプルサイズが良く分からん ...
• Influence of the Dynamic Social Network Timeframe Type and Size on the Group ...
  Influence of the Dynamic Social Network Timeframe Type and Size on the Group Evolution Discovery Stanisław Saganowski, Piotr Bródka, Przemysław Kazienko ASONAM 2012 概要 GED (Group Evolution Discovery) 法のパラメータチューニングの解析 グループ発展 時間発展でコミュニティは変化していくが，それを下記に分類 Continuing(停滞) サイズに変化なし．頂点がちょっと変わるくらいならOK Shrinking サイズが小さくなる Growing サイズが大きくなる...
• Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest
  Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata SDM 2014 概要 AXみたいな行列計算を高速にしたい Aの列中の値が同じ（確率遷移行列とか）だと余分な計算を省ける さらにAを分解して個々に省略手法を適用できる 3倍位速くなった 提案手法 Single Tree Adjacency Forest(STAF) Column-scaled nonzeros property 行列の各列j中の値＝0 or cj こんなやつ $$ A = \left( ...
• 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...
• Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs
  Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs Zhaonian Zou Workshop on Mining and Learning with Graphs 概要だけ Uncertain graphから期待密度最大の部分グラフ抽出 問題1 制約無し (期待密度)=(∑各辺の確率) 各辺の周辺確率が分かっていれば良い ただの最密部分グラフ $$ \mathcal{O}(nm\log(n^2/m)) $$時間 問題2 頂点集合Rを含む 別にUncertain graph特有の何かではない parametric maximum flowで同じ計算時間 ...
• Is Nearly-linear the Same in Theory and Practice? A Case Study with a ...
  Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner SEA 2015 概要 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！ ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！ low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
• Suggesting Ghost Edges for a Smaller World
  Suggesting Ghost Edges for a Smaller World Manos Papagelis, Francesco Bonchi, Aristides Gionis CIKM 2011 問題 平均最短経路長最小化 G 連結無向グラフ R⊆V×V-E(G) (|R|≦k)で 平均最短経路長L(V,E∪R))を最小化したい 候補がO(n^2)あるので大変 手法 貪欲 k回×n^2候補辺×n^3(WF)=O(kn^5) やばお ヒューリスティック ヒューリスティック+標本抽出 実験 |V| 3K, |E| 8K 適用的な貪欲が一番良い 速度：貪欲は遅い ヒューリスティック...
• On Influential Node Discovery in Dynamic Social Networks
  On Influential Node Discovery in Dynamic Social Networks Charu Aggarwal, Shuyang Lin, Philip S. Yu SDM 2012 概要 SN上のやりとりは瞬間的 その確率は瞬間を表す時間の関数 globally optimized forward trace approach locally optimized backward approach 動的モデル 頂点・辺はある時間帯に存在するみたいな感じ f_ij(δt) = a(1-exp(-λ_ij*δt)) δtの時間だけ辺ijが出現する時の伝播確率 (t1, t2)の間に辺(i, j)があるとする (t1, t2)をm分割してδt_iとす...
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
  Path Sampling A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts Madhav Jha, C. Seshadhri, Ali Pinar WWW 2015 概要 数千万辺でも数十秒 誤差1%以下 Chernoff boundからエラーバーも出せる 問題定義 4-頂点部分グラフは6種類 3-star, 3-path, tailed-triangle 4-cycle, chordal-4-cycle, 4-clique C_i 誘導部分グラフにおけるi-th 部分グラフの出現個数 N_i i-th 部分グラフの出現個数 (C_i)と(N_i)は簡単な線形関係に...
• 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内の頂点から出てる単...
• 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 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 残った辺 カスケードの仕...
• Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a ...
  Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang KDD 2014 概要 大きいカスケードが「起こりやすい」ようにシードを選びたい 期待値の代わりに確率を議論するのがミソ この問題は劣モジュラでない 色々解析 動機付け トピックがある閾値まで広まって欲しい tipping point 当然シードセットは小さくしたい しかも確率保証つきで 問題定義 独立カスケードモデル Seed Mini...
• Information Diffusion and External Influence in Networks
  Information Diffusion and External Influence in Networks Seth Myers, Chenguang Zhu, Jure Leskovec In KDD 2012 メモ http //cs.stanford.edu/people/jure/pubs/ext-kdd12.pdf アブスト influence の始まりってどこ？ってのを考える influence の伝わり方は2パターンある ノード-ノードを伝って ネットワーク外から これに注目 新しいモデル フィッティングしやすいパラメータ Twitterに適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• 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,...
• Inverse Density as an Inverse Problem: The Fredholm Equation Approach
  Inverse Density as an Inverse Problem The Fredholm Equation Approach 密度比推定問題を第一種Fredholm方程式に変形して解く 応用 importance sampling 共変量シフト・バイアスサンプリング 訓練データとテストデータの分布が異なるとき 分布p,qがある d次元からスカラー それぞれサンプリング p(x)/q(x)を推定したい ナイーブ 直接推定して商を取る こっちのが難しい（当たり前 直接推定しないのがポイント やべえわからねえ… Fredholm方程式を解く手法を色々ある NIPS 2014-...
• 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...
• Anytime Influence Bounds and the Explosive Behavior of Continuous-Time ...
  Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks Kevin Scaman, Rémi Lemonnier, Nicolas Vayatis NIPS 2015 概要だけ Tight Bounds for Influence in Diffusion Networks and Application to Bond ...の続き Hazard matrixを拡張するために、Laplace変換を導入した定義をしている 証明しているもの ある時刻での影響拡散の上限 Critical time（いつ拡散がでかくなるか）の下限 特定の確率設定や、SIRモデルでの応用 先...
• @wiki全体から「Approximate Distance Oracle with Constant Query Time」で調べる

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