todo314 @ ウィキ
todo314 @ ウィキ

Nonnegative Spectral Clustering with Discriminative Regularization

todo314 @ ウィキ内検索 / 「Nonnegative Spectral Clustering with Discriminative Regularization」で検索した結果

検索 :
  • Nonnegative Spectral Clustering with Discriminative Regularization
    Nonnegative Spectral Clustering with Discriminative Regularization Yi Yang, Heng Tao Shen, Feiping Nie, Rongrong Ji, Xiaofang Zhou AAAI 2011 概要（だけ） よくあるクラスタリング手法 どの要素がどのクラスタに属するかを表すindicator matrixで目的関数を表現 そのままだと解けないので{0,1}から緩和する 固有値分解をココらへんで使う 頑張って解く ±混ざっている {0,1}にする 何が問題？ 混合符号の行列がもらえた時にそれを量子化する簡単な方法が無い EM-like / k-means / spe...
  • 気になった論文
    ...008 Nonnegative Matrix Factorization for Combinatorial Optimization Spectral Clustering, Graph Matching, and Clique Finding 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 S...
  • 論文一覧
    ...works Nonnegative Spectral Clustering with Discriminative Regularization AAAI 2012 Exacting Social Events for Tweets Using a Factor Graph Time-Critical Influence Maximization in Social Networks with Time-Delayed ... Two New Local Search Strategies for Minimum Vertex Cover AAAI 2013 Sensitivity of Diffusion Dynamics to Network Uncertainty Spectral Rotati...
  • 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...
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • Streaming Submodular Maximization: Massive Data Summarization on the Fly
    Streaming Submodular Maximization Massive Data Summarization on the Fly Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbas, Andreas Krause KDD 2014 概要 ストリーム設定の単調劣モジュラ関数最大化 ワンパスで1/2-ε近似 関数評価も無作為標本で近似 実験で爆速 アルゴリズム1 最適値$$ \texttt{OPT} $$を知っている $$ \alpha \texttt{OPT} \leq v \leq \texttt{OPT} $$ $$ \textbf{for } i = 1 \textbf{ to } n $$ ...
  • Maximizing Influence in a Competitive Social Network: A Follower's Perspective
    Maximizing Influence in a Competitive Social Network A Follower s Perspective Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen ICEC 2007 概要 既に敵対するカスケードが広がっている時に，自分はどうシード集合を選択するか 2つのモデルを提案 NP-hardだけど1-1/e近似可能 モデル Aが自分で，Bが敵 I_B すでにBのシード集合 σ(I_A | I_B)が最大となるI_Aを選びたい ベースはICモデルと同じランダムグラフを考える E_a 残った辺 カスケードの仕...
  • How to Influence People with Partial Incentives
    How to Influence People with Partial Incentives Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghadam WWW 2014 概要 今までのinfluence maximizationは二者択一だった 実際には中間があるので，そういうモデルを作ったよ 分数版は積分版との違い モデル 積分影響モデル(integral influence model) Mossel and Rochの提案 f_v 2^V→[0,1] 辺を含んだ集合関数 ...
  • Competitive Influence Maximization in Social Networks
    Competitive Influence Maximization in Social Networks Shishir Bharathi, David Kempe, Mahyar Salek WINE 2007 概要 モデル 辺uvが試行成功したら指数分布の遅延時間T_{uv}が発生する bプレイヤがサイズk_i以下の集合S_iを選択する 複数人が選択した頂点はランダムに誰かの頂点になる これでカスケードをしていく 純粋戦略ナッシュ均衡は無い（？） 混合戦略ナッシュ均衡は有る 戦略 もし，他の人の戦略が固定されていたら 自分の戦略に対するσは単調かつ劣モジュラ First Mover Strategies Influence Max...
  • 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人位 割りと疎...
  • 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...
  • 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)でアクティベーションが成功する これは一回だけ ...
  • Co-clustering documents and words using Bipartite Spectral Graph Partitioning
    Co-clustering documents and words using Bipartite Spectral Graph Partitioning Inderjit S. Dhillon KDD 2001 概要 文書と単語の共クラスタリング カット最小化として妥当な問題設定 スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和 後はk-meansすると大体上手い 問題設定 $$ G=({\cal D}, {\cal W}, E) $$ 文書と単語の二部グラフ 辺重みが謎… 単語・文書クラスタリングの関係 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える というわけで、k...
  • 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
  • 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}...
  • Influence Maximization with Viral Product Design
    Influence Maximization with Viral Product Design Nicola Barbieri, Francesco Bonchi SDM 2014 概要 製品設計も考えた情報拡散LTモデル 同じアイテムでも特徴が違うとσが変わる 頂点+特徴の選択が必要 提案モデルF-TMの学習手法 最適化アルゴリズムを頑張る share-of-choice (SoC)問題 u_{f,l}^i 人i，特徴f，レベルlについてその効果 負もありうる 各人iについて Σ_fΣ_l x_{f,l} u_{f,l}^i ≧ h_i ならiはこの製品を採用する x_{f,l}は0-1変数，これを決定するのが問題 fe...
  • 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回ループ 各辺を割り当てられた確率に応じて消す...
  • Negative Influence Minimizing by Blocking Nodes in Social Networks
    Negative Influence Minimizing by Blocking Nodes in Social Networks Senzhang Wang, Xiaojian Zhao, Yan Chen, Zhoujun Li, Kai Zhang, Jiali Xia AAAI Workshop 2013 概要 ノードを取り除いて影響の拡散を抑えたい！ ウイルス，誤情報等 Negative Influence Minimization 感染シード(given) I ブロック S(|S|=k) 目標 minimize σ(I; V-S) Sは感染しない 手法 σが小さくなるノードを貪欲に選んでいく 実験 比較...
  • Streaming Graph Partitioning for Large Distributed Graphs
    Streaming Graph Partitioning for Large Distributed Graphs Isabelle Stanton, Gabriel Kliot In KDD 2012 メモ セミナー K.Inabaさん 問題 巨大グラフを複数に分割したい ストリーミングアルゴリズムじゃないと意味ないお 入力 G(V,E) k マシン台数 ε アンバランス度 出力 V1, V2, …, Vk $$ |Vi| \leq \frac{(1+\epsilon)|V|}{k} $$ または $$ \sum \deg(V_i) \leq (1+\epsilon)\sum \deg(v)/k $$ を満たすよ...
  • 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とグラフクラスタリングが等価だ...
  • CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in ...
    CINEMA Conformity-Aware Greedy Algorithm for Influence Maximization in Online Social Networks Hui Li, Sourav S Bhowmick, Aixin Sun EDBT 2013 Contribution conformity-aware cascade model(c^2 model) の提案 mag-list というデータ構造 CINEMA (Conformity-aware INfluEnce MAximization) 部分グラフに分割する←a novel approach ??? 何が問題なの？ ぶっちゃけよく分からん とにかく普通のIC・LTモデルはダメでconfo...
  • 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-...
  • 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 ...
  • Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and ...
    Towards Scaling Fully Personalized PageRank Algorithms, Lower Bounds, and Experiments Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós Internet Mathematics 2005 概要 fully personalizationが良いです ランダムウォーク手法を考案 分解定理を使って少し精度改善 実験もしました 関連研究 Topic-sensitive PageRank [Haveliwala 02] tトピックの線形結合のみ、O(tV)空間 Hub Decomposition [Jeh-Widom 03...
  • Evaluating Multi-Way Joins over Discounted Hitting Time
    Evaluating Multi-Way Joins over Discounted Hitting Time Wangda Zhang, Reynold Cheng, Ben Kao ICDE 2014 概要 random walkに基づくスコアのでかいtop-k n-tupleを返す問題の提案 それに対する色々な枝刈りを詰めまくった手法を提案 実験的に相当早くなった top-k n-way joins 定義 入力 グラフ G=(V_G, E_G) クエリグラフ Q=(V_Q, E_Q) V_Q=(R_1, …, R_n) R_i⊆V_G 単調集計関数 f R^|E_Q|→R maxとかminとか+とか重み付けとか… k ...
  • 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で高速化 実験 ...
  • 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...
  • 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つに被...
  • 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...
  • 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とセットする...
  • 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...
  • 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...
  • 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に関する保証 問題定式化 ...
  • 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} $$ ...
  • Learning with Local and Global Consistency
    Learning with Local and Global Consistency Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, Bernhard Schölkopf NIPS 2003 概要 半教師あり学習 滑らかにしたい 仮定 局所的：近くの点は同じラベルを持つ 大域的：同じ構造中の点同士は同じラベルを持ちやすい k-NNとかは前者だけで後者はあまり反映出来ていない ただのSVMでも微妙 提案アルゴリズム 自分のラベルを周りに伝播する感じ x1,…xlがラベル有り（y1,…,yl）、x{l+1},…,xnがラベル無し n×c行列F $$ y_i = ...
  • 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...
  • Maximizing the Extent of Spread in a Dynamic Network
    Maximizing the Extent of Spread in a Dynamic Network Habiba, Tanya Y. Berger-Wolf ? 2007 概要 動的ネットワークでinfluence maximizationやるお！ 問題定義 Dynamic Network G_t = (V_t, E_t)の列 特定の時点のものだから，辺は消えたりする Independent Cascade Modelの拡張 uが時刻tでactiveだったら(u_t, v_t)なv_tを伝播確率でactivate 成功したらvは時刻t+1でactiveになる 一旦activeになったらずっとactive 他の時刻で辺があったらまた試行できる ...
  • 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 ...
  • On Influential Node Discovery in Dynamic Social Networks
    On Influential Node Discovery in Dynamic Social Networks Charu Aggarwal, Shuyang Lin, Philip S. Yu SDM 2012 概要 SN上のやりとりは瞬間的 その確率は瞬間を表す時間の関数 globally optimized forward trace approach locally optimized backward approach 動的モデル 頂点・辺はある時間帯に存在するみたいな感じ f_ij(δt) = a(1-exp(-λ_ij*δt)) δtの時間だけ辺ijが出現する時の伝播確率 (t1, t2)の間に辺(i, j)があるとする (t1, t2)をm分割してδt_iとす...
  • Reducing Social Network Dimensions Using Matrix Factorization Methods
    Reducing Social Network Dimensions Using Matrix Factorization Methods Václav Snášel, Zdenek Horák, Jana Kocıbová, Ajith Abraham ASONAM 2009 概要だけ グラフを小さくしたい concept lattice(概念束)なるものがあるらしい Formal concept analysis(形式概念分析)と特異値分解 ASONAM 概念束 特異値分解 2014-09-21 01 47 31 (Sun)
  • 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の行列積のようなもの？ 以降の反復...
  • 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ベースの貪欲アルゴリズム ちょっと遅い 評価関数をサンプリングで近似 グラフサイズの線形時間で...
  • An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting ...
    An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree Jochen Koenemann, Sina Sadeghian, Laura Sanità In FOCS 2013 ノード重みはキテるんですよ！！ Prize collecting node-weighted steiner tree w V→R+ p V→R+ min w(V(T)) + P(V-V(T)) s.t. Tはtree 左はスパンしている、右はしていない LMP Lagrangian multiplier preserving w(V(T))+αp(V-V(T))≦αw(V(...
  • 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...
  • 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上のランダムウォークでやる ...
  • 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の長さ 数十 ~ 数百 ...
  • From Machu_Picchu to rafting the urubamba river: Anticipating information ...
    From Machu_Picchu to "rafting the urubamba river" Anticipating information needs via the Entity-Query Graph Ilaria Bordino, Gianmarco De Francisci Morales, Ingmar Weber, Francesco Bonchi WSDM 2013 概要 今見ているwebページの内容から非自明かつ偶察力を有する少数かつ多様な検索クエリを提示 手法 ページ内容をWikipediaエンティティで表現 エンティティとクエリからなるグラフ上でPersonalized PageRank PageRankスコアの高いクエリを出力 実験 提...
  • 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...
  • 2.5K-Graphs: from Sampling to Generation
    2.5K-Graphs from Sampling to Generation Minas Gjoka, Maciej Kurant, Athina Markopoulou INFOCOM 2013 概要 2.5K-graph 次数kの頂点と次数lの頂点を結ぶ辺の個数の分布と、次数kの頂点のクラスタ係数の平均値を分布に着目 ソーシャルネットワークから↑を高速に見積もり、そういう分布になるグラフも生成する ↑以外の分布も結構一致する！ 問題 JDD(k,l) = 次数kの頂点と次数lの頂点を結ぶ辺の数 JDD = Joint Degree Distribution 2頂点の部分グラフの次数依存の分布 ‾c(k) = 次数kの頂点のクラスタ係数の平均値 dk...
  • @wiki全体から「Nonnegative Spectral Clustering with Discriminative Regularization」で調べる

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