todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Reliable Clustering on Uncertain Graphs」で検索した結果

• 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 ...
• 論文一覧
  ... The Most Reliable Subgraph Problem PKDD 2007 Frequent Subgraph Pattern Mining on Uncertain Graph Data CIKM 2009 Fast Discovery of Reliable Subnetworks ASONAM 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 Un...
• 気になった論文
  ...works Reliable Clustering on Uncertain Graphs Profit Maximization over Social Networks Community Preserving Lossy Compression of Social Networks Risks of Friendships on Social Networks Privacy-Preserving SimRank over Distributed Information Network Defining and Evaluating Network Communities based on Ground-truth ICDM 2013 Tree-Like Structure in Large Social...
• 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...
• 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ネットワークでの応用例...
• 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 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
• 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...
• 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につ...
• 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への辺を戻す、下限が簡単に計算出来る 最適化手法 最短路を取ってきて貪欲に追加していく それっぽい現実の設定で上手く動きました まとめ とても通信ネットワーク感があった アルゴリズム的な面白さはほぼ無し ...
• 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，閾値θ 出力 期待サポート≧θの部分グラフパターン 自明に分かること ...
• 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 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...
• 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からパス部分集合を...
• 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で高速近似計算 比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった 感想 ...
• 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...
• 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 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) $$のネットワ...
• 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$$ 信頼度の値の計算はいらないので...
• 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は期待値（サポート） 期待値→構造パターン ...
• Correlation Clustering in MapReduce
  Correlation Clustering in MapReduce Flavio Chierichetti, Nilesh Dalvi, Ravi Kumar KDD 2014 概要 AIlon et al.の手法の効率化 pivotを並列に選択 [Ailon, Charikar, Newman]のPivotアルゴリズム v ← Vから一様無作為選択 C_i ← v∪Γ+(v) V ← V-C_i E+ ← E+∩(V×V) ↑の問題点 ストリーム設定だと，走査数が多い，|V|パスもあり得る 提案手法 完全グラフ 3近似に近い 一般のグラフ 次数制限あっても近似難しい 最大正次数のpolylogラウンド ...
• 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)で生きる ランダムグラフがクラスタリ...
• 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版ではない原稿を読んだのでちょっと違う イントロ 確率的グラフ 辺に確率が割り振られている センサや実験による雑音 不安定な通信 リンク予測 秘匿性のための摂動 気になること...
• 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...
• 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...
• 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で同じ計算時間 ...
• 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 $$ を満たすよ...
• Streaming k-means on Well-Clusterable Data
  Streaming k-means on Well-Clusterable Data Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku In SODA 2011 メモ UCLA（カリフォルニア大学ロサンゼルス校）の人々らしい 概要 Online Facility Locationを元にしたストリームk-meansアルゴリズム 時間・空間計算量共に良く、近似比は定数。 アルゴリズム 点xを読み込む xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる 施設の数が増えすぎたら...
• Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming
  Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming Yangyang Hou, Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon KDD 2015 概要 Non-exhaustive, Overlapping k-meansの続き 元の反復アルゴリズムはあまり良くなかったりする 違う解き方を考案 凸SDPで緩和 そのままだと大変なので低ランク近似 初期化・丸めもちょっと頑張る 実験してみたら良かった 重複有りコミュニティ検出にも使える kernel k-meansとグラフクラスタリングが等価だ...
• 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)| $$を最小化せよ ...
• 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(...
• 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 色々提案されてる ただし、離散ラベル グラフの分類 化合物とか？ 対象とするグラフ ...
• 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)の間の「互いに素」なカットの集合 「カットが切られな...
• 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 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...
• 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)（福永さん） 何でノードだとめんどいの？ ...
• 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...
• 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...
• k-means--: A unified approach to clustering and outlier detection
  k-means-- A unified approach to clustering and outlier detection Sanjay Chawla, Aristides Gionis SDM 2013 概要 l点除いてかつk-meansも最小 除いたLが外れ値 問題定義 D(X\L, C)を最小化するC (of size k) とL (of size l) を求めたい Dは最小二乗距離和 k=1ならn^d^3で解けるけど基本NP-hard 提案手法 k-meansの変形に相当 各点についてクラスタまでの距離計算 距離でソートして大きいl点をLにつっこむ Lを無視してクラスタ更新 これを収束するま...
• 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)を求めないで頑...
• 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)$$-...
• Spectral Redemption: Clustering Sparse Networks
  Spectral Redemption Clustering Sparse Networks Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhanga PNAS 2010 概要 スペクトル法によるコミュニティ検出 固有値を使う 問題 グラフが疎だと検出できない スペクトルが悲しい感じらしい 密…平均次数が（定数でも）割りと高い（10以上？） 主張 nonbacktracking行列なるものを使うとGOOD Nonbacktracking 行列Bとは？ u→vいってv→uいってというのができない B_ijのi,jが...
• 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
• 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 and Parallelizable Processing of Influence Maximization for ...
  Scalable and Parallelizable Processing of Influence Maximization for Large-Scale Social Networks Jinha Kim, Seung-Keol Kim, Hwanjo Yu 浦項（ぽはん）工科大学校 In ICDE 2013 概要 並列化可能なアルゴリズム 競技相手はPMIA 質はCELF並、PMIAより良い 速度はPMIAより速い 提案手法 Independent Path Algorithm(IPA) 経路を指定したらそれを使う確率は全部かければ良い グラフがもらえた 有るノードからtraverseして木っぽくパスを広げる（同じ頂点がいくつかある...
• 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} $$ ...
• 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) 普通...
• 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)...
• 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...
• 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...
• @wiki全体から「Reliable Clustering on Uncertain Graphs」で調べる

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