todo314 @ ウィキ
todo314 @ ウィキ

Random-walk Domination in Large Graphs

todo314 @ ウィキ内検索 / 「Random-walk Domination in Large Graphs」で検索した結果

検索 :
  • Random-walk Domination in Large Graphs
    Random-walk Domination in Large Graphs Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng ICDE 2014 Random-walk domination in large graphs problem definitions and fast solutions を参照 ICDE random walk 2013-12-27 01 24 46 (Fri)
  • Random-walk domination in large graphs: problem definitions and fast solutions
    Random-walk domination in large graphs problem definitions and fast solutions Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng CoRR 多分KDDに出した？ 概要 2種類ランダムウォーク支配問題、というものを考えた ソーシャルネットワーク上にアイテムを配置したり、色々なアプリケーションがある どの頂点からも長さLのランダムウォークによるヒッティングタイムが短い 長さLのランダムウォークがターゲットノードに到達する確率が高い DPベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
  • 論文一覧
    ...Graph Random-walk Domination in Large Graphs Evaluating Multi-Way Joins over Discounted Hitting Time Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive ... International Conference on Very Large Data Bases VLDB 2010 Shortest Path Computation on Air Indexes Fast Incremental and Personalized PageRank k-Nearest Neighbors in Uncertain Graphs...
  • 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 $$ を満たすよ...
  • Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large ...
    Subgraph Frequencies Mapping the Empirical and Extremal Geography of Large Graph Collections Johan Ugander, Lars Backstrom, Jon Kleinberg In WWW 2013 メモ 岩田さん 概要 social networkを全体を見て解析するのではなく、密な部分ごとに見る 3-4頂点の部分グラフの出現頻度を見ると特徴がわかる 実験データ Facebook Lars BackstromがFacebookの人だからしょーがないね(´・ω・`) 抽出する部分グラフ Neighborhoods 友人 Groups...
  • 気になった論文
    理論計算機科学 ACM Symposium on Theory of Computing STOC 2000 Circuit minimization problem A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Improved algorithms for submodular function minimization and submodular flow On dual minimum cost flow algorithms The small-world phenomenon an algorithm perspective A random graph model for mass...
  • 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...
  • Sampling Node Pairs Over Large Graphs
    Sampling Node Pairs Over Large Graphs Pinghui Wang, Junzhou Zhao, John C.S. Lui, Don Towsley, Xiaohong Guan In ICDE 2013 概要 ノードのペアに関する性質 平均距離とか サンプリングで求めるが 一様っぽいサンプリングは一様じゃない xを決める、u,vをxの近傍から決める [u,v]が選ばれる確率は$$ \sum_{u-x-v}{\deg(x) \choose 2}^{-1} $$に比例 biasがかかる 提案手法 weighted vertex sampling neighborhood random walk 問題 ...
  • Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation
    Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation Haim Avron IBM Research（っぽい？） COSN 2013 概要 タイトルそのまんまの内容 トレースを愚直に求めるのは難しいので、ランダムベクトルで挟んでいっぱい計算して平均をとる サンプル数は結構多いけど、実験的にはO(log^2|V|)個でよい 実験は微妙… 既存手法とか 簡単なアルゴリズム Σdeg(v)^2で遅い 行列積とかで頑張る…O(|E|^1.41) 近似する場合…サンプリング Spectral counting $$ \Delta(G) = \fr...
  • FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
    FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri KDD 2014 概要 $$ \pi_s(t) \delta $$を$$ \mathcal{O}(\sqrt{d/\delta}) $$時間で近似計算 相対誤差が小さい 既存は$$ \Omega(1/\delta) $$時間で、$$ \delta=\Theta(1/n) $$にしたいので遅い□ 計算時間の下限$$ \Omega(1/\sqrt{\delta}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • A scaling law for random walks on networks
    A scaling law for random walks on networks Theodore J. Perkins, Eric Foxall, Leon Glass, Roderick Edwards Nature Communications 2014 話題 「パス実現確率」分布 任意のs-tパス頂点からなる誘導部分グラフについて，長さrのパスが発生する確率分布は？ cycleがない→有限 1つ→指数 沢山→べき乗則 応用？ 現実のグラフの特徴ではない PageRankの解析？ Nature Communications ランダムウォーク 2014/12/06
  • 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...
  • Gelling, and Melting, Large Graphs by Edge Manipulation
    Gelling, and Melting, Large Graphs by Edge Manipulation Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, Christos Faloutsos CIKM 2012 概要 これまでは頂点を弄って拡散を操作していた 今回は辺を追加／削除して拡散を増強／減退 アルゴリズム，解析，実験 ベストペーパー 動機付け NetMelt問題 辺を削除して感染を最小化したい マルウェアの広がりとか 問題 既存手法は頂点に関してのみ NetGel問題 辺を追加して拡散を拡大したい 問題 候補が多すぎO(n^2)...
  • 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になるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
  • PageRank on an Evolving Graph
    PageRank on an Evolving Graph Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, Eli Upfal In KDD 2012 概要 PageRankの入力データが固定なんて意味ないだろいい加減にしろ！！ ちょこちょこグラフが変化するモデルを考えたよ でも、実際にはあまりprobeできないので、1頂点だけout-edgeを調べる問題を考えたよ 頂点を選ぶ簡単なアルゴリズムを作ったけど、理論的保証があるし、実験的にも上手くいったよ モデル G^t 時刻tでのモデル G^{t+1}とG^tの違いは（極端には）多くないとする 高々1頂点だけprobeできる どの段階でもある程度精度の良いPageRankベクトル...
  • Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly ...
    Fast Robustness Estimation in Large Social Graphs Communities and Anomaly Detection Fragkiskos D. Malliaros, Vasileios Megalooikonomou, Christos Faloutsos SDM 2012 概要だけ 頂点は閉路の数が多いほど重要と考える 部分グラフ中心性（物理側から持ってきた） $$ \mathrm{SC}(v) = \sum_{i} u_{vi}^2 \sinh(\lambda_i) $$ i番目の固有ベクトルのv要素目 まとめると $$ \xi(G) = \sqrt{ \frac{1}{|V|}\sum_{v} \left\{ \log(u_{v1}) -...
  • A General Framework of Hybrid Graph Sampling for Complex Network Analysis
    A General Framework of Hybrid Graph Sampling for Complex Network Analysis Xin Xu, Chul-Ho Lee, Do Young Eun INFOCOM 2014 概要 グラフをサンプリングしたい どっちかっていうとΣf(v)を近似したい ランダムウォークとかランダムジャンプとかある ランダムジャンプはたまに失敗する ↑を統合したのを考えて解析 分散（小さいと良）がランダムジャンプ確率に対して凸 既存手法 ランダムウォーク Simple Random Walk (SRW) with Re-weighting Metropolis-Hastings Random Walk ...
  • 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_...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • k-Nearest Neighbors in Uncertain Graphs
    k-Nearest Neighbors in Uncertain Graphs Michalis Potamias, Francesco Bonchi, Aristides Gionis, George Kollios VLDB 2010 概要 k近傍クエリ 最短距離や酔歩に基づく尺度を拡張 厳密計算は難しい Monte-Carloサンプリングで近似アルゴリズム グラフ変形，枝刈り 実験：数十M辺 メモ VLDB版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • The Effect of the Back Button in a Random Walk: Application for PageRank
    The Effect of the Back Button in a Random Walk Application for PageRank Fabien Mathieu, Mohamed Bouklit WWW 2004 概要 バックボタンを入れたPageRankを考える 計算も早そう Back Button Model Reversible Back バックボタンの効果 1つ前の「状態」に戻る 2回バックすると，今いるページに戻る 記憶領域は前の状態一つだけ どれかの辺をたどる確率とバックボタンの確率は同じ t+1ステップ目でwからvに遷移する確率 Pr[今wにいてwvを辿る]+Pr[vからwに移動した状態でバック] (wv∈E) Pr...
  • Preserving Personalized Pagerank in Subgraphs
    Preserving Personalized Pagerank in Subgraphs Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich ICML 2011 概要 既存のグラフサンプリングは、Sを計算して、G[S]を出力 局所的な指標は良いけど、大域的な指標は駄目 S={u,v}だと、N(u)∩N(u)が大きくても、微妙になる 辺を弄ってPPRを保持する問題 SINKを足すと上手く行く 密になるので疎化 問題定式化と提案手法 入力 $$ G=(V,w_G), S \subseteq V $$ 出力 $$ H=(S,w_H) $$ 目標 $$ \pi_i^H(j) = \pi_i^H(...
  • Efficient Subgraph Search over Large Uncertain Graphs
    Efficient Subgraph Search over Large Uncertain Graphs Ye Yuan, Guoren Wang, Haixun Wang, Lei Chen VLDB 2011 概要 閾値以上の確率でクエリが部分グラフ同型となるデータベース中のグラフをとってくる問題 基本的な方針に加えて、様々な確率的要素を考慮した枝刈り手法を提案 実験したらやったでおい 問題設定 入力 $$ D = \{\mathcal{G}_1, \ldots, \mathcal{G}_n\}, Q, \epsilon $$ 出力 $$ \mathcal{G} \in \mathcal{D} \text{ s.t. } \Pr_{G \sim \mathcal{G}}[Q \subs...
  • 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...
  • VoG: Summarizing and Understanding Large Graphs
    VoG Summarizing and Understanding Large Graphs Danai Koutra, U Kang, Jilles Vreeken, Christos Faloutsos SDM 2014 概要 ソーシャルネットワークがもらえる グラフの構造に対してなにか言いたい いろんな語彙をもってしてグラフを簡潔に表現したい 但し，グラフ圧縮が目的では無くてあくまでグラフの理解が目的（らしい） 問題定式化 効率的手法 実験 提案手法 MDLを評価関数として使う Mが構造の集合，GがグラフでL(G, M) 位置とかそういう情報も記述長がある 語彙 Ω={完全・近似クリーク，完全・近似二部グラフ，スタ...
  • An Application of Boosting to Graph Classification
    An Application of Boosting to Graph Classification Taku Kudo, Eisaku Maeda, Yuji Matsumoto NIPS 2004 概要 グラフ分類にBoostingを応用する（最初期の論文？） 提案手法 概要 ラベル付きグラフがL個あります 決定株$$ h_{\langle t,y \rangle}(\mathbf{x}) $$ xについてある部分グラフyを含んでいたらyを返す ものすごく弱いので、Boosting(特にAdaBoost)を適用 決定株をK個用意する $$ \mathrm{gain}(\langle t,y \rangle) = \sum_{1 \leq i \leq L} ...
  • Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and ...
    Towards Scaling Fully Personalized PageRank Algorithms, Lower Bounds, and Experiments Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós Internet Mathematics 2005 概要 fully personalizationが良いです ランダムウォーク手法を考案 分解定理を使って少し精度改善 実験もしました 関連研究 Topic-sensitive PageRank [Haveliwala 02] tトピックの線形結合のみ、O(tV)空間 Hub Decomposition [Jeh-Widom 03...
  • Querying K-Truss Community in Large and Dynamic Graph
    Querying K-Truss Community in Large and Dynamic Graph Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, Jeffrey Xu Yu SIGMOD 2014 (α, γ)-OCS γ-quasi-k-クリークを頂点とする γ{k choose 2}本以上のk頂点部分グラフ ↑を各頂点として，α頂点以上共有なら辺を張る ヘボい！ k-truss どの辺も少なくともk-2個の三角形に属する極大な部分グラフ 辺の連結 どの2辺も三角形の連結で到達可能 k-truss コミュニティ vを含むk-truss コミュニティを列挙 利点 ...
  • TurboISO: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large ...
    TurboISO Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases Wook-Shin Han, Jinsoo Lee, Jeong-Hoon Lee In SIGMOD 2013 概要 graph isomorphismの高速アルゴリズム 謎データ構造と探索の仕方を工夫して、探索候補領域を狭める 数オーダーレベルで速いらしい
  • 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$を求めたい！...
  • Marginalized Kernels Between Labeled Graphs
    Marginalized Kernels Between Labeled Graphs Hisashi Kashima, Koji Tsuda, Akihiro Inokuchi ICML 2003 概要 新しくグラフカーネルを作りました ランダムウォークで生成されるラベル列のカウントが特徴ベクトル 無限次元だけど、効率的に計算できます Marginalized Kernel 本当に欲しいもの $$ K({\bf x}, {\bf x} ) = \sum_{{\bf h}}p({\bf x}|{\bf h}) p({\bf x} |{\bf h}) p({\bf h}) $$ hという隠れ変数からx、x が生成される過程 実際に取れるもの $$ K({\bf x}, {\bf...
  • 4chan and /b/: An Analysis of Anonymity and Ephemerality in a Large Online ...
    4chan and /b/ An Analysis of Anonymity and Ephemerality in a Large Online Community Michael S. Bernstein, Andrés Monroy-hernández, Drew Harry, Paul André, Katrina Panovich, Greg Vargas ICWSM 2011 概要 anonymity（匿名性）とephemerality（短命であること）の面から4chanを理解する 4chanと/b/ /b/はランダム掲示板 4chan全体の30%のトラフィック リプライしたりすると最初のページに浮上 15ページ目の最下層に行くと消されて`Page Not Found ...
  • COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
    COMMIT A Scalable Approach to Mining Communication Motifs from Dynamic Networks Saket Gurukar, Sayan Ranu, Balaraman Ravindran SIGMOD 2015 概要 テンポラルネットワーク上で頻出するモチーフを抽出したい 次数列に変換，部分列マイニングで絞る Frequent subgraph mining A- B(1)とB- C(2) A- B(2)とB- C(1) 違うお グラフ同型問題的なので，時間的関係を考慮するのはちょいやばめ？ マイニング的手法…厳密でない 定義 辺はある時刻に瞬間的に発生 $$ |t_i - t_...
  • Top-k Reliable Edge Colors in Uncertain Graphs
    Top-k Reliable Edge Colors in Uncertain Graphs Arijit Khan, Francesco Gullo, Thomas Wohler, Francesco Bonchi CIKM 2015 概要 各辺に色とその出現確率がついたuncertain graphsを考える s-tの連結確率が最大となるようなk色を求める問題 （残りの色に対応する確率は0） 難しいのでヒューリスティック 動機付け 応用 生物学的ネットワーク上の経路生成 トピック付き情報カスケード よさ気な特徴を見つけるために使う 問題定義 各辺e各色cについて，その出現確率 $$ = p_e^c $$ 色集合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 ...
  • Where Graph Topology Matters: The Robust Subgraph Problem
    Where Graph Topology Matters The Robust Subgraph Problem Hau Chan, Shuchu Han, Leman Akoglu SDM 2015 概要 輸送／通信ネットワークでは頑健性が大事 全体の頑健性でなく，局所的な頑健性に注目 どちらかというと部分グラフマイニング 密グラフっぽいけど目的関数がぜんぜん違う 平均次数・辺密度は関係ない NP-hardなのでヒューリスティック2つ メモ どうやら全体的にMake It or Break It Manipulating Robustness in Large Networksが大元のアイデアらしい 定義等 頑健性として，[Wu, Mauri...
  • 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) =...
  • How to Partition a Billion-Node Graph
    How to Partition a Billion-Node Graph Lu Wang, Yanghua Xiao, Bin Shao, Haixun Wang MSR ICDE 2014 概要 分散メモリシステムにグラフを載せることを考える どうやって分割すればイイ？ 部分グラフのサイズ、辺カット、等が評価基準 提案手法 multi-level propagation G頂点のグラフでも数時間で処理できたよ！ 背景 Kerninghan-Lin メモリベース グラフを二分していく クラスタ間の頂点を辺カットが小さくなるように交換 METIS Graph Coarseningをする 先にある程...
  • 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} $$ ...
  • First Passage Time for Random Walks in Heterogeneous Networks
    First Passage Time for Random Walks in Heterogeneous Networks S. Hwang, D.-S. Lee, B. Kahng PRL 2012 概要 スケールフリーネットワーク上のランダムウォーク 次数kの頂点への到達のしやすさ：3パターン（ベキ指数γ、スペクトル次元で分ける） 色々 スペクトル次元 ラプラシアン行列の固有値の分布のベキのところ 何か固有値ソートして並べたのをフィッティングしたとするらしい RTO(Return to the origin) R(t) tステップ後に元の頂点に戻る確率 スペクトル次元が関係 ホントは頂点毎に変わるよ！ 次数で式が3パターンになるらしい ...
  • 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...
  • 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...
  • 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...
  • 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...
  • A Structural Smoothing Framework For Robust Graph-Comparison
    A Structural Smoothing Framework For Robust Graph-Comparison Pinar Yanardag, S. V. N. Vishwanathan NIPS 2015 概要だけ R-convolutionの問題 特徴空間がデカイと、自分以外とは類似しにくい（対角優位問題） 低次数部分構造（ちっちゃい部分グラフ）が分布を占めてしまう 部分構造は互いに関連しているけど、R-convolutionはEXACTを要求するので微妙 Deep Graph Kernelとはここが違うらしい 解決法 頻度ベクトルを平滑化する 色んな部分グラフを層っぽい感じに捉えて、関連性で平滑化 アイデア Maximum Likeliho...
  • Scalable Maximum Clique Computation Using MapReduce
    Scalable Maximum Clique Computation Using MapReduce Jingen Xiang, Cong Guo, Ashraf Aboulnaga ICDE 2013 概要 MapReduceを使った最大クリークアルゴリズム グラフの分割が味噌 Multi-depth Color-based (BMC) partitioning 分割した後は個々に解く この時も枝刈りをして早くする 実験は10^2~10^3オーダー頂点で密なグラフ 最大クリークアルゴリズム 分割後に使う最大クリークアルゴリズム MCRアルゴリズム（すでにある手法） 分枝限定法 ωを最大クリークのサイズとするとω(G)は下のどれか $$ \...
  • 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...
  • Estimating Clustering Coefficients and Size of Social Networks via Random Walk
    Estimating Clustering Coefficients and Size of Social Networks via Random Walk Stephen J. Hardiman, Liran Katzir In WWW 2013 メモ Liran KatzirはMSR Israel 概要 ランダムウォークでクラスタ係数と頂点数を見積もる 全体をとってくるのが厳しい用 ちょっとタイムリー 既存手法よりかなり良い 近似が指数関数的によくなる（ランダムウォークの長さの 頂点のIDと、隣接リスト（次数）さえわかれば良い しかも前と後の1つずつだけ覚えていれば計算可能 問題 global clustering coefficien...
  • BackRank: an Alternative for PageRank?
    BackRank an Alternative for PageRank? Mohamed Bouklit, Fabien Mathieu WWW 2005 概要 The Effect of the Back Button in a Random Walk Application for PageRankの続き Irreversible Backを実装して実験 結果 greenhouse effect (温室効果)を考えているらしい ランキングが割りと逆転している1位2位とか PageRank WWW 2014/12/08
  • Local Graph Sparsification for Scalable Clustering
    Local Graph Sparsification for Scalable Clustering Venu Satuluri, Srinivasan Parthasarathy, Yiye Ruan SIGMOD 2011 概要だけ クラスタリング手法 (Metis, Metis+MQI, MLR-MCL, Graclus) を疎化で高速化したい 基本アイデアは、「辺の重要度 = 近傍のJaccard類似度」 これだけだと、最密なコミュニティの辺の重要度が高すぎて、他のコミュニティ内の辺がなくなってしまう 各頂点の疎具合を制限するために、次数をd^eと設定 Jaccard類似度はMinHashで高速近似計算 比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった 感想 ...
  • @wiki全体から「Random-walk Domination in Large Graphs」で調べる

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