todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Independent Set, Induced Matching, and Pricing: Connections Tight ...」で検索した結果

• 論文一覧
  ...and Model Independent Approach for Efficient Influence Maximization ... WISE 2013 Influence Spread in Large-Scale Social Networks - A Belief Propagation Approach ECML PKDD 2012 IMRank Influence Maximization via Finding Self-Consistent Ranking SIGIR 2014 ASIM A Scalable Algorithm for Influence Maximization under the Independent ... WWW 2015 Holistic Influence Maximization Comb...
• 気になった論文
  ...r Maximum Independent Set On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs Augmenting Graphs to Minimize the Diameter Sliding Bloom Filters An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching Smoothed Analysis of the 2-Opt Heuristic for the TSP Polynomial Bounds for Gaussian Noise Approximating t...
• Independent Set, Induced Matching, and Pricing: Connections and Tight ...
  Independent Set, Induced Matching, and Pricing Connections and Tight (Subexponential Time) Approximation Hardnesses Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai In FOCS k-hypergraph Pricing Problem 入力 V 商品 E_i 客iの好きなvのset |E_i|≦k b_i 客iの予算 出力 p_j v_jの値段 目的 max g=Σ_i g_i g_i = \min_{j∈E_i} p_j (p_j≦b_i) つまり一番安いのを買お...
• Learning Stochastic Models of Information Flow
  ...ities for Independent Cascade Model Learning Continuous-Time Information Diffusion Model for Social Behavioral ... Learning Influence Probabilities In Social Networks 確率分布は色々な設定で歪ませてある RMSEで比較 まとめ 機械学習よりは難しい… ICDE 情報拡散 情報拡散パラメータ推定 2014-03-31 23 57 24 (Mon)
• An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ...
  An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks Chuan Zhou, Peng Zhang, Jing Guo, Li Guo WWW 2014 companion ポスター 概要 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ...のLT版 CELFより5倍速い 提案手法 σ(S)=ΣΠw(e)の形でかける ↑は行列のべき乗和（有限）で上から抑えられる Wのべき乗和は(I-W)^-1で上から抑えられる 確率だから1以下って制約とか...
• 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...
• Maximizing the Long-term Integral Influence in Social Networks Under the ...
  Maximizing the Long-term Integral Influence in Social Networks Under the Voter Model Chuan Zhou, Peng Zhang, Wenyu Zang, Li Guo WWW 2014 companion ポスター 概要 Voter Modelにおける影響最大化 long-term integralを最大化したい 問題+提案手法 モデルはInfluence Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[...
• Sampling Community Structure
  Sampling Community Structure Arun S. Maiya, Tanya Y. Berger-Wolf WWW 2010 概要 expander graphのコンセプトによるコミュニティのサンプリング手法 コミュニティ検出で推論っぽいこと？もできるらしい 問題 X(S) = |N(S)|/|S| 隣接頂点数/頂点数 サイズkのサンプルSがcommunity representative sample minimize D[P_S(G(S)), P_S(G)] D[,]は分割に対する距離尺度 P_S(G)はGを使って作られた分割 手法 X(S)の最小化もあるけれどそうではなくて、最大のサンプルを見つ...
• Anytime Influence Bounds and the Explosive Behavior of Continuous-Time ...
  Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks Kevin Scaman, Rémi Lemonnier, Nicolas Vayatis NIPS 2015 概要だけ Tight Bounds for Influence in Diffusion Networks and Application to Bond ...の続き Hazard matrixを拡張するために、Laplace変換を導入した定義をしている 証明しているもの ある時刻での影響拡散の上限 Critical time（いつ拡散がでかくなるか）の下限 特定の確率設定や、SIRモデルでの応用 先...
• Selecting Information Diffusion Models over Social Networks for Behavioral ...
  Selecting Information Diffusion Models over Social Networks for Behavioral Analysis Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda ECML PKDD 2010 概要？ こっちではAsIC,AsLTモデルと言っているが， Learning Continuous-Time Information Diffusion Model for Social Behavioral ...とほぼ同じっぽいぞ…？ ECMLPKDD 情報拡散 情報拡散モデル 2014-09-14 04 08 53 (Sun)
• 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)| $$を最小化せよ ...
• Maximizing Submodular Set Function with Connectivity Constraint: Theory and ...
  Maximizing Submodular Set Function with Connectivity Constraint Theory and Application to Networks Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai Research Center for Information Technology Innovation（資訊科技創新研究中心） National Tsing Hua University（國立清華大學） INFOCOM 2013 概要 ワイヤレスネットワークのルーターの設置問題 submodular関数で表せる さらにルーターは連結であるという制約を追加 この設定でも近似アルゴリズムが設計できる 1...
• Predicting Japanese General Election in 2013 with Twitter: Considering ...
  Predicting Japanese General Election in 2013 with Twitter Considering Diffusion of Candidates Tweets Twitter における候補者の情報拡散に着目した国政選挙当選者予測 Nasuno Kaoru, Matsuo Yutaka JSAI 2014 関連研究 Twitterを使った選挙結果の予測 有権者に焦点 2010にうまおな論文が出たらしいが，2012年に否定されて，色々あって結局微妙っぽい 候補者に焦点 ほとんど無いっぽいよ！これやるよ！ アイデア 情報拡散の規模・多様度・候補者への忠誠度の指標 Twitterアカウントの状態の指標 をいれる...
• Tight Bounds for Influence in Diffusion Networks and Application to Bond ...
  Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology Rémi Lemonnier, Kevin Scaman, Nicolas Vayatis NIPS 2014 概要だけ 情報拡散のサイズの期待値のバウンドが欲しい ネットワーク科学方面の結果は辺確率が一様の場合 拡散モデル 離散時間情報カスケード いつもの 連続時間情報カスケード 遅延時間の分布、T→∞だけ考える ランダムグラフ 到達可能なら拡散 無限時間後なので、ぶっちゃけ同じ（補題1） Hazard matrix ...
• 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つに被...
• Influence Blocking Maximization in Social Networks under the Competitive ...
  Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Xinran He, Guojie Song, Wei Chen, Qingye Jiang SDM 2012 概要 Competitive Linear Threshold モデルを考えたよ 目的関数は自分の最大化じゃなくて，相手の最大化だよ そうするとこのモデルではsubmodularだよ 目的関数の計算が大変なのでPMIAっぽいものを作った Competitive Linear Threshold Model 各辺には2つの重みw+とw-がある 各頂点の閾値も2つθ+とθ- 状態はin...
• Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a ...
  Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang KDD 2014 概要 大きいカスケードが「起こりやすい」ようにシードを選びたい 期待値の代わりに確率を議論するのがミソ この問題は劣モジュラでない 色々解析 動機付け トピックがある閾値まで広まって欲しい tipping point 当然シードセットは小さくしたい しかも確率保証つきで 問題定義 独立カスケードモデル Seed Mini...
• 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...
• More is Simpler: Effectively and Efficiently Assessing Node Pair ...
  More is Simpler Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks Weiren Yu, Xuemin Lin, Wenjie Zhang, Lijun Chang, Jian Pei VLDB 2014 概要 SimRankを改良 SimRank* 速い旨い SimRankの書き方 行列でシンプルに書けるともーじゃん？ S=C(QSQ^T)+(1-C)I_n 嘘であった(´・ω・`) この論文どうするんでしょう みんなまちがえている 提案手法 何が問題？ 2つのノードが類似しているためには、2つ...
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...
  Path Sampling A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts Madhav Jha, C. Seshadhri, Ali Pinar WWW 2015 概要 数千万辺でも数十秒 誤差1%以下 Chernoff boundからエラーバーも出せる 問題定義 4-頂点部分グラフは6種類 3-star, 3-path, tailed-triangle 4-cycle, chordal-4-cycle, 4-clique C_i 誘導部分グラフにおけるi-th 部分グラフの出現個数 N_i i-th 部分グラフの出現個数 (C_i)と(N_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 ...
• Approximate Bayesian Image Interpretation using Generative Probabilistic ...
  Approximate Bayesian Image Interpretation using. Generative Probabilistic Graphics Programs 画像認識の新手法 応用 CAPTHA…これは文字ほげだ！ 道路認識 画像のシーンをシンボリックに 大きなコーパスが必要 トップダウンに考えるよ！ ボトムアップ 画像を要素に分解 それぞれを解釈 トップダウン 要素を仮定し画像を構成 その確率を出す モデル シーン…文字の種類とか 入力からこれを推定する レンダラを使った生成モデルで予測 Metropolis-Hastings 変数をちょっと動かしてほげ...
• 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カットを構成→必ず到達不可能 良く分から...
• Spectral Counting of Triangles in Power-Law Networks via Element-Wise ...
  Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification 概要 三角形の個数を早く求めたい 辺を確率1-pで削除 残った辺に重み1/pを割り振る 固有値で近似 何か速いよ！( (ﾟ∀ﾟ∩ 提案手法 まず，隣接行列を低ランクに近似 高固有値だけ計算する Lanczos methodというのを使い固有値を大きい順に求めていく 現在の固有値の三乗和に対する寄与がtot以下になったら打ち切り Eigen Triangle $$ \Delta(G) = \frac{1}{6}\sum_{i=1}^{n}\lambda_i^3 $$ でかい...
• 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...
• 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...
• Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in ...
  Stop-and-Stare Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks Hung T. Nguyen, My T. Thai, Thang N. Dinh SIGMOD 2016 概要 TIM+やIMMより速い影響最大化アルゴリズムを作りました RR集合のサンプル数が最小だよ！ 枠組み 2つの条件 $$ \Pr[\widehat{\mathsf{Inf}}(S_k) \leq (1+\epsilon_a)\mathsf{Inf}(S_k)] \geq 1-\delta_a $$ $$ \Pr[\widehat{\mathsf{Inf}}(S_k^*) \geq (1+\epsilon_b)...
• Influence Maximization in Big Networks: An Incremental Algorithm for ...
  Influence Maximization in Big Networks An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li Gao IJCAI 2015 概要 小さい部分グラフに分割する 頂点を共有しうるが辺は互いに素 挑戦 部分グラフ間のシミュレーションが重なる 提案手法 M=シミュレーション回数 N=分割個数 $$ (V_i)_i $$ Vの被覆 $$ (E_i)_i $$ Eの分割 X_r = コインフリッピング結果rを表す01値ベクトル ...
• 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...
• A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence ...
  A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence Problem Maxime Crochemore, Costas S. Iliopoulos, Yoan J. Pinzon, James F. Reid IPL(Information Processing Letters) 2001 概要 bit vectorによる爆速LCS、正確にはその長さ 時間 O(nm/w) 空間 O(m/w) w ビット数 事前知識 Σ アルファベット s=|Σ| LCSの時間計算量の下界 Ω(nlogm) 最速 Σサイズ制限無 $$ O(n^2 \log \l...
• Tracking the Random Surfer: Empirically Measured Teleportation Parameters in ...
  Tracking the Random Surfer Empirically Measured Teleportation Parameters in PageRank David F. Gleich, Paul G. Constantine, Abraham D. Flaxman, Asela Gunawardana WWW 2010 概要 PageRankのαの値は何なんだ？ 平均が0.3~0.7のβ分布に従う 分布の測定 人一人なら簡単 (リンククリックによる総閲覧ページ数) / (総閲覧ページ数) 複数人いると，平均とかいうわけにも行かない PageRankはαに対して非線形だから 代わりに，人毎にαを求め，グループ全体にフィットする分布を求める ↓の2...
• Is Nearly-linear the Same in Theory and Practice? A Case Study with a ...
  Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner SEA 2015 概要 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！ ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！ low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
• 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)$$近似を保証するサンプルサイズが良く分からん ...
• Influence of the Dynamic Social Network Timeframe Type and Size on the Group ...
  Influence of the Dynamic Social Network Timeframe Type and Size on the Group Evolution Discovery Stanisław Saganowski, Piotr Bródka, Przemysław Kazienko ASONAM 2012 概要 GED (Group Evolution Discovery) 法のパラメータチューニングの解析 グループ発展 時間発展でコミュニティは変化していくが，それを下記に分類 Continuing(停滞) サイズに変化なし．頂点がちょっと変わるくらいならOK Shrinking サイズが小さくなる Growing サイズが大きくなる...
• @wiki全体から「Independent Set, Induced Matching, and Pricing: Connections Tight ...」で調べる

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