todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Accelerated k-means with adaptive distance bounds」で検索した結果

• 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の間くらい 微妙じゃね？ どちらかには大体負けている… 中位では勝ってたわ 実デ...
• 論文一覧
  ...MGPU GPU-Accelerated Influence Maximization in Large-Scale Social Networks TPDS 2014 Influence Maximization in Big Networks An Incremental Algorithm for ... IJCAI 2015 Influence at Scale Distributed Computation of Complex Contagion in Networks KDD 2015 Outward Influence and Cascade Size Estimation in Billion-scale Networks SIGMETRICS 2017 RIS Maximizing Social Influe...
• 気になった論文
  ... Bolt Accelerated Data Mining with Fast Vector Compression PAMAE Parallel k-Medoids Clustering with High Accuracy and Efficiency When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks Robust Spectral Clustering for Noisy Data Unsupervised Feature Selection in Signed Social Networks Statistical Emerging Pattern Mining with Mu...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• Making k-means even faster
  Making k-means even faster Greg Hamerly In SDM 2010 参考 http //d.hatena.ne.jp/ny23/20101126/p2 概要 Lloyd s algoの高速化 ベクトル間の距離の計算を刈る Using the Triangle Inequality to Accelerate k-Meansの改良 省メモリになったらしい アイデア 各点に対し、upper bound(割当クラスタ中心)/lower bound(2番目に近いクラスタ中心)を1つ持つ アルゴリズム 各点について、 Elkanのように、u(x)で刈れるかチェック $$ u(i) \leq l(i) $$...
• Extrapolation Methods for Accelerating PageRank Computations
  Extrapolation Methods for Accelerating PageRank Computations Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub WWW 2003 概要 PageRankのためのPower methodの高速化 25--300%速くなった メモ：イントロで… Dangling nodesからは一様に飛ぶとしている Aitken Extrapolation $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい！...
• 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つに被...
• Hartigan's Method: k-means Clustering without Voronoi
  Hartigan s Method k-means Clustering without Voronoi Matus Telgarsky, Andrea Vattani JMLR 2010 Journal of Machine Learning Research
• Using the Triangle Inequality to Accelerate k-Means
  Using the Triangle Inequality to Accelerate k-Means Charles Elkan In ICML 2003 参考 http //ibisforest.org/index.php?Paper%2FICML-2003-p147 概要 Lloyd s algoの高速化 ベクトル間の距離の計算を刈る 補題 Lemma 1 $$ d(b,c) \geq 2d(x,b) \Rightarrow d(x,c) \geq d(x,b) $$ Lemma 2 $$ d(x,c) \geq \max\{ 0, d(x,b)-d(b,c) \} $$ アイデア 三角不等式、距離の上限・下限を利用 ...
• Evaluating Multi-Way Joins over Discounted Hitting Time
  Evaluating Multi-Way Joins over Discounted Hitting Time Wangda Zhang, Reynold Cheng, Ben Kao ICDE 2014 概要 random walkに基づくスコアのでかいtop-k n-tupleを返す問題の提案 それに対する色々な枝刈りを詰めまくった手法を提案 実験的に相当早くなった top-k n-way joins 定義 入力 グラフ G=(V_G, E_G) クエリグラフ Q=(V_Q, E_Q) V_Q=(R_1, …, R_n) R_i⊆V_G 単調集計関数 f R^|E_Q|→R maxとかminとか+とか重み付けとか… k ...
• Fast and Accurate k-means For Large Datasets
  Fast and Accurate k-means For Large Datasets Michael Shindler, Alex Wong, Adam Meyerson In NIPS 2011 メモ Shindlerはオレゴン州大学 WongはUC Los Angeles MeyersonはOnline Facility Locationの著者（単独）、でGoogle 概要 k-meansの爆速ストリームアルゴリズム Streaming k-means on Well-Clusterable Dataを簡易化して実装して実験しました、って感じ 理論がやばい（意味不 アルゴリズム 解の候補を高々O(klogn)個だけ保持しておく 入力点を新しく読む度...
• 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ネットワークでの応用例...
• k-means--: A unified approach to clustering and outlier detection
  k-means-- A unified approach to clustering and outlier detection Sanjay Chawla, Aristides Gionis SDM 2013 概要 l点除いてかつk-meansも最小 除いたLが外れ値 問題定義 D(X\L, C)を最小化するC (of size k) とL (of size l) を求めたい Dは最小二乗距離和 k=1ならn^d^3で解けるけど基本NP-hard 提案手法 k-meansの変形に相当 各点についてクラスタまでの距離計算 距離でソートして大きいl点をLにつっこむ Lを無視してクラスタ更新 これを収束するま...
• Non-exhaustive, Overlapping k-means
  Non-exhaustive, Overlapping k-means Joyce Jiyoung Whang, Inderjit S. Dhillon, David F. Gleich SDM 2015 概要 既存のクラスタリング（特にk-means）手法は、外れ値の重複のどちらかだけだった NEO-K-Means (Non-Exhaustive Overlapping K-Means) を提案 重み付きカーネルk-meansとの互換性もある 外れ値 重複有りグラフクラスタリングに使える 定式化 $$ U=[u_{ij}]_{n \times k} $$ $$ \mathbf{x}_i $$がクラスタ$$j$$の属する 重複の具合の制約 $$ \mathrm{trace}(...
• 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...
• 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...
• 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モデルでの応用 先...
• Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming
  Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming Yangyang Hou, Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon KDD 2015 概要 Non-exhaustive, Overlapping k-meansの続き 元の反復アルゴリズムはあまり良くなかったりする 違う解き方を考案 凸SDPで緩和 そのままだと大変なので低ランク近似 初期化・丸めもちょっと頑張る 実験してみたら良かった 重複有りコミュニティ検出にも使える kernel k-meansとグラフクラスタリングが等価だ...
• 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...
• Streaming k-means on Well-Clusterable Data
  Streaming k-means on Well-Clusterable Data Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku In SODA 2011 メモ UCLA（カリフォルニア大学ロサンゼルス校）の人々らしい 概要 Online Facility Locationを元にしたストリームk-meansアルゴリズム 時間・空間計算量共に良く、近似比は定数。 アルゴリズム 点xを読み込む xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる 施設の数が増えすぎたら...
• 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 ...
• TwitterRank: Finding Topic-sensitive Influential Twitterers
  TwitterRank Finding Topic-sensitive Influential Twitterers Jianshu Weng, Ee-Peng Lim, Jing Jiang, Qi He WSDM 2010 ビデオ見て書いてみたよ http //videolectures.net/wsdm2010_weng_trft/ 概要 トピックを指定して影響力の高い頂点を見つけたい 応用 leaderの特定 マーケティング、広告 難しいところ ユーザ同士の関係がnon-serious トピックが分からん ground truthとは…？ データ シンガポールに限って 1000人位 割りと疎...
• 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 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...
• 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-...
• 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...
• Scalable Methods for Adaptively Seeding a Social Network
  Scalable Methods for Adaptively Seeding a Social Network Thibaut Horel, Yaron Singer WWW 2015 概要 影響最大化の問題 … アクセスできる頂点には制限有 解決法 … 二段階アプローチ [Seeman-Singer. FOCS 13] 独立カスケード・線形閾値等で定数近似 独立カスケード・線形閾値等で定数近似 すごく遅い この論文 より簡単な拡散モデルで効率的近似手法 実験でスケーラビリティ 効果を検証 詳細は https //www.slideshare.net/secret/nIKkJnFLPQeMj WWW 影響最大化 情報拡散 2017/10/02
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• Parameterized Algorithms
  Parameterized Algorithms Introduction 頂点被覆 k人だけ消して競合を防ぐ→大きさのkの頂点被覆 NP完全 n=1000, k≦10 総当り 2^1000≒10^301 $$ {n \choose k} $$ {1000 c 10}≒10^23 ばか 観察1 ぼっちは消さなくて良い k人超過と競合する人は必ず消す そうでないと，その人の近傍を全て消す→k人超消すことになる 各頂点の次数∈[1,k]になる 辺数 k^2 →無理 $$ {2k^2 \choose k} $$ 観察2 次数1の頂点vがある→端点wを被覆に入れるのが最適 $$ {k^2 \choose k} $$ ...
• 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] 辺を含んだ集合関数 ...
• 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...
• Fast Random Walk with Restart and Its Applications
  Fast Random Walk with Restart and Its Applications Hanghang Tong, Christos Faloutsos, Jia-Yu Pan ICDM 2006 概要 ベストペーパー RWRを高速にクエリ計算した 提案手法 B_LIN グラフを（METISとかで）k分割する 確率遷移行列W（論文中では正規化Laplacianもどき）をW_1+W_2に分割する RWR行列は$$ (1-c)(I-cW)^{-1} $$ W_1：分割内だけ；diag(W_11, …, W_1k)な感じ W_2：分割間だけ； Q_1 = diag(Q_11, …, Q_1k) Q_1i = (I-cQ_1i)の逆行列 ...
• Streaming k-means approximation
  Streaming k-means approximation Nir Ailon, Ragesh Jaiswal, Claire Monteleoni In NIPS 2009 メモ Google Researchとコロンビア大学の人々 概要 ストリーム k-means アルゴリズムの提案 O(log k)近似 アルゴリズム k-means # O(1)近似 ランダムにXの中から3 log k点選び，Cに追加 C ← Pから選んだ 3log k 点 k-1回繰り返す C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点 本命 O(log k)近似 PをP1,…,Pl ...
• Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with ...
  Yinyang K-Means A Drop-In Replacement of the Classic K-Means with Consistent Speedup Yufei Ding, Yue Zhao, Xipeng Shen, Madanlal Musuvathi, Todd Mytkowicz ICML 2015 概要 k-meansのLloydアルゴリズムの距離計算枝刈り+中心再計算省略による高速化手法 提案手法 三角不等式 $$ |d(x,b)-d(b,c)| \leq d(x,c) \leq d(x,b)+d(b,c) $$ $$C,c$$ クラスタ中心の集合、クラスタ中心（のどれか） $$b(x)$$ xの属するクラスタ中心 $$C ,c ,b (x)$$ 次の反復...
• 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...
• Fast and Provably Good Seedings for k-Means
  Fast and Provably Good Seedings for k-Means Olivier Bachem, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2016 概要 Approximate K-Means++ in Sublinear Time K-MC^2の改善版 データに対する強い仮定があるという欠点有り 頂点の標本分布を「一様」から「k-means++の最初の反復っぽい奴」に変える 但し、一回の全点スキャンが必要 仮定無しで、MCMCの連鎖長をバウンドし、期待近似比を保証 実験したら提案手法AFK-MC^2はK-MC^2より実際かなり良い K-MC^2 Metropolis-Hastings ...
• 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 モチベーション グラフ上でのカスケードを検知したい！ 水質汚染 ...
• StreamKM++: A Clustering Algorithm for Data Streams
  StreamKM++ A Clustering Algorithm for Data Streams In JEA 2012 Journal of Experimental Algorithmics In ALENEX 2010 概要 コアセットを使ったストリームk-meansアルゴリズム アルゴリズム ストリームモデルでコアセットを頑張って計算する 確かマルチパス 最後にk-means++を適用 コアセット Pの(k,ε)コアセット 重み付き集合Sと重み関数wの組 $$ \forall C \subset \mathbb{R}^{d}(|C|=k) \quad (1-\epsilon)cost(P,C) \leq cost_w (S,C) \...
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for ...
  Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems Yin Tat Lee, Aaron Sidford In FOCS 2013 リプシッツ連続、強凸関数の最小化 加速座標勾配法 逆条件数κ^-1が0に近いとヤバイ 収束しにくい 加速勾配法・座標勾配法のマージ 今まではupdateがO(n)で遅い これをO(1)にしたヨ！！！ 遅延評価っぽいことをする FOCS 2013-11-03 02 19 09 (Sun)
• Overlapping Community Detection Using Seed Set Expansion
  Overlapping Community Detection Using Seed Set Expansion Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon CIKM 2013 概要 コンダクタンスがいい感じになる重複コミュニティ検出手法を提案 提案手法 目標 全体をカバーしつつ、最大のコンダクタンスを小さくしたい Filtering whiskerを取り除きたいので、以下のような分解をする core=（ざっくりいうと）最大の2点連結成分 bridge=橋 whisker=残り Seeding 色々な手法でクラスタ中心を決める Graclus centers, Spr...
• Scalable K-Means++
  Scalable K-Means++ Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii VLDB 2012 概要 $$ k\texttt{-means}\parallel $$という手法を提案 複数反復で複数点選ぶ 選ぶところで並列化 一般的な理論的保証が成り立つのが良い 動機付け k-meansは例え理論的には良くなくても実際的な用途では強力 k-means++が現時点で最強 ただし，O(nkd)時間 Lloyd s methodの一反復と同じ 並列化が難しそう k=100,1000とかで難しい $$ k\tex...
• 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)$$近似を保証するサンプルサイズが良く分からん ...
• Tracking the Random Surfer: Empirically Measured Teleportation Parameters in ...
  Tracking the Random Surfer Empirically Measured Teleportation Parameters in PageRank David F. Gleich, Paul G. Constantine, Abraham D. Flaxman, Asela Gunawardana WWW 2010 概要 PageRankのαの値は何なんだ？ 平均が0.3~0.7のβ分布に従う 分布の測定 人一人なら簡単 (リンククリックによる総閲覧ページ数) / (総閲覧ページ数) 複数人いると，平均とかいうわけにも行かない PageRankはαに対して非線形だから 代わりに，人毎にαを求め，グループ全体にフィットする分布を求める ↓の2...
• 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保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
• An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ...
  An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Li Guo WWW 2014 companion ポスター 概要 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ...のLT版 CELFより5倍速い 提案手法 σ(S)=ΣΠw(e)の形でかける ↑は行列のべき乗和（有限）で上から抑えられる Wのべき乗和は(I-W)^-1で上から抑えられる 確率だから1以下って制約とか...
• k-means++: The Advantages of Careful Seeding
  k-means++ The Advantages of Careful Seeding David Arthur, Sergei Vassilvitskii In SODA 2007 メモ Stanford大学の人々 概要 k-meansアルゴリズム（Lloydのアルゴリズム）の改良版 元のアルゴリズムの問題点である初期値依存性を解決し、Θ(log k)近似を達成。 k-meansアルゴリズムの問題点 最適コストとの比に上界が無い nとkの値が固定でも、コストがいくらでも悪くなるような入力を作れる k-means++ k個のクラスタ中心c1,…ckの初期値を確率的に選択する。 入力点から一様ランダムに初期点c1を選択し、C←{c...
• 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´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
• The Importance of Communities for Learning to Influence
  The Importance of Communities for Learning to Influence Eric Balkanski, Nicole Immorlica, Yaron Singer NIPS 2017 概要 The Power of Optimization from Samplesはcurvature制限時だった 今回は影響最大化をコミュニティ構造が明らかな場合、OPSの枠組みでなんとかするよ コミュニティの大きさを捉えられそうなアルゴリズムを提案 SBMの簡単な設定で近似比を証明 アルゴリズム COmmunity Pruning from Samples 設定 無向なので、基本的に連結成分の大きさ（の和）の期待値が影響力になる underlyingな...
• Reliable Clustering on Uncertain Graphs
  Reliable Clustering on Uncertain Lin Liu, Ruoming Jin, Charu Aggarwal, Yelong Shen ICDM 2012 概要 uncertain graphsをクラスタリングしたい 清浄(purity)と均衡(size balance)に基づく信頼度尺度 k-meansっぽい局所改善手法 問題定式化 $$1 \leq i \leq N$$ ランダムグラフのID（試行数） $$1 \leq j \leq L_i$$ 各ランダムグラフの連結成分 $$1 \leq k \leq K$$ 各クラスタ $$ C_k^{i,j} $$ $$G_i$$における(クラスタk)∩(連結成分j) Purity ...
• 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 $$ ...
• @wiki全体から「Accelerated k-means with adaptive distance bounds」で調べる

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