todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Efficient Subgraph Search over Large Uncertain Graphs」で検索した結果

• 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...
• 気になった論文
  ... Oracles Efficient Dynamic Algorithms for the Steiner Tree. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC 2016 Simpler Analysis and Enumeration of Parametric Minimum Cuts David Karger Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithmic Barrier for Truthful Co...
• 論文一覧
  ... 2011 Efficient Influence Maximization in Social Networks KDD 2009 StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization CIKM 2013 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ... ICDM 2013 An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ... WWW 2014 Extracting Influential Nodes for Informa...
• 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...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• 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...
• 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...
• 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は期待値（サポート） 期待値→構造パターン ...
• 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で同じ計算時間 ...
• 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からパス部分集合を...
• 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 ...
• Efficient Ad-hoc Search for Personalized PageRank
  Efficient Ad-hoc Search for Personalized PageRank Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Takeshi Mishima, Makoto Onizuka SIGMOD 2013 概要 PPRが上位k頂点を順位つきで出力 提案手法Castanet 前処理、パラメータ無し、厳密 既存手法より速い 提案手法 大まかにはFast and Exact Top-k Algorithm for PageRankと大体同じ 上限下限の反復改善計算 細かい数式が改善している？ 部分グラフ抽出 (上位kに必ず入らない)∨(順位が確定した)頂点はどうでも良い ...
• 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) $$のネットワ...
• 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アルゴリズムだと思う多分 提案手法 木...
• 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につ...
• COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
  ...ニング Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database が使えるように頑張る SIGMOD モチーフ 2015/11/12
• 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 コミュニティを列挙 利点 ...
• BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries
  BMC An Efficient Method to Evaluate Probabilistic Reachability Queries Ke Zhu, Wenjie Zhang, Gaoping Zhu, Ying Zhang, Xuemin Lin DASFAA 2011 概要 $$ \mathrm{rel}_{\mathcal{G}}(s,t) \theta? $$に答えたい 適当にrel(s,t)の上限を求める手法 駄目なら工夫したMonte-Carlo 提案手法 上限計算 out Pr[sから距離l以上遠くへ到達可能] in Pr[tへ距離m以上遠くへ到達可能] C B(s,l)とB(t,m)の間の「互いに素」なカットの集合 「カットが切られな...
• 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...
• 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をする 先にある程...
• 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...
• 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})≦λ...
• 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ネットワークでの応用例...
• Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
  Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, Shen Chen Xu KDD 2015 概要 The K-clique Densest Subgraph Problemの後続 k-クリーク密部分グラフをいい感じの二部グラフ構築＋疎化により爆速で解く 基本はランダムサンプリング 10~10000倍早くなった $$(p,q)$$-clique densest subgraph $$\#(p,q)$$-clique/点数 を最大化したい ...
• 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(...
• 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...
• 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 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$$ 信頼度の値の計算はいらないので...
• 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...
• 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，閾値θ 出力 期待サポート≧θの部分グラフパターン 自明に分かること ...
• 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...
• 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)| $$を最小化せよ ...
• Massive Graph Triangulation
  Massive Graph Triangulation Xiaocheng Hu, Yufei Tao, Chin-Wan Chung In SIGMOD 2013 塩川さん@NTT の発表資料より 目的 graph triangulation を高速に解く 全てのtriangleを列挙 貢献 CPU I/O efficient CPU $$ O(|E|\log |E| \frac{|E|^2}{M} + \alpha |E|) $$ I/O $$ O(\frac{|E|^2}{MB} + \frac{K}{B}) $$ worstではoptimal M メモリサイズ B ブロックサイズ K （発見した）△の数 ...
• 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...
• 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 ...
• 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...
• 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...
• 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(...
• 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)$$-...
• 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 ...
• Stochastic Submodular Maximization: The Case of Coverage Functions
  Stochastic Submodular Maximization The Case of Coverage Functions Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause NIPS 2017 概要 確率的劣モジュラ最大化のための新しい手法を提案 まずは、被覆関数から 連続拡張をさらに緩和した問題を直接解いてから元に戻す 問題 目的関数 $$ f(S) = \mathbb{E}_{\gamma \sim \Gamma}[f_\gamma(S)] $$ 影響最大化なら、影響グラフからサンプルしたグラフ上で到達可能な頂点数 線形連続拡張 $$ F(\bm{x}) = \mathbb{E}...
• The K-clique Densest Subgraph Problem
  The K-clique Densest Subgraph Problem Charalampos E. Tsourakakis WWW 2015 概要 平均k-clique数最大の部分グラフ k=2 densest subgraph k=3 $$ \frac{\# \Delta(S)}{|S|} $$ 厳密多項式時間アルゴリズム（k定数） 効率的1/k-近似アルゴリズム 実験 3-clique densestの解はnear-clique 動機づけと問題定式化 例えば辺密度$$ \frac{e(S)}{{|S| \choose 2}} $$はどうですか？ 単一辺が最適なので意味無し 最密部分グラフはどうですか？ 解けるけど、本当に欲しいのはl...
• 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)で生きる ランダムグラフがクラスタリ...
• 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...
• 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上のランダムウォークでやる ...
• 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
• Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
  Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, Hang Li MSRAとUniversity of Science and Technology of China WWW 2009 概要 たった今調べたクエリからURLを正しくレコメンドするのは無理 例 ホントは車のレビューサイトを見たい 検索クエリ Ford new cars → Toyota new cars 個々のクエリに着目するとautohome.comは出てこない ...
• 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)（福永さん） 何でノードだとめんどいの？ ...
• @wiki全体から「Efficient Subgraph Search over Large Uncertain Graphs」で調べる

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