todo314 @ ウィキ
todo314 @ ウィキ

Overlapping Community Detection Using Seed Set Expansion

todo314 @ ウィキ内検索 / 「Overlapping Community Detection Using Seed Set Expansion」で検索した結果

検索 :
  • 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...
  • 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...
  • 気になった論文
    ...nding Overlapping Matrix Pattern Visualization A Hypergraph Approach Fast Counting of Triangles in Large Real Networks without Counting Algorithms and Laws RTM Laws and a Recursive Generator for Weighted Time-Evolving Graphs Mining Large Networks with Subgraph Counting Spotting Significant Changing Subgraphs in Evolving Graphs Frequent Subgraph Retrieval in Geometric ...
  • 論文一覧
    ...haustive, 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 Approximating the Spectrum of a Graph IEEE International Conference on Data Mining ICDM 2006 Fast Random Walk with Restart ...
  • 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...
  • 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)の最小化もあるけれどそうではなくて、最大のサンプルを見つ...
  • 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...
  • Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming
    Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming Yangyang Hou, Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon KDD 2015 概要 Non-exhaustive, Overlapping k-meansの続き 元の反復アルゴリズムはあまり良くなかったりする 違う解き方を考案 凸SDPで緩和 そのままだと大変なので低ランク近似 初期化・丸めもちょっと頑張る 実験してみたら良かった 重複有りコミュニティ検出にも使える kernel k-meansとグラフクラスタリングが等価だ...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • 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...
  • k-means--: A unified approach to clustering and outlier detection
    k-means-- A unified approach to clustering and outlier detection Sanjay Chawla, Aristides Gionis SDM 2013 概要 l点除いてかつk-meansも最小 除いたLが外れ値 問題定義 D(X\L, C)を最小化するC (of size k) とL (of size l) を求めたい Dは最小二乗距離和 k=1ならn^d^3で解けるけど基本NP-hard 提案手法 k-meansの変形に相当 各点についてクラスタまでの距離計算 距離でソートして大きいl点をLにつっこむ Lを無視してクラスタ更新 これを収束するま...
  • 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...
  • 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アカウントの状態の指標 をいれる...
  • 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上のランダムウォークでやる ...
  • Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local ...
    Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local Community Methods David F. Gleich, Seshadhri Comandur せしゃどり In KDD 2012 (closed) vertex neighbor 距離1以内の頂点集合 これがそれなりに良いコミュニティ マジかよ 理論的に示す 実データも使う 目的関数 $$ vol(S) = \sum_{v \in S} \deg(v) $$ $$ cut(S,T) = \{ (u, v) \in E | u \in S, v \in T \} $$ コンダクタンス（これが目的関数） ...
  • 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は出てこない ...
  • Mining Social Networks Using Heat Diffusion Processes for Marketing ...
    Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King CIKM 2008 概要 熱拡散過程によるモデリング 3つの拡散モデル，3つのアルゴリズム 製品採択に時間を入れる クラスタ（係数）を反映 正負の意見を伝える 熱拡散モデル 当然，物理現象 分類，次元削減とかに使われている 開発者・ターゲットは熱源として振る舞い，一杯熱を持ってる で，どんどん広がっていく f_t(x,t)=Δf(x,t) f(x,t) 時刻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) つまり一番安いのを買お...
  • Assessing Attack Vulnerability in Networks with Uncertainty
    Assessing Attack Vulnerability in Networks with Uncertainty Thang N. Dinh, My T. Thai INFOCOM 2015 概要 ネットワーク脆弱性を「期待対連結性」で評価したい 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題 提案手法は、LPによる緩和＋交換ヒューリスティクス 期待対連結性のFPRASを提案 期待対連結性 脆弱性の色々な尺度 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない 対連結性 (pairwise connectivity)は結構良いらしい 致命的頂点検出問題 (critical node detection; CND) 普通...
  • 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 ...
  • 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はコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
  • 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} $$ ...
  • A Local Search Approximation Algorithm for k-Means Clustering
    A Local Search Approximation Algorithm for k-Means Clustering Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y.Wu In SCG 2002 Symposium on Computational Geometry 概要 k-meansアルゴリズム 多項式時間で(9+ε)-近似 Single-Swap ヒューリスティクス 山登り法 初期状態から状態遷移していき、局所解を答えとする 状態 k個の施設 遷移 k個の施設の内1つを残りのn-k個と交換（だから、Single-...
  • 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) $$のネットワ...
  • Non-exhaustive, Overlapping k-means
    Non-exhaustive, Overlapping k-means Joyce Jiyoung Whang, Inderjit S. Dhillon, David F. Gleich SDM 2015 概要 既存のクラスタリング（特にk-means）手法は、外れ値の重複のどちらかだけだった NEO-K-Means (Non-Exhaustive Overlapping K-Means) を提案 重み付きカーネルk-meansとの互換性もある 外れ値 重複有りグラフクラスタリングに使える 定式化 $$ U=[u_{ij}]_{n \times k} $$ $$ \mathbf{x}_i $$がクラスタ$$j$$の属する 重複の具合の制約 $$ \mathrm{trace}(...
  • 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) = φ 木幅は制限し...
  • 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の長さ 数十 ~ 数百 ...
  • Minimizing the expected complete influence time of a social network
    Minimizing the expected complete influence time of a social network Yaodong Ni, Lei Xie, Zhi-Qiang Liu Information Sciences 2010 概要 最終的に全員が活性化する MP3プレーヤーがカセットテープの上位互換，みたいに駆逐される設定 時間が勝負 incremental chance model 無向グラフ G=(V,E,w) jumping 1つ以上の活性頂点を近傍に持つ sleeping 近傍は全て非活性 時刻tで頂点jは $$ p_t^j = \frac{\sum_{i \in N(j) \mathrm{active}}w_{ij}...
  • TwitterRank: Finding Topic-sensitive Influential Twitterers
    TwitterRank Finding Topic-sensitive Influential Twitterers Jianshu Weng, Ee-Peng Lim, Jing Jiang, Qi He WSDM 2010 ビデオ見て書いてみたよ http //videolectures.net/wsdm2010_weng_trft/ 概要 トピックを指定して影響力の高い頂点を見つけたい 応用 leaderの特定 マーケティング、広告 難しいところ ユーザ同士の関係がnon-serious トピックが分からん ground truthとは…？ データ シンガポールに限って 1000人位 割りと疎...
  • Cost-effective Outbreak Detection in Networks
    Cost-effective Outbreak Detection in Networks Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance KDD 2007 概要 outbreak detection問題を考える 色々あるけど目的関数はsubmodularになるのが多い 貪欲アルゴリズムで近似だ！ しかもsubmodularityを活かした高速化手法+online boundも考案 安定のLeskovecといったところか Outbreak detection モチベーション グラフ上でのカスケードを検知したい！ 水質汚染 ...
  • 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(ε)...
  • 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 スパム同士は結合...
  • 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の出辺を...
  • 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_...
  • Inverse Density as an Inverse Problem: The Fredholm Equation Approach
    Inverse Density as an Inverse Problem The Fredholm Equation Approach 密度比推定問題を第一種Fredholm方程式に変形して解く 応用 importance sampling 共変量シフト・バイアスサンプリング 訓練データとテストデータの分布が異なるとき 分布p,qがある d次元からスカラー それぞれサンプリング p(x)/q(x)を推定したい ナイーブ 直接推定して商を取る こっちのが難しい（当たり前 直接推定しないのがポイント やべえわからねえ… Fredholm方程式を解く手法を色々ある NIPS 2014-...
  • 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...
  • Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
    Viral Marketing Meets Social Advertising Ad Allocation with Minimum Regret Çigdem Aslay, Wei Lu, Francesco Bonchi, Amit Goyal, Laks V. S. Lakshmanan VLDB 2015 概要 ソーシャルネットワーク上で広告マーケティングをしたい 今までのは伝播を未考慮 ホスト、広告主、ユーザの関係をうまく定式化 ホスト…自分の利益を最大化するように、ユーザに広告を配置 広告主…エンゲージメント毎にホストへ（予算の範囲で）金を支払う ユーザ…タイムラインに大量の広告が流れてくるとやだ 貪欲アルゴリズム…regretに関する保証 問題定式化 ...
  • In Search of Influential Event Organizers in Online Social Networks
    In Search of Influential Event Organizers 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) ...
  • 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) ...
  • Resampling-based Predictive Simulation for Identifying Influential Nodes ...
    Resampling-based Predictive Simulation for Identifying Influential Nodes over Social Network 社会ネットワーク上の強影響度ノード同定のためのリサンプリングに基づく予測シミュレーション法の提案 Kouzou Ohara, Kazumi Saito, Masahiro Kimura, Hiroshi Motoda JSAI 2014 概要 ICモデルのシミュレーションは何回やればいいの？ 真の影響度との誤差を知りたいけれど，真値が分からない leave-N-out 交差検証 |S|回シミュレートした $$ \bar{A}_S(v) $$ 試行集合Sに対するvの影響度の平均値 パラメータNについて↓で...
  • 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] + ...
  • 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する 予備知識みたいな...
  • 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...
  • 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)を求めないで頑...
  • A Dual-tree Algorithm for Fast k-means Clustering with Large k
    A Dual-tree Algorithm for Fast k-means Clustering with Large k Ryan R. Curtin SDM 2017 概要だけ Lloydのアルゴリズムと同じ結果を出力するk-means高速化アルゴリズム 基本戦略 点集合と中心集合をそれぞれ木（kd-木、cover tree等）で管理する 点部分集合と中心部分集合の対の関係をまとめて見る 枝刈りをまとめて行える（各点の属する中心の更新とか） 枝刈り条件が沢山ある（一応強そう） 計算時間 結構色々な仮定の下O(N+klogk)時間 expansion constant, related quantityの多項式が掛かってくる 実際には速い 実験;...
  • Social Network Sensors for Early Detection of Contagious Outbreaks
    Social Network Sensors for Early Detection of Contagious Outbreaks Nicholas A. Christakis, James H. Fowler PLoS ONE 2010 概要（だけ） outbreakを検知したい でもネットワーク全体を入手するのがダルい ランダムに選択した頂点の近傍をモニターすると良い ランダムに選択しただけよりも中心性が高くなるから 調査（インフルエンザの拡散）すると，提案手法の方が早くピークを検知できていた PLoS1 outbreak detection 2014-03-15 06 00 12 (Sat)
  • 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保証のある手法よりも、単純な全域木のほうが良かったりしたよ！ 準備 基本的なソルバの...
  • Inferring the Underlying Structure of Information Cascades
    Inferring the Underlying Structure of Information Cascades Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan ICDM 2012 概要 ICモデルのカスケードが部分的に与えられる 時刻tにuがアクティブになったみたいな どういう経路を辿ったかの木を知りたい 時刻が厳密に一致する場合とそうでない場合の問題を定式化 難しいけど頑張って解く 実験したらいい感じ 問題定式化 カスケードC 根付き木で時刻がある bounded consistent tree 木上での根sから頂点v_iまでの距離が観測時刻t_i以下 d(s,v_i)≦t_i...
  • 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以下って制約とか...
  • 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})≦λ...
  • @wiki全体から「Overlapping Community Detection Using Seed Set Expansion」で調べる

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