2011-12-09
LaTeXを学びながら簡単に書けるサイト
神。sumと分数と添え字くらいは自分で書けるようになった。
Online LaTeX Equation Editor
Online LaTeX Equation Editor - create, integrate and download
「ネットワーク分析の道具箱」＜クラスタリング編その2＞
- Girvan-Newmanアルゴリズム
【重要】
Newmanコミュニティーの指標Q値は、コミュニティー（ノードの属性＝ラベリング）ごとの同種結合or異種結合を基礎として構成されている。
↓
コミュニティーが一緒であれば、同種結合もセルフループも同じ
↓
コミュニティーの結合＝ノードの結合 の擬制が可能！
分割しかり！
- 媒介中心性
σ[s,t]：ノードペア(s,t)間の最短経路の数
σ[s,t](u)：そのうちuを通るものの数
→適当にノードペアを取ったときに最短経路上にいる確率みたいなもの。（ただし寄与度で補正する（最短経路が複数の時はそれに応じて薄める））
従って、
「ネットワーク科学の道具箱」＜クラスタリング編その1＞
- 選択交配（assorting mix）：生物同種間で選択交配が行われることから。ノード属性がカテゴライズされていると仮定する。
- 考える事例：エッジ＝性的関係、ノード属性カテゴリ：黒人、白人、ヒスパニック（所与） つまり何系と何系がつきあっているか。
- クラスタリング的視点：黒人同士が密、他人種とは疎みたいなこと
以下、選択交配＝つながっているのが同種か異種か をデータの根本として評価関数を構成していくよ！
以下無向グラフっぽく書いてるけど有向グラフにも簡単に拡張可能。
- 【全数】属性iと属性jでつながっているとこはいくつあるかな？（黒人×白人ペアは何個あるかな？）
n[i,j]：属性iを持つノードと属性jを持つノードの間のリンクの総和
リンクの総和の総和＝リンクの全数＝Mとして、属性ペア(i,j)を持つようなリンクの割合e[i,j]は
のようになる。
- 白人で結婚している人はどのくらい？
eに対して、i,jそれぞれの視点で集計すると（つまり有向グラフでindegreeとoutdegreeを考えると）a[i]とb[j]が取れる。
評価関数完成間近
- どのくらい同種でくっつきやすいんだろう？
assortativity coefficient（同種交配の強さ）aは
と表現される。
分子の第一項
は同属性を持つ端点を結ぶリンクの割合。
分子の第二項
はランダムネットワークにおいて期待される量。
∵一方がiである確率a[i]、他方がjである確率b[j]であり、aとbの選択は帰無仮説の下で独立。
→分子はランダムネットワークの時ゼロ
→ランダムネットワークでa=0 〜同種っぽさなし（ネットワークのあり方は属性によらない）〜が表現できる！
分母
→分子第一項が1になる（完全な正の選択交配＝同種で全部くっつく）時にaが1になるように規格化する項
これをクラスタリングの指標として応用する。
- Q値
さっきの分子部分（規格化する部分は最大化問題だからいらない）をクラスタリングの文脈（属性を解析者が試行錯誤しながら与えるということ）で、Q値と呼ぶ。
- Q値
「集合知プログラミング」
買った。
- 作者: Toby Segaran,當山仁健,鴨澤眞夫
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/07/25
- メディア: 大型本
- 購入: 79人 クリック: 1,951回
- この商品を含むブログ (260件) を見る