日時：2007年11月22日(木) 18:30 から
場所：東京工業大学 大岡山キャンパス 西8号館Ｗ棟10階1008号室 (地図)
話者：
鶴見 敏行 (東京工業大学)
話題：
大規模社会ネットワークからのクラスタ構造の抽出
概要：
Clauset，Newman，Moore はネットワークをボトム
アップかつ貪欲に解析する手法(CNM アルゴリズム) を
提案し、50 万ノード程度までの社会ネットワーク解析
を可能としたが、それ以上の規模については実用的な時
間内での解析は困難であった。そこでCNM アルゴリズ
ムの合併の過程を観察した。その結果合併するクラスタ
サイズの不均衡が計算コストに大きく影響していること
が明らかとなった。この観測から、合併するクラスタサ
イズの均衡がアルゴリズムの速度向上につながると考え
た。本研究では、合併時のクラスタのサイズを考慮するこ
とにより合併比率を向上させる3 種類の手法を提案す
る。提案手法の実験データセットとして、国内最大級の
ソーシャルネットワーキングサービスより2006 年10 月
に取得した550 万ユーザーの友人関係のネットワークを
使用した。提案した3 つの手法を用いたところ、CNM
アルゴリズムに比べ劇的なスケーラビリティの向上がみ
られた。もっとも速度向上がみられた手法では、100 万
ノードに対して5 分、400 万ノードに対しては35 分程
度で解析する事に成功した。また別の手法では、50 万
ノードに対して50 分（CNM アルゴリズムより7 倍早
い）で解析でき、モジュール性の向上にも成功した。
出席者：15名
和田英一（IIJ）、伊知地宏（ラムダ数教研）、日比野啓（朝日ネット）、 首藤一幸（ウタゴエ）、三廻部大（日本IBM）、匿名希望、 寺田実、卜部昌平、高須賀清隆（電気通信大）、五十嵐和久（電通大OB）、 脇田建（東京工業大）、田中哲朗、筧一彦、横山大作、丸山一貴（東京大）
Q. コミュニティをいきなりグラフでモデル化してしまったのは突然と感じるが、 それは本当に妥当なのか。コミュニティの情報（AさんはXに属している、とか） からグラフを作る話なのか、グラフが与えられてコミュニティ（クラスタ）を 抽出する話なのか。 A. 誤解を与えてしまいましてすいません。本研究では、人間関係のネットワークを 個々の人間としてのノード、人間関係を表すエッジを用いグラフとして扱って います。一方、密接に関係した人間の集団としてのコミュニティはノードの 集合として考えています。 Q. Cluster FindingとGraph Clusteringの違いは何か。 A. Cluster Findingは、ノードを与え、そのノードに関連したノードの集合を 抽出する手法です。Graph Clusteringは、グラフ全体を与え、そのグラフを 関連したクラスタに分割する手法です。 Q. Graph Clusteringは、単純にCluster Findingの手法をN回繰り返すよりも よい手法ということなのか。 A. 比較してみないとわからないです。 Q. Cluster（部分Graph）の定義は何か。どのような条件を満たせばClusterと なるか。その定義が論文ごとに異なるとすると、各手法を比較することは難しいのか。 A. 本研究では、アルゴリズムにより得られた部分グラフそれぞれをClusterと定義 している。また、定義が異なっていても、モジュール性などで比較することは可能です。 Q. CNMアルゴリズムのモデルの定義が分からないが、有向グラフや重み付きグラフ にはなっていないということか。 A. 重み無し無向グラフを対象としています。 Q. mixiのユーザ関係のデータを元にしているというが、ユーザが複数のコミュニティに 属している場合はどうなるのか。 A. ここでコミュニティとは、mixi上で提供されているコミュニティではなく、関連する 人によって構成される密なネットワークとしています。解析過程では各ノードは 特定のクラスタのみに所属しています。 Q. 決められたクラスタの数に収束させるのか。 A. 提案アルゴリズムは、グラフに対してボトムアップかつGreedyに合併を行います。 そのため、グラフの特性により合併の順序や回数が変わるので、得られるクラスタの 数は決まっていません。 Q. CNMアルゴリズムはMaximum Spanning Treeのアルゴリズムと似ているように 見えるが。 A. Greedyなアルゴリズムという点では似ています。CNMアルゴリズムは最適値を 得られないという点で異なります。 Q. mixiのユーザデータにCNMを適用した例で、50万ユーザの計算は40万ユーザの 計算結果を利用して実行するのか。 A. 40万ユーザーと50万ユーザーの計算は独立して行っています。 Q. 密なグラフでは隣接するクラスタがもっと合併されるように思えるが、そうならない のはグラフが疎だからか。 A. そうです。密なグラフではクラスタ自体のサイズが大きいので、合併が多く 行われます。具体的な例としては、完全グラフに対して解析するとノード数回の 合併が行われ、グラフが一つのクラスタとなります。 Q. フルセットネットワークの実行でメモリ不足があったというが、どの程度の メモリを搭載した計算機で実行したのか。 A. CPU:Xeon 2.8Ghz, L2Cache=2MB メモリ:4GB 実装言語：Java (JDK5.0) を実行環境としました。 Q. グラフの2分割アルゴリズムはどのような手法か。 A. 2分割したグラフ間でのエッジを最小にする手法です。 具体的には、 Simple Algorithms for Graph Partition Problems Onsjo, M. and O. Watanabe Theory of Computing Systems, Vol. 4288, 2006, pp. 507-516 を用います。 Q. 分割後のグラフにアルゴリズムを適用する場合は、分割されたものが全てと 思ってClusteringするのか。 A. グラフを分割をする理由が、分割により計算コストを分散させるためなので、 計算コストを抑えるためにグラフを分割ごとに完全に独立させています。 Q. 定義されていたモジュール性は、どういう分野で「よい」とされているのか。 A. 社会ネットワーク解析で、クラスタリング結果の精度比較に用いられています。 Q. mixiからコミュニティが抽出されたが、それぞれがどのように分類されたのか。 A. まだ調べていません。現在研究室のメンバーが解析中です。 Q. このアルゴリズムは停止するのか。 A. このアルゴリズムはループの中で2つのクラスタを1つのクラスタにまとめあげます。 したがって、クラスタの数は単調減少するので停止します。 Q. この分野で、標準的なベンチマーク用のデータはあるのか。 A. An Information Flow Model for Conflict and Fission in Small Groups Wayne W. Zachary Journal of Anthropological Research, Vol. 33, 1977, pp. 452-473 Chaotic neural networks Aihara, K. and Takabe, T. and Toyoda, M. journal of Physics Letters A, Vol. 144, 1900, pp. 333-340 Emergence of Scaling in Random Networks Albert-Laszio Barabasi and Reka Albert Journal of Science, Vol. 286, 1999, pp. 509-512 などがベンチマーク用のデータとしてよく使われています。 Q. CNMアルゴリズムの初期の併合が遅かったのは、何が理由か。memory locality が下がってしまうのが原因になることはあるか。 A. CNMアルゴリズムの初期の合併が遅かったのは、memory localityが原因ではなく、 合併が一つのクラスタに集中してしまい、巨大なクラスタが生成されたためです。 合併にかかる計算コストは隣接クラスタ数に比例します。そのため、巨大なクラスタと 合併するには大きな計算コストがかかります。提案アルゴリズムでは合併サイズの 偏りを考慮した合併を行い、一つのクラスタに合併が集中することを抑制し、 計算コストを抑えることに成功しました。
当日はPTT終了後に、東京工業大学 学術国際情報センター 西川先生のご厚意により、 PTT出席者全員でTSUBAMEを見学させていただきました。その際に撮影した写真を 公開する許可をいただきましたので、TSUBAME見学記 として公開いたします。