todo314 @ ウィキ

todo314 @ ウィキ内検索 / 「Reciprocity in Social Networks with Capacity Constraints」で検索した結果

• Reciprocity in Social Networks with Capacity Constraints
  Reciprocity in Social Networks with Capacity Constraints Bo Jiang, Zhi-Li Zhang, Don Towsley KDD 2015 概要 相互性（双方向辺の割合）が知りたい 双方向辺数最大化問題 NP-hard 3-pathを調整するヒューリスティクス 上限とか考える 実験的考察 実際のネットワークのいくつかは上限に凄く近い ヒューリスティクスが意外と良い 動機付け スウェーデンのWikipedia 相互性 21% …これは大きいか？ ランダムグラフ 0% …よく分からん （次数制限の下の）上限 28% …21%は凄そう 逆に 90% …...
• 論文一覧
  ...works Reciprocity in Social Networks with Capacity Constraints Online Influence Maximization Locally Densest Subgraph Discovery ✔Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming KDD 2016 ✔Robust Influence Maximization (He-Kempe) Robust Influence Maximization...
• Analyzing Spammer's Social Networks for Fun and Profit
  ...7 Reciprocity bi-directionalな辺の数/出辺の数 悪垢 95%が0.2以上 互いにフォロバするからだね 普通 55%が0.2以上 平均最短路長 普通 4.12 悪垢 2.60 でかい連結成分 じゃあ何でそうなるの？ Possible Factor 1 悪垢は何も考えずにフォローしまくる following quality あるアカウントをフォローしている人のフォロワー数 明確な差が出た Possible Factor 2 同じ組織に属する悪垢は、意図的に結合しあう ポストしたURLでクラスタリング それっぽい criminal hubとcriminal l...
• 気になった論文
  理論計算機科学 ACM Symposium on Theory of Computing STOC 2000 Circuit minimization problem A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Improved algorithms for submodular function minimization and submodular flow On dual minimum cost flow algorithms The small-world phenomenon an algorithm perspective A random graph model for mass...
• Diffusion Centrality in Social Networks
  Diffusion Centrality in Social Networks Chanhyun Kang, Cristian Molinaro, Sarit Kraus, Yuval Shavitt, V.S. Subrahmanian ASONAM 2012 概要（だけ） Degree, Betweenness, Stress, Closeness, Eigenvectorなどの中心性は何が伝わるかとかあんま考えていない そういうのを考慮した中心性 Diffusion Centrality 頂点・辺が述語（何が伝わるかみたいな）をもっている 色々性質があるので，何がどういう確率で伝わるかみたいなのをかなり細かく定義している 拡散過程の定義がもはや読んでない これで中心性を速く求める手法を作った...
• Theory of Cooperation in Complex Social Networks
  Theory of Cooperation in Complex Social Networks Bijan Ranjbar-Sahraei, Haitham Bou Ammar, Daan Bloembergen, Karl Tuyls, Gerhard Weiss AAAI 2014 概要だけ Continuous-Action Iterated Prisoner s Dilemma (CAIPD) Modelなるモデルがある ソーシャルネットワーク上の協調の進化のためのモデル これをめちゃ解析（理論＋実験） evolutionary networksとsocial networksとは違うらしい 主な貢献は3つ 状態が収束する その証明がcoevolutionary netw...
• On the Approximability of Influence in Social Networks
  On the Approximability of Influence in Social Networks Ning Chen SODA 2008 メモ程度に モデル 無向グラフG 閾値1≦t(v)≦deg(v) 近傍の内t(v)以上が活性化したら自分も活性化 Target Set Selection 問題 ある割合の頂点数を活性化するためのシードサイズを最小化したい ちょっと違うけどまあ 結果 $$ O(2^{\log^{1-\epsilon}n}) $$で近似できない（仮定のもと） Majority Thresholds 半分以上で活性化 Small Thresholds 小さい定数 Unan...
• 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)でアクティベーションが成功する これは一回だけ ...
• 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...
• 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 ...
• Dynamic social networks promote cooperation in experiments with humans
  Dynamic social networks promote cooperation in experiments with humans David G. Rand, Samuel Arbesman, Nicholas A. Christakis In PNAS 2011 メモ Y.Horita 社会的ネットワークの社会科学的研究 実証データをもとに理論・モデルを修正 協力 コストを払って他者に資源を与える行動 背景 実験でおかしかったところ 関係が静的だった ホントは誰と付き合うかは動的じゃね？ 動的ネットワークで実験 このpaper 実験 Amazon Mechanical Turksで囚人のジレン...
• Learning Influence Probabilities In Social Networks
  Learning Influence Probabilities In Social Networks Amit Goyal, Francesco Bonchi, Laks V.S. Lakshmanan WSDM 2010 概要 情報拡散の確率を学習したい 色々モデル提案 アクティブになる時刻も推定できるよ 問題定義 辺が作成されたタイムスタンプの考える (u, a, t_u)が一杯もらえる u ユーザー a 行動 t_u 時刻 (u,v)について，u,vの順に行動して，辺の作成時刻に矛盾が無ければ，uからvに伝搬した 各行動について，↑でありうる辺を取ってきた時の伝播グラフを考える 枠組み？ uの近傍のアクティブ...
• 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...
• Influence Maximization with Novelty Decay in Social Networks
  Influence Maximization with Novelty Decay in Social Networks Shanshan Feng, Xuefeng Chen, Gao Cong, Yifeng Zeng, Yeow Meng Chee, Yanping Xiang AAAI 2014 概要 目新しさの減衰を考慮した情報拡散モデル 非単調だし非劣モジュラ Novelty Decay 実データセットを調査 n人の友達が既に影響されているとする nが大きい程，その人自信は影響されやすいけれど，徐々にその効果が弱まるはず (nの時の確率 / n-1の時の確率)みたいなものを計算すると，f(n) = γ^{n-1}くらい これを根拠 IC Model wi...
• The Role of Social Networks in Information Diffusion
  The Role of Social Networks in Information Diffusion Eytan Bakshy, Itamar Rosenn, Cameron Marlow, Lada Adamic In WWW 2012 メモ Y.Yoshidaさん 新しい情報は「疎遠」な友人から not 親しい友人 仕事とか 思ったよりは多いねというくらい 親しい友人の方が多い なんで？ 強い 情報がすぐ拡散 公募はすぐ埋まる 得る情報 Feed 友人のURLをシェア 外界 メールとか Feedを遮断 |V|=253M Feed有：6...
• Word of Mouth: Rumor Dissemination in Social Networks
  Word of Mouth Rumor Dissemination in Social Networks Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer SIROCCO 2008 概要 Bharathi+WINE 07とかあるけど，先手に注目したらしい？ 先手がどうやっても負けるインスタンスがある Centroid problem 先手 後手が選ぶ頂点数が分かった上で最適なシード集合を選択する Medianoid problem 後手 先手が選んだ頂点数がわかった上で最適なシード集合を選択する CentroidもMedianoidもNP-hard ヒューリスティクスはあまりイカないらしい まとめ ...
• 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...
• 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とセットする...
• 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...
• 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...
• 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)
• メニュー
  メニュー トップページ 論文一覧 気になった論文 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...
• Threshold Models for Competitive Influence in Social Networks
  Threshold Models for Competitive Influence in Social Networks Allan Borodin, Yuval Filmus, Joel Oren WINE 2010 久しぶりの論文記事(ヽ´ω`) 概要 LTモデルを競合者付きモデルに拡張 劣モジュラどころか単調ですらないものもある Weight-Proportional Competitive Linear Threshold Model 頂点vはしきい値θ_vを持つ 活性近傍からの重みの和がθ_vになったら活性化 状態は3つ 非活性，活性A，活性B 活性Aの近傍の割合 活性Bの近傍の割合で確率的にAかBかに決まる S_B=∅なら元のLTモデルと同じ ...
• The Power of Random Neighbors in Social Networks
  The Power of Random Neighbors in Social Networks Silvio Lattanzi, Yaron Singer WSDM 2015 概要 友達は友達が多い (friendship paradox) power-lawが十分条件では無い どういうモデルがparadoxを説明できるのか？ というわけで，モデルを提案 辺を張り替える 影響最大化への適用例 友達の逆説 friendship paradox 友達は友達が多い （頂点の近傍次数） （その頂点の近傍の平均次数） power-lawが十分条件では無い 実際にそういう例を作れる 極端な例 正則グラフ ☆ ...
• Faster Random Walks By Rewiring Online Social Networks On-The-Fly
  Faster Random Walks By Rewiring Online Social Networks On-The-Fly Zhuojie Zhou, Nan Zhang, Zhiguo Gong, Gautam Das ICDE 2013 概要 ランダムウォークでサンプリングしたい！ Third party（全データが無いのでAPIとかでとってくる でも、変なところにはまりやすい（孤立したコミュニティっぽいところ 辺を消したり付け替えたりして、conductanceを大きくする ランダムウォークなので、今見てる頂点の近傍だけから操作を行う 定常状態に速く収束する！（mixing timeが小さい 貢献 グラフトポロジーを変化させ、サンプリングを効率的にする、という「問題...
• Learning Diffusion Probability based on Node Attributes in Social Networks
  Learning Diffusion Probability based on Node Attributes in Social Networks Kazumi Saito, Kouzou Ohara, Yuki Yamagishi, Masahiro Kimura, Hiroshi Motoda ISMIS 2011 概要 拡張した情報拡散モデル 時間遅延付き 頂点属性付き（新しい） パラメータ学習を提案 人口データで実験 上手くいった！ AsICモデル 実際の情報拡散は離散時間なワケがない p_uv 伝播確率 r_uv 遅延時間のパラメータ 遅延時間は指数分布 頂点属性 頂点vはJ個の属性を持つ，j番目はv...
• Maximizing the Long-term Integral Influence in Social Networks Under the ...
  Maximizing the Long-term Integral Influence in Social Networks Under the Voter Model Chuan Zhou, Peng Zhang, Wenyu Zang, Li Guo WWW 2014 companion ポスター 概要 Voter Modelにおける影響最大化 long-term integralを最大化したい 問題+提案手法 モデルはInfluence Diffusion Dynamics and Influence Maximization in Social Networks ... long-term integral influence maximization σ(S) = E[...
• 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という速いアルゴリズムを提案 実験して提案手法とベースラインを比較 モデル・問...
• 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...
• 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は明示的に与える と主張しているはず モデル ...
• 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 Note on Maximizing the Spread of Influence in Social Networks
  A Note on Maximizing the Spread of Influence in Social Networks Eyal Even-Dar, Asaf Shapira WINE 2007 概要 投票者モデルで考えてみたよ 投票者モデルと問題定義 f_t(v) = 0/1 時刻tでのvの意見 f_t+1(v)…vの近傍uを等確率で選びf_t(u)に更新 入力 各頂点のコストc_v 予算B 目標時刻t 出力 頂点集合S Σ_v∈S c_v ≦ B E[Σf_t(v)]を最大化 時刻0にSの頂点を1にする 定理とか ランダムウォークに関連がある 近傍1つ選んで採択するんだ...
• Scalable Methods for Adaptively Seeding a Social Network
  Scalable Methods for Adaptively Seeding a Social Network Thibaut Horel, Yaron Singer WWW 2015 概要 影響最大化の問題 … アクセスできる頂点には制限有 解決法 … 二段階アプローチ [Seeman-Singer. FOCS 13] 独立カスケード・線形閾値等で定数近似 独立カスケード・線形閾値等で定数近似 すごく遅い この論文 より簡単な拡散モデルで効率的近似手法 実験でスケーラビリティ 効果を検証 詳細は https //www.slideshare.net/secret/nIKkJnFLPQeMj WWW 影響最大化 情報拡散 2017/10/02
• Influence of the Dynamic Social Network Timeframe Type and Size on the Group ...
  Influence of the Dynamic Social Network Timeframe Type and Size on the Group Evolution Discovery Stanisław Saganowski, Piotr Bródka, Przemysław Kazienko ASONAM 2012 概要 GED (Group Evolution Discovery) 法のパラメータチューニングの解析 グループ発展 時間発展でコミュニティは変化していくが，それを下記に分類 Continuing(停滞) サイズに変化なし．頂点がちょっと変わるくらいならOK Shrinking サイズが小さくなる Growing サイズが大きくなる...
• 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する 予備知識みたいな...
• Super mediator - A new centrality measure of node importance for information ...
  Super mediator - A new centrality measure of node importance for information diffusion over social network Kazumi Saito, Masahiro Kimura, Kouzou Ohara, Hiroshi Motoda Information Sciences 2015 メモ Uncorrected Proof 概要 影響最大化の解は影響力が高いが，影響力が強い頂点はそれだけではない super mediator 消すとσが下がる 色々な中心性との違いを実験的に見る 定義 Data-driven super mediator ある頂点の拡散過程を沢...
• 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ノードを一様サンプリングす...
• 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}...
• Information Diffusion in Mobile Social Networks: The Speed Perspective
  Information Diffusion in Mobile Social Networks The Speed Perspective Zongqing Lu, Yonggang Wen, Guohong Cao INFOCOM 2014 概要 拡散（時間）最小化問題 できるだけ早く全体に伝わって欲しい k-center 問題になる 近似比 log*n，時間 O(n^5)くらいしかない コミュニティベースのアルゴリズムを考案 分散集合被覆アルゴリズム（謎 問題定義 辺には重みがあって確率が決まる そういうのから期待遅延時間が定義できる max_v |(S,v)|を最小化したい！！ |(S,v)|はSからvに伝わる最小期待伝播時間 ...
• 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以下って制約とか...
• 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)) ...
• 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 残った辺 カスケードの仕...
• Social Influence Spectrum with Guarantees: Computing More in Less Time
  Social Influence Spectrum with Guarantees Computing More in Less Time Dinh, Thang and Nguyen, Hung and Ghosh, Preetam and Mayo, Michael CSoNet 2015 概要 新しいアルゴリズムLISA $$k=1,\ldots,n$$について同時に解けるよ！ $$ O(\epsilon^{-2}\ln \frac{2}{\delta} (n+m)) $$時間だよ！ 提案手法 Linear-time Influence Spectrum Algorithm (LISA) 終了条件が重要 $$ \Upsilon_L = 1+4.6\epsilon^{-2}...
• 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...
• 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...
• 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...
• CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social ...
  CELF++ Optimizing the Greedy Algorithm for Influence Maximization in Social Networks Amit Goyal, Wei Lu, Laks V.S. Lakshmanan 何かよく見るな名前 WWW 2011 CELF++ CELFを速くしたよ！！！ 頂点uは→を持つ u.mg1, u.prev_best, u.mg2, u.flag mg1 Sに対するマージン prev_best u以前に見た中でbest mg2 S+prev_bestに対するマージン flag 最後にmg1が更新された時刻 どうやって早くなるの？ とりあえず、↑の値を全部計算済みだとする 最後に...
• 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_...
• 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はコスト高 ｰ すこしの頂点（アンカー）だけに設置 互いに距離が小さい所は通信 その距離が分からない場合...
• Piggybacking on Social Networks
  Piggybacking on Social Networks Aristides Gionis, Flavio Junqueira, Vincent Leroy, Marco Serafini, Ingmar Weber In VLDB 2013 岩田さん Piggybacking? おんぶ 概要 巨大なSNS クラスタ係数を利用してスループット向上 ↑最適化問題 アルゴリズム O(log n)近似 Hadoop用のヒューリスティクス スループット とりあえず1ユーザに1台のサーバ 実際は1台が複数ユーザ 定式化 Social Dissemination Problem 辺 ...
• @wiki全体から「Reciprocity in Social Networks with Capacity Constraints」で調べる

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