todo314 @ ウィキ
todo314 @ ウィキ

k-Nearest Neighbors in Uncertain Graphs

todo314 @ ウィキ内検索 / 「k-Nearest Neighbors in Uncertain Graphs」で検索した結果

検索 :
  • 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • 論文一覧
    ... 2010 k-Nearest Neighbors in Uncertain Graphs VLDB 2010 Finding Top-k Maximal Cliques in an Uncertain Graph ICDE 2010 Fast Discovery of Reliable k-terminal Subgraphs PAKDD 2010 Discovering Frequent Subgraphs over Uncertain Graph Databases under ... KDD 2010 BMC An Efficient Method to Evaluate Probabilistic Reachability Queries DASFAA 2011 Efficient Discovery of Frequent...
  • 気になった論文
    ...uction of k-Nearest Neighbor Graphs in Metric Spaces Fast and Simple Approximation of the Diameter and Radius of a Graph Kernels for the Vertex Cover Problem on the Preferred Attachment Model Practical Partitioning-Based Methods for the Steiner Problem Updating Directed Minimum Cost Spanning Trees Experiments on Exact Crossing Minimization Using Column Generation Goal Di...
  • 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につ...
  • 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で同じ計算時間 ...
  • Discovering Highly Reliable Subgraphs in Uncertain Graphs
    Discovering Highly Reliable Subgraphs in Uncertain Graphs Ruoming Jin, Lin Liu, Charu C. Aggarwal KDD 2011 概要 高信頼部分グラフ問題…連結な確率が閾値以上の（誘導）部分グラフをとってくる 厳密は無理→近似 イントロ 電気通信網 (telecommunication network) タンパク質間相互作用ネットワーク (protein interaction network) ソーシャルネットワーク …信頼／影響 部分グラフ発見の応用は上の面で色々ある 密部分グラフ抽出っぽいが違う 問題定式化 $$ G=(V,E,p) $$のネットワ...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • Triangle-Based Representative Possible Worlds of Uncertain Graphs
    Triangle-Based Representative Possible Worlds of Uncertain Graphs Shaoying Song, Zhaonian Zou, Kang Liu DASFAA 2016 概要 三角形次数を保存する決定的グラフを抽出するよ！ The Pursuit of a Good Possible World Extracting Representative Instances of ...の発展 やってることは簡単なヒューリスティクス 問題定義 $$ \sum_{v}|d_{G}(v)-\bar{d}_{\mathcal{G}}(v)| + \sum_{v}|t_{G}(v)-\bar{t}_{\mathcal{G}}(v)| $$を最小化せよ ...
  • Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive ...
    Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, Tan Jin ICDE 2014 概要 よくある期待値クエリ評価と閾値クエリ評価を計算したい 愚直のMonte-Carloは分散が悪いので、 階層的な標本をする推定器を提案 影響力評価と期待信頼距離クエリに応用 解く問題 クエリ頂点q、何らかの評価関数φq(G) 期待値クエリ $$ \mathbf{E}_{G \sim \mathcal{G}}[\phi_q(G)] $$ 閾値クエリ $$ \mathbf{Pr}_{G ...
  • Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph
    ...arch with k-Nearest Neighbor Graph Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang In IJCAI 2011 メモ hatenaから引っ張ってきたのだからアレ 概要 k近傍グラフ上での山登り方による近似最近傍探索 Locality Sensitive Hashing、KD-木よりも速くて高速 問題 最近傍探索。d次元空間上の点集合Dと距離尺度ρが与えられる。各クエリQに対して、次を求める $$ X^{*} = ￥arg \min_{X \in D} \rho(X, Q) $$ 線形探索 O(nd) 提案手法 The Graph Nea...
  • 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 問題 ...
  • The Power of Random Neighbors in Social Networks
    The Power of Random Neighbors in Social Networks Silvio Lattanzi, Yaron Singer WSDM 2015 概要 友達は友達が多い (friendship paradox) power-lawが十分条件では無い どういうモデルがparadoxを説明できるのか？ というわけで，モデルを提案 辺を張り替える 影響最大化への適用例 友達の逆説 friendship paradox 友達は友達が多い （頂点の近傍次数） （その頂点の近傍の平均次数） power-lawが十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
  • The Pursuit of a Good Possible World: Extracting Representative Instances of ...
    The Pursuit of a Good Possible World Extracting Representative Instances of Uncertain Graphs Panos Parchas, Francesco Gullo, Dimitris Papadias Francesco Bonchi SIGMOD 2014 概要 Uncertain graphsを扱うのは大変 サンプリングは標本数が多くなる 問題：最短経路長，パターンマイニング，部分グラフ探索 問題毎にアドホックに開発されている→既存の枠組みが無駄→辛い あるグラフで代表させたい 元の性質を保ったまま，決定的な代表的グラフを作るよ 元の性質=（今回は）期待頂点次数 平均次数リワイヤ(AD...
  • Assessing Attack Vulnerability in Networks with Uncertainty
    Assessing Attack Vulnerability in Networks with Uncertainty Thang N. Dinh, My T. Thai INFOCOM 2015 概要 ネットワーク脆弱性を「期待対連結性」で評価したい 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題 提案手法は、LPによる緩和＋交換ヒューリスティクス 期待対連結性のFPRASを提案 期待対連結性 脆弱性の色々な尺度 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない 対連結性 (pairwise connectivity)は結構良いらしい 致命的頂点検出問題 (critical node detection; CND) 普通...
  • Fast Algorithm for the Lasso based L1-Graph Construction
    Fast Algorithm for the Lasso based L1-Graph Construction Yasuhiro Fujiwara, Yasutoshi Ida, Junya Arai, Mai Nishimura, Sotetsu Iwamura VLDB 2016 概要 L1-Graph + Lassoなグラフ構築手法がある とても遅いので高速化 基本アイデアは正重みな辺の事前計算＋反復の高速化 Lasso based L1-graph Least absolute shrinkage and selection operator $$ \min_{\mathbf{w}_p} \frac{1}{2M}\| \mathbf{x}_p - \mathbf{X} \mathb...
  • 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(...
  • 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...
  • 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 ...
  • 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...
  • Computing Top-k Closeness Centrality Faster in Unweighted Graphs
    Computing Top-k Closeness Centrality Faster in Unweighted Graphs Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke ALENEX 2016 概要 近接中心性の上位k頂点を厳密に得たい 値が似通っているので，近似だと不十分 2種類の距離和の下限を使った簡単な枝刈り手法を提案 実験したら既存の枝刈り手法より探索辺数の意味で良かった 提案手法 戦略 各頂点からの距離和の下限を計算 下限の小さい順に見ていって遅延評価的にBFSをして確定させていく 最悪でn回BFSする ...
  • Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free ...
    Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs Joseph Cheriyan, Laszlo A. Vegh In FOCS 2013 k-connectivity SNDP min v(F) s.t. (V,F)がk-connected 近似アルゴリズム O(log k log n/(n-k)) k=n-o(n)の時やばお O(k) n 3k-3 iterative rouding 6-近似 n≧k^3(k-1)+k ←かっこいい！！（この論文） Ω(k^3)（福永さん） 何でノードだとめんどいの？ ...
  • On Triangulation-based Dense Neighborhood Graph Discovery
    On Triangulation-based Dense Neighborhood Graph Discovery Nan Wang, Jingbo Zhang, KianLee Tan, Anthony K. H. Tung VLDB 2011 概要 僕の考えた最強のdense graph 任意の2頂点が共有する近傍がλ個以上 そこそこいい性質を持っている（らしい） triangulationを上手く使って、検出 DN-graph λ(V ) 頂点対が共有する近傍の数の最小値 Dense Neighborhood graph G =(V ,E )について 任意の2頂点はλ個以上の近傍を共有している λ(V ∪{v}) λ, λ(V -{v})≦λ...
  • Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local ...
    Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local Community Methods David F. Gleich, Seshadhri Comandur せしゃどり In KDD 2012 (closed) vertex neighbor 距離1以内の頂点集合 これがそれなりに良いコミュニティ マジかよ 理論的に示す 実データも使う 目的関数 $$ vol(S) = \sum_{v \in S} \deg(v) $$ $$ cut(S,T) = \{ (u, v) \in E | u \in S, v \in T \} $$ コンダクタンス（これが目的関数） ...
  • 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...
  • On k-skip Shortest Paths
    On k-skip Shortest Paths Yufei Tao, Cheng Sheng, Jian Pei SIGMOD 2011 概要 k-skip coverを考えた 要はk-shortest pathのhitting set 色々使えそう 理論的な解析とそこそこ速そうなアルゴリズム 問題定義とか k-skip Shortest Paths SP(s,t)をs-t間の最短経路とし，その順番をv_1,v_2,…,v_lとする P*が以下を満たすならs-t間のk-skip shortest path ∀i P*∩{v_i,…,v_{i+k-1}}≠∅ つまり，どの連続するk頂点を選んでも，どれかひとつ以上はP*に含まれている k-s...
  • Crowdsourcing Algorithms for Entity Resolution
    Crowdsourcing Algorithms for Entity Resolution Norases Vesdapunt, Kedar Bellare, Nilesh Dalvi VLDB 2014 概要 Entity Resolution = 同じエンティティを差すレコード集合を特定する 入力=uncertain graph（辺確率はある種の信念） 人間に各点対の辺の有無を質問できる 出来るだけ少ない質問数で、完遂したい 推移閉包の性質を利用する 手法を提案 既存の手法は実は良くない 実験したよ 問題定式化 Uncertain graph $$ G=(X,E) $$ 各辺eは確率p(e)で生きる ランダムグラフがクラスタリ...
  • Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms
    Truss Decomposition of Probabilistic Graphs Semantics and Algorithms Xin Huang, Wei Lu, Laks V.S. Lakshmanan SIGMOD 2016 概要 Core decomposition of uncertain graphsのk-trussへの拡張 局所的：部分グラフの各辺がk-2△に含まれる確率≧γ k-coreっぽく辺を取り除いていく 当該確率はDPで計算 大域的：部分グラフ全体がk-trussを含む≧γ 確率の厳密計算が#P-hard ランダムサンプリングして探索 実験しました 問題定式化 局所$$(k, \gamma)$$-...
  • Fast Discovery of Reliable k-terminal Subgraphs
    Fast Discovery of Reliable k-terminal Subgraphs Melissa Kasari, Hannu Toivonen, Petteri Hintsanen PAKDD 2010 概要 Uncertain graphがもらえるので、 クエリ頂点集合の連結確率を最大化する辺数に制限のついた部分グラフが欲しい 謎ヒューリスティクス提案 Path coveringを元に [Hintsanen-Toivonen-Sevon Fast discovery of reliable subnetworks]多分ASONAM 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
  • Speedup Graph Processing by Graph Ordering
    Speedup Graph Processing by Graph Ordering Hao Wei, Jeffrey Xu Yu, Can Lu, Xuemin Lin SIGMOD 2016 概要 CPUキャッシュミスを減らす頂点順序を求めたい 幅w以内の頂点対間の(共通近傍サイズ)+(辺数)を最大化 MaxTSPのインスタンスとして1/2w近似アルゴリズム ∑(出次数)^2時間 沢山実験やって2倍以上の高速化を確認 問題定式化 局所性を考慮したスコア関数 $$ S(u,v) = |\mathcal{N}^-(u) \cap \mathcal{N}^-(v)| + [(u,v) \in E] + [(v,u) \in E] $$ 前者 出近傍を全走査するので、uと...
  • 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ネットワークでの応用例...
  • Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases
    Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases Odysseas Papapetrou, Ekaterini Ioannou, Dimitrios Skoutas EDBT 2011 概要 MUSEFrequent Subgraph Pattern Mining on Uncertain Graph Dataの高速化 期待頻度の推定とかの，基本は同じ ↑をしない色々な上限見積もりで枝刈りをする subgraph isomorphismがかなり減って速くなる 提案手法 Edge index 各$$ (L_u, L_v, L_{uv}) $$について以下を保存 $$ L(u...
  • 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 ...
  • Top-k Reliability Search on Uncertain Graphs
    Top-k Reliability Search on Uncertain Graphs Rong Zhu, Zhaonian Zou, Jianzhong Li ICDM 2015 概要 クエリ頂点sから連結する確率が上位kの頂点を返す問題 サンプリングしたグラフからのBFSをビット並列で高速化 サンプリングしたグラフはビットベクトルだけなので軽め 愚直な実装の10倍速い 問題定式化 入力 $$\mathcal{G}, s, k$$ 出力 $$ \textsf{Rel}_{\mathcal{G}}(s,v) $$が上位kの頂点 本当は"述語"があるがどうでもいいので割愛 Q. Fast Reliability Search in Unce...
  • 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 $$ を満たすよ...
  • 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...
  • Fast Reliability Search in Uncertain Graphs
    Fast Reliability Search in Uncertain Graphs Arijit Khan, Francesco Bonchi, Aristides Gionis, Francesco Gullo EDBT 2014 概要 信頼性検索…確率η以上でSから到達可能な頂点集合 索引RQ-tree 階層的クラスタリング クエリ評価 候補生成…最大流ベース 検証… 下界ベース 候補集合に関するサンプリング 精度 0.95、再現率 0.75で爆速 提案手法 RQ-tree…頂点集合の階層的分割 クエリ処理 候補生成 Rout(S,C) = Sから「Cの外の頂点」へ到達する確率 Rout(...
  • On a Routing Problem Within Probabilistic Graphs ...
    On a Routing Problem Within Probabilistic Graphs and its Application to Intermittently Connected Networks Joy Ghosh, Hung Q. Ngo, Seokhoon Yoon, Chunming Qiao INFOCOM 2007 概要だけ 問題 確率的有向グラフからk辺だけ残し、s-t間到達可能確率を最大化せよ 色々応用があるよ 近似計算 最短路木を作る＋tへの辺を戻す、下限が簡単に計算出来る 最適化手法 最短路を取ってきて貪欲に追加していく それっぽい現実の設定で上手く動きました まとめ とても通信ネットワーク感があった アルゴリズム的な面白さはほぼ無し ...
  • Fast Discovery of Reliable Subnetworks
    Fast Discovery of Reliable Subnetworks Petteri Hintsanen, Hannu Toivonen, Petteri Sevon ASONAM 2010 概要 The Most Reliable Subgraph Problemの2端子版のアルゴリズム ヒューリスティクス 提案手法 基本はランダムグラフのサンプリング Phase1 パスサンプリング s-tパスの候補集合を集める パスPを候補Cに足した時，Pr[C∨P]=Pr[C]+Pr[\bar{C}∧P]を最大化したい 怪しい感じ（保証等なし）に右項を近似計算する Phase2 部分グラフの構築 Pr[∨P]が最大となるようにCからパス部分集合を...
  • 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}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • 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...
  • 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...
  • Minimum Spanning Trees in Temporal Graphs
    Minimum Spanning Trees in Temporal Graphs Silu Huang, Ada Wai-Chee Fu, Ruifeng Liu SIGMDO 2015 概要 Temporal グラフでのMST 根と時間区間が入力 MSTa 線形時間，簡単 MSTw 近似，難しい 問題定義 (u,v)間の辺 s,t [w] sに出発tに到着wが重み 根r，時間幅[α,β] [α,β]の間にrから矛盾が無い全域木が欲しい パスの意味での矛盾をいっている MSTa rからの到着時間を最小化 MStw 辺の費用の総和を最小化 MSTaの線形時間アルゴリズム 0時間遷移が無 開始時間...
  • 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) 位置とかそういう情報も記述長がある 語彙 Ω={完全・近似クリーク，完全・近似二部グラフ，スタ...
  • 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}) -...
  • Finding Top-k Maximal Cliques in an Uncertain Graph
    Finding Top-k Maximal Cliques in an Uncertain Graph Zhaonian Zou, Jianzhong Li, Hong Gao, Shuo Zhang ICDE 2010 概要 uncertain graphでtop-k極大クリーク列挙を考えるよ 難しいけど，探索するよ Top-k 極大クリーク問題 頂点・辺に確率が付与 入力 G, k, s 出力 大きさs以上かつ極大クリーク確率が上位kの頂点集合の族 極大クリーク列挙を含む $$ C \subseteq C $$なら$$ \Pr[\mathrm{cliq}(C)] \geq \Pr[\mathrm{cliq}(C )] $$ $$C$$ クリーク $$C...
  • Scalable kernels for graphs with continuous attributes
    Scalable kernels for graphs with continuous attributes ベクトルをノード属性、長さをエッジとして持つグラフのカーネルを提案 GraphHopper Kernel 同じ長さの最短路のノードの類似度を足し算 Graph kernel グラフの類似度計算 K(G,G ) = φ(G),φ(G ) カーネルトリック！！ 共通する部分グラフの数をカウントする φ(G) = パス、木、サイクルとかを成分とするベクトル 全ての部分グラフをカウントするカーネルはNP-hard 色々提案されてる ただし、離散ラベル グラフの分類 化合物とか？ 対象とするグラフ ...
  • 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( ...
  • A practical bounding algorithm for computing two-terminal reliability based ...
    A practical bounding algorithm for computing two-terminal reliability based on decomposition technique Yi-feng Niu, Fang-Ming Shao Computers and Mathematics with Applications 2011 概要 2端子信頼性計算のアルゴリズム 実験なし （某イベントで知った） 提案手法 C 事象の集合 事象=各辺の状態 A1(C) Cでの状態が生の辺集合 A2(C) Cでの状態が死の辺集合 A1(C)がs-t経路を構成→必ず到達可能 A2(C)がs-tカットを構成→必ず到達不可能 良く分から...
  • The Most Reliable Subgraph Problem
    The Most Reliable Subgraph Problem Petteri Hintsanen PKDD 2007 概要 K辺だけ除いて信頼度all-,two-,k-terminal 信頼度を最大化 どの辺が貢献度高い／どうでも良い？ 直並列グラフ上の2端子信頼度に対する厳密アルゴリズム ほかはヒューリスティック 最信頼部分グラフ問題 (Most Reliable Subgraph Problem) 信頼度の指標 無向／有向グラフで全体，頂点対，k頂点が連結となる確率 問題定義 以下を満たす部分グラフHを見つけよ Hの信頼指標が最大となる $$|E[H]| = |E|-K$$ 信頼度の値の計算はいらないので...
  • 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をする 先にある程...
  • @wiki全体から「k-Nearest Neighbors in Uncertain Graphs」で調べる

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