todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Minimum-Risk Maximum Clique Problem」で検索した結果

• Minimum-Risk Maximum Clique Problem
  Minimum-Risk Maximum Clique Problem Maciej Rysz, Pavlo A. Krokhmal, and Eduardo L. Pasiliao Dynamics of Information Systems Algorithmic Approaches 2013 概要 最小危険最大クリーク問題 各頂点には費用／損失を表す確率変数 同時分布は既知 特定の危険尺度で危険最小のクリークを見つけたい 尺度の単調性から最適解は極大クリークになる Erdős–Rényiグラフで実験 導入 状況 頂点 が不確かさを持つ 危険回避グラフ理論的問題 Xi 頂点iに紐づく確率変数 Xiの同時分布は分かる...
• 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)は下のどれか $$ \...
• 論文一覧
  ...OR系 Minimum-Risk Maximum Clique Problem k-means Streaming k-means approximation StreamKM++ A Clustering Algorithm for Data Streams k-means++ The Advantages of Careful Seeding Streaming k-means on Well-Clusterable Data A Local Search Approximation Algorithm for k-Means Clustering Fast and Accurate k-means For Large Datasets Hartigan s Method k-mea...
• 気になった論文
  理論計算機科学 ACM Symposium on Theory of Computing STOC 2000 Circuit minimization problem A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Improved algorithms for submodular function minimization and submodular flow On dual minimum cost flow algorithms The small-world phenomenon an algorithm perspective A random graph model for mass...
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• 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...
• The complexity of influence maximization problem in the deterministic linear ...
  The complexity of influence maximization problem in the deterministic linear threshold model Zaixin Lu, Wei Zhang, WeiliWu, Joonmo Kim, Bin Fu Journal of Combinatorial Optimization 2012 概要だけ linear threshold modelのしきい値を固定したバージョンを考える 近似の難しさ しきい値を固定するとσは多項式時間で求められる 当たり前。なぜO(n^2)で求めている？ 何でこんなことをしたのか若干謎
• 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...
• Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...
  Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks Wei Chen, Chi Wang, Yajun Wang In KDD 2010 概要 MIAモデルというのを使ってinfluence maximizationを高速化 アルゴリズム maximum influence paths (MIP) v- uへの伝搬は最短経路だけを考える しきい値θ以下の伝搬は無視する Dijkstraの途中で打ち切る maximum influence arborescence model influence spreadを以下で近似 $$ ...
• Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
  Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks Yang Zhang, Srinivasan Parthasarathy ICDE 2012 概要 Triangle K-Core なる密グラフの概念を提案 かなり速く抽出できる しかも動的更新もできる template pattern cliquesをサポート 可視化とかイベント検出とか Triangle K-Core 部分グラフG がTriangle K-Core G 内の各辺がk個以上の三角形に含まれている 辺eのMaximum Triangle K-Core eを含む部分グラフG_eでTri...
• A Fast and Provable Method for Estimating Clique Counts Using Turan's Theorem
  A Fast and Provable Method for Estimating Clique Counts Using Turán s Theorem Shweta Jain, C. Seshadhri CoRR 概要 k-クリークの個数の数え上げ サンプリングでの精度を上げるために、元のグラフをclique shadowと言うものに分解し、その上でサンプリング shadowの良さをTuránの定理を使って与える←辺密度がある値以上 構築はクリーク探索の再帰的アルゴリズムを途中打ち切り shadowの大きさは上手くバウンドできないけど、実際的にはかなり小さく上手く行く Turán s theorem k-cliqueの密度 $$ \rho_k(G) = |C_k(G)|/{|V| ...
• 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...
• 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につ...
• Influence Maximization in Dynamic Social Networks
  Influence Maximization in Dynamic Social Networks Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, Xiaoming Sun ICDM 2013 概要 influence max.の動的グラフ版を考える 現実的設定で、どこの頂点をprobeし直せば良いかを問題とする b頂点だけ更新できる influence spreadのずれがでかそうな頂点を頑張って計算する 実験の結果ベースラインよりかなり良かった 問題設定 G^t 時刻tでのグラフ b probeできる頂点数 b頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい ...
• Redundancy-Aware Maximal Cliques
  Redundancy-Aware Maximal Cliques Jia Wang, James Cheng, Ada Wai-Chee Fu KDD 2013 http //videolectures.net/kdd2013_wang_maximal_cliques/ 概要 極大クリークの列挙の問題点 めっちゃ重複するので、サイズがやばい 極大クリークと大体かぶるように一部だけ列挙するアルゴリズムを作ったよ！ まさかの乱択アルゴリズム 問題 Redundancy-Aware Maximal Cliques S 極大クリークの部分集合 $$ vis(C) = \max_{C \in S} \frac{|C \cap C |}{|C|} $$ ...
• Revenue Maximization in Incentivized Social Advertising
  Revenue Maximization in Incentivized Social Advertising Çigdem Aslay, Francesco Bonchi, Laks V. S. Lakshmanan, Wei Lu VLDB 2017 概要 Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret VLDB 15の続き感 Incentivized ユーザにも収入の分け前を上げる設定 単調劣モジュラ最大化 with 分割マトロイド制約 (for 広告-シード配置) and 劣モジュラナップサック制約 (for 各広告主の予算) 2つの近似手法を提案して、RISで高速化 定式化 ...
• 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_\...
• IRIE: Scalable and Robust Influence Maximization in Social Networks
  IRIE Scalable and Robust Influence Maximization in Social Networks Kyomin Jung, Wooram Heo, Wei Chen In ICDM 2012 概要 Influence maximizationを超高速に求めるアルゴリズムを開発 しかもロバストに良い解を発見する アルゴリズム $$ \sigma(S \cup \{v\}) - \sigma(S) $$を次で近似する $$ r(v) = (1-AP_S(v))\left[ 1+\alpha \sum_{vu}p_{vu}r(u) \right] $$ AP_S(v) Sがvをactivateする確率 $$ AP_S(v) - \sum_{s \in ...
• Robust Influence Maximization (Lowalekar+)
  Robust Influence Maximization (Lowalekar+) Meghna Lowalekar, Pradeep Varakantham, Akshat Kumar AAMAS 2016 概要だけ 最大後悔最小化する頂点集合が欲しい Robust Influence Maximization (He-Kempe) Robust Influence Maximization (Chen+)とだいたい同じ サンプリングの方法だとかアルゴリズムを提案 貪欲と比較しました～ 2ページなので良く分からず AAMAS 影響最大化 頑健最適化 2017/10/02
• 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) $$のネットワ...
• On minimizing budget and time in influence propagation over social networks
  On minimizing budget and time in influence propagation over social networks Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan Social Network Analysis and Mining (SNAM) 2012 MINTSS (minimum target set selection) 入力 閾値η 出力 σ(S)≧ηなる最小サイズのS 提案手法 貪欲算法 σ(S)＜η-εの間，増量（min{σ(S+t),η}で考える）が最大の頂点をSに追加 定理1 貪欲算法で双基準近似 σ(S)≧η-ε |S|≦(1+ln(n/ε))OPT 関...
• Influence Maximization in Social Networks When Negative Opinions May Emerge ...
  Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan SDM 2011 概要 商品の質が低かったらdisる人も出るよねーをモデル化 質をパラメータに含めたNegative Opinion付き positiveな人数が目的関数ならsubmodularは保たれる 速い手法を作って実験してみたよ Independent Cascade Mode...
• Robust Influence Maximization (He-Kempe)
  Robust Influence Maximization Xinran He, David Kempe KDD 2016 概要 様々な要因で影響関数が沢山ある min f(S)/f(S*) を最大化し、同時に良い近似を達成したい *対数因子を許すと1-1/e近似 実験したら実はヒューリスティクスも良い 動機づけ Q.何で影響最大化？ A.大人気だから 不確実性・雑音の原因 定義・基準が一杯 モデルは近似でしかない（？） 人間行動に関して無数の変数がある データが不完全（API制限・匿名化） パラメタ推定 というわけで、「第一目標として頑健性に注目する事は研究コミュニティにとって必須」 定式化 目的関数 $...
• Real-time Targeted Influence Maximization for Online Advertisements
  Real-time Targeted Influence Maximization for Online Advertisements Yuchen Li, Dongxiang Zhang, Kian-Lee Tan VLDB 2015 概要だけ Keyword-Based Targeted Influence Maximization トピックつきのモデル キーワード集合Tとシードサイズkが与えられる Tによって、頂点の重みが変わる(TF-IDFに基づいた奴)、Tに関して線形な感じ $$ \phi(v,T) = \sum_{w \in T}\mathrm{tf}_{w,v} \cdot \mathrm{idf}_w $$ if_wvはユーザvのワードwへの嗜好 だから"targeted...
• Influence Maximization in Near-Linear Time: A Martingale Approach
  Influence Maximization in Near-Linear Time A Martingale Approach Youze Tang, Yanchen Shi, Xiaokui Xiao SIGMOD 2015 概要 TIMInfluence Maximization Near-Optimal Time Complexity Meets Practical Efficiencyから更に改善しました 直接最適値の下限を推定するよ！ TIMよりめっちゃ速くなった TIMの問題点 最悪時には下限が最適値よりn/k倍悪い 下限の計算自体が結構（シード選択段階よりも）遅い 提案手法 Influence Maximization via Martingales (IMM)...
• 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の長さ 数十 ~ 数百 ...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• 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を割り当てる ...
• EWLS: A New Local Search for Minimum Vertex Cover
  EWLS A New Local Search for Minimum Vertex Cover Shaowei Cai, Kaile Su, Qingliang Chen AAAI 2010 概要 最小頂点被覆を求めたい 理論的には2近似は最高，1.3606未満はNP-hard ヒューリスティック 辺重み付けと上界見積もりが新規な点 DIMACSとBHOSLIBで検証 動機付け 何故最小頂点被覆をしたいのか？ 応用：ネットワークセキュリティ，スケジュール，VLSI設計 最大独立集合・最大クリークと関連がある（そのまんま） SATはいい感じの手法が沢山→頂点被覆を変換すれば？→流石にでかすぎて しょうがないので特化させた手法を作るよ 提案手...
• 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/点数 を最大化したい ...
• Real-time Topic-aware Influence Maximization Using Preprocessing
  Real-time Topic-aware Influence Maximization Using Preprocessing Wei Chen, Tian Lin, Cheng Yang CSoNet 2015 概要 トピックモデルで重みがクエリで高速影響最大化 手法1 実は単一トピックと考えて答えてもよさ気 手法2 影響拡散の増分を少し真面目に考える 実験の結果，マイクロ秒で返答 問題 $$ p_i(u,v) $$ トピックiに関する辺(u,v)の確率 クエリ$$ I=(\lambda_1, \lambda_2, \ldots, \lambda_2) $$ 辺確率$$ p(u,v) = \sum_i \lambda_i p_i(u,v) $$で影響最大化 ...
• Minimum Bisection is Fixed Parameter Tractable
  Minimum Bisection is Fixed Parameter Tractable Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh STOC 2014 minimum bisection グラフを半分にするためには何本の辺を除けばいいか k本取り除いて頂点集合AとBに分割される ||A|-|B||≦1 これがFPT!! O(2^O(k^3)*n^3*log^3 n) k 解の大きさ おおまかな流れ 専用の木分解→DP!! 分割 A∪B = V E(A\B, B\A) = φ 木幅は制限し...
• 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...
• Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ...
  Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, Hang Li MSRAとUniversity of Science and Technology of China WWW 2009 概要 たった今調べたクエリからURLを正しくレコメンドするのは無理 例 ホントは車のレビューサイトを見たい 検索クエリ Ford new cars → Toyota new cars 個々のクエリに着目するとautohome.comは出てこない ...
• Blocking Links to Minimize Contamination Spread in a Social Network
  Blocking Links to Minimize Contamination Spread in a Social Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda TKDD 2009 多分Minimizing the Spread of Contamination by Blocking Links in a Networkのジャーナル版
• 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...
• Time-Critical Influence Maximization in Social Networks with Time-Delayed ...
  Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process Wei Chen, Wei Lu, Ning Zhang AAAI 2012 概要 ICモデルは時間制限を設けないからダメ 締切＋時間の遅延付きモデルを考案 高速(?)アルゴリズムも提案して実験 Independent Cascade with Meeting events 遭遇確率 m(u,v) 伝搬確率 p(u,v) 各ステップtで、アクティブな頂点uは非アクティブな頂点に確率m(u,v)で遭遇する 一回目の遭遇において確率p(u,v)でアクティベーションが成功する これは一回だけ ...
• ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
  ASIM A Scalable Algorithm for Influence Maximization under the Independent Cascade Model Sainyam Galhotra, Akhil Arora, Srinivas Virinchi, Shourya Roy WWW 2015 概要だけ 当時最強のTIMはメモリ消費がやばいので、新しいアルゴリズムを作ったよ！ アルゴリズム Simpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復...
• Minimizing the Spread of Contamination by Blocking Links in a Network
  Minimizing the Spread of Contamination by Blocking Links in a Network Masahiro Kimura, Kazumi Saito, Hiroshi Motoda AAAI 2008 概要 タイトルまんまの論文 汚染最小化問題 目的関数は各頂点のσの平均 既存の研究（Kempe依然）では，出次数の大きい順に頂点を消していけば大体良いとしてた 今回は辺を消す 問題定義 min 1/|V|Σσ(v) Eからk辺取り除ける 提案手法 最も目的関数が小さい辺を選ぶ貪欲アルゴリズム σの計算がやばい この著者らが考えたBond Percolationで高速化 実験 ...
• StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
  StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng In CIKM 2013 ArXiv 2012 概要 実は今までのMonte-Carloは間違っていた！ 毎回ランダムグラフを作っているのが問題 そのせいで莫大な試行回数が要求される 俺が最強のMonte-Carloアルゴリズムを提案するぜ！ ランダムグラフを使いまわす Rは1/100に減った StaticGreedy R回ループ 各辺を割り当てられた確率に応じて消す...
• 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 ...
• 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...
• 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は期待値（サポート） 期待値→構造パターン ...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• 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アルゴリズ...
• Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study
  Debunking the Myths of Influence Maximization An In-Depth Benchmarking Study SIGMOD 2017 概要だけ 提案されたきた影響最大化の手法は本当に効率的なのか？ 比較手法 CELF, CELF++, TIM+, IMM, PMC, StaticGreedy, LDAG, SIMPATH, EaSyIM, IRIE, IMRANK 徹底的な実験を決行 個々の論文の著者の主張は間違っている！！ • PMC [39] PMC establishes itself as the only technique that consistently provides high spread and scales for bot...
• 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)...
• 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ベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
• 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...
• Simulated Annealing Based Influence Maximization in Social Networks
  Simulated Annealing Based Influence Maximization in Social Networks Qingye Jiang, Guojie Song, Cong Gao, Yu Wang, Wenjun Si, Kunqing Xie In AAAI 2011 概要 influence maximizationに対する初の焼きなましベースアルゴリズム influence spreadを高速に近似計算 アルゴリズム SA based 適当にseed setを変更するだけ SAEDV (Expected Diffusion Value) Aによりactivateされるノード数の期待値は $$ |A| + \sum_{v \in N^{o...
• @wiki全体から「Minimum-Risk Maximum Clique Problem」で調べる

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