読者です 読者をやめる 読者になる 読者になる

無向ネットワークのリンクの結合度

ノート 手慰み

ネットワークサイエンスについて勉強している。

ノード間のリンクの結合の強さを表す尺度を思いついた。既に発見されているかもしれないが記録しておく。*1

仮説1: リンクに重みが予め付加されていない場合でも、ネットワークの構造からリンクの結合度を表すことができる。

重み付きネットワークであれば、どのリンクが重要かという問について悩む必要はない。大きい重みが付けられているリンクが重要なリンクであろう。もちろん何をもって重要とするかによって、どのリンクが重要かは変わってくるだろうが、(変な言葉だが)重みによってウェイトがつけられるのは間違いないだろう。

一方、リンクに重みが明に付加されていないネットワークであっても、すべてのリンクが等しく重要であるということはないだろう。重要なリンクもあればそうでないリンクもある。非重み付きネットワークであっても、リンクの重要度、言い換えると結合の強さというのが存在するはずだ。そして、それはネットワークの構造から計算できるに違いない。

ネットワークサイエンスを学んでいると、クラスタリング係数 (Transivity) というものが登場します。実在するネットワークは一般に、一部のノードが密にリンクを張っていて、クラスタを作っています。家族だとか、サークルだとか、互いに見知り合った集団のことです。コミュニティともモジュールとも呼び方はいろいろあるかと思います。クラスタリング係数はクラスタリングが起こっている度合いを示す指標です。

仮説2: クラスタ内のリンクは結合度が高い。

結合度、結びつきの強さを考えます。厳密な定義はまだできないですが、リンクの重みと同じイメージです。結合が強いリンクがあるところにクラスタができるのか、クラスタがあったらリンクが強くなるのかはわかりませんが、感覚的にクラスタ内の結合は強いと思われます。

クラスタを作るようなリンクは結合度が高いとすると、次の仮説が得られます。

仮説3: 共通のノードに接続している2つのノード間のリンクは結合度が高い。

共通の知り合いが多い二人組は強い関係にあるということです。例えば夫婦とかです。

f:id:fjkz:20161202215436p:plain

図の上と下のノードは4つの共通のノードにリンクしています。点線のリンクは強いリンクであると考えられます。

このような考え方で、リンクの結合度を表す値が定義できるのではないだろうか。そうすると、重みなしネットワークから、重みつきネットワークを生成できる。何かしら新しいものが見えてきそうだ。

だが、上のコンセプトの元でも、結合度の定義は幾通りも考えれる。単に共通のノードの数としてもいいし、次数を用いて [0, 1] の区間の値を持つように規格化してもいい。どのような定義が適切かはデータを元に決めるしかない。

仮説4: よいノードの結合度の定義は2つのノードが結合している確率と強い相関をもつ

結合度の強いリンクというのは生じやすくて、切れづらいと考えれる。任意の2つのノード間にリンクが貼られている確率が高い条件というものがあったとき、その条件下で結合している2つのノードは結合度が強いと言えるのではないだろうか。

例えば、上の図でいうと、2つのノードが共通にリンクを張っているノードの数と、その2つのノード間にリンクがある確率に強い相関があるとすれば、2つのノードが共通にリンクしているノードの数が2つのノード間の結合度を示していると言えるでしょう。

ただ、この考えでいくと、結合度はリンクがないノード間にも定義できなければならなくなる。統計値を得やすいという利点はあるが、そのように定義された結合度が適切なのかはよくわからない。

副作用として、確率的にそこにリンクがあって然るべきなのに、リンクがないという状況があれば、リコメンデーションに利用できるだろう。Facebook のもしかして友達?という通知はそういう戦略なのかもしられない。

以上、ただの思いつきです。気が向けば上記の方針で適切な結合度を探すことをしてみる。クラスの依存関係のグラフは有向グラフだからちょっと取り扱いにくい……。無向グラフで、ベンチマークがしやすいような適当なサンプルデータはないのだろうか?


追記 2016-12-03

Ahn, Bagrow, Hehmann の link-clustering algorithm のアイデアに似ている。こちらは2つのリンクの類似度というのを求めている。

Link communities reveal multiscale complexity in networks : Nature : Nature Research

*1:もし既存の研究を見つけたら後から追記します。似ているが、異なるものはありました。

クラスの依存関係グラフ 4

手慰み 計算機 ノート

Java および Scala のクラスの依存関係のグラフについて調べている。

今回はクラスタリング係数を見てみる。

クラスタリング係数とは、あるノードにリンクしたノード群が互いにリンクしている割合を表します。C で表します。ノードごとに値を持ち [0, 1] の範囲を取ります。あるノードで C=0 であれば、そのノードにリンクしているノード同士は互いにリンクしていなく、C=1 であれば、そのノードにリンクしているノード同士はすべてリンクしています。

f:id:fjkz:20161127005456p:plain

現実のグラフは全体としては非常に疎であるが、知り合いが共通しているような部分的に密となるようなクラスタを作っていることが知られています。Twitter とかで、○○クラスタに属している人と言いますが、あのクラスタです。このとき、クラスタリング係数は値を持つことになります。

Apache Spark が依存する 214 個の JAR パッケージに含まれるクラスの依存関係のグラフを対象とします。

クラスタリング係数の分布は以下の

平均値は C = 0.53 C = 0.46 でした。クラスの依存関係グラフはクラスタリング性を持っていると言えるでしょう。*1

次数とクラスタリング係数の関係の散布図を描いてみました。

入力次数とクラスタリング係数の関係です。k_in は入力次数です。

f:id:fjkz:20161127030859p:plain

出力次数とクラスタリング係数の関係です。k_out は出力次数です。

f:id:fjkz:20161127030905p:plain

入力次数の方はっきりと、k^-1 に比例するように分布しています。出力次数の方もそういう傾向が見えないこともないですが、あまり出力次数とクラスタリング係数に強い関係はなさそうです。

この結果の何が興味深いのかというと、ネットワークの模型のひとつである Hierarchical Network モデルでは C(k) ∝ k^-1 の関係が成り立ちということが知られています(Hierarchical Network モデルについてはいつかまとめる)。ソフトウェアモジュールの成り立ちを考えると、ソフトウェアモジュールの依存関係は Hierarchical Network モデルでうまく説明できそうだと予想できます。入力次数とクラスタリング係数の関係が Hierarchical Network モデルと一致しているという事実は、この仮説を支えていると言えるでしょう。

*1:graph_tool で計算したが、なんか結果が胡散臭い。別の小さな系について、gephi で計算したものと、graph_tool で計算したもので違う値となった。傾向は同じなので、議論には差し支えないと思う。gephi だと遅すぎて今回のようなエッヂが100万を超えるようなのものの計算ができない……どうしたものか。速くて、Python で使えて、安定しているツールはないのだろうか。

→ igraph で計算しなおした。C = 0.46 は igraph の値。igraph も nan になる結果が混じってたり、ちょっと怪しいけれど

クラスの依存関係グラフ 3

手慰み Java 計算機

Java および Scala のクラスの依存関係のグラフについて調べている。

驚くべきことに(まあ予想はしていたけれども)、クラス間の依存関係のグラフはスケールフリーネットワークの性質を持つことが明らかになりました。スケールフリーネットワークでは、ノードの次数がべき乗則に従います。

勉強しながら調べているので、次数の非常に大きいクラス、例えば java.lang.Object クラスの存在がべき乗則で現れうるクラスなのかべき乗則でも説明できないほど例外的に次数の大きいクラスか、よくわからないと前回・前々回に素人っぽい言及をしました。

プロットの仕方を工夫すると、次数が大きいところも綺麗に図がかけることがわかったので、今回は次数が大きいところでもべき乗則が成立しているかどうかを検証します。

f:id:fjkz:20161112185046p:plain

上は前回載せた図で、次数の分布を示しています。これは、Bin の幅が 1 のヒストグラムです。次数が大きいところはサンプルが少ないのでガタガタになっていてべき乗則なのかどうかよく分からなくなっています。

そこで、Bin の幅を 1 に固定せずに、対数プロットしたときに Bin の幅が同じにやるようなヒストグラムを書きます。つまり、1 つめの Bin は次数が 1 のノードの割合、2 つめの Bin は次数が 2 か 3 のノードの値、3 つめは 4, 5, 6, 7 のいずれか、N つめは log2(N-1) から log2(N)-1 となります。

上のような Log-Bin で書いたヒストグラムが下の図です。

f:id:fjkz:20161123191256p:plain

次数が高いところは前の図ではが省きました、Log-Bin で描くと次数が高いところまでグラフに含められるようになりました。

入力次数は、次数が大きいところまで、きれいなべき分布になっていることが分かります。次数が 10^5 といった非常に大きな値を持つノードは、java.lang.Object クラスなのですが、この存在もべき乗則に従うことが分かりました。

出力次数は、次数が小さいところはよくわからない分布をしていますが、次数が大きいとべき乗則っぽい分布になっています。

積分布を描いても、次数の高いところが上手く表現できます。

下の2つの図は、次数 k に対して、次数が k を超えるノードの割合を示しています。上の図が入力次数、下の図が出力次数です。*1

f:id:fjkz:20161123192131p:plain f:id:fjkz:20161123192136p:plain

Log-Bin だとプロットの数が減るのでデータが丸められてしまっている不安がありますが、累積分布ではプロットの数は減りません。

さて、入力次数の方に関しては、きれいなべき乗則になっています。グラフの傾きは -1 です。累積分布の場合は傾きは べき指数 + 1 になります。累積なのに、k が小さいところの P が 1 になっていませんが、それは k = 0 のノードがいるからです。また、ヒストグラムを描いたときには気付かなかったが、次数が 10 以下のところで傾きが少し緩くなっています。べき乗則に従うと言われるデータは一般的にこうなっています。次数が大きいところはちょっとガタガタっとなっていますが、k = 10^4 に何か意味があるとは思えないので、ノイズでしょう。

出力次数の方が、k = 30 から k = 200 まではべき乗則に従っています。k が小さいところは謎の分布なのは、Log-Bin の図の方が分かりやすいです。

出力次数の次数が大きいところは、ガタガタしてわかりづらいが、グラフの傾きが急になっているようにも見えます。ソフトウェアを作る視点で考えると、出力次数は、ソースコードを書く人間が決めることで、あまりに依存先が多いクラスというのは作らないものなので、上限値があることが予想されます。べき乗則に従うということはサンプル数を増やせば、想像を絶する巨大なクラスが現れるということを意味していますが、おそらくありえないでしょう。10^3 のオーダーが上限なのではないかと推測されます。このことに関しては、ソフトウェア特有の現象なので、もう少し調べる価値がありそうです。

今はべき指数は目分量で見ているので、次回は定量的にべき指数を計算してみようと思う。

参考

Network Science

Network Science

*1:積分布の図は matplotlib で描きました。他の図は gnuplot で描いています。gnuplot が慣れているので、なんとなく guplot を使っていましたが、 matplotlib の方が使いやすいですね。

アニメーションと機械学習

所感 a.k.a. poem 映画 計算機

TV 番組で ドワンゴ の人が アニメーション監督の宮崎駿氏に機械学習のデモを見せて「生命への冒涜だ」と怒られたことが話題になりました。

インターネットの記事を見ると、「川上(ドワンゴの代表)め、ざまあみろ」といった意見が目立ちますが、私は宮崎氏の言っていることには同意できないと思いました。とは言っても、TV に放映された映像からは川上氏がどれぐらい機械学習について説明したのかも、宮崎氏がどれぐらい理解してドワンゴがやっていることを否定したのかも、分からないので、どっちが正しいとかはあまり語れないです。ただ、宮崎氏のような強い自負を持った人に対して、何かプレゼンするのは、やっぱり大変だと認識しました。

まあ、宮崎氏のような世界で最も生命の動きというものに対して敏感な人に、あんな失敗作の動画を見せたらアカンだろ――とは思いましたが。

失敗作とは、ドワンゴの人が言っているわけではなくて、私の推測です。人型の物体に、各種の力学的条件を与えて、進行する動きを学習させたら、きっと生命らしい動きを覚えるだろう、たとえば歩行を覚えるだとかを期待して実験をしてみたら、痛覚だとか重要な条件がないために、生命らしからぬ「気持ち悪い」動きを覚えてしまった――といったところだと想像します。必ずしも失敗とは言えないが、まだ研究の途中のものなのでしょう。

しかし、研究がある程度完成して、生命らしい動きを機械が覚えられるようになれば、生命らしい動きを生むための条件が分かります。それは生命を生命たらしめているものは何かを知るということです。ドワンゴの人がそんなことを考えて、機械学習の研究をしているのかは知りませんが、生命とはなんぞやということは、多くの人が考えてきた問題でこれに対してひとつの答えを出すということは、私は意味のあることだと思います。

動き、つまり力学の観点から、生命について論じた例というのはありません。単に無知なだけかも知らないが、力学から生命を論じた例を私は知りません。化学反応の連鎖として生命を見る分子生物学は成果を上げています。また、生態系、つまりマクロ的に生命を見ることもされています。心理学だとか動物行動学だとかで行動から見ることもされている。しかし、生命の動きというのはよく分かっていません。生きているものとそうでないもので動き方が異なるということもよく分かっていません。私は生物と非生物では明らかに違うと思っているが、証拠はない。ボストンダイナミクス社のロボットは生き物の動きをしていないし、トトロは生き物の動きをしている。この差異がどこから来るのかは分からないのです。

アニメーターが偉大だと思うのは、生き物らしい動きというのを想像して描くことができることです。祟り神だとか猫バスはいない。にも関わらす、存在しないものの動きを実在感を持って描くというのは、天才にしかできないことです。

ドワンゴ機械学習の技術が完成したら、天才にしかできない芸当が機械でもできるようになるかもしれません。存在しない生物であっても、力学的条件を与えれば、自ら「リアル」な動きを覚えて、動き始める。そういうことができるようになれば、アニメの表現というのが変わるかもしれない。ドワンゴの人はこういうことがしたいのかな?

機械学習はまだアニメーションには全く使えないが、古典的な力学の演算は既に広く使われています。CG アニメの怪獣の毛の動きだとか、飛び散る水しぶきの動きだとかは、もう人間が描くよりも計算機に計算させた方が「リアル」な動きをします。

しかし、私が面白いと思うのは、力学的な「リアル」な動きとアニメ的な「リアル」な動きは違うことです。仮にトトロが実在したとして、あんな動きができるかというと力学的に無理です。だが、力学的に正しい動きをしているトトロなんてまったく実在感のないものになるに違いありません。力学的にはリアルでないからこそ、アニメ的にはリアルなのです。「板野サーカス」と呼ばれるミサイル群がうねうね動く表現方法についても、あんな動きをするミサイルなんて現実には作ろうとしても作れないが、アニメ内ではあの動きの方がリアリティがあります。*1人間フィルターを通したときに、正しく思える動きというのは、現実とはずれているのでしょう。

人工知能がそこまで考慮できるようになったら、人工知能と人間は本当に区別できなくなるかもしれない。まあ無理かな?

*1:余談だが、板野サーカスは高速に動く物体に対して、カメラが寄ったり離れたりするのですが、カメラの方が高速に動く物体よりもずっと速く動くことに気づいてから、気持ち悪く思えてきました。

クラスの依存関係グラフ 2

手慰み 計算機 Java

前回: クラスの依存関係グラフ - 超ウィザード級ハッカーのたのしみ

クラスの依存関係のグラフについて調べています。

今回は前回よりも大きな系について調べました。

対象は、Spark 2.0.1 です。前回は、Hadoop 由来のクラスだけ調べたが、今回は Spark のクラスだでなく、Spark が呼び出している外部ライブラリ内のクラスも含めた、クラス群の依存関係のグラフについて調べます。Spark 2.0.1 の Hadoop 2.7 用ビルドに含まれている JAR をすべて調べます。*1

グラフの大きさは、頂点の数が 113434、辺の数が 1456523 となっています。可視化した結果が下の図です。Modularity を強調しています。色は可視化ツール(gephi)が計算した Modularity Class で、辺の色は元の頂点の Modularity Class を示しています。

f:id:fjkz:20161112210202p:plain

次数の分布は以下の図のようになっていました。

f:id:fjkz:20161112185046p:plain

入力次数に関しては、綺麗なべき乗則に従っています。クラスの依存関係は、一般的にべき指数 2 のスケールフリーネットワークとなっていると予想できます。このようになっている理由は、ネットワーク理論の枠組みで説明できそうです。

ただ、グラフに収まらないほど、次数が大きいところにも JavaScala の標準ライブラリのクラスがあります。java.lang.Object クラスなんかは、100957 の次数を持ちます。そいつらの存在がべき乗則に従わない例外的なのか、それともべき乗則であっても確率的現れうるのかは、今後検証する必要があります。

出力次数に関しては、前回とは見た目が異なります。すべての依存関係について調べると今回の結果になるようです。よく知られた確率分布の形ではなく、この形状の意味は物理法則では説明できない感じがします。

依存するクラスの数が 8 個の場合が最も多くなっています。この値は感覚と一致しています。

また、非常に多くのクラスに依存するようなクラスも少ないながら、存在します。べき乗則っぽい見た目をしています。入力次数の場合よりべき指数は大きいです。出力次数はクラスを書いた人が決めることですが、あまり出力次数を大きくはしたくないものなので、出力次数が大きいクラスが稀になることは妥当でしょう。サンプルをさらに大きくしたら、出力次数が大きいクラスの数はべき乗則を下回ってくるのではないかと予想されます。1000個のクラスに依存したクラスなんて巨大すぎて作れないです。

Modularity という値は 0.571 という値でした。この値の詳細はよくわからないのですが、可視化の結果からも推測できるように、Modularity が高いようです。

このサンプルで得られる情報はもっとありそうなので、もうちょっと分析してみたい。

*1:Spark は Hadoop の JAR も含んでいるので、前回と重複した要素もある。

クラスの依存関係グラフ

計算機 手慰み Java

Java のクラスの依存関係を調べてみた。

規模が大きいアプリケーションの方が統計が取りやすいので、Apache Hadoop の 3.0.0-alpha バージョンを対象に調べる。テストとアノテーションを除いた、Hadoop 由良のパッケージに含まれるクラスに依存関係のグラフについて調査する。

クラス間の依存関係を調べるのに、JDK8 に含まれる jdeps というコマンドを使った。jdeps に -verbose オプションをつけると 各 jar 内のクラスが依存しているクラスが出力される。-dotoutput オプションで DOT ファイルに結果を保存することができる。下のようなファイルが出力される。

digraph "hadoop-mapreduce-client-common-3.0.0-alpha1.jar" {
    // Path: ./mapreduce/hadoop-mapreduce-client-common-3.0.0-alpha1.jar
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.io.IOException";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.Object";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.String";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.net.InetSocketAddress";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience$Private (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.conf.Configuration (hadoop-common-3.0.0-alpha1.jar)";

依存先のクラス名の後ろに( ) 内にパッケージ名が付く。(not found)はパッケージが見つからないという意味です。これがあると→の元と先が同じクラスでも別の名前になってしまうので、sed で取り除く。

今回は、対象の JAR 内のクラスの関係のみを調べたい。そこで、辺が示す先がorg.apache.hadoop以外から始まるパッケージに含まれるクラスとなっている辺は除いた。また、org.apache.hadoop.classification パッケージのクラスも、今回の対象のJAR内のクラスではないので、それらが先にある辺も除いた。

JAR ごとに DOT ファイルが生成されるが、全部をまとめてひとつのグラフとして調べる。

頂点が 7844, 辺が 36076 のサイズの有向グラフとなっている。

graph-tool だと描写が非力だったので、gephi で可視化をする。

f:id:fjkz:20161111223015p:plain

上の画像はグラフを可視化したものである。大きくて色の濃い丸が、in/out を問わない次数の大きい頂点である。辺の色は頂点の色に基づく。少ない頂点のみが次数が大きく、ほとんどの頂点は次数が小さいことが可視化の結果から予想できる。

そこで、次数と、その次数のクラスの数の関係を調べてみる。

f:id:fjkz:20161111203145p:plain

上の図は、次数とその次数を持つクラスの割合を示している。入力次数・出力次数いずれの場合も、次数が10以上100以下のクラスはべき乗則に従っているように見える。どうやらクラスの依存関係のグラフはスケールフリーネットワークの性質を持つ可能性があるようだ。べき係数は 2 程度で、スケールフリーネットワークでは典型的な値となっている。Barabási–Albert モデルのネットワークの成長過程は、ソフトウェアが拡大していく過程と似ていることから、クラスの関係がスケールフリーネットワークとなっていることが説明できるだろう。*1

次数が大きいクラスというのは、ソフトウェアの中で重要なクラスであると考えられる。べき乗則に従うということは、特定のクラスの重要度が飛び抜けて高いということを意味している。

入力次数が大きいクラスは多くのクラスから呼び出される Fan-in なクラスである。何度も再利用されている非常に有用な部品と言える。多くのクラスから利用されていることから、欠陥も少ないと考えられる。一方で、利用者が多いクラスの動きを変える場合は影響範囲が非常に大きくなるので、なかなか変更できあに。そのため、安定度が高いクラスであると言える。

出力次数が大きいクラスは多くのクラスを呼び出している。Fan-out なクラスである。GoFデザインパターンでいうところの Facade となっていて、そのクラスから呼び出される機能が多いということを意味していると思われる。変更の影響を受けやすく、そのため欠陥密度も高いだろう。このクラスを重点的にテストすると効果が高そうだ。

入力次数の大きいところで、べき乗則に従わない特異的に大きい次数を持ったクラスが存在していて、図の右からはみ出してしまっている。具体的には、org.apache.hadoop.conf.Configuration という設定プロパティの値を得るためのクラスが 1368 の入力次数を持っている。このクラスは、非常に多くのクラスから横断的に使用されるクラスである。このようなクラスの存在が、今回調べたソフトウェアに特有のものなのか一般的に存在しうるのかは、他のソフトウェアも調査しないと分からない。もし異常に入力次数が多いクラスが存在するということが一般的であるとしたら、ソフトウェアにスケールフリーネットワークとは異なる特別なネットワーク構造があると言えるかもしれない。

*1:Barabási–Albert モデルのべき係数は 3 で完全な説明はできない。いつかちゃんとまとめたい。

graph-tool で遊ぶ1

計算機 手慰み Python

複雑な世界のありようを理解するのに、「グラフ」の可視化だとか分析はすごく有用なのではと考え始めたので、グラフについて勉強してみる。

動くおもちゃがないと楽しくないので、いいのかどうか知らないが、検索して出てきた graph-tool というツールで可視化等をしてみる。

graph-tool.skewed.de

インストールは 「Download - graph-tool: Efficent network analysis with python」 に従えばできた。

みんな大好きな Barabási-Albert モデルのネットワークの絵を書いてみる。

import graph_tool.all as gt

# ノード数 1000 の Barabási-Albert モデルのネットワークを作る
g = gt.price_network(1000, directed=False)

# グラフを描写するときのいい感じのノードの配置を計算する。
# どうも斥力と引力が働く粒子の運動を計算して、釣り合いがとれるような場所を計算しているっぽい。
# 試行毎に違う配置になる。
p = gt.sfdp_layout(g)

# グラフを PNG 画像として出力する。
gt.graph_draw(g, pos=p, output="barabasi-albert.png")

f:id:fjkz:20161108195044p:plain

美しい……。