WWW '15 アブスト読み

論文読み アブストのみ

いくつかの論文のアブストだけ読んだ。

Provably Fast Inference of Latent Features from Networks

Charalampos Tsourakakis.

概要

ソーシャルネットワーク上において、各エージェントは自分と似た性質を持つエージェントと関係を持つ傾向があることが知られており、結果としてコミュニティが出現する。また、複数のコミュニティに属するエージェントというのも存在する。

無向グラフGが与えられて、ある確率的生成モデルを仮定したときに各頂点の特徴を推測したい。 この論文では二つの頂点が多くの特徴を共有するほど高い確率で辺がはられる確率的生成モデルと、高速に混合するマルコフ連鎖を用いて頂点の特徴を推定する手法を提案する。

実データに対する実験によって機械学習に基づく手法より2,400倍高速に質の良い推定を行うことができることを示した。

Network A/B Testing: From Sampling to Estimation

Huan Gui, Ya Xu, Anmol Bhasin and Jiawei Han.

概要

A/Bテストは新しいサービスに対するユーザの反応を測る手法として知られている。 A/Bテストを行うときには、ユーザ同士がソーシャルネットワークで相互に関係している場合でも、ユーザ同士が互いに影響を与えないものとしてユーザをサンプルするが多い。しかし実際にはそうではないということを示し、ユーザ同士の干渉がある場合でも精度をおとさずに推測を行う方法を提案した。

Querying Web-Scale Information Networks Through Bounding Matching Scores

Jiahui Jin, Samamon Khemmarat, Lixin Gao and Junzhou Luo.

概要

Web-scale informationネットワークへのクエリはsubgraph matchingとして見ることができるが、現実のデータは不完全であり多くのノイズを含んでいる。この論文では与えられたクエリに対して前処理なしで、Top-Kの答えを出力する手法を提案する。グラフ同士の類似度を定義し、分散処理でも動かせる枝刈り手法を用いて高速化する。

Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment

Anshumali Shrivastava and Ping Li.

概要

Minwise hashingは集合同士の演算を近似的に行うための乱択データ構造であるが元々の対称なMinwise hashingには集合を小さめに見積もってしまうというバイアスが存在する。本論文ではそのバイアスを克服するための非対称なMinwise hashingを提案する。