todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Efficient Label Propagation」で検索した結果

• Efficient Label Propagation
  2017/04/02 Efficient Label Propagation Yasuhiro Fujiwara, Go Irie ICML 2014 概要 半教師有り学習法であるラベル伝播は大事だよ 実質的に逆行列の計算が必要 各点に対して、最大のスコアを持つラベルを割り当てる 点数n、ラベル数c 厳密手法 $$ O(n^3 + cn^2) $$時間 近似手法 べき情報でまとめて計算、ただし、ラベル割当が異なりうる 提案手法 厳密のまま高速化 アイデアは、上界下界の保持によるラベルの枝刈り（いつもの感じ） $$ O(cnt) $$時間（tは反復回数） ラベル伝播 入力 点$$ (x_i)_i $$、ラベル（一部の点のみ）$...
• 論文一覧
  ... 2011 Efficient Influence Maximization in Social Networks KDD 2009 StaticGreedy Solving the Scalability-Accuracy Dilemma in Influence Maximization CIKM 2013 UBLF An Upper Bound Based Approach to Discover Influential Nodes in Social ... ICDM 2013 An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ... WWW 2014 Extracting Influential Nodes for Informa...
• 気になった論文
  ... Oracles Efficient Dynamic Algorithms for the Steiner Tree. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC 2016 Simpler Analysis and Enumeration of Parametric Minimum Cuts David Karger Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem Breaking the Logarithmic Barrier for Truthful Co...
• 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...
• A Novel and Model Independent Approach for Efficient Influence Maximization ...
  ...roach for Efficient Influence Maximization in Social Networks Hemank Lamba, Ramasuri Narayanam WISE 2013 概要 influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!! sparsificationするよ！ 精度を落とさずに数倍高速化 提案手法 ある頂点の近傍のスコアを出す スコアの出し方 色々な基準を大量に持ってくる 適当に重みを計算して足し合わせる スコアの大きい近傍をdeg(i)^eだけ残す 0 =e =1 実験 基準 次数とか共通近傍とかJaccard係数...
• 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をする 先にある程...
• Latent Feature Independent Cascade Model for Social Propagation
  Latent Feature Independent Cascade Model for Social Propagation Yuya Yoshikawa, Tomoharu Iwata, Hiroshi Sawada PDPTA 2013 International Conference on Parallel Distributed Processing Techniques Applications 概要 頂点属性っぽいのがついたICモデル 特徴が潜在的なのがポイント Learning Diffusion Probability based on Node Attributes in Social Networksは明示的に与える と主張しているはず モデル ...
• Influence Spread in Large-Scale Social Networks - A Belief Propagation Approach
  Influence Spread in Large-Scale Social Networks - A Belief Propagation Approach Huy Nguyen, Rong Zheng ECML PKDD 2012 概要だけ 大体PMIAの拡張みたいなもん DAGに変換して信念伝播法っぽいことをする ECMLPKDD 影響最大化 2014/12/11
• Holistic Influence Maximization: Combining Scalability and Efficiency with ...
  Holistic Influence Maximization Combining Scalability and Efficiency with Opinion-Aware Models Sainyam Galhotra, Akhil Arora, Shourya Roy SIGMOD 2016 概要 新しいモデル opinion-cum-interaction 高速アルゴリズム OSIM：OI用 EaSyIM：普通の影響最大化用 5%くらい質が悪いけど、良いよ！ モデル 省略します 　　,r´⌒ヽ,⌒ヽ,ヽ 　　　(⌒)､　　 .人　 λ＼､ .＿＿＿ 　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼ 　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●） 　　　　 |　 ...
• Efficiently Anonymizing Social Networks with Reachability Preservation
  Efficiently Anonymizing Social Networks with Reachability Preservation Xiangyu Liu, Bin Wang, Xiaochun Yang CIKM 2013 概要 匿名化の話 Kleinbergのに考え方は似てる 目標 個人情報を隠しつつ、なんかのクエリ=到達可能性を処理する k-degree anonymous 敵がvを次数情報のみから頂点を特定できる確率は1/k以下 有向グラフだけど、in-degとout-degがそれぞれ等しい頂点はk個以上 Reachability Preserving Anonymization 問題設定 入力 G=(V,E), 整数k ...
• COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
  ...ニング Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database が使えるように頑張る SIGMOD モチーフ 2015/11/12
• BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries
  BMC An Efficient Method to Evaluate Probabilistic Reachability Queries Ke Zhu, Wenjie Zhang, Gaoping Zhu, Ying Zhang, Xuemin Lin DASFAA 2011 概要 $$ \mathrm{rel}_{\mathcal{G}}(s,t) \theta? $$に答えたい 適当にrel(s,t)の上限を求める手法 駄目なら工夫したMonte-Carlo 提案手法 上限計算 out Pr[sから距離l以上遠くへ到達可能] in Pr[tへ距離m以上遠くへ到達可能] C B(s,l)とB(t,m)の間の「互いに素」なカットの集合 「カットが切られな...
• Efficient Estimation of Influence Functions for SIS Model on Social Networks
  Efficient Estimation of Influence Functions for SIS Model on Social Networks Masahiro Kimura, Kazumi Saito, Hiroshi Motoda IJCAI 2009 概要 SISモデルのシミュレートを高速化 ボンドパーコレーションと適当な枝刈り 精度には影響しない 実験で数百倍以上速い SISモデル 時刻は離散的 最初に頂点を活性化 活性頂点は非活性な頂点を与えられた確率で活性化 成功したら次の時刻に活性化 何も影響されなかった頂点は次の時刻に非活性化 求めたいもの σ(v,t) 時刻0でvを活性化したとき，時刻tで活性な頂点の数...
• Probabilistic Solutions of Influence Propagation on Networks
  Probabilistic Solutions of Influence Propagation on Networks Miao Zhang, Chunni Dai, Chris Ding, Enhong Chen 色々いるし名前を知らん CIKM 2013 概要 新しいinfluence spreadの計算方法 包除原理？ 実験もしてオリジナルより速くなったよ！ Exact influence spread n=3,4,5について、頑張ってinfluence spreadを厳密計算する 3頂点について 1がseed パターンを全部考えて、2、3がactiveになる確率を求めた でも、もっと簡単にできる 1から2がactiveにな...
• ASIM: A Scalable Algorithm for Influence Maximization under the Independent ...
  ...mpath An Efficient Algorithm for Influence Maximization under the Linear ...のような事をする vのスコア：vから始まる単純経路の重み付き和、重みは辺確率の積 辺確率行列Pの行列積のようなもの？ 以降の反復では、既に選んだシードの貢献を無視した差分を計算 CELF++より6--8倍速くて、TIMよりメモリ消費が1/200だよ まとめ 単純経路は本当に出来るのかな？重複しそう WWW 影響最大化 2017/10/01
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• More is Simpler: Effectively and Efficiently Assessing Node Pair ...
  ...ively 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つのノードから同じ距離辿って共通にならんと...
• 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がアクテ...
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for ...
  Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems Yin Tat Lee, Aaron Sidford In FOCS 2013 リプシッツ連続、強凸関数の最小化 加速座標勾配法 逆条件数κ^-1が0に近いとヤバイ 収束しにくい 加速勾配法・座標勾配法のマージ 今まではupdateがO(n)で遅い これをO(1)にしたヨ！！！ 遅延評価っぽいことをする FOCS 2013-11-03 02 19 09 (Sun)
• 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...
• 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...
• Computing and maximizing influence in linear threshold and triggering models
  ...の経路全体 Efficient influence spread estimation for influence maximization under the ...と一部かぶっている 最悪時には全然駄目、下限=1.5、上限=(n+2)/4 適当に仮定を置いて下限/上限をバウンドしようとしている Triggeringモデル 何かそれっぽいやつ その他性質 下限はすごく特殊な場合（近傍しか見てない）には、単調劣モジュラ 実験 目的：上下限がそれ程タイトか？貪欲アルゴリズムはどれくらい良いか？ データ：Erdős–Rényi、Preferential attachment、Gridで全て小さめ シードの選び方はシミュレーション回数が全体的に雑 まと...
• 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
• 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ノードを一様サンプリングす...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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は出てこない ...
• 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 （発見した）△の数 ...
• Efficient Location-Aware Influence Maximization
  Efficient Location-Aware Influence Maximization Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, Wen-Syan Li SIGMOD 2014 概要 位置を考慮した影響最大化 Foursquareとか クエリは領域とk 2つの手法を提案 1-1/e近似 expansion-based assembly-based それでも遅いのでさらに2手法 ε(1-1/e)近似 bound-based hint-based 問題定式化 vの位置は二次元座標(x,y) 情報拡散モデルはICモデル クエリ Q=(R,...
• 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)...
• Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
  Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy NIPS 2016 概要 Joint M-best-diverse labeling 問題をパラメトリック劣モジュラ最小化問題に帰着して解く 動機づけ・問題定式化 2値画像のノイズ除去・画像分割 エネルギー関数最小化として定式化 エネルギー関数 データ項= 「入力と出力の近さ」＋平滑化項=「出力の滑らかさ」 例 $$ E(y) = \sum_{v \in V}b_v [x_v \neq y_v] + ...
• Influence-based Network-oblivious Community Detection
  Influence-based Network-oblivious Community Detection Nicola Barbieri, Francesco Bonchi, Giuseppe Manco 最初の2人はYahoo Labs, Barcelona ICDM 2013 概要 ネットワークは与えられない 誰がいつ何かしたかのログが大量にある コミュニティ検出をしたい 情報拡散モデルをちょっと変えて検出させる 拡散具合はほぼコミュニティに依存するので、それを見積もろう Overview Q. ネットワークを再構築すればいいのでは？ A. 時間かかるので無理 例 Inferring Networks of Diffusion and Influe...
• Proposal of AIDM: Agent-based Information Diffusion Model
  Proposal of AIDM Agent-based Information Diffusion Model マルチエージェント型情報拡散モデル(AIDM) の提案 Keisuke IKEDA, Yoshiyuki OKADA, Takeshi SAKAKI, Fujio TORIUMI, Youiti KAZAMA, Itsuki NODA, Kosuke SHINODA, Hirohiko SUWA, Satoshi KURIHARA JSAI 2014 概要 ピークが沢山あるようなモデルを作ったよ モチベーション 東日本大震災でのTwitterの使われ方に注目 デマ（訂正）情報の拡散のピークが1個だけだったり一杯あったりするよ マルチバースト型（一杯の方）を再現したい ...
• Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest
  Accelerating Graph Adjacency Matrix Multiplications with Adjacency Forest Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata SDM 2014 概要 AXみたいな行列計算を高速にしたい Aの列中の値が同じ（確率遷移行列とか）だと余分な計算を省ける さらにAを分解して個々に省略手法を適用できる 3倍位速くなった 提案手法 Single Tree Adjacency Forest(STAF) Column-scaled nonzeros property 行列の各列j中の値＝0 or cj こんなやつ $$ A = \left( ...
• Playing Atari with Deep Reinforcement Learning
  Playing Atari with Deep Reinforcement Learning ポイント ゲーム+深層学習+強化学習 結果がやばい 深層学習+強化学習 Q(s,a)を畳み込みニューラルネットワークで表現 Atari 2600の7つのゲームで評価 背景削除とかいらないぜ！！ 3/7で人間に勝利 Arcade Learning Environment っていう環境があるらしい（知らなかった） 強化学習タスク 部分観測マルコフ決定過程 観測した画面だけでは現在の状況は分からん シューティングとか、弾がどっちに飛んでるか分からん ゲームのはじめからの画面と自分がとってきた行動を状態とする ↑のおかげでスタンダードな...
• 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...
• On Budgeted Influence Maximization in Social Networks
  On Budgeted Influence Maximization in Social Networks Huy Nguyen, Rong Zheng JSAC 2013 概要 頂点に単一でないコストがついた影響最大化 貪欲アルゴリズムをちょっと変形して1-1/√e近似 σを効率良く求めるためにDAGを作って信念伝搬っぽいことをやる Budgeted Influence Maximization 情報拡散モデルはIC max σ(S) s.t. c(S)≦b c(S)はc(u)(u∈S)の総和 [σ(S+v)-σ(S)]/c(v)で貪欲に選ぶと近似比が任意に悪くなる Leskovecのでも説明してたな… Improved Greedy ↑...
• Prediction of Information Diffusion Probabilities for Independent Cascade Model
  Prediction of Information Diffusion Probabilities for Independent Cascade Model Kazumi Saito, Ryohei Nakano, and Masahiro Kimura KES 2008 概要 ICモデルの辺の伝搬確率を沢山のカスケードから予測したい 頂点uが時刻tにアクティブになった情報 u,t が分かる 尤度を設定して期待値最大化 人工的なネットワークで実験するとそれなりに良い 問題 カスケードが与えられたとして vが時刻t+1でアクティブになる確率は↓ $$ P_v(t+1) = 1 - \prod_{u \in A_t}(1 - p_{uv}) $$ 伝搬確率p_uvを...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• Personalized Influence Maximization on Social Networks
  ... Efficient Local Greedy Algorithm (ELGA) wから逆にたどれば、各頂点から到達可能かをまとめて計算できる O(kD(m+m*)) Local Cascade Algorithm (LCA) 最短路木っぽいのを持っておく？ オンライン向けらしい 実験 比較対象 次数、ランダム、最大次数の近傍 データセット Epinions、Wikipedia（何で？） WPは(2M,5M) 結果 まぁよいよね LGAは重すぎるらしい ELGAも1000secくらい？ まとめ この問題だとまぁ早くしやすいわな 特定個人に注目するのはいいんだけど...
• Efficient algorithms for influence maximization in social networks
  Efficient algorithms for influence maximization in social networks Yi-Cheng Chen, Wen-Chih Peng, Suh-Yin Lee KAIS 2012 概要 CDH Community and Degree Heuristic CDH-KcutとCDH-SHRINK Heat diffusion model (HDM) 熱拡散（物理現象） f_i(t) 時刻tでのv_iの熱 初期状態t=0が与えられる 近傍からΔtの間影響を受ける iの変化量 = αΣ_j [f_j(t)-f_i(t)] 熱がθを超えたらアクティブになったとする シードに対してf(t_0)=h_0とセットする...
• 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}...
• 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上のランダムウォークでやる ...
• Simpath: An Efficient Algorithm for Influence Maximization under the Linear ...
  Simpath An Efficient Algorithm for Influence Maximization under the Linear Threshold Model Amit Goyal, Wei Lu, Laks V. S. Lakshmanan ICDM 2011 LTモデルの性質 $$ \sigma(S) = \sum_{v \in V} \Upsilon_{S,v} $$ Υ_S,v = Sがvを活性化させる確率 $$ \Upsilon_{s,t} = \sum_{\pi \in \text{Path}(s,t)} \Pr[\pi] $$ By definition of the ``live-edge model と簡単に言うが… ※結局はσ({s})はsを始点とす...
• Efficient Influence Maximization in Social Networks
  Efficient Influence Maximization in Social Networks Wei Chen, Yajun Wang, Siyu Yang In KDD 2009 概要 Wei Chen 劇場の始まりっぽい influence maximization のアルゴリズムを2つ提案 greedy based algorithm の高速化 ヒューリスティックによるinfluence spreadの近似 アルゴリズム NewGreedyIC seedを選ぶためにグラフをR=20000個作る Sから到達可能なノードは省く vから到達可能なノード数を計算、これがmarginに相当 これの計算は自明ではないが論文ではlinearでできると...
• 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 ...
• Analyzing Spammer's Social Networks for Fun and Profit
  Analyzing Spammer s Social Networks for Fun and Profit -- A Case Study of Cyber Criminal Ecosystem on Twitter Chao Yang, Robert Harkreader, Jialong Zhang, Seungwon Shin, Guofei Gu Texas A M Universityの人々 In WWW 2012 参考 http //www.slideshare.net/KuoE0/www2012-analyzing-spammers-social-networks-for-fun-and-profit 概要 Twitterのスパムに関するcase study スパム同士は結合...
• Efficient influence spread estimation for influence maximization under the ...
  Efficient influence spread estimation for influence maximization under the linear threshold model Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang Computational Social Networks 2014 概要 LTモデルの影響拡散を厳密or精度良く計算 4hop以内の影響について厳密計算 4hopはRandom walkで近似 性質 $$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$ P(S) = S内の頂点から出てる単...
• 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...
• 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...
• 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の長さ 数十 ~ 数百 ...
• @wiki全体から「Efficient Label Propagation」で調べる

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