todo314 @ ウィキ
todo314 @ ウィキ

Discovering Highly Reliable Subgraphs in Uncertain Graphs

todo314 @ ウィキ内検索 / 「Discovering Highly Reliable Subgraphs in Uncertain Graphs」で検索した結果

検索 :
  • 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) $$のネットワ...
  • 論文一覧
    ... 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 Subgraph Patterns in Uncertain Graph Databases EDBT 2011 Discovering Highly Reliable Subgraphs in Uncertain Graphs KDD 2011 Distance Constraint Reachability Computation in Un...
  • 気になった論文
    ...よ Discovering frequent topological structures from graph datasets topologicalなのが気になる topological minorがベース Evaluating similarity measures a large-scale study in the orkut social network 6つの類似度をメンバ推薦に使えるか比較 Building connected neighborhood graphs for isometric data embedding 近傍グラフ 最近傍が良いとは限らん k-edge-connected neighborhood graphがある 手法も色々ある ...
  • 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で同じ計算時間 ...
  • 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
  • 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 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
  • 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からパス部分集合を...
  • Discovering Frequent Subgraphs over Uncertain Graph Databases under ...
    Discovering Frequent Subgraphs over Uncertain Graph Databases under Probabilistic Semantics Zhaonian Zou, Hong Gao, Jianzhong Li KDD 2010 概要 Uncertain graphs上の頻出グラフマイニング $$\Pr [\{G_1, \ldots, G_n\}$$の$$\phi$$割合以上出現$$] \geq \tau$$な部分グラフを探す 例のごとく失敗確率δを与える 実験したら良さ気 動機付け等 Frequent Subgraph Pattern Mining on Uncertain Graph Dataは期待値（サポート） 期待値→構造パターン ...
  • 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への辺を戻す、下限が簡単に計算出来る 最適化手法 最短路を取ってきて貪欲に追加していく それっぽい現実の設定で上手く動きました まとめ とても通信ネットワーク感があった アルゴリズム的な面白さはほぼ無し ...
  • 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につ...
  • 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...
  • 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$$ 信頼度の値の計算はいらないので...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • Dynamic Social Influence Analysis through Time-dependent Factor Graphs
    Dynamic Social Influence Analysis through Time-dependent Factor Graphs Chi Wang, Jie Tang, Jimeng Sun, Jiawei Han ASONAM 2011 概要 Pairwise Factor Graph (PFG) model Dynamic Factor Graph (DFG) model 問題設定 各時刻で重み付き辺が有ったり無かったり Pairwise influence μ_ij Dynamic social influence μ^t_ij G =(V,E,Ω)が欲しい Ωは時刻毎のμ_ij これって問題って言うのか？？？ ...
  • 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...
  • 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する ...
  • 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(...
  • 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...
  • 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})≦λ...
  • 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 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}) -...
  • 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)で生きる ランダムグラフがクラスタリ...
  • Frequent Subgraph Pattern Mining on Uncertain Graph Data
    Frequent Subgraph Pattern Mining on Uncertain Graph Data Zhaonian Zou, Jianzhong Li, Hong Gao, Shuo Zhang CIKM 2009 概要 部分グラフをパターンマイニングをしたい 期待サポートという新しい尺度を提案 これが高い部分グラフを探す近似アルゴリズムを作ったよ 問題定義 期待サポート 不確実グラフのデータベース（というか集合）Dの，実体化全体を考える 各実体化について，部分グラフSのサポート=(#{Sが出現する実体化中のグラフ}/|D|)をとる 入力 不確実グラフの集合D，閾値θ 出力 期待サポート≧θの部分グラフパターン 自明に分かること ...
  • 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...
  • 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(...
  • 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...
  • Locally Densest Subgraph Discovery
    Locally Densest Subgraph Discovery Lu Qin, Rong-Hua Li, Lijun Chang, Chengqi Zhang KDD 2015 動機付け 皆密部分グラフ大好き でかいコミュニティからk個←ツマラン 重複回避で似てるの 最密部分グラフ(WSDM 15) クリーク(VLDB 15) 提案概念・手法 Gがρ-compact 任意のSをGから取り除くと、ρ|S|辺以上消える 極大ρ-compact部分グラフを考える Locally densest subgraph gがGの極大density(g)-compact部分グラフ LDSは互いに素なので、列挙可能 「最...
  • 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 ...
  • 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} $$ ...
  • Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis
    Rabbit Order Just-in-time Parallel Reordering for Fast Graph Analysis IPDPS 2016 Junya Arai, Hiroaki Shiokawa, Takeshi Yamamuro, Makoto Onizuka, Sotetsu Iwamura 概要 主に$$x^{(t+1)} = Ax^{(t)} $$系の反復法=疎行列ベクトル乗算のキャッシュミスを減らしたい 頂点順序を工夫しよう Q値を基準に併合していってデンドログラムを作る PageRankとかが全体で2倍速くなった！ Rabbit Order 高い局所性を達成したい 問題定義 キャッシュミスを最小化する頂点順序を見つけたい 実グラフの階層的コ...
  • Pushing the Envelope in Graph Compression
    Pushing the Envelope in Graph Compression Panagiotis Liakos, Katia Papakonstantinopoulou, Michael Sioutis CIKM 2014 概要 Pushing the Envelope 限界に挑む（慣用句） グラフ圧縮の限界 隣接行列がある 対角成分付近を圧縮する手法を提案 残りは既存手法 調査 隣接行列のヒートマップを見てみると，対角成分付近に集中しているっぽいぞ ID付けはそのまんまで前処理無しらしい 良さそうに並び替える問題も研究されているらしい… 提案手法 対角成分の前後kの要素を圧縮するよ 各行は，長さ2k+1の01ベ...
  • 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の長さ 数十 ~ 数百 ...
  • 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...
  • 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_...
  • 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 ...
  • 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をする 先にある程...
  • 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 辺 ...
  • 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...
  • 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スコアの高いクエリを出力 実験 提...
  • Efficient Algorithms for Public-Private Social Networks
    Efficient Algorithms for Public-Private Social Networks Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, Vahab Mirrokni KDD 2015 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
  • 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ベクトル...
  • Independent Set, Induced Matching, and Pricing: Connections and Tight ...
    Independent Set, Induced Matching, and Pricing Connections and Tight (Subexponential Time) Approximation Hardnesses Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai In FOCS k-hypergraph Pricing Problem 入力 V 商品 E_i 客iの好きなvのset |E_i|≦k b_i 客iの予算 出力 p_j v_jの値段 目的 max g=Σ_i g_i g_i = \min_{j∈E_i} p_j (p_j≦b_i) つまり一番安いのを買お...
  • 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 ...
  • 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...
  • 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上のランダムウォークでやる ...
  • 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 問題 ...
  • Efficiently Computing k-Edge Connected Components via Graph Decomposition
    Efficiently Computing k-Edge Connected Components via Graph Decomposition Lijun Chang, Jeffrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, Weifa Liang In SIGMOD 2013 メモ K.Oka 問題 k枝連結成分 少なくともk本消さないと非連結にならない 大きさk-1のカットがない 極大k枝連結成分 共通部分を持たない 分解できる 応用 social networkで似た頂点 可視化 既存手法 最小全域カットしまくる O(n^2(m+n log n)) ...
  • 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...
  • I/O Efficient: Computing SCCs in Massive Graphs
    I/O Efficient Computing SCCs in Massive Graphs Zhiwei Zhang, Jeffrey Xu Yu, Lu Qin, Lijun Chang, Xuemin Lin In SIGMOD 2013 駒水（筑波大）さんの資料 概要 SCCしたい グラフがメモリに乗らない 既存手法 EM-SCC Contraction-based グラフを適当に分割する メモリ乗らないサイズのSCCは発見できない DFS-SCC semi-external DFS木を2回 逆グラフ作って…ってやつ よくやるSCCアルゴリズムだと思う多分 提案手法 木...
  • @wiki全体から「Discovering Highly Reliable Subgraphs in Uncertain Graphs」で調べる

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