誤情報が拡散してしまった！ ソレを訂正する情報を流し，できるだけ多くの人に訂正情報を先に見せる モデル：Multi-campaign ICM 誤情報 C の拡散，訂正情報 L の拡散，早くついたほうが信じられる 状況：Eventual influence limitation problem (EIL) r タ…

hidden distance を取りれたモデル 手法概要 頂点間の hidden distance hidden distance に基づいたスケールフリーなネットワーク（power law, cluster coefficient) hidden distance に関する greedy search ネットワーク生成 hidden distance が小さいと結…

例 Erdos-Renyi グラフ G The Four Functions Theorem N: {1..n}, P(N): all subsets 4 つの関数があって，集合2つについてホゲ（∩, ∪）が満たされれば，冪集合２つに対してピヨ． 冪集合だけじゃなく，分配速を満たす束にも拡張可 Corollary: 分配速を満た…

The Local Lemma イベントの dependency digraph 条件ホゲを満たせば，全部の事象が起こらない，という減少がある確率ピヨ以上で起こる 証明：帰納法．独立な場合と従属な場合を分けて計算するだけ． Symmetric Case 各イベント（発生確率 p 以下）が d 個ま…

5/4 朝 人に何か言われて iwi.tc に繋がらなくなっていることを知る．サーバは正常． DNS が解決できなくなっており，メールも届かない． ~% nslookup iwi.tc Server: 192.168.1.1 Address: 192.168.1.1#53 server can’t find iwi.tc: SERVFAIL 少しググった…

ストーリー ツイート → 固有名詞抽出 → リンク → 密グラフ抽出 → 今何が起きているかわかる!! 定式化 Graph 重みの付け方：他の論文 density avgweight, sqrtdens, avgdegree density が T 以上でサイズが N_max 以下の全ての部分グラフを列挙する アルゴリ…

この論文で扱う時間スケール ネットワークの変化の時間スケールと，dynamic process の時間スケールが同じ 感染症など 観察1：PRL 共著ネットワーク 時間，期間で違うグラフ time-aggregated network スナップショットの和 activity potential 論文生産性 分…

自分は今まで ACM スタイル (sig-alternate.cls) で subfig をずっと使ってきていたが，適当に subfig を使っていたせいで，キャプションが太字じゃなくなっていた．（キャプションは普通太字にならないものだと思っていたが，実は太字が普通で，subfig を入…

基本アイディア 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) 二点間の距離に依存したショートカットの生成確率 $…

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

null 57.22% Central Time (US & Canada) 5.32% Eastern Time (US & Canada) 4.72% Pacific Time (US & Canada) 3.56% Brasilia 3.29% ...

コンフィグモデル モデル 任意の次数分布を決める． 頂点の次数を最初に生成（スポーク）し，等確率で接続する． 生成原理を説明する気は無い 平均場近似，次数列を保ったまま繋ぎ変えることにより実データの性質を検証 性質 直径 $L$ $2 $\gamma = 3$ → $L …

http://iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2F%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E2%80%95%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89%E5%BF%9C%E7%94%A8%E3%81%BE%E3%81%A7%2F04.%20%E5%8F%A4%E5%85%B8%E7%9A%84…

WS モデル 小さい $L$ と大きい $C$ を同時に達成するネットワーク モデル 拡張サイクル（左右定数個につなぐ）を作る 割合 $p$ の枝を選び，片方の端点をランダムに接続（つなぎかえ，ショートカット） $C(p)$：簡単に計算できる $L(p)$：大変 空間について…

http://iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2F%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E2%80%95%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89%E5%BF%9C%E7%94%A8%E3%81%BE%E3%81%A7%2F06.%20%E6%88%90%E9%95%B7%E3%81%99…

http://sea2013.dis.uniroma1.it/accepted.php少しでも気になる論文 Sharon Bruckner, Bastian Kayser and Tim Conrad. Finding Modules in Networks with Non-modular Regions Daniel Delling, Andrew Goldberg and Renato Werneck. Hub Label Compression …

http://qiita.com/items/fdec3466c4dea5818b3a

時系列データで，なにらかの変化が起こったとされる点を探す．最も基礎とされるアルゴリズムは以下． 平均値を計算して，各点から平均値を引く（垂直に移動） 累積和を計算して，絶対値が最大になる点でぶった切る これを再帰的に好きなだけやる もっと進ん…

Qiita に書いてみましたhttp://qiita.com/items/4c7635d4c84bc785e47a

純粋に間引いて表示 every X という風に書けば X 行ごとに表示してくれる #!/bin/sh gnuplot -persistent <

行ってきた．フカシギの数え方を目当てに行って，CS っぽいのはフカシギの数え方だけかなぁと思っていたのだけれど，他にも自分の興味のツボにハマる物が何個もあって素晴らしく楽しかった． フカシギの数え方 The Art of 10^64 -Understanding Vastness- ht…