todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Online Search of Overlapping Communities」で検索した結果

• Online Search of Overlapping Communities
  Online Search of Overlapping Communities Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, Wei Wang SIGMOD 2013 問題 コミュニティの考え方 k-clique グラフを頂点とする ↑の頂点ペアがk-1頂点を共有しているたら辺を張る それでの連結成分がコミュニティになる 定義 入力：頂点v，整数k 出力：vが属するk-cliqueコミュニティ（の列挙） 頂点ごとにkを変えられる うまお（という主張） これが仕事だ！（という主張） 貢献 問題定義、アルゴリズム設計、実験 (α,γ)-OCS γ-quasi-k...
• 気になった論文
  ...orest Online Submodular Welfare Maximization Greedy beats 1/2 Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). The Po...
• 論文一覧
  ...9.pdf Online TCS Seminars https //cstheory.stackexchange.com/questions/46930/online-tcs-seminars Algorithms Randomization Computation https //sites.google.com/di.uniroma1.it/arc/home Felix Reidl https //tcs.rwth-aachen.de/~reidl/ https //rjlipton.wordpress.com/2014/12/21/modulating-the-permanent/ https //barthesi.gricad-pages.univ-grenoble-alpes.fr/personal-website/dpps/2018...
• The Importance of Communities for Learning to Influence
  The Importance of Communities for Learning to Influence Eric Balkanski, Nicole Immorlica, Yaron Singer NIPS 2017 概要 The Power of Optimization from Samplesはcurvature制限時だった 今回は影響最大化をコミュニティ構造が明らかな場合、OPSの枠組みでなんとかするよ コミュニティの大きさを捉えられそうなアルゴリズムを提案 SBMの簡単な設定で近似比を証明 アルゴリズム COmmunity Pruning from Samples 設定 無向なので、基本的に連結成分の大きさ（の和）の期待値が影響力になる underlyingな...
• In Search of Influential Event Organizers in Online Social Networks
  ...nizers in Online Social Networks Kaiyu Feng, Gao Cong, Sourav S. Bhowmick, Shuai Ma SIGMOD 2014 概要 影響最大化 + 集合被覆のような問題 タイトルの通りイベント主催者を見つけるのが動機づけ 貪欲アルゴリズムと近似比2のアルゴリズムを提案 イントロ Plancast，Meetupというサービスが出てきている イベント主催者も影響力が有ったほうがいいね でも，分野横断とかだと色々な内容をカバーしてないと駄目だね this paper 問題定義 グラフ G = (V, E, w, A) wは辺確率，Aは頂点から特性集合への写像 k ...
• 4chan and /b/: An Analysis of Anonymity and Ephemerality in a Large Online ...
  ...n a Large Online Community Michael S. Bernstein, Andrés Monroy-hernández, Drew Harry, Paul André, Katrina Panovich, Greg Vargas ICWSM 2011 概要 anonymity（匿名性）とephemerality（短命であること）の面から4chanを理解する 4chanと/b/ /b/はランダム掲示板 4chan全体の30%のトラフィック リプライしたりすると最初のページに浮上 15ページ目の最下層に行くと消されて`Page Not Found ほとんど匿名で画像付きのレスが投稿される age，sageすると浮上するけど，ずっとsageられ...
• 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 ...
• ICWSM - A Great Catchy Name: Semi-Supervised Recognition of Sarcastic ...
  ...tences in Online Product Reviews Oren Tsur, Dmitry Davidov, Ari Rappoport ICWSM 2010 レビューが皮肉かどうか？ Greatとかあるとダルい 応用 意見抽出 要約 コーパス（データ） 1,2 皮肉でない 3,4,5 皮肉 これがアノテートされたコーパスで「教師つき学習」 普通はn-gramだけど今回はPhrase Patternを使う n-gramの一般拡張 語を変数で置換 変数は任意の語にマッチする 細かく設定できる パターンに語を挿入したらマッチ パターンの変数を削除したらマッチ データ...
• 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...
• Community-based Greedy Algorithm for Mining Top-K Influential Nodes in ...
  Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks Yu Wang, Gao Cong, Guojie Song, Kunqing Xie 焼きなましベースの人々と大体同じ KDD 2010 概要 NewGreedyIC（MixedGreedy）がstate-of-the-artだったころの話 どうしても時間がかかっちゃうので、コミュニティに分割することにした Community-based Greedy algorithm ちょっとおもしろい点 コミュニティ分割がICモデルのシミュレートで行われる ↑の後はDPする 予備知識みたいな...
• 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は出てこない ...
• 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_...
• 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 $...
• 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)に従う 平均α/(α+β) 拡散の履歴から各α，βをインクリメントするだ...
• 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...
• 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...
• 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) ...
• 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 ...
• 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ノードを一様サンプリングす...
• 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上のランダムウォークでやる ...
• 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...
• 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)で求めている？ 何でこんなことをしたのか若干謎
• 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}...
• Sparsification of Influence Networks
  Sparsification of Influence Networks Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, Antti Ukkonen KDD 2011 概要 Yahoo! Research, Barcelonaの方々 尤度最大化という観点で辺をk本残す問題を提案 近似がNP-hard 最適解は頑張ってDPできる 貪欲アルゴリズムを提案（最適解に近い） 実験したら最強 influence maximizationにも使えるよ！ モデル とりあえず，トレースから確率を推定したい カスケードのトレースは頂点と時刻のペアの列とする (v,t)につい...
• Quick Detection of High-degree Entities in Large Directed Networks
  Quick Detection of High-degree Entities in Large Directed Networks Konstantin Avrachenkov, Nelly Litvak, Liudmila Ostroumova Prokhorenkova, Eugenia Suyargulova ICDM 2014 概要 準線形時間で高次数の頂点を同定したい！ 問題 |V|より遥かに小さいAPI呼び出しで人気ユーザを知る 人気…高次数 API ユーザを一様ランダムに選ぶ ユーザ1人の入次数 ユーザ1人の出辺 ホントは1回当たり5000本 提案手法 S ← n1頂点をランダムに選ぶ Sの出辺を...
• Learnability of Influence in Networks
  Learnability of Influence in Networks Harikrishna Narasimhan, David C. Parkes, Yaron Singer NIPS 2015 概要だけ 様々な拡散モデルのPAC学習性 辺のパラメータそのものより、影響関数値の方が大事 Linear threshold 多層NN分類器っぽみ、VC次元 部分観測×、完全観測○ Independent cascade Covering numberで考えられる 完全観測○ Voter 線形回帰に帰着 部分観測○、完全観測○ 推定したいもの 影響関数$$ F 2^V \to [0,1]^n $$ シード集合に対して、各頂点...
• Locating the Source of Diffusion in Large-Scale Network
  Locating the Source of Diffusion in Large-Scale Network Pedro C. Pinto, Patrick Thiran, Martin Vetterli PRL 2012 概要 情報拡散の話 一部の頂点だけを観測して、「「発信源」」を推定する モデル化+実験 モデル 辺の時間 正規分布 負の値はごまかす 発信源 uniformly at randomに選択される 受信者 時刻+ソース 他の頂点に伝えない 理不尽な仮定はおかない 受信者がネットワークを分離したり、最初の観測時刻だけ記録 問題設定 入力 グラフ G=(V,E) 分布 ...
• 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で高速化 実験 ...
• 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がアクテ...
• A user-centric model of voting intention from Social Media
  A user-centric model of voting intention from Social Media Vasileios Lampos, Daniel Preotiuc-Pietro, Trevor Cohn ACL 2013 株価，伝染病，地震の被害予測 世論調査 媒体 個別訪問，電話（ランダム），インターネット 媒体としてのTwitter 利点 低コスト，若者の意見を反映 欠点 ユーザの偏り（暇人ばっか），嘘 線形回帰モデル 目的変数=係数*説明変数+決定項 y=ax+c 正則化項の目的 パラメータがスパースになれるよ！ 提案モデル Bilinear Elastic Net(BEN) 単語頻度とユーザ...
• Limiting the Spread of Misinformation in Social Networks
  Limiting the Spread of Misinformation in Social Networks Ceren Budak, Divyakant Agrawal, Amr El Abbadi In WWW 2011 概要 誤情報に対する訂正情報をイイ感じに流して誤情報の伝播を減らしたい submodular ってからのヒューリスティクス 問題 Multi-Campaign Independent Cascade Model 誤情報と訂正情報はそれぞれ辺ごとに異なる確率をとる 同時なら訂正優先 一度情報を受け取ったら以後変化しない 到達時間が大事 定式化 既に誤情報はいくらか伝わっている rターンたっている k...
• Triadic Measures on Graphs: The Power of Wedge Sampling
  Triadic Measures on Graphs The Power of Wedge Sampling C. Seshadhri, Ali Pinar, Tamara G. Kolda SDM 2013 概要 クラスタ係数、次数毎のとか、色々を統一的なフレームワークでもとめる wedgeを適当な重みでサンプリングしてtriangleを数えるだけ サンプルサイズがグラフのサイズに依存しないところがポイント シンプルにboundが出る 提案手法 サンプリングの方法 基本的にはwedgeをとってきて、それがtriangleを構成するか？を判定する global clustering coefficient choose(deg(v), 2)に比例する確率でv...
• Rounded Dynamic Programming for Tree-Structured Stochastic Network Design
  Rounded Dynamic Programming for Tree-Structured Stochastic Network Design Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein AAAI 2014 Xiaojian WuにはAAAIでお会いした このグループはあくまでStochastic Network Designとして捉えているっぽい（影響最大化も） 概要 有向木上の確率的ネットワーク設計に対する丸め動的計画法 河のネットワークでの状況を想定できるらしい FPTASでO(n^2/ε^2)だけど実験的にはもう少し速い（し精度も良い） 動機付けとか リバーネットワーク(?)の階層的構造を木構造で表現 その応...
• Top-K Nearest Keyword Search on Large Graphs
  Top-K Nearest Keyword Search on Large Graphs Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian In VLDB 2013 メモ Jeffrey Xu Yu!! 概要 top-k nearest keyword search 頂点 0個以上のキーワード 辺 長さ クエリ ノード、キーワード、k 出力 キーワードを含みノードに近いkノード top-k nearest keyword search に対するアルゴリズム 最短経路木 2つ提案 kが小さいよう 大きくてもOK 応用 Facebo...
• 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して木っぽくパスを広げる（同じ頂点がいくつかある...
• 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 スパム同士は結合...
• New Models for Competitive Contagion
  New Models for Competitive Contagion Moez Draief, Hoda Heidari, Michael Kearns AAAI 2014 概要 競合モデル2つ Connectivity と Endogenous 過去にはGoyal and Kearnsモデルがある 影響度だけでは不十分なので 連結度を考える Price of Anarchy と Budget Multiplierが大事な要素（らしい） これに結果を与えた Switching-selection framework Goyal and Kearnsのモデル Connectivity 活性頂点内の辺の数も考慮する E...
• Approximating the Spectrum of a Graph
  Approximating the Spectrum of a Graph David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant KDD 2018 概要 （正規化）Laplacianのスペクトラムが欲しい！ $$ \exp(O(1/\epsilon)) $$時間：定数！！！ $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$ 性質検査的な話もあるよ！ 提案手法 定数時間にしたいので、出力は[0,2]上の離散分布 $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番...
• The Role of Network Distance in LinkedIn People Search
  The Role of Network Distance in LinkedIn People Search Shih-Wen Huang, Daniel Tunkelang, Karrie Karahalios 2人目はLinkedIn SIGIR 2014 概要 LinkedInのクエリを色々調べてみた クエリの種類（タグ）でクリックの挙動がかなり変わる 名前じゃないクエリは自分から2次の人が選ばれやすい 1次はもういらないが，距離1の人のコネを使うと新しいコネができやすい ログ解析 Non-name Job Title, Skill, Company Name Name Last Name, First Name, First Nam...
• 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 $$ でかい...
• Real-Time Influence Maximization on Dynamic Social Streams
  Real-Time Influence Maximization on Dynamic Social Streams Yanhao Wang, Qi Fan, Yuchen Li, Kian-Lee Tan VLDB 2017 概要 クエリ Stream Influence Maximization sliding windowモデルで考える Influential Checkpoints 途中途中で結果をとっておいて ε-近似 Sparse Influential Checkpoints チェックポイントの数が多すぎるので、対数個くらいにまで減らす (log N)/β個で、ε(1-β)/2-近似 問題定式化 行動 $$ a_t = \langle...
• Structure-Preserving Sparsification of Social Networks
  Structure-Preserving Sparsification of Social Networks Gerd Lindner, Christian L. Staudt, Michael Hamann, Henning Meyerhenke, Dorothea Wagner ASONAM 2015 概要 疎化したグラフの性質を調べたよ "Local Degree"なる単純な手法で実は充分良いよ 辺数が元の20%でも、大体保存される 比較手法 Random Edge (RE) 一様ランダムに辺を選んでいく Triangles 属する△の個数の多い辺を順に残す Local Similarity (LS) 得点 = J(N(u...
• Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms
  Truss Decomposition of Probabilistic Graphs Semantics and Algorithms Xin Huang, Wei Lu, Laks V.S. Lakshmanan SIGMOD 2016 概要 Core decomposition of uncertain graphsのk-trussへの拡張 局所的：部分グラフの各辺がk-2△に含まれる確率≧γ k-coreっぽく辺を取り除いていく 当該確率はDPで計算 大域的：部分グラフ全体がk-trussを含む≧γ 確率の厳密計算が#P-hard ランダムサンプリングして探索 実験しました 問題定式化 局所$$(k, \gamma)$$-...
• Outward Influence and Cascade Size Estimation in Billion-scale Networks
  Outward Influence and Cascade Size Estimation in Billion-scale Networks]] Hung T. Nguyen, Tri P. Nguyen, Tam N. Vu, Thang N. Dinh SIGMETRICS 2017 （会議） Proceedings of the ACM on Measurement and Analysis of Computing Systems 2017 （ジャーナル） 概要 影響力推定の新しい指標outward influenceを作ったよ！…E[拡散サイズ]-|シードサイズ| 相対誤差を保証するのが難しい 高速アルゴリズムを作ったよ カスケードが小さくなり過ぎようにimportance samplingを...
• Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
  Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs Liam Roditty, Virginia Vassilevska Williams In STOC 2013 メモ Y.Yano 直径2近似O(n+m) BFSして最大の高さ additive approximation Aingworth 2つの組み合わせ 2種類のBFS木の高さの最大値 $$ s \in [1,n] $$ O(ns^2 + (s+n/s)m) 論文の内容 ns^2の項を消したい ↑高々s頂点のBFS N_s^out(v)を求めないで頑...
• Learning Sums of Independent Integer Random Variables
  Learning Sums of Independent Integer Random Variables In FOCS 2013 「離散」変数に対する中心極限定理のようなもの S = Σi X_i X_i∈{0,…k-1} 各X_iは独立かつiid性が「無い」 それぞれ分布が違う 何個Sからドローすれば良い？ k=2の時 簡単らしい、正規分布で近似 k=3の時 偶奇性が出る、やべえ ランダムなのに周期性が出る 結果 (i)構造定理 S \approx c*離散正規分布 + {1,…c}値をとる確率変数 c∈{0,…,k-1} (ii)学習定理 poly(k,1/ε)個ドロー！！ X_...
• Sensitivity of Diffusion Dynamics to Network Uncertainty
  Sensitivity of Diffusion Dynamics to Network Uncertainty Abhijin Adiga, Chris Kuhlman, Henning S. Mortveit, Anil Kumar S. Vullikanti ネットワークダイナミクスとかの研究所 AAAI 2013 概要 IC/LTモデルについて考える グラフに辺をちょっと足したら、influence spreadはどうなるか？がメイン アクティブノード数の期待値について適当な仮定をおいて解析 モデルとか ノイズモデル G=(V, E) 元のグラフ R(ε)=(V, E(ε)) (u, v)∈E(ε) wp ε/n G =G ⊕ R(ε)...
• On the Hardness of Graph Anonymization
  On the Hardness of Graph Anonymization Charu C. Aggarwal, Yao Li, Philip S. Yu ICDM 2011 概要 匿名化手法は色々あるけど、ランダムに辺を追加削除するだけはヤバイ！ これを理論的に示す 特にソーシャルネットワークはmassiveかるsparseでこれが効いてくるらしい perturbation（摂動）に対してロバストなパラメータがある ↑を元にした手法を作り実験 Linkage Covariance $$ LinkCov(p,q) = \sum_{i}x_{pi}x_{qi}/n - \sum_{i}x_{pi}/n \sum_{j}x_{qj}/N $$ ロバスト性 確率f_aで辺を追...
• 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
• Spheres of Influence for More Effective Viral Marketing
  Spheres of Influence for More Effective Viral Marketing Yasir Mehmood, Francesco Bonchi, David Garcia-Soriano SIGMOD 2016 概要 確率的な挙動の典型的なカスケードが欲しい 期待Jaccardを最小化する頂点集合を計算する問題 ありうるカスケード皆に程々に近い、安定性の指標でもある O(1)サンプルで定数倍近似 貪欲に勝った！ 動機づけ 「少数のスーパースター」よりも「多数の凡人」の方が信頼できる 個々の影響力は小さいけれど、クリティカルマス到達 最確カスケードは良くない カスケードは2^n種類あるので、最大の確率はかなり小さく、代表的とは...
• @wiki全体から「Online Search of Overlapping Communities」で調べる

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