グラフを扱うJavaライブラリ「Jung」の紹介 - Twitterのグラフ構造を視覚化

java-ja 第12回のLTで話そうと思ったのですが、出番がなかったので資料をブログで公開しておきます。
Jungは研究などでグラフ構造が出たときに、理解しやすくするために可視化するのに使っています。他にもいくつかグラフを扱うライブラリは存在していますが、日本語の資料があったのと拡張可能なことが多かったのでJungを結果的に使うようになりました。
以下はそのJungについての簡単な解説です。

Jungとは

Jungの正式名称はJava Universal Network/Graph Frameworkで、ネットワーク(グラフ) 構造の分析や視覚化を行うためのJavaのOSSライブラリです。グラフ理論、データマイニング、ソーシャルネットワーク分析のアルゴリズムを数多く実装しています。
安定バージョンは1.7.6で最新は2.0betaで、BSDライセンスで使用できます。
http://jung.sourceforge.net/

グラフって何？

ここでいうグラフは棒グラフや折れ線グラフではありません。
数学の一分野のグラフ理論におけるグラフは点（ノード）と辺（エッジ）の集合で構成され、現実のある要素の関係性を点と辺に抽象化してその性質の分析をするのに使います。
データ構造・アルゴリズムなどに広く応用されています。
有名な例：

巡回セールスマン問題
4色定理

グラフの例

Jungで簡単なグラフを作成する

Jungを使ってグラフを生成する手順は以下のようになります。

//グラフの作成
Graph graph = new UndirectedSparseGraph();
Vertex[] vertices = new Vertex[5];
// ノード作成
for (int i = 0; i < vertices.length; i++) {
　　　　vertices[i] = graph.addVertex(new UndirectedSparseVertex());
}
// エッジ作成
for (int i = 0; i < vertices.length; i++) {
    for (int j = 0; j < vertices.length; j++) {
        graph.addEdge(new UndirectedSparseEdge(vertices[i], vertices[j]));
    }
}
//描画ための処理
Layout layout = new CircleLayout(graph);
Renderer renderer = new PluggableRenderer();
VisualizationViewer viewer = new VisualizationViewer(layout, renderer);

VisualizationViewerはJPanelを継承しているので、JFrameにaddすれば簡単にGUIで表示することができます。

実行結果

グラフの種類

Jungのグラフは大きく分けると、方向を持つ有向グラフと、方向を持たない無向グラフに分かれます。
それぞれで使うノードやエッジにクラスや適応可能なアルゴリズムが異なるので注意が必要です。

Jungで作ったグラフ例：Twitterのリプライ関係のグラフ

フォロー関係より面白そうだったのでやってみました。今回のjava-jaの参加者でTwitterを使っている人のリプライ関係をTwitter検索（http://pcod.no-ip.org/yats/）から取得してきて、以下のような行列を生成して、グラフとしてJungで描画します。

	yoshiori	lalha	yamashiro
yoshiori	0	1	2
lalha	1	0	1
yamashiro	2	1	0

描画結果

リプライの多さでエッジの太さを変えています。

グラフレイアウト

グラフはノードの位置によって印象が大きく異なってくるのでどのようにノードを配置するかが非常に大切です。自動でノードを配置するアルゴリズムはばねモデルをはじめとして、さまざまなものがあります。JungではLayoutインターフェースを実装したクラスを切り替えることでレイアウトを変更することができます。
上記のリプライ関係のグラフ描画には自己組織化マップを使ったレイアウトを利用しています。
以下の図はjava-ja参加者のフォロー関係について円環レイアウトで表示したものです。

クリックしたノードにつながっているエッジを強調しています。青が片思いで赤が両思いを表しています。これだけ密なグラフだと普通に描画しても見づらいので、このような表示方法のほうがわかりやすいのではないかと思います。

分析をしてみる

ただグラフを描画するだけだと他にもいくつかライブラリが存在するのですが、グラフの構造の分析を行うことができるのもJungの特徴です。

中心性を求める

ネットワークの特徴を知る上で、中心的なノード（＝そのグラフにおいて重要な位置の行為者）を求めることは重要です。中心性を求める方法はいくつか存在しますが、Jungでは媒介中心性、マルコフ中心性、PageRank、HITSなど多くの中心性を求めるアルゴリズムを利用可能です。
以下は与えられたグラフのPageRankを求めるソースコードです。

PageRank rank = new PageRank((DirectedGraph)graph, 0.5);
rank.evaluate();
List<NodeRanking> rankings = rank.getRankings();
rank.printRankings(true, true);

以下はリプライ関係のグラフのページランクを求めた結果です。

ID			Score
cactusman:	0.09556843685176082
yuripop:	0.08203343054586779
yamashiro:	0.05518103427914454
yoshiori:	0.05266528819081352
bose999:	0.041731677983314314

クラスタリング

ノードの類似性によって，複数の対象をグループ化する方法をクラスタリングと呼びます。
以下はBetweennessクラスタリング *1という手法を実行するソースコードです。

EdgeBetweennessClusterer clusterer = new EdgeBetweennessClusterer(10);
VertexClusterSet clusters = (VertexClusterSet) clusterer.extract(graph);
System.out.println("community count = " + clusters.size());

その他の機能

ランダムグラフの生成
ネットワーク距離や最大流の計算
統計解析

など。

Jung2 comming soon

近いうちにJava5に対応したJung2が出ます。
Genericsへの対応やアニメーション機能など多くの機能追加と改善が行われているらしいので期待です。

日本語で参考になるサイト

｢Jung-TECHSCORE-｣
http://www.techscore.com/tech/Others/Jung/index.html
｢Jung｣で日本語のページをぐぐったら一番上に出てくるはず。

｢Jungで相関行列のグラフ化｣
http://txqz.net/blog/2008/10/25/1155
Jungの実践的な使い方。

*1:媒介性の高いエッジを取り除いていく手法

public static void main