問題 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） 訪れたノード集合をハイパーエッジにする アクティブノードの総数がある程度大き…