問題：匿名化 手法 random edge pertubation 一定確率 μ で辺の有無を入れ替える (perturbation probability) 特徴量の推定 特徴量は，変化してしまうが，推定ができる（最尤推定する） density, degree distribution, transitivity, modularity 独立でラン…

問題 ネットワーク上で拡散が起こる 一部の頂点のみを観測して，発信源を推定する モデル 最初は発信源だけが情報を持っている 隣接する頂点に情報を伝えるのにかかる時間は正規分布 一部の頂点はオブザーバで観測した時刻が分かる 推定アルゴリズム 最尤推…

田部井さんのスライドを見ればだいたい分かる http://www.slideshare.net/tbyasu/nips2013-scalable-kernels-for-graphs-with-continuous-attributes 問題 グラフ同士のカーネル しかもグラフの頂点には連続値ベクトルの属性がついている 辺には重み（長さ）…

http://iwiwi.m12.coreserver.jp/iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2FGraph%20Theory%2F11.%20Random%20Graphs The notion of a random graph Erdos-Renyi model $G(n, p)$ $q = 1 - p$ とおく 独立集合 $ P[\alpha(G) \geq k] \leq {n \choose k}q…

バラバシのグループ 論文事の非引用回数の時系列変化を予測する研究 引用ネットワークの入次数の変化 （論文の価値 ＝ 引用数） モデル BA に類似 論文本来の魅力×優先的選択×魅力の時間的減衰 結果 凄い！全部の論文をスケールしたら全部同じ累積分布に！

概要 グラフを考慮した進化シミュレーションで「第三者罰」が進化するかを検討 背景 罰を導入することで協力を促す 今回の罰：特別な形態の「第三者罰」というもの 普通のやつは損を被った人が直接非協力者を罰する 今回は，直接の被害者でない人が罰する 先…

MkECS の応用だ!!!! 概要 頂点に適当な ID を割り当てるだけの匿名化は不十分である （タイトルはロミオとジュリエットのセリフで名前をIDに置き換えている） 攻撃 b 頂点を特定したい active attack: 匿名化前にグラフを操作して，匿名化後，特定頂点のラベ…

問題 reachability を保って anonymize k-degree anonymous：各 v が k-1 頂点以上は同じ次数の頂点を持つ これは k 匿名性というやつの自然な拡張になっていて，匿名性をコレで定義するのは既存 辿りつける頂点ペアの集合をできるだけ本来に近づける アルゴ…

題材 個人の行動と集団の振る舞いを繋ぐす類モデル cascading behavior (噂・情報の伝搬) cascading behaviorの数理モデル threshold models global cascade が起こるか起こらないかの条件の解析 [Watts 02] epidemic models SRI, SIS, ... Stifler Model：周…

Siffocoemt conditions 頂点数３以上，すべての頂点の次数が n/2 位上ならハミルトニアン 頂点数３以上，α(G)≦κ(G) ならハミルトニアン α：最大独立集合，κ：連結性 頂点数３以上連結，任意の induced path uvw で d(u)+d(w)≧|N(u)∪N(v)∪N(w)| ならハミルト…

概要：SimRank を改良した SimRank* を提案 復習 SimRank 「似ているノードからリンクされているノードは似ている」 SimRank (別の書き方) ←対角成分が間違ってる 不満：同じ長さのパスが存在しないと影響が来ない！ 提案手法：g-SimRank*, e-SimRank* 実験 …

Quasilinear-time Algorithm ハイパーグラフの構築 各ノード「に」伝搬するノード集合を計算する（転置グラフを用いる） シードを１つランダムに選び逆向きシミュレート(BFS） 訪れたノード集合をハイパーエッジにする アクティブノードの総数がある程度大き…