todo314 @ ウィキ
todo314 @ ウィキ

Massive Graph Triangulation

todo314 @ ウィキ内検索 / 「Massive Graph Triangulation」で検索した結果

検索 :
  • 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 （発見した）△の数 ...
  • 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})≦λ...
  • 気になった論文
    ...ueries on Massive Networks Improved Practical Matrix Sketching with Guarantees ESA 2018 Scalable Katz Ranking Computation in Large Dynamic Graphs On the Worst-Case Complexity of TimSort Parameterized Approximation Algorithms for Bidirected Steiner Network Problems An exact algorithm for the Steiner forest problem Large Low-Diameter Graphs are Good Expanders ...
  • 論文一覧
    ...mization Massive Data Summarization on the Fly Fast Influence-based Coarsening for Large Networks FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs KDD 2015 Influence at Scale Distributed Computation of Complex Contagion in Networks Efficient Algorithms for Public-Private Social Networks Reciprocity in Social Networks with Capacity Constraints ...
  • 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)| $$を最小化せよ ...
  • On the Hardness of Graph Anonymization
    On the Hardness of Graph Anonymization Charu C. Aggarwal, Yao Li, Philip S. Yu ICDM 2011 概要 匿名化手法は色々あるけど、ランダムに辺を追加削除するだけはヤバイ！ これを理論的に示す 特にソーシャルネットワークはmassiveかるsparseでこれが効いてくるらしい perturbation（摂動）に対してロバストなパラメータがある ↑を元にした手法を作り実験 Linkage Covariance $$ LinkCov(p,q) = \sum_{i}x_{pi}x_{qi}/n - \sum_{i}x_{pi}/n \sum_{j}x_{qj}/N $$ ロバスト性 確率f_aで辺を追...
  • I/O Efficient: Computing SCCs in Massive Graphs
    ...g 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アルゴリズムだと思う多分 提案手法 木の構築は一度 2フェイズア...
  • 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)...
  • 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} ...
  • 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...
  • 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 ...
  • 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...
  • 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...
  • 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...
  • Overlapping correlation clustering
    Overlapping correlation clustering Francesco Bonchi, Aristides Gionis, Antti Ukkonen ICDM 2011 概要 重複クラスタリング 頂点→ラベル（小）集合 点間の距離最小化 集合交差指示関数 Jaccard係数 局所探索法 各反復がムズい 集合交差…貪欲法（集合被覆） Jaccard…最小二乗法（NP-hard） 問題定義 s(u,v) 類似度 [0,1]か{0,1} 非重複クラスタリング C_cc(V,l) = ∑同クラスタ内の(1-s(u,v)) + ∑異クラスタのs(u,v) {0,1...
  • Semi-Supervised Feature Selection for Graph Classification
    Semi-Supervised Feature Selection for Graph Classification Xiangnan Kong, Philip S. Yu KDD 2010 概要 タイトルのまんま、半教師有りで特徴選択 ラベル無しグラフも与えられるときに3つの原則に従って、良い部分グラフを選ぶ（探索する） 簡単な実験をするとラベル無しグラフを入れることにも意味が有るとわかったよ 提案基準 gSemi ラベル(±1)有り・無しグラフがもらえる 部分グラフ（パターン）を選んだら、各グラフに対応する出現ベクトル$$x_i$$が得られる Cannot-link $$ y_i \neq y_j $$なら$$x_i$$と$$x_j$$は*離れて*欲しい Must-...
  • 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...
  • Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
    Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs Liam Roditty, Virginia Vassilevska Williams In STOC 2013 メモ Y.Yano 直径2近似O(n+m) BFSして最大の高さ additive approximation Aingworth 2つの組み合わせ 2種類のBFS木の高さの最大値 $$ s \in [1,n] $$ O(ns^2 + (s+n/s)m) 論文の内容 ns^2の項を消したい ↑高々s頂点のBFS N_s^out(v)を求めないで頑...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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スコアの高いクエリを出力 実験 提...
  • 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上のランダムウォークでやる ...
  • 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...
  • 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) $$のネットワ...
  • Approximating the Spectrum of a Graph
    Approximating the Spectrum of a Graph David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant KDD 2018 概要 （正規化）Laplacianのスペクトラムが欲しい！ $$ \exp(O(1/\epsilon)) $$時間：定数！！！ $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$ 性質検査的な話もあるよ！ 提案手法 定数時間にしたいので、出力は[0,2]上の離散分布 $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番...
  • 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と...
  • Approximate Bayesian Image Interpretation using Generative Probabilistic ...
    Approximate Bayesian Image Interpretation using. Generative Probabilistic Graphics Programs 画像認識の新手法 応用 CAPTHA…これは文字ほげだ！ 道路認識 画像のシーンをシンボリックに 大きなコーパスが必要 トップダウンに考えるよ！ ボトムアップ 画像を要素に分解 それぞれを解釈 トップダウン 要素を仮定し画像を構成 その確率を出す モデル シーン…文字の種類とか 入力からこれを推定する レンダラを使った生成モデルで予測 Metropolis-Hastings 変数をちょっと動かしてほげ...
  • 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...
  • 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( ...
  • 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は期待値（サポート） 期待値→構造パターン ...
  • 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で高速近似計算 比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった 感想 ...
  • 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ベ...
  • 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}) -...
  • 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ベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
  • Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
    Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy NIPS 2016 概要 Joint M-best-diverse labeling 問題をパラメトリック劣モジュラ最小化問題に帰着して解く 動機づけ・問題定式化 2値画像のノイズ除去・画像分割 エネルギー関数最小化として定式化 エネルギー関数 データ項= 「入力と出力の近さ」＋平滑化項=「出力の滑らかさ」 例 $$ E(y) = \sum_{v \in V}b_v [x_v \neq y_v] + ...
  • 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...
  • Exacting Social Events for Tweets Using a Factor Graph
    Exacting Social Events for Tweets Using a Factor Graph Xiaohua Liu, Xiangyang Zhou, Zhongyang Fu, Furu Wei, Ming Zhou AAAI 2012 概要（だけ） ソーシャルイベントをTweetからいい感じに抽出したい ノイズがひどいのでNLPでやるのは超難しい イベントは2通り Interaction 互いに知っている Observation 片方がもう一方を知っている グラフっぽいものを作る あるツイートについて、人名を抽出してペアを作る ペアが同じだったら関係を持たせる 単一のイベントの重みと、ペアの重みをつける（学習） 結局尤度最大化になる ...
  • On k-Path Covers and their Applications
    On k-Path Covers and their Applications Stefan Funke, André Nusser, Sabine Storandt VLDB 2014 best paper award スライド見てね 概要 Minimum k-All Path Cover (k-APC) 入力 有向グラフ G=(V,E) 整数k 出力 C⊆V であって，任意の長さkの単純経路πについて，C∩π≠∅ minimize |C| Minimum k-Shortest-Path Cover (k-SPC) [Tao, Sheng, Pei. SIGMOD 11] 入力 有向グラフ G=(V,E,c) ...
  • 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...
  • A Graph Minor Perspective to Network Coding: Connecting Algebraic Coding ...
    A Graph Minor Perspective to Network Coding Connecting Algebraic Coding with Network Topologies Xunrui Yin, Yan Wang, Zongpeng Li, Xin Wang, Xiangyang Xue INFOCOM 2013 ぶっちゃけ良く分からない Network Coding 例えば、2つのソースが2つの頂点にそれぞれAとBを送信する 辺はAとBの演算結果1つだけしか送信できない A+BとAを受け取ったら、Bを復元できる こんなかんじで上手く情報を伝えたい これの一般化を考えている？ NC-Minor Conjecture Multicast network GがK_{...
  • 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
  • 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...
  • 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}...
  • 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の長さ 数十 ~ 数百 ...
  • 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • 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)（福永さん） 何でノードだとめんどいの？ ...
  • 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...
  • 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 コミュニティを列挙 利点 ...
  • 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)で生きる ランダムグラフがクラスタリ...
  • @wiki全体から「Massive Graph Triangulation」で調べる

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