todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Streaming k-means on Well-Clusterable Data」で検索した結果

• 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を最近の施設に割り当てる 施設の数が増えすぎたら...
• Fast and Accurate k-means For Large Datasets
  ...ルゴリズム Streaming k-means on Well-Clusterable Dataを簡易化して実装して実験しました、って感じ 理論がやばい（意味不 アルゴリズム 解の候補を高々O(klogn)個だけ保持しておく 入力点を新しく読む度に、入力点から最も近い解の候補との距離の自乗値に比例した確率で入力点を解の候補に追加する 入力点に近い点が解の候補に有ったら入力点は割とどうでもよいが、無かったら入力点の重要度は高いという観察 解の候補が増えすぎたら、入力点の処理とほぼ同じ処理を自分自身に適用する 最後に、既存のk-meansアルゴリズムで点の数をO(klogn)からk以下に減らす 最近傍探索は1次元ベクトルにRandom Projectionしてる へぼそう ...
• 論文一覧
  ...ans Streaming k-means approximation StreamKM++ A Clustering Algorithm for Data Streams k-means++ The Advantages of Careful Seeding Streaming k-means on Well-Clusterable Data A Local Search Approximation Algorithm for k-Means Clustering Fast and Accurate k-means For Large Datasets Hartigan s Method k-means Clustering without Voronoi Hartigan s K-Means Versus ...
• 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 ...
• 気になった論文
  ...ngle-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders Graph Isomorphism in Quasipolynomial Time Laszlo Babai IEEE Symposium on Foundations of Computer Science FOCS 2000 Random graph models for the web graph Hardness of Approximate Hypergraph Coloring How Bad is S...
• Spectral Rotation versus K-Means in Spectral Clustering
  Spectral Rotation versus K-Means in Spectral Clustering Jin Huang, Feiping Nie, Heng Huang AAAI 2013 Kindle 買ったし再開だよ スペクトラルクラスタリング $$ \sum_{i=1}^{K} \frac{s(C_i, \bar{C_i})}{\sigma(C_i)} $$ σは点の個数、重みの和等 sはカットの重み $$ \hat{q}_i $$をj要素がクラスタiに属するかを表すindicatorとすると 上の目的関数は行列とかで良さげに書ける 正規化とかすると↓みたいになる $$ \sum_{i=1}^{K}q_i^{\top}(D-W)q_i $$ よくあ...
• 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-...
• 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) \...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• 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の多項式が掛かってくる 実際には速い 実験;...
• 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 $$ ...
• 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...
• 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...
• 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}(...
• 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とグラフクラスタリングが等価だ...
• 2.5K-Graphs: from Sampling to Generation
  2.5K-Graphs from Sampling to Generation Minas Gjoka, Maciej Kurant, Athina Markopoulou INFOCOM 2013 概要 2.5K-graph 次数kの頂点と次数lの頂点を結ぶ辺の個数の分布と、次数kの頂点のクラスタ係数の平均値を分布に着目 ソーシャルネットワークから↑を高速に見積もり、そういう分布になるグラフも生成する ↑以外の分布も結構一致する！ 問題 JDD(k,l) = 次数kの頂点と次数lの頂点を結ぶ辺の数 JDD = Joint Degree Distribution 2頂点の部分グラフの次数依存の分布 ‾c(k) = 次数kの頂点のクラスタ係数の平均値 dk...
• 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
• Chromatic Correlation Clustering
  Chromatic Correlation Clustering Francesco Bonchi, Aristides Gionis, Francesco Gullo, Antti Ukkonen KDD 2012 概要 Correlation clustering 各頂点対に類似度がありクラスタリング 今回は，頂点対にラベルがついたクラスタリング 応用 タンパク質間相互作用ネットワーク，関係ネットワーク，共著ネットワーク 問題定義 完全グラフが与えられる Correlation Clustering $$ \text{cost}({\cal C}) = \sum_{(x,y) \in V \times V {\cal C}(x) = {\cal C}(y...
• 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...
• 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
  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} $$ ...
• 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 ...
• 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) $$で影響最大化 ...
• 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 ...
• Memory Efficient Minimum Substring Partitioning
  Memory Efficient Minimum Substring Partitioning Yang Li, Pegah Kamousi, Fangqiu Han, Shengqi Yang, Xifeng Yan, Subhash Suri In VLDB 2013 アブスト 並列DNAシーケンス技術が進歩している Illumina, SOLiD Human Whole Genome Sequencingの値段 $3,750 数G個の断片をとってきて遺伝子全体の再構築 short read A,C,G,Tからなる短いシーケンス 既存手法 ランダムサンプリングして、重複があるreadを拾ってくる readの長さ 数十 ~ 数百 ...
• 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)$$ 次の反復...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• Minimum Bisection is Fixed Parameter Tractable
  Minimum Bisection is Fixed Parameter Tractable Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh STOC 2014 minimum bisection グラフを半分にするためには何本の辺を除けばいいか k本取り除いて頂点集合AとBに分割される ||A|-|B||≦1 これがFPT!! O(2^O(k^3)*n^3*log^3 n) k 解の大きさ おおまかな流れ 専用の木分解→DP!! 分割 A∪B = V E(A\B, B\A) = φ 木幅は制限し...
• 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...
• On the Streaming Complexity of Computing Local Clustering Coefficients
  On the Streaming Complexity of Computing Local Clustering Coefficients Konstantin Kutzkov, Rasmus Pagh WSDM 2013 概要 ワンパスでlocal clustering coefficientを求めたい ローカルなので、頂点ごと 辺リストが任意の順でもらえる 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要 ↑の限界にマッチした乱択アルゴリズムを考案 Lower bound Theorem 1 ワンパス乱択アルゴリズムが 次数2dの頂点はクラスタ係数0 ...
• 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...
• Streaming Graph Partitioning for Large Distributed Graphs
  Streaming Graph Partitioning for Large Distributed Graphs Isabelle Stanton, Gabriel Kliot In KDD 2012 メモ セミナー K.Inabaさん 問題 巨大グラフを複数に分割したい ストリーミングアルゴリズムじゃないと意味ないお 入力 G(V,E) k マシン台数 ε アンバランス度 出力 V1, V2, …, Vk $$ |Vi| \leq \frac{(1+\epsilon)|V|}{k} $$ または $$ \sum \deg(V_i) \leq (1+\epsilon)\sum \deg(v)/k $$ を満たすよ...
• 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...
• gSketch: On Query Estimation in Graph Streams
  gSketch On Query Estimation in Graph Streams Peixiang Zhao, Charu C. Aggarwal, Min Wang VLDB 2012 yanoさん 概要 ストリームモデルでのグラフの扱い 問題 辺がストリームでもらえる (xi, yi; ti)の形、tiはタイムスタンプ f(xi, yi; ti) 重みのようなもの、普段は1 全体構造は謎 クエリ Edge Query Σf(x,y,ti)を推定 ある辺が今までに来た回数 Aggregate Subgraph Query あるサブグラフに含まれる辺が来た回数の平均・合計・最小を求める Γ(f~(x...
• DAG Reduction: Fast Answering Reachability Queries
  DAG Reduction Fast Answering Reachability Queries Junfeng Zhou, Shijie Zhou, Jeffrey Xu Yu, Hao Wei, Ziyang Chen, Xian Tang SIGMOD 2017 概要 到達可能性クエリを高速に応えるためのグラフの前処理を考える． ◯最も基本的な処理 = SCCを潰しDAGにする これだけでは不十分なので，以下の"DAG reduction"を考え， 到達可能性を失わずにグラフを更に小さく（し，既存の到達可能性クエリ手法を適用）する． ◯Transitive reduction (TR) 目標 Transitive closureを保持したまま辺を削除する． 著...
• 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$を求めたい！...
• From Dango to Japanese Cakes: Query Reformulation Models and Patterns
  From "Dango" to "Japanese Cakes" Query Reformulation Models and Patterns Paolo Boldi, Francesco Bonchi, Carlos Castillo, Sebastiano Vigna 概要 Reformulation model QRT(query reformulation type)の分類 学習結果は精度92% Reformulation strategies QRTの列からミッションを探してパターンを見つける 手動（小さいデータ）と一致するよ！ Query Flow GraphをQRTでアノテート レコメンドをQFG上のランダムウォークでやる ...
• Piggybacking on Social Networks
  Piggybacking on Social Networks Aristides Gionis, Flavio Junqueira, Vincent Leroy, Marco Serafini, Ingmar Weber In VLDB 2013 岩田さん Piggybacking? おんぶ 概要 巨大なSNS クラスタ係数を利用してスループット向上 ↑最適化問題 アルゴリズム O(log n)近似 Hadoop用のヒューリスティクス スループット とりあえず1ユーザに1台のサーバ 実際は1台が複数ユーザ 定式化 Social Dissemination Problem 辺 ...
• 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| ...
• Delineating Social Network Data Anonymization via Random Edge Perturbation
  Delineating Social Network Data Anonymization via Random Edge Perturbation Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Panos Kalnis, Hung Keng Pung CIKM 2012 概要 random edge perturbation によるグラフの匿名化 上を攻撃する手法 グラフの特徴量を推定 Random Edge Perturbation 辺を確率μで独立に足したり消したりする XORってこと denseになるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
• 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...
• Triadic Measures on Graphs: The Power of Wedge Sampling
  Triadic Measures on Graphs The Power of Wedge Sampling C. Seshadhri, Ali Pinar, Tamara G. Kolda SDM 2013 概要 クラスタ係数、次数毎のとか、色々を統一的なフレームワークでもとめる wedgeを適当な重みでサンプリングしてtriangleを数えるだけ サンプルサイズがグラフのサイズに依存しないところがポイント シンプルにboundが出る 提案手法 サンプリングの方法 基本的にはwedgeをとってきて、それがtriangleを構成するか？を判定する global clustering coefficient choose(deg(v), 2)に比例する確率でv...
• 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 ...
• 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を...
• 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 ...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• Dynamic PageRank using Evolving Teleportation
  Dynamic PageRank Using Evolving Teleportation Ryan A. Rossi and David F. Gleich WAW 2012 概要 嗜好ベクトルが変化する下でPageRankの微分方程式を考える Euler法が実は、べき乗法=Richardson法と似た手法 嗜好ベクトルが固定なら、普通のPageRankに収束する 色々便利; 予測 動的テレポーテーションなPageRank Δx^(k) = x^(k+1)-x^(k) = (1-α)v-(I-αP)x^(k)のアナロジーで、 x (t) = (1-α)v(t)-(I-αP)x(t)という微分方程式を考える 普通の微分方程式なので、x(t)は解ける 特にv(t)=tの時は...
• 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ネットワークでの応用例...
• 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に適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
• Clustering Large Probabilistic Graphs
  Clustering Large Probabilistic Graphs George Kollios, Michalis Potamias, Evimaria Terzi TKDE 2013 概要 Uncertain graphのクラスタリング 編集距離ベースの目的関数 Correlation Clusteringと同じになる その他自明な拡張 問題定義＋提案手法 pClusterEdit クラスタグラフ （Gと同じ頂点集合を持つ、）互いに素なクリークの和集合 期待編集距離 「Gからサンプルした部分グラフ」と「クラスタグラフ」の（辺の意味での）編集距離の期待値 辺毎に考えれば良く、クラスタグラフに辺が無い→p(e)／有る→1-p(e) これはCo...
• @wiki全体から「Streaming k-means on Well-Clusterable Data」で調べる

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