todo314 @ ウィキ
todo314 @ ウィキ

Similarity Component Analysis

todo314 @ ウィキ内検索 / 「Similarity Component Analysis」で検索した結果

検索 :
  • Similarity Component Analysis
    Similarity Component Analysis metric learning 類似とは？？？ ケンタウロス、馬、人間 やばくね？ 不等式制約が無い 「局所特徴量」…上半身、下半身、みたいなの どこを比べればいいか？みたいな話？ アイデア 局所特徴量を作って、確率を計算。積和演算してスコアを計算 積モデルコンセプトってのが良いらしい は？どうやんの？ 難しいお(´・ω・`) NIPS 2014-01-24 14 17 52 (Fri)
  • 気になった論文
    ...ast Top-k Similarity Search on Large Networks 基準も新しい類似頂点対検索、random path sampling COSNET Connecting Heterogeneous Social Networks with Local and Global Consistency 複数のグラフに渡って、一貫性のあるマッチング的なのが欲しいの新しい問題を提案したよ Edge-Weighted Personalized PageRank Breaking A Decade-Old Performance Barrier Adaptive Message Update for Fast Affinity Propagation Yasuhiro Fujiwara、Affinity...
  • 論文一覧
    ... Scalable Similarity Estimation in Social Networks Closeness, Node Labels, ... Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation International Conference on Computational Social Networks CSoNet 2015 Real-time Topic-aware Influence Maximization Using Preprocessing Social Influence Spectrum with Guarantees Computing More in Less Time SNA-K...
  • 4chan and /b/: An Analysis of Anonymity and Ephemerality in a Large Online ...
    4chan and /b/ An Analysis of Anonymity and Ephemerality in 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 ...
  • 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...
  • Visual Analysis of Dynamic Networks using Change Centrality
    Visual Analysis of Dynamic Networks using Change Centrality Paolo Federico, Jürgen Pfeffer, Wolfgang Aigner, Silvia Miksch, Lukas Zenk ASONAM 2012 動的グラフに対する新しい中心性 $$ \frac{|N_{t_1}(i) \triangle N_{t_2}(i) |}{|N_{t_1}(i) \cup N_{t_2}(i)|} $$ N_t(i) 時刻tでのiからの距離が丁度1の頂点集合 分子は時刻t1からt2にかけて，追加/削除した辺の数 分母は時刻t1からt2にかけて，追加/削除/生存した辺の数 距離が1でなくてnの場合の一般ケース $$ r_{t_1,t_...
  • The matching polytope has exponential extension complexity
    The matching polytope has exponential extension complexity Thomas Rothvoss STOC 2014 概要 extension complexityって何？ LPで問題を表現した時の不等式の数 matching polytope マッチングを表現する超多面体 結果 matching polytopeをLPで表現するには「指数個の制約」が必要 マッチングはPなのに？！ ↑ここが驚くべきこと 今まで NP-hardな問題だけだった Extention Complexity TSP polytopeは対称な多項式個の制約式では表現できない LPで簡単には表現できない ...
  • Link Evolution: Analysis and Algorithms
    Link Evolution Analysis and Algorithms Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, D. Sivakumar Internet Mathematics 2010 概要 PageRankの動的更新手法 アイデアは追加・削除された辺の近傍のみを真面目に再計算する 提案手法 aggregation/disaggregation method 観察 辺ijが追加されたら，iとjの近傍についてのみPageRankスコアが変化する S(t)←時刻tで追加・削除された辺の近傍集合 G ←V\S(t)を1つの頂点に縮約したグラフ 辺の遷移確率は注意深く設定する G のP...
  • A General Framework of Hybrid Graph Sampling for Complex Network Analysis
    A General Framework of Hybrid Graph Sampling for Complex Network Analysis Xin Xu, Chul-Ho Lee, Do Young Eun INFOCOM 2014 概要 グラフをサンプリングしたい どっちかっていうとΣf(v)を近似したい ランダムウォークとかランダムジャンプとかある ランダムジャンプはたまに失敗する ↑を統合したのを考えて解析 分散（小さいと良）がランダムジャンプ確率に対して凸 既存手法 ランダムウォーク Simple Random Walk (SRW) with Re-weighting Metropolis-Hastings Random Walk ...
  • Analyzing Spammer's Social Networks for Fun and Profit
    ... Semantic Similarity scoreとかいうのを使う seedを選んでそこからどうにかするらしい 何かイイらしい まとめ こういう現象解析は面白いね Twitterの中の人がいなくてもそこそこ大きいデータでできるんね 悪垢検出みたいなのは難しそう あんまり分からんのでスコアの定式化が良いのかどうか分からない WWW ecosystem spammer 2014-01-14 18 19 01 (Tue)
  • Efficiently Computing k-Edge Connected Components via Graph Decomposition
    Efficiently Computing k-Edge Connected Components via Graph Decomposition Lijun Chang, Jeffrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, Weifa Liang In SIGMOD 2013 メモ K.Oka 問題 k枝連結成分 少なくともk本消さないと非連結にならない 大きさk-1のカットがない 極大k枝連結成分 共通部分を持たない 分解できる 応用 social networkで似た頂点 可視化 既存手法 最小全域カットしまくる O(n^2(m+n log n)) ...
  • Link Analysis, Eigenvectors and Stability
    Link Analysis, Eigenvectors and Stability Andrew Y. Ng, Alice X. Zheng, Michael I. Jordan IJCAI 2001 概要だけ HITSとPageRankは摂動に対してどれくらい安定なの？ とりあえずランダムな摂動で実験 HISTはかなり変わるがPageRankは安定 解析しました HITS 固有ギャップが大事 PageRank 変更した頂点のPageRankの総和／αくらい 感想 結構大事な論文だった PageRankのバウンドはかなり緩そう、これじゃ実際の安定さは説明できないような気がする HITS IJCAI PageRank 2016/12/28
  • メニュー
    メニュー トップページ 論文一覧 気になった論文 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...
  • Dynamic Social Influence Analysis through Time-dependent Factor Graphs
    Dynamic Social Influence Analysis through Time-dependent Factor Graphs Chi Wang, Jie Tang, Jimeng Sun, Jiawei Han ASONAM 2011 概要 Pairwise Factor Graph (PFG) model Dynamic Factor Graph (DFG) model 問題設定 各時刻で重み付き辺が有ったり無かったり Pairwise influence μ_ij Dynamic social influence μ^t_ij G =(V,E,Ω)が欲しい Ωは時刻毎のμ_ij これって問題って言うのか？？？ ...
  • 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を...
  • 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 概要 ベストペーパー ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい めっちゃ色々な問題に対して考えたよ 動機付け ソーシャルネットワーク上のプライバシー（の例） ユーザが友達をプライベートに設定 そのユーザ-友達間の辺はそのユーザにしか見えない ユーザがプライベートグループを作る クリークがグループ外からは見えない 証拠 ...
  • 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 $...
  • Predicting Directed Links using Nondiagonal Matrix Decompositions
    Predicting Directed Links using Nondiagonal Matrix Decompositions Jerome Kunegis, Jorg Fliege ICDM 2012 A=UXU^T に分解(Decomposition into Directed Components) U 直交行列 X 対角行列でなくてよい 何か読んでも分からなかった… リンク予測系をその内まとめて読もう ICDM link prediction 2014-02-09 20 39 27 (Sun)
  • 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 analysis of information diffusion focusing on directed networks
    Influence analysis of information diffusion focusing on directed networks 有向ネットワークの構造が情報拡散に与える影響の分析 Shohei Usui, Fujio Toriumi, Takatsugu Hirayama, Kenji Mase JSAI 2014 概要だけ 有向グラフで色々なパラメータを変化させるとどうなるか？ パラメータ例 相互リンクの割合 到達可能な頂点数の総和 出次数と入次数の相関係数 次数のベキ指数 実験結果 AID Σ_v σ(v)/n 出次数と入次数の相関が高いとAIDが高い 解釈 情報発信能力と情報収集能力が共に高い頂点が多いと情報拡散能力の高いグラフ...
  • More is Simpler: Effectively and Efficiently Assessing Node Pair ...
    More is Simpler Effectively 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つ...
  • Streaming Algorithms for k-core Decomposition
    Streaming Algorithms for k-core Decomposition Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, Ümit V. Çatalyürek VLBD 2013 概要 k-core decompositionあるよねー 実際は、辺が挿入されたり削除されたりするから、そういう走査サポートしたいよねー 作りました 実験しました 毎回batchするより断然良い k-core decomposition K(v) vが属せるk-coreのうち最大のk 基本的に、周りに1があって、中に2があって、その内側に3があって…ってなる アルゴリ...
  • 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 関...
  • 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)
  • 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...
  • Influence Diffusion Dynamics and Influence Maximization in Social Networks ...
    Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang WSDM 2013 概要 voter modelを拡張 元はunsigned network signed networkにした 味方とは同じ意見（色） 敵とは違う意見（色） 最初の色の分布を与えた時の挙動を解析（面白い） このモデルでinfluence maximization ある意味で簡単 確率的振舞を計算するのが超大変 Voter ...
  • One-shot learning by inverting a compositional causal process
    One-shot learning by inverting a compositional causal process 書きかけが消えた・・・ 人間にできて機械にできないこと 1個だけから似てるのを見つけたり生成できる そういうのをモデリング いっぱいのデータからprimitiveなストロークとか、ストローク数とか、色々出す 動画をとっておく ターゲットとシンボルの集合について、 後者から推論されるストロークでターゲットを作れるか？みたいなのを推論する NIPS 2014-01-24 14 18 00 (Fri)
  • Influence Maximization in Continuous Time Diffusion Networks
    Influence Maximization in Continuous Time Diffusion Networks Manuel Gomez-Rodriguez, Bernhard Schölkopf ICML 2012 概要 Uncovering the Temporal Dynamics of Diffusion Networksの続き 連続時間モデル上の影響最大化を提案 影響拡散がシミュレーション以外の方法で効率的に求められる 1-1/e近似が可能 実験したよ 問題定式化 f(t_j | t_i; α_{i,j}) ∝ exp(-α_{i,j}(t_j-t_i)) つまり，遅延時間の分布が指数関数 他の関数でも使える 情報拡散過程は普通 ...
  • On Compressing Social Networks
    On Compressing Social Networks Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, Prabhakar Raghavan KDD 2009 概要 ウェブグラフの圧縮は既にある 平均3bits ソーシャルネットワークの場合は？ 問題を定式化、NP-hardだけど適当にヒューリスティクスで頑張る ウェブグラフの圧縮 [Boldi-Vigna. WWW 04] The WebGraph Framework I Compression Techniquesとか URL順の恩恵がある 類似性と局所性 ノード順...
  • Random Warping Series: A Random Features Method for Time-Series Embedding
    Random Warping Series A Random Features Method for Time-Series Embedding Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, Michael Witbrock AISTATS 2018 概要 課題：Gram行列の対角優位と自乗時間 random features approximationを採用 DTW距離 2つの時系列$$x_i, x_j$$に対する任意のalignment $$a$$を考える 対応する各要素対のdissimilarityの和の最小が距離 $$ S(x,y) = \min_{a} \sum_{1 \leq t \leq |a|} \tau(x[a_...
  • Structure-Preserving Sparsification of Social Networks
    ... Local Similarity (LS) 得点 = J(N(u), N(v)) 頂点uに接続する辺は$$ \lfloor d(u)^\alpha \rfloor $$本残す d(u)=2のときとかやばくね？ Simmelian Backbones (TS, QLS) よく分からんので省略 Edge Forest Fire (EFF) 森火事で訪問しやすい辺は大事 Local Degree (LD) 提案手法 各頂点uについて$$ \lfloor d(u)^\alpha \rfloor $$本、高次数頂点に繋がる辺から残す ハブに繋がる辺は残したいらしい 実験 Facebookのデータセットから100グラフについて平均を取る ...
  • 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)$$-...
  • 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)で求めている？ 何でこんなことをしたのか若干謎
  • 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を始点とす...
  • 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...
  • 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...
  • 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とす...
  • 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 ...
  • 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 ...
  • 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)の最小化もあるけれどそうではなくて、最大のサンプルを見つ...
  • 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の行列積のようなもの？ 以降の反復...
  • 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で高速化 定式化 ...
  • Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
    Influence Maximization Near-Optimal Time Complexity Meets Practical Efficiency Youze Tang, Xiaokui Xiao, Yanchen Shi SIGMOD 2014 概要 RIS (SODA 14)を実用的に改良するよ！ 提案手法 TIM, TIM+ サンプリング回数をいい感じにしました。 $$ O(\epsilon^{-2}(k+\ell)(n+m)\log n) $$時間 ヒューリスティックで更に効率改善→TIM+ triggeringモデルにも拡張したよ 提案手法 Two-phase Influence Maximization (TIM) フェーズ1：サンプリング回数θを...
  • 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...
  • 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...
  • A practical bounding algorithm for computing two-terminal reliability based ...
    A practical bounding algorithm for computing two-terminal reliability based on decomposition technique Yi-feng Niu, Fang-Ming Shao Computers and Mathematics with Applications 2011 概要 2端子信頼性計算のアルゴリズム 実験なし （某イベントで知った） 提案手法 C 事象の集合 事象=各辺の状態 A1(C) Cでの状態が生の辺集合 A2(C) Cでの状態が死の辺集合 A1(C)がs-t経路を構成→必ず到達可能 A2(C)がs-tカットを構成→必ず到達不可能 良く分から...
  • Selecting Information Diffusion Models over Social Networks for Behavioral ...
    Selecting Information Diffusion Models over Social Networks for Behavioral Analysis Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda ECML PKDD 2010 概要？ こっちではAsIC,AsLTモデルと言っているが， Learning Continuous-Time Information Diffusion Model for Social Behavioral ...とほぼ同じっぽいぞ…？ ECMLPKDD 情報拡散 情報拡散モデル 2014-09-14 04 08 53 (Sun)
  • 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して木っぽくパスを広げる（同じ頂点がいくつかある...
  • Learning Continuous-Time Information Diffusion Model for Social Behavioral ...
    Learning Continuous-Time Information Diffusion Model for Social Behavioral Data Analysis Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda ACML 2009 概要 Continuous-Time Independent Cascade Model r_uv 時間遅延パラメータ κ_uv 伝播確率 時刻tでuがactiveになったら， vを時刻t+δに確率κ_uvでactiveにする δはr_uvからきまる指数分布 学習したいパラメータ パラメータはrとκ カスケードの観測データD_Mは各頂点がactiveになっ...
  • 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する 予備知識みたいな...
  • @wiki全体から「Similarity Component Analysis」で調べる

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