2006-05-08

近況

このごろあまりぼそぼそとしたことを書いてなかった. 今日はぼそぼそと書く.

Social Network Analysis という本を読み始めた. 大物. 先は長い. 何かウェブっぽいものを読みたいと思っていた. まず候補に上がったのは自然言語処理とデータマイニング. ただ私は確立統計が(も)とても苦手なので, この手のを読むならそっちの復習が先だろうと思いパスした. しばらくウェブを徘徊していたら, 本棚.orgkazama の本棚 というページを発見. これが並んでいた. なんとなくウェブっぽいし, グラフ理論が中心らしいので読んでみることにした. いちおうアルゴリズムの研究室にいたので, グラフ理論ならなんとかなるだろう.

数学が苦手な私は, 計算そのものに面白みを感じることは少い. この本は社会科学系の本なだけあって, 計算機科学より下心がはっきりしている. 本文も動機を示すのに重点がおかれている. 序盤だからというのもあるとは思うけど.

social network は actor(node)の集合 と tie(edge)の集合 の対である. ここまでは認識していた. グラフの定義そのままだ. でもこれには続きがあって, actor の集合や tie の集合が複数ある場合もある, と定義を広げる.

たとえば 企業(actor1)の集合とNPO(actor2)の集合, 寄付(tie) は企業とNPOの間にしかない. こういう場合は actor の集合が二つある. グラフの発想だと, node の集合はひとつで 個々の node の種類が違うと考えるのが普通だろう. でも言われてみれば node の集合が二つあると考えてもいい. たしかに.

同様に tie の集合も一つとは限らない. たとえば人間関係. 人(actor)の集合があるとして, その上にはたとえば 好きという関係(tie1)や嫌いという関係(tie2)がある. グラフだと edge に種類があるケースは少なかった気がする. social network では割と普通のことらしい. まあそうだよね.

グラフの表現方法として "図"(丸と線), "行列", "代数" の三つを挙げている. 代数表現はおまけっぽいので 図と行列 がメイン.

図の利点は見た目がわかりやすいことと, actor に属性を付加しやすいこと. かわりに tie の属性は表現しにくいし, 複数の tie があると区別が面倒. 点線の書き方を変えるくらいしかない.

行列の利点は, tie の属性を保持しやすいこと. 行列の個々の要素が属性になる. また, 複数種の tie も扱いやすい. N 人の間の 好き/嫌い 関係なら, NxNx2 の高次行列で表現できる. なるほどね. また企業と NPO のように actor の集合が二種類のケースなら NxM の行列になる. 現実には actor の集合は二種類くらいを扱うのがせいぜいらしいので, これは都合がいいらしい. 行列表現の弱点は頂点の属性を保持しづらいこと. まあ行列だけだとそうかもね. プログラマからすると actor の配列を併用すれば済む話なのでピンとこない欠点だが, 定式化の際は不便なのかもしれない.

こんな風に, 主記憶のような計算機寄りの見方以外にも グラフ表現の評価方法には色々ある. 言われてみればそうだ. 気にしたこともない話で面白かった. diad, triad, affiliate など, social な分析をする上で意味のある 特別なグラフも紹介されている. 逆にグラフに出てきて social network (の導入部)では出てこないものがある. 面. social network はまったく平面グラフではないから, 面には意味がない. メッシュを作るときにいつもどう持つかで悩んでいた面がここにはない. グラフにも色々あるものだなあ.

学生のころ, 何度かグラフのアルゴリズムを実装した. そのときも先のような表現の違い, つまり図に近い方法 (Node クラスとそのオブジェクト間の参照) を使うか 行列を使うかでいつも悩んだ. ただトレードオフのポイントはもっぱら 主記憶の容量と速度で, 粗なグラフは行列だと損, 密だと逆. そういう感覚. 私は Node クラスを使う方がオブジェクトっぽくて好きだった. 本当は趣味で選ぶより問題で選ぶ方が正しい気はする. 逆にインターフェイスを揃えて実装を複数用意してみたこともあった. Graph インターフェイスを実装する MatrixGraph と LinkedGraph みたいなかんじ. この方法は楽しくはあったけれど実用性はいまいちだった. グラフくらいなら問題毎に実装する方が都合が良い. 慣れるとすぐ書ける. そのあとに書くコードの複雑さからすれば手間は誤差の範囲という気がする. 実際には, 世の中には汎用のグラフ実装がけっこうある. どのくらい使われているのだろう.

それにしても 100 ページくらい読んだのにさっぱり本題に入らない. まずグラフ理論の概要をやって, 行列の話をして ... 道程は遠い.