todo314 @ ウィキ
todo314 @ ウィキ

Locally Densest Subgraph Discovery

todo314 @ ウィキ内検索 / 「Locally Densest Subgraph Discovery」で検索した結果

検索 :
  • Locally Densest Subgraph Discovery
    Locally Densest Subgraph Discovery Lu Qin, Rong-Hua Li, Lijun Chang, Chengqi Zhang KDD 2015 動機付け 皆密部分グラフ大好き でかいコミュニティからk個←ツマラン 重複回避で似てるの 最密部分グラフ(WSDM 15) クリーク(VLDB 15) 提案概念・手法 Gがρ-compact 任意のSをGから取り除くと、ρ|S|辺以上消える 極大ρ-compact部分グラフを考える Locally densest subgraph gがGの極大density(g)-compact部分グラフ LDSは互いに素なので、列挙可能 「最...
  • 気になった論文
    ...ation Locally Adaptive Optimization Adaptive Seeding for Monotone Submodular Functions How to Round Subspaces A New Spectral Clustering Algorithm Deterministic Algorithms for Submodular Maximization Problems Locality-sensitive Hashing without False Negatives Treetopes and their Graphs Improved Approximation Algorithms for k-Submodular Function Maximization Improved...
  • 論文一覧
    ...ation Locally Densest Subgraph Discovery ✔Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming KDD 2016 ✔Robust Influence Maximization (He-Kempe) Robust Influence Maximization (Chen+) FRAUDAR Bounding Graph Fraud in the Face of Camouflage KDD 2018 Appr...
  • 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 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 動機付け・問題定義 グラフがデカイので抽出するのが目的 興味があるもの（遺伝子とか）に関連あるのだけで良い 入...
  • 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で同じ計算時間 ...
  • 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...
  • 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は期待値（サポート） 期待値→構造パターン ...
  • 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...
  • 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...
  • 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/点数 を最大化したい ...
  • 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) $$のネットワ...
  • 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上のランダムウォークでやる ...
  • 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(...
  • 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) ...
  • 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...
  • 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 辺 ...
  • 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})≦λ...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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と...
  • 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...
  • Two New Local Search Strategies for Minimum Vertex Cover
    Two New Local Search Strategies for Minimum Vertex Cover Shaowei Cai, Kaile Su, Abdul Sattar AAAI 2012 概要 最先端の手法=[Cai-Su-Chen AAAI 10]には2つの問題が有る 頂点対の選択は時間がかかる →2段階制にするよ！ 辺重みを減らす処理が無い 遥か昔の重みが邪魔になるかも →忘却を入れる 上を解決したNuMVCを提案 提案手法 2段階交換 k-頂点被覆が手許にある→(k-1)-頂点被覆を探す |C|=k-1のまま頂点を消す入れるを反復 （AAAI 10みたいな上界を使わんらしい） ...
  • 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}...
  • 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で高速近似計算 比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった 感想 ...
  • On Influential Node Discovery in Dynamic Social Networks
    On Influential Node Discovery in Dynamic Social Networks Charu Aggarwal, Shuyang Lin, Philip S. Yu SDM 2012 概要 SN上のやりとりは瞬間的 その確率は瞬間を表す時間の関数 globally optimized forward trace approach locally optimized backward approach 動的モデル 頂点・辺はある時間帯に存在するみたいな感じ f_ij(δt) = a(1-exp(-λ_ij*δt)) δtの時間だけ辺ijが出現する時の伝播確率 (t1, t2)の間に辺(i, j)があるとする (t1, t2)をm分割してδt_iとす...
  • UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ...
    UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo ICDM 2013 概要 CELFは最初のiterationが遅い！ もうちょっとだけ早くするんじゃ 大まかな見積もりを行列計算でやる タイトかは分からんが正しい上界が出る 上界順にMonte-Carloして、それが最上位って分かったら抜ける シミュレーション数95%カット 速度は2~5倍(´・ω・`) 提案手法 上界の見積もり方 Pr_{S,t}[v] Sが時刻tにvをactivat...
  • 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...
  • FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
    FAST-PPR Scaling Personalized PageRank Estimation for Large Graphs Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri KDD 2014 概要 $$ \pi_s(t) \delta $$を$$ \mathcal{O}(\sqrt{d/\delta}) $$時間で近似計算 相対誤差が小さい 既存は$$ \Omega(1/\delta) $$時間で、$$ \delta=\Theta(1/n) $$にしたいので遅い□ 計算時間の下限$$ \Omega(1/\sqrt{\delta}) $$を示した 実験的には数十倍速い 提案手法 設定 ...
  • Maximizing the Spread of Cascades Using Network Design
    Maximizing the Spread of Cascades Using Network Design Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David Shmoys, William Allen, Ole Amundsen, William Vaughan UAI 2010 We apply our model to a sustainability problem that is part of an ongoing collaboration with The Conservation Fund to optimize the conservation of ...
  • Optimizing Budget Allocation Among Channels and Influencers
    Optimizing Budget Allocation Among Channels and Influencers Noga Alon, Iftah Gamzu, Moshe Tennenholtz WWW 2012 概要 最適予算配分問題の定式化 二部グラフ的な広告マーケティングを広告媒体視点と顧客視点のそれぞれでモデル化 ポイント 予算の配分という概念，今までは頂点を選ぶだけだった 影響の伝播は扱わない，予算の配分が主眼だから hardnessを解析 影響モデル G=(S,T,E) Sはソース，Tはターゲット，Eは辺集合 c_s (s∈S) 整数容量 B 予算 各ソースsに0以上c_s以下の整数予算b_sを割り当てる ...
  • 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_...
  • A Structural Smoothing Framework For Robust Graph-Comparison
    A Structural Smoothing Framework For Robust Graph-Comparison Pinar Yanardag, S. V. N. Vishwanathan NIPS 2015 概要だけ R-convolutionの問題 特徴空間がデカイと、自分以外とは類似しにくい（対角優位問題） 低次数部分構造（ちっちゃい部分グラフ）が分布を占めてしまう 部分構造は互いに関連しているけど、R-convolutionはEXACTを要求するので微妙 Deep Graph Kernelとはここが違うらしい 解決法 頻度ベクトルを平滑化する 色んな部分グラフを層っぽい感じに捉えて、関連性で平滑化 アイデア Maximum Likeliho...
  • 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につ...
  • 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)（福永さん） 何でノードだとめんどいの？ ...
  • 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...
  • 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}) -...
  • 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の長さ 数十 ~ 数百 ...
  • Reciprocity in Social Networks with Capacity Constraints
    Reciprocity in Social Networks with Capacity Constraints Bo Jiang, Zhi-Li Zhang, Don Towsley KDD 2015 概要 相互性（双方向辺の割合）が知りたい 双方向辺数最大化問題 NP-hard 3-pathを調整するヒューリスティクス 上限とか考える 実験的考察 実際のネットワークのいくつかは上限に凄く近い ヒューリスティクスが意外と良い 動機付け スウェーデンのWikipedia 相互性 21% …これは大きいか？ ランダムグラフ 0% …よく分からん （次数制限の下の）上限 28% …21%は凄そう 逆に 90% …...
  • 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，閾値θ 出力 期待サポート≧θの部分グラフパターン 自明に分かること ...
  • On k-skip Shortest Paths
    On k-skip Shortest Paths Yufei Tao, Cheng Sheng, Jian Pei SIGMOD 2011 概要 k-skip coverを考えた 要はk-shortest pathのhitting set 色々使えそう 理論的な解析とそこそこ速そうなアルゴリズム 問題定義とか k-skip Shortest Paths SP(s,t)をs-t間の最短経路とし，その順番をv_1,v_2,…,v_lとする P*が以下を満たすならs-t間のk-skip shortest path ∀i P*∩{v_i,…,v_{i+k-1}}≠∅ つまり，どの連続するk頂点を選んでも，どれかひとつ以上はP*に含まれている k-s...
  • Dynamic Social Influence Analysis through Time-dependent Factor Graphs
    Dynamic Social Influence Analysis through Time-dependent Factor Graphs Chi Wang, Jie Tang, Jimeng Sun, Jiawei Han ASONAM 2011 概要 Pairwise Factor Graph (PFG) model Dynamic Factor Graph (DFG) model 問題設定 各時刻で重み付き辺が有ったり無かったり Pairwise influence μ_ij Dynamic social influence μ^t_ij G =(V,E,Ω)が欲しい Ωは時刻毎のμ_ij これって問題って言うのか？？？ ...
  • 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...
  • 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 ...
  • 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スコアの高いクエリを出力 実験 提...
  • 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ネットワークでの応用例...
  • 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} $$ ...
  • Approximate Convex Decomposition Based Localization in Wireless Sensor Networks
    Approximate Convex Decomposition Based Localization in Wireless Sensor Networks Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu, Chonggang Wang INFOCOM 2012 概要 Localization やばいのでヒューリスティクスばかり MDSって既存手法 凹だったり穴があるとやばい 凸図形に分割して気合 問題 2次元のWireless Sensor Netrwork 各頂点の位置が知りたい GPSはコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
  • 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 色々提案されてる ただし、離散ラベル グラフの分類 化合物とか？ 対象とするグラフ ...
  • Why approximate when you can get the exact? Optimal Targeted Viral Marketing ...
    Why approximate when you can get the exact? Optimal Targeted Viral Marketing at Scale Xiang Li, J. David Smith, Thang N. Dinh, My T. Thai INFOCOM 2017 概要 普通に厳密解目指すんで、オレ。 RR集合をサンプルしてからMaxCover部分を整数計画ソルバで解く 得られた結果の精度を保証するのがミソ 普通の いわゆるtwo-stage stochastic programmingを使った場合 各サンプルがO(m)サイズ 信頼区間だけなのが嫌だ $$(\epsilon,\delta)$$近似を保証するサンプルサイズが良く分からん ...
  • Two Weighting Local Search for Minimum Vertex Cover
    Two Weighting Local Search for Minimum Vertex Cover Shaowei Cai, Jinkun Lin, Kaile Su AAAI 2015 概要 AAAI 12の改良 貪欲ヒューリスティックを頃すような入力に対して弱い 頂点重み付で↑を解決（何で？） 提案手法TwMCV（NuMVCの改良） DIMACS+BHOSLIB+実世界ネットワーク(!) 提案手法 NuMVCと同じ枠組み Cが頂点被覆になったら1頂点削除 交換 C←C-u+v 頂点重み付け Cにあまりいないような頂点を強制的にCに入れるようにする 貪欲ヒューリスティックだと全く選ばれない頂点が必要なインスタンスに効果有り...
  • @wiki全体から「Locally Densest Subgraph Discovery」で調べる

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