todo314 @ ウィキ
todo314 @ ウィキ

Chromatic Correlation Clustering

todo314 @ ウィキ内検索 / 「Chromatic Correlation Clustering」で検索した結果

検索 :
  • Chromatic Correlation Clustering
    Chromatic Correlation Clustering Francesco Bonchi, Aristides Gionis, Francesco Gullo, Antti Ukkonen KDD 2012 概要 Correlation clustering 各頂点対に類似度がありクラスタリング 今回は，頂点対にラベルがついたクラスタリング 応用 タンパク質間相互作用ネットワーク，関係ネットワーク，共著ネットワーク 問題定義 完全グラフが与えられる Correlation Clustering $$ \text{cost}({\cal C}) = \sum_{(x,y) \in V \times V {\cal C}(x) = {\cal C}(y...
  • 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ラウンド ...
  • 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...
  • 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...
  • 気になった論文
    ...ntees for Chromatic Correlation Clustering LPベースの手法4近似 遅いけど理論的理解 ヒューリスティクス ✔Efficient Densest Subgraph Computation in Evolving Graphs 動的・大規模同時はない ↑クロールの手間 2(1+ε)近似　O(polylog(n+r))コスト Skolemising Blank Nodes while Preserving Isomorphism RDFグラフ Global Diffusion via Cascading Invitations Structure, Growth, and Homophily Webサイトとか招待でメンバが増え...
  • Influence and Correlation in Social Networks
    Influence and Correlation in Social Networks Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian KDD 2008 概要 社会的な繋がりは大事ですよ 相関（似た行動）を引き起こすのは、「社会影響」の所為？ 同類性とか他の色々な要素があって紛らわしい 単純なテストを考案 Flickrで調べたら、相関はあるけど影響の所為ではない 導入とか 既存研究「Flickrで友達同士のタグの語彙が似ている」 相関の源は？ influence 友達の最近の行動に引き起こされる homophily 同じゲームを持っている人は友達になりやすい e...
  • 論文一覧
    ...r ... Chromatic Correlation Clustering Efficient Personalized PageRank with Accuracy Assurance KDD 2013 Denser than the Densest Subgraph Extracting Optimal Quasi-Cliques with ... Redundancy-Aware Maximal Cliques Trial and Error in Influential Social Networks Workshop on Mining and Learning with Graphs (MLG) Polynomial-Time Algorithm for Finding Densest Subg...
  • A Local Search Approximation Algorithm for k-Means Clustering
    A Local Search Approximation Algorithm for k-Means Clustering Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y.Wu In SCG 2002 Symposium on Computational Geometry 概要 k-meansアルゴリズム 多項式時間で(9+ε)-近似 Single-Swap ヒューリスティクス 山登り法 初期状態から状態遷移していき、局所解を答えとする 状態 k個の施設 遷移 k個の施設の内1つを残りのn-k個と交換（だから、Single-...
  • 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 ...
  • 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...
  • Estimating Clustering Coefficients and Size of Social Networks via Random Walk
    Estimating Clustering Coefficients and Size of Social Networks via Random Walk Stephen J. Hardiman, Liran Katzir In WWW 2013 メモ Liran KatzirはMSR Israel 概要 ランダムウォークでクラスタ係数と頂点数を見積もる 全体をとってくるのが厳しい用 ちょっとタイムリー 既存手法よりかなり良い 近似が指数関数的によくなる（ランダムウォークの長さの 頂点のIDと、隣接リスト（次数）さえわかれば良い しかも前と後の1つずつだけ覚えていれば計算可能 問題 global clustering coefficien...
  • Spectral Rotation versus K-Means in Spectral Clustering
    Spectral Rotation versus K-Means in Spectral Clustering Jin Huang, Feiping Nie, Heng Huang AAAI 2013 Kindle 買ったし再開だよ スペクトラルクラスタリング $$ \sum_{i=1}^{K} \frac{s(C_i, \bar{C_i})}{\sigma(C_i)} $$ σは点の個数、重みの和等 sはカットの重み $$ \hat{q}_i $$をj要素がクラスタiに属するかを表すindicatorとすると 上の目的関数は行列とかで良さげに書ける 正規化とかすると↓みたいになる $$ \sum_{i=1}^{K}q_i^{\top}(D-W)q_i $$ よくあ...
  • 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上のランダムウォークでやる ...
  • 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スコアの高いクエリを出力 実験 提...
  • 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で高速近似計算 比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった 感想 ...
  • 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)で生きる ランダムグラフがクラスタリ...
  • 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
  • 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...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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が...
  • Fast Random Walk with Restart and Its Applications
    Fast Random Walk with Restart and Its Applications Hanghang Tong, Christos Faloutsos, Jia-Yu Pan ICDM 2006 概要 ベストペーパー RWRを高速にクエリ計算した 提案手法 B_LIN グラフを（METISとかで）k分割する 確率遷移行列W（論文中では正規化Laplacianもどき）をW_1+W_2に分割する RWR行列は$$ (1-c)(I-cW)^{-1} $$ W_1：分割内だけ；diag(W_11, …, W_1k)な感じ W_2：分割間だけ； Q_1 = diag(Q_11, …, Q_1k) Q_1i = (I-cQ_1i)の逆行列 ...
  • Learning Stochastic Models of Information Flow
    Learning Stochastic Models of Information Flow Luke Dickens, Ian Molloy, Jorge Lobo, Pau-Chen Cheng, Alessandra Russo ICDE 2012 概要 ICモデルの確率予測 Metropolis-Hastingsアルゴリズム attributed 影響の親が分かる unattributed 親が分からん 両方について実験 Attributedの場合 シード集合，活性頂点集合，拡散の履歴が分かる βICモデル 各辺の確率 ベータ分布(α_e,β_e)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
  • 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...
  • 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を最近の施設に割り当てる 施設の数が増えすぎたら...
  • 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$を求めたい！...
  • Parameterized Algorithms
    ...$$ Chromatic Coding 補題 辺数kのグラフの頂点を$$ \sqrt{8k} $$色で塗る 彩色が妥当な確率は≧$$ 2^{-\sqrt{k/2}} $$ $$ d\mathsf{-Clustering} $$ 与えられたグラフに辺挿入／削除を高々k回繰り返しd-clustering graphにできるか？ d-clustering graph 連結成分数がd，各連結成分がクリーク 同じ色の辺を編集しないとする 運が良い時 解の辺（k本）の端点の色が違う…補題の確率 脱乱択 答えが何でも良いような複数の彩色を決定的に使う color codingの場合 $$(n,k)$$-完全ハッシュ族 n要素からどのk要素を取...
  • Hartigan's Method: k-means Clustering without Voronoi
    Hartigan s Method k-means Clustering without Voronoi Matus Telgarsky, Andrea Vattani JMLR 2010 Journal of Machine Learning Research
  • Topic-aware Social Influence Propagation Models
    Topic-aware Social Influence Propagation Models Topic-aware Social Influence Propagation Models Nicola Barbieri, Francesco Bonchi, Giuseppe Manco Yahoo! Research Barcelona ICDM 2012 概要 トピックを考慮したモデルにICとLTを拡張 期待値最大化でパラメータを見積もる 上のモデルは大変なので，ちょっとパラメータ数を減らしたモデルを考案 実験して普通のICより良かった Topic-awareモデル Topic-aware Independent Cascade Model (TIC) z...
  • Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues
    Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues Alexander Tsiatas, Iraj Saniee, Onuttom Narayan, Matthew Andrews In WWW 2013 概要 スペクトルグラフ理論 有限グラフでは適切なカット・コミュニティが見つけられない Dirichlet固有値を使うよ！ スペクトルグラフ理論 正規化されたラプラシアン degreeのところをちょっと変える $$ 0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2 $$ スペクトルギャップ$$ \lambda_2 $...
  • 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...
  • Human Wayfinding in Information Networks
    Human Wayfinding in Information Networks Robert West, Jure Leskovec Stanford univ. In WWW 2012 概要 クリックの列に関する大量のデータを解析 人間をどうナビゲートするか？ Wikispedia Game スタートとゴールが与えられるので、wikipediaだけ辿ってゴールを目指す リストとかの汎用的なページは確か見れない 人間の探索能力 ヒストグラムを見てみる shortest paths small-world human, effective human, incl. back-clicks human, drop-ou...
  • Streaming Submodular Maximization: Massive Data Summarization on the Fly
    Streaming Submodular Maximization Massive Data Summarization on the Fly Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbas, Andreas Krause KDD 2014 概要 ストリーム設定の単調劣モジュラ関数最大化 ワンパスで1/2-ε近似 関数評価も無作為標本で近似 実験で爆速 アルゴリズム1 最適値$$ \texttt{OPT} $$を知っている $$ \alpha \texttt{OPT} \leq v \leq \texttt{OPT} $$ $$ \textbf{for } i = 1 \textbf{ to } n $$ ...
  • 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を無視してクラスタ更新 これを収束するま...
  • Estimating Sizes of Social Networks via Biased Sampling
    Estimating Sizes of Social Networks via Biased Sampling Liran Katzir, Edo Liberty, Oren Somekh Yahoo! Labs, Israel WWW 2011 概要 ネットワークのサイズ=頂点数を見積もりたい どういうシチュエーション？ FacebookとかTwitterとか…隣接リストは辿れるけどexplicitに|V|が得られない ランダムウォークベースのアルゴリズム 一様サンプリングでなくて次数でバイアスがかかっているのがポイント 一様よりも高性能であることを実験で示した サンプリング 誕生日パラドックスに基づいた手法 rノードを一様サンプリングす...
  • Robust Quadratic Programming for Price Optimization
    Robust Quadratic Programming for Price Optimization Akihiro Yabe, Shinji Ito, Ryohei Fujimaki IJCAI 2017 概要 価格最適化は二段階 需要モデル 機械学習なので、ノイズとか推定誤差あるよ ロバストにしたいね 最良価格戦略 binary quadratic programmingとかsemi-definite programmingとか アプローチ 価格最適化に関して、不確実性を行列正規分布で表現した 非ロバスト版をサブルーチンとして解く感じ 問題定式化 すっ飛ばすと$$ \mathrm{min} v(x)^\top Q v(...
  • StreamKM++: A Clustering Algorithm for Data Streams
    StreamKM++ A Clustering Algorithm for Data Streams In JEA 2012 Journal of Experimental Algorithmics In ALENEX 2010 概要 コアセットを使ったストリームk-meansアルゴリズム アルゴリズム ストリームモデルでコアセットを頑張って計算する 確かマルチパス 最後にk-means++を適用 コアセット Pの(k,ε)コアセット 重み付き集合Sと重み関数wの組 $$ \forall C \subset \mathbb{R}^{d}(|C|=k) \quad (1-\epsilon)cost(P,C) \leq cost_w (S,C) \...
  • Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...
    Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing Zachary Friggstad, Chaitanya Swamy STOC 2014 概要 Approximation Algorithms for Regret-Bounded Vehicle Routingについて 30.86近似アルゴリズム 今までO(log n)近似 RVRP 入力 完全グラフ 距離 三角不等式 始点r 整数R rを始点とするパスの集合で次を満たす 全頂点が少なくとも1つに被...
  • Finding Influential Nodes in a Social Network from Information Diffusion Data
    Finding Influential Nodes in a Social Network from Information Diffusion Data Masahiro Kimura, Kazumi Saito, Ryohei Nakano, Hiroshi Motoda SBP 2009 Social Computing and Behavioral Modeling 概要 ノードの影響力をカスケード情報からランキングしたい ICモデルで確率を見積もるよ！ ただし，確率の値は一様 実際のネットワークで実験してみる ヒューリスティクスより精度良い 手法 Prediction of Information Diffusion Probabilities ...
  • Computing and maximizing influence in linear threshold and triggering models
    Computing and maximizing influence in linear threshold and triggering models Justin T. Khim, Varun Jog, Po-Ling Loh NIPS 2016 概要 影響拡散の上下限を新たに作ったよ！ LTモデルとTriggeringモデル 下限は単調劣モジュラなので、最大化できて良い解になる 主結果 LTモデル 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$ An Upper Bound based Greed...
  • 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とグラフクラスタリングが等価だ...
  • 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • Catching the head, tail, and everything in between: a streaming algorithm ...
    Catching the head, tail, and everything in between a streaming algorithm for the degree distribution Olivia Simpson, C. Seshadhri, Andrew McGregor ICDM 2015 概要 ストリームで次数分布を求めたい 精確には累積分布 普通にやると，tail部分の精度が酷いことに（というか破滅）なる head／tailそれぞれに推定器を用意 Relative Hausdorff距離というナイスな距離を導入 実験では↑で評価→良 アルゴリズム 各辺が任意の順番にワンパスで来る n,mは知らない（というか不定） 辺削除／繰り返...
  • Inferring the Underlying Structure of Information Cascades
    Inferring the Underlying Structure of Information Cascades Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan ICDM 2012 概要 ICモデルのカスケードが部分的に与えられる 時刻tにuがアクティブになったみたいな どういう経路を辿ったかの木を知りたい 時刻が厳密に一致する場合とそうでない場合の問題を定式化 難しいけど頑張って解く 実験したらいい感じ 問題定式化 カスケードC 根付き木で時刻がある bounded consistent tree 木上での根sから頂点v_iまでの距離が観測時刻t_i以下 d(s,v_i)≦t_i...
  • Information Diffusion and External Influence in Networks
    Information Diffusion and External Influence in Networks Seth Myers, Chenguang Zhu, Jure Leskovec In KDD 2012 メモ http //cs.stanford.edu/people/jure/pubs/ext-kdd12.pdf アブスト influence の始まりってどこ？ってのを考える influence の伝わり方は2パターンある ノード-ノードを伝って ネットワーク外から これに注目 新しいモデル フィッティングしやすいパラメータ Twitterに適用 完全なひと月のデータ 情報がネットワークをジャンプしている ...
  • Non-exhaustive, Overlapping k-means
    Non-exhaustive, Overlapping k-means Joyce Jiyoung Whang, Inderjit S. Dhillon, David F. Gleich SDM 2015 概要 既存のクラスタリング（特にk-means）手法は、外れ値の重複のどちらかだけだった NEO-K-Means (Non-Exhaustive Overlapping K-Means) を提案 重み付きカーネルk-meansとの互換性もある 外れ値 重複有りグラフクラスタリングに使える 定式化 $$ U=[u_{ij}]_{n \times k} $$ $$ \mathbf{x}_i $$がクラスタ$$j$$の属する 重複の具合の制約 $$ \mathrm{trace}(...
  • Scalable Maximum Clique Computation Using MapReduce
    Scalable Maximum Clique Computation Using MapReduce Jingen Xiang, Cong Guo, Ashraf Aboulnaga ICDE 2013 概要 MapReduceを使った最大クリークアルゴリズム グラフの分割が味噌 Multi-depth Color-based (BMC) partitioning 分割した後は個々に解く この時も枝刈りをして早くする 実験は10^2~10^3オーダー頂点で密なグラフ 最大クリークアルゴリズム 分割後に使う最大クリークアルゴリズム MCRアルゴリズム（すでにある手法） 分枝限定法 ωを最大クリークのサイズとするとω(G)は下のどれか $$ \...
  • Influence maximization in complex networks through optimal percolation
    Influence maximization in complex networks through optimal percolation Flaviano Morone, Hernán A. Makse Nature 2015 概要 頂点を削除して最大の連結成分を最小化したい 強影響力頂点抽出，immunization，コミュニティ検出 既存手法…ヒューリスティクス 本手法 最適化問題 ある種の貪欲アルゴリズム 輪郭 最適パーコレーション 固有値の最小化問題 上を解く 最適パーコレーション $$ \nu_i $$の計算
  • Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
    Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang WSDM 2013 概要 voter modelを拡張 元はunsigned network signed networkにした 味方とは同じ意見（色） 敵とは違う意見（色） 最初の色の分布を与えた時の挙動を解析（面白い） このモデルでinfluence maximization ある意味で簡単 確率的振舞を計算するのが超大変 Voter ...
  • Modeling Information Diffusion in Implicit Networks
    Modeling Information Diffusion in Implicit Networks Jaewon Yang, Jure Leskovec ICDM 2010 概要 基本的にunderlyingなグラフは分からん グラフ構造っぽいのを使わずにモデリング Linear Influence Model Linear Influence Model 定式化 仮定 uがアクティブになった時刻 これだけ、リンク関係は謎 V(t) 時刻tに情報に言及した頂点の数 I_u(l) 頂点uが言及してから影響を受けてl時間後の言及した頂点の数 A(t) 時刻tまでにアクティブになった頂点の集合 M_u,k(t) 時刻tまでにuがアクテ...
  • Robust Influence Maximization (Chen+)
    Robust Influence Maximization Chen+ Robust Influence Maximization Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou KDD 2016 概要 最悪時比を最大化したい 解依存バウンド パラメタ空間をいい感じに狭めるサンプリング手法提案 実際、パラメタ空間が大きいと解が良くないので提案手法が効果的 問題定式化 パラメタ空間 $$ \Theta = \times_{e \in E}[l_e, r_e] $$ 頑健比 $$ g(\Theta, S) = \min_{\theta \in \Theta}\frac{\sigma_\theta(S)}{\sigma_\...
  • @wiki全体から「Chromatic Correlation Clustering」で調べる

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