Zadrozny and Elkan, “Transforming classifier scores into multiclass probability estimates”, SIGKDD‘02 (http://www.research.ibm.com/people/z/zadrozny/kdd2002-Transf.pdf) を読んだ。なぜ読んだかというと、Scikit-learnのSGDClassifierに関するド…

社内で使用されている高速省メモリなビット集合の実装であるRoaringBitmap (https://github.com/RoaringBitmap/RoaringBitmap)の解説 (https://arxiv.org/pdf/1402.6407.pdf)を読んだ。以下では32bit整数の集合を管理することを前提に話を進める。この実装の…

今年の10月10日から12月12日にかけてKaggleで開催されたAllstate Claims Severityというコンペに参加した． www.kaggle.com 各保険請求に関する特徴量として114個のカテゴリ変数と16個の連続変数が与えられるので，それを元に保険請求の金額を予測する．訓練…

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs Ethan R. Elenberg, K. Shanmugam, M. Borokhovich, Alexandros G. Dimakis (The University of Texas, Austin, TX, USA) 概要 3-vertex subgraphの数え上げをsparsif…

Network Lasso: Clustering and Optimization in Large Graphs David Hallac, Jure Leskovec, Stephen Boyd (Stanford University) 概要 凸最適化はデータ分析において非常に重要な役割を担っているが汎用の凸最適化ソルバは大規模な問題に対してスケールせ…

Localization and centrality in networks (Phys. Rev. E. '14) T. Martin, Z. Xiao, M.E. J. Newman 概要 Eigenvector centralityは頂点の重要度を表す有名な指標であるが,高い次数の頂点とその隣接頂点のみ値が大きくなってしまい（localization）それ以外…

Maintaining the duality of closeness and betweenness centrality (Social Networks'15) U. Brandes, S. Borgatti, L.C. Freeman 概要 媒介中心性は各ノードが持つ他のノードへの影響力を表しており,近接中心性は他のノードへのアクセスの効率または他のノ…

グラフアルゴリズムっぽいやつらだけ。それにしても最近論文読めてない... A Divide‐and‐Conquer Algorithm for Betweenness Centrality Dora Erdos*, Boston University; Vatche Ishakian, IBM ; Evimaria Terzi, Boston University; Azer Bestavros Cheeta…

内容把握したら色をつける GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks Hui Li (Xidian University); Sourav S Bhowmick (Nanyang Technological University); Jiangtao Cui (Xidian University); …

(Paper ID: 40) Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages Riondato, E. Upfal. Brown University アブストを読んでみたがタイトル内容以上のことを理解できなかった. 知識のなさを感じる・・・ (Paper ID: 53) Pant…

いくつかの論文のアブストだけ読んだ。 Provably Fast Inference of Latent Features from Networks Charalampos Tsourakakis. 概要 ソーシャルネットワーク上において、各エージェントは自分と似た性質を持つエージェントと関係を持つ傾向があることが知ら…

Efficient Densest Subgraph Computation in Evolving Graphs (WWW '15) Alessandro Epasto, Silvio Lattanzi and Mauro Sozio. 概要 Densest subgraphを動的なグラフで効率良く計算する。densest subgraphと動的なグラフという流行りと流行りを合わせた感じ…

Replacing the Irreplaceable : Fast Algorithms for Team Member Recommendation (WWW '15) Liangyue Li, Hanghang Tong, Nan Cao, Kate Ehrlich, Yu-Ru Lin and Norbou Buchler. 概要 チームメンバが諸事情により欠けてしまい新しいメンバをチームに加える…

Scalable Methods for Adaptively Seeding a Social Network (WWW '15) Thibaut Horel and Yaron Singer. 概要 Influence maximizationの亜種について考える。多くの応用において情報を拡散させるためのシードとして選べる人（core set）は限られており、cor…

Compressed indexes for string searching in labeled graphs (WWW '15) Paolo Ferragina, Francesco Piccinno and Rossano Venturini. 概要 ラベル付きグラフの索引を作り、それに対して検索するというのはソーシャルネットワークや知識グラフを効率良く処…

Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily Ashton (WWW '15) Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec and Mitul Tiwari. 概要 ウェブサービスにおいてユーザが周りの人達をそのサービス…

Path Sampling : A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts (WWW '15) Jha, Madhav Seshadhri, C. Pinar, Ali 概要 名前の通りパスをランダムサンプリングして４頂点の連結部分グラフの個数を近似計算するという論文。３頂点の連…

The K-clique Densest Subgraph Problem (WWW '15) Tsourakakis, Charalampos E 概要 多くの応用ではクリークに似た大きな部分グラフを見つけたい。適当に定式化するとMaximum-Clique問題との関係でNP-hardになってしまい近似計算すら難しくなってしまう。一…

Density-friendly graph decomposition (WWW '15) Nikolaj Tatti and Aristides Gionis. 概要 k-core分解はグラフの階層的構造を見る上で基本的な操作として知られているが、 k-core分解で得られた部分グラフの内部が密になっているとは限らない。 この論文…

Spanning edge centrality: large-scale computation and applications (WWW '15) Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis and Evimaria Terzi. 概要 Spanning edge centralityは各辺を含んでいる全域木の割合がどのくらいである…

毎回混乱する。 true positive, false positive, true negative, false negative についてを見た。 prefixがtrueになっているのが正しい結果が得られているやつ。false positiveは本来正解と言ってはいけないにも関わらず判別器が正解と言ってしまったやつ。

Graph structure in the web (Comput. Netw. 2000) Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener 概要 ウェブグラフ（Webページとリンク関係からなる有向グラフ）の構…

Heuristics for Speeding Up Betweenness Centrality Computation (PASSAT/SocialCom '12) R. Puzis, P. Zilberman, Y. Elovici, S. Dolev, U. Brandes 概要 媒介中心性の計算を高速に行うための２つのヒューリスティクスを提案している。著者にBrandesがい…

Betweenness Centrality - Incremental and Faster (MFCS '14) M. Nasre, M. Pontecorvi, V. Ramachandran 概要 厳密な媒介中心性の動的更新に関する論文。理論系の会議で媒介中心性珍しい。辺のコスト減少・頂点に接続する任意の辺のコスト減少により生じる…

A Faster Algorithm to Update Betweenness Centrality after Node Alteration (WAW '13) 概要 既存の厳密な動的手法 [Lee+ WWW'12], [Green+ SocialCom/PASSAT'13]は頂点の削除には対応していないので、頂点の挿入・削除が行われた時の動的更新を効率良く行…

機械学習のコンペティションサイトKaggle(https://www.kaggle.com/)においてsentiment analysisをしてみた。参加登録をしたコンペは"When bag of words meets bags of popcorn"(https://www.kaggle.com/c/word2vec-nlp-tutorial)で、元々はword2vecのチュー…

CF #260 (Div. 1) E. Function http://codeforces.com/contest/455/problem/EのEditorial(http://codeforces.com/blog/entry/13336)を読み今更理解したことを書く。 Convex Hull Trickでは\(N\)本の直線のある\(x\)座標における最小値(または最大値)を\(\log…

Codeforces Round #235 (Div. 2) E. Olympic Games 問題 ５つの整数\(n, m, l, r, p\)が与えられる。 以下の条件を満たす\( (x_1, y_1), (x_2, y_2) \)の組の個数を\(p\)で割った余りを求めよ. \( 0 \le x_1, x_2, \le m \) \( 0 \le y_1, y_2, \le n \) \( …