todo314 @ ウィキ
todo314 @ ウィキ

Balanced Graph Edge Partition

todo314 @ ウィキ内検索 / 「Balanced Graph Edge Partition」で検索した結果

検索 :
  • Balanced Graph Edge Partition
    Balanced Graph Edge Partition Florian Bourse, Marc Lelarge, Milan Vojnovic KDD 2014 概要 平衡辺分割…並列計算の効率化 メッセージの集約の有無について期待費用を特徴付け 平衡辺分割に対する近似アルゴリズム 疑問 頂点分割に比べた辺分割の定量的な良さ メッセージの集約有 頂点分割 分割の境界にある辺数 辺分割 クラスタをまたぐ頂点の複製(?)の数 メッセージの集約無 辺分割の近似保証は？自然なストリームアルゴリズムはイイ感じになる？ 定式化 C(x)を最小化したい ∀j L_j(x)≦(1+ν)ave(L_i(x)) L_...
  • 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 $$ を満たすよ...
  • 気になった論文
    ...s for the Balanced Edge Partitioning Problem Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem WEA 2008 Comparing Integer Data Structures for 32 and 64 Bit Keys Fast Local Search for the Maximum Independent Set Pro...
  • 論文一覧
    ...ction Balanced Graph Edge Partition Correlation Clustering in MapReduce Streaming Submodular Maximization 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 ...
  • 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をする 先にある程...
  • Scalable Maximum Clique Computation Using MapReduce
    ... 提案 Balanced Multi-depth Color-based (BMC) partitioning 最後の2つを合わせた感じ 次数順にソート 彩色 彩色を考慮してソート その順に分割を適用 実行時間 T(G)=f(|G|,ρ(G))^{|G|g(ρ(G))} でフィッティング 実装と最適化 MapReduceに合わせて頑張る 何か込み入った話をしているように見える 実装 Hadoopでの最適化 グローバルパラメータMAX 見つかった最大クリークのサイズ BOUNDは実行時間のしきい値 これより少ない部分グラフについて実行する 実験 データセット ...
  • 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につ...
  • FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
    ... Balanced FAST-PPR $$ \epsilon_r $$の値を動的に制御する 実験 速度・精度・性能解析をする データセット 6.7M～3.7B辺 比較手法 FAST-PPRの個々のサブルーチンであるMonte-Carlo、Local-Update 無作為な(s,t)に対するPPRの分布 1/n以上が全体の2.8% 4/n以上が全体の1%未満 δをかなり小さくする必要有 実行時間 tを一様／PRに従いサンプル 総時間 圧倒的な差 個々の時間 PR(t)が大きいと時間が掛かる 実際の精度 相対（平均）15% 相対（最悪）65% $$F_t(\epsilon_r)$$の代わ...
  • 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ベクトル...
  • 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...
  • 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)) ...
  • 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)...
  • 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...
  • Random-walk Domination in Large Graphs
    Random-walk Domination in Large Graphs Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng ICDE 2014 Random-walk domination in large graphs problem definitions and fast solutions を参照 ICDE random walk 2013-12-27 01 24 46 (Fri)
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
    ...る Balanced digraph 分割S,Tがあり，S,T内は正辺，S,Tカットは負辺 Anti-balanced digraph 分割S,Tがあり，S,T内は負辺，S,Tカットは正辺 Strictly unbalanced digraph balancedでもanti-balancedでも無い balanced かつ anti-balancedはあり得るが，aperiodicの時は両方同時には成り立たない 結局変動はどう収束するの？ ergodicグラフについて，P^tは… Balanced 定常分布っぽいのに収束 Strictly unbalanced 0に収束 Anti-balanced 定常分布ぽいのとその-1倍の間で収束 ...
  • 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...
  • 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...
  • 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ベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
  • 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...
  • 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の長さ 数十 ~ 数百 ...
  • 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})≦λ...
  • Delineating Social Network Data Anonymization via Random Edge Perturbation
    Delineating Social Network Data Anonymization via Random Edge Perturbation Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Panos Kalnis, Hung Keng Pung CIKM 2012 概要 random edge perturbation によるグラフの匿名化 上を攻撃する手法 グラフの特徴量を推定 Random Edge Perturbation 辺を確率μで独立に足したり消したりする XORってこと denseになるけどいいや 色々推定 ※μは公開するとして良い 密度 μが分かるので、て...
  • 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...
  • 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} $$ ...
  • 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アルゴリズムだと思う多分 提案手法 木...
  • 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...
  • 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 辺 ...
  • 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)| $$を最小化せよ ...
  • 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...
  • 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}) -...
  • 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)$$-...
  • 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_...
  • 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スコアの高いクエリを出力 実験 提...
  • Scalable Influence Maximization in Social Networks under the Linear ...
    Scalable Influence Maximization in Social Networks under the Linear Threshold Model Wei Chen, Yifei Yuan, Li Zhang In ICDM 2010 概要 LTモデル用の高速アルゴリズム LTモデルでのσの計算は#P-hard DAGをとってきて、それの上で高速計算 #P-hardness 基本は単純経路の数え上げからの帰着 アルゴリズム LTモデルからlive-edge graphを考える eはw_eの確率で残ると書いてあるが、本当だろうか…？ Kempeのではもっと複雑なことをしていた こうすると、random graph上でのreacha...
  • 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-...
  • Extrapolation Methods for Accelerating PageRank Computations
    Extrapolation Methods for Accelerating PageRank Computations Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub WWW 2003 概要 PageRankのためのPower methodの高速化 25--300%速くなった メモ：イントロで… Dangling nodesからは一様に飛ぶとしている Aitken Extrapolation $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい！...
  • 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...
  • Overlapping Community Detection Using Seed Set Expansion
    Overlapping Community Detection Using Seed Set Expansion Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon CIKM 2013 概要 コンダクタンスがいい感じになる重複コミュニティ検出手法を提案 提案手法 目標 全体をカバーしつつ、最大のコンダクタンスを小さくしたい Filtering whiskerを取り除きたいので、以下のような分解をする core=（ざっくりいうと）最大の2点連結成分 bridge=橋 whisker=残り Seeding 色々な手法でクラスタ中心を決める Graclus centers, Spr...
  • 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 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...
  • 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は期待値（サポート） 期待値→構造パターン ...
  • ICWSM - A Great Catchy Name: Semi-Supervised Recognition of Sarcastic ...
    ICWSM - A Great Catchy Name Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews Oren Tsur, Dmitry Davidov, Ari Rappoport ICWSM 2010 レビューが皮肉かどうか？ Greatとかあるとダルい 応用 意見抽出 要約 コーパス（データ） 1,2 皮肉でない 3,4,5 皮肉 これがアノテートされたコーパスで「教師つき学習」 普通はn-gramだけど今回はPhrase Patternを使う n-gramの一般拡張 語を変数で置換 変数は任意の語にマッチする ...
  • 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...
  • A Data-Based Approach to Social Influence Maximization
    A Data-Based Approach to Social Influence Maximization Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan VLDB 2012 概要 Data-Basedの意味：伝播確率をデータから推定するのではなく、直接σを推定する Credit Distribution Modelというモデルを提案 NP-hardでsubmodular σ_CDでの最大化が良いし速い！！ 何でこんなことになったのか いろんなモデルを使って実験してみよう weighted cascade model trivalency model uniform IC model EMアルゴリズ...
  • Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, ...
    Scalable Similarity Estimation in Social Networks Closeness, Node Labels, and Random Edge Lengths Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, Renato F. Werneck COSN 2013 背景 直径が小さいグラフで最短路を求める意味はあるのか？ そこを考えよう！ 概要 最短路ベースの頂点間関連性 RWR, SimRank, Resistance dsitance, … この論文 色々提案して、その計算、既存の関連性との比較 神か A...
  • 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 （発見した）△の数 ...
  • @wiki全体から「Balanced Graph Edge Partition」で調べる

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