基本アイディア X の分布があまり大きくないので，ほとんどの場合 X≒Y，のようなことを証明 どのようなときにそうなるのか？ Chebyshev's Inequality 分散，標準偏差 $\sigma$ $Pr[|X - E[X]| \geq \lambda \sigma] \leq \lambda^{-2}$ これを使うことを，se…

手法 Alteration 期待値を使って計算量や解の大きさなどをバウンドする 基本アイディア：期待値が T → T 以上（以下）のものが存在 ランダムに解生成 → ちゃんとした解になるように修正，というののバウンドを考える 例: maximum independent set 確率 p で…

OSN を，巨大な疎なグラフでなく，小さな密グラフの集合として着目． 友人，グループ，イベント 3 点部分グラフの出現頻度 ランダムグラフと比較 → 三角形が多いなぁ モデル だいたいランダムだけど，三角形を作りやすくする Extremal Bounds 色々な不等式を…

テレポーテーションを改良して，ranking, clustering を良くする クラス node: 頂点に飛ぶ link: 辺に飛ぶ unrecorded: ジャンプして来たのはカウントしない recorded: ジャンプして来たのもカウントする 定常分布 unrecorded だとなんか綺麗になる benchmar…

古典的に研究されてきた，オフラインでのソーシャルネットワークと OSN， 違いはあるのか？ 昔から言われてきた仮説を検証することはできるか？ 仮説 Dunber's number: 友達は 150 人まで Dunbar's circles: 親密さで層があって，3人-15人-45人-150人（3 に…

atomic (C++11) C++11 には atomic に atomic_compare_exchange_weak, atomic_compare_exchange_strong がある． http://en.cppreference.com/w/cpp/atomic/atomic_compare_exchange http://d.hatena.ne.jp/yohhoy/20120725/p1 でも，計算クラスタ等の gcc …

Price of Anarchy (POA) 輸送の効率の指標 POA = C_UE / C_SO = 1.25 C_UE: 全員が自己中に動くときのコスト (nash均衡) C_SO: 協調して中央値を最小化したときのコスト Braess's paradox 不思議現象 辺を削除したほうが効率が上がる 辺を追加したほうが効率…

モチベーション Evolving Graph Sequence (EGS) large, numerous, gradually evolving 今の解析は static ばっかりだけど dynamic もやろう 最短路，（近接）中心性 ある一点，とかでなく，「どう変化したか」という種類のクエリのみ 手法 グラフ間の類似度…

bounded treewidth -> monadic second order logic (MSO) は線形時間で判定可 first order logic: 変数について quantifier がつけられる ちょうど k （定数）個存在する，という quantifier も OK らしい． monadic second order logic: 頂点集合 (≒boolean…

モチベーション ミルグラムの実験 どういう構造であればこのように数ホップで辿りつけるのか どういう原理に基づきそのようなネットワークが生じるのか 既存研究 Kleinberg small-world model (Nature'00) 二点間の距離に依存したショートカットの生成確率 $…

目には見えないネットワーク，現象の結果は目に見える 目に見える情報からネットワークを推定可能か？ カスケードの拡散モデルの定義 枝：伝搬確率，伝搬時間の分布 有向木，ただ１つの親 カスケードに対するグラフの尤度を定義 確率 グラフの尤度の効率的な…