Social Network Analysis輪読会ークラスタリング手 …アルゴリズム [Algorism.]...

2005/6/22Copyright 2003 柴田尚樹 All Rights Reserved.本書の全部または一部の無断転載を禁じます。

1

Social Network Analysis輪読会ークラスタリング手法ー

東京大学大学院･修士課程2年2005/6/22 [Wed] 柴田尚樹, [email protected]

2005/6/22Copyright 2002 - 2004 柴田尚樹 All Rights Reserved.本書の全部または一部の無断転載を禁じます。 2

自己紹介

◆ 柴田尚樹（しばたなおき） / 24歳（修士2年） / ♂◆ 所属

! 工学系研究科環境海洋工学専攻テクノロジー・マネジメントコース

! 総合研究機構俯瞰工学部門

◆ 研究テーマ! （ネットワーク分析、自然言語処理を用いた）知の構造化手法に関

する研究

◆ 好きなもの / 嫌いなもの! インターネット、プロレス、歴史の勉強 / 納豆、ネクタイ、頭の悪い

人、情熱のない人

◆ 得意なこと / 苦手なこと! わーっとやってしまうこと / 地味にこつこつとやること


はじめに

◆ Newmanによる、クラスタリングの最新手法を紹介します。

◆ 対象論文：1. M. E. J. Newman and M. Girvan, Finding and

evaluating community structure in networks, PHYSICAL REVIEW E 69, 026113 2004.

2. M. E. J. Newman, Fast algorithm for detecting community structure in networks, PHYSICAL REVIEW E 69, 066133 2004.

◆ なぜ、クラスタリング手法をテーマに選定したのか。! 教科書には掲載されていない、かつ、実用的と思われる手法があったため。

! その手法が、つい最近（昨年）に発表され、素人の私でもあまり不利にならない（みなさんとまともに議論できる）と考えたため。


4

Finding and evaluating community structure in

networks (Feb. 2004)


5

1. Introduction


背景

実用的なクラスタリング手法の提案。◆ ネットワークをいくつかの集合に分割すること（以下、クラスタリングとする。）は、ネットワーク構造を理解し、可視化する上で重要である。

◆ 他方、クラスタリングの研究は、昔からなされてきたが、現実的な計算量でないなどの問題があった。

◆ 本論文では、実用的なクラスタリング手法を提案することを目的とする。


クラスタリングの2つの考え方クラスタリングには2つの考え方があるが、ここではDivisive Methodを扱う。

Agglomerative Method

Divisive Method


Agglomerative Methodの問題点Agglomerative Methodには問題点

がある。

◆ Agglomerative Methodの場合、図の太線のようなクラスターを見つけることはできるが、その他のリンクは見つけられない場合がある。

! 下図の場合、明らかに2つのクラスターに分割されるべきだが、Agglomerative Methodではそうならない。


9

2. Finding Communities in a Network


クラスタリングの基本的な考え方Highest betweennessなリンクを順番に切っていけば、クラスターができる。

Divisive Method


参考：Edge Betweenness法

[Algorism.] edge betweenness法[考え方]×：（従来手法）”least central”なリンクに注目する。○：（edge betweenness法）”most ’between’ communities”なリンクに注目する。

Betweenness centralityの考え方をリンクにも応用する。

[アルゴリズム]1. 全てのリンクのedge betweennessを計算する。2. 最もedge betweennessが高いリンクを切る。3. 再度、全てのedge betweennessを計算する。4. 2-3を、リンクな無くなるまで繰り返す。


Highest betweennessなリンクの見つけ方3つの方法のうち、どれが最も“良い”

方法か?◆ Highest betweennessなリンクの見つけ方。

1. shortest-path betweenness– 任意の2ノード間の最短パスに最も多く含まれるリンク（を

Highest betweennessなリンクとする）。2. random walk betweenness

– 任意の2ノード間を情報が伝搬する際に、情報がrandom walkに伝搬する場合に、最も多く通過するリンク（をHighest betweennessなリンクとする）。

3. current-flow betweenness– 任意の2ノード間を情報が伝搬する際に、最も情報流量が多いリンク（をHighest betweennessなリンクとする）。

◆ 実は、2と3は全く同じ。


Recalculation stepに関していちいちRecalculationしていては、時間がかかるだけではないか?

◆ あるネットワークに対して、highest betweennessなリンクを見つけて、それを切断する。

◆ すると、また異なるネットワークが出来上がり、再度、 highest betweennessなリンクを見つけて、それを切断する必要がある。

◆ このステップは果たして、意味があるのか?! 時間の無駄ではないのか。! 一度にたくさんのリンクを切ってはダメなのか。

◆ [結論] Recalculationするのとしないのとでは、結果に大きな違いがあるため、 Recalculationする価値は十分にある。


14

3. Implementation


A. Shortest-path betweenness基本的な考え方：あるノードsに注目して、最も離れたノードから距離を足していく。

◆ だが、、、現実はそんなに甘くない。

◆ 同じパス長の最短パスが2つ以上ある場合はどうするのか。


A. Shortest-path betweenness

まずはノードの距離、重みを計算する。

s

a

c

b

[0,1]

[1,1][1,1]

[2,1]

[3,2] [3,1]

[2,2]×

[3,3]×

1. The initial vertex s is given distance d(s)=0 and weight w(s)=1.

2. Every vertex i adjacent to s is given distance d(i)=d(s)+1=1 and weight w(i)=w(s)=1.

3. For each vertex j adjacent to one of those vertices i, we do one of three things:

! (a) If j has not yet been assigned a distance, it is assigned distance d(j)=d(i)+1 and weight w(j)=w(i) ;

! (b) if j has already been assigned a distance and d(j)=d(i)+1, then the vertex’s weight is increased by wi, that is, w(j)←w(j)+w(i);

! (c) if j has already been assigned a distance and d(j)<d(i)+1, we do nothing.

4. Repeat from step 3 until no vertices remain that have assigned distances but whose neighbors do not have assigned distances.

[2,1]d

e f

表記：[d(i), w(i)]


A. Shortest-path betweenness

1. Find every "leaf" vertex t, i.e., a vertex such that no paths from s to other vertices go though t.

2. For each vertex i neighboring t, assign a score to the edge from t to i of w(i)/w(t).

3. Now, starting with the edges that are farthest from the source vertex s—lower down in a diagram such as Fig. —work up towards s.

! To the edge from vertex i to vertex j, with j being farther from s than i, assign a score that is 1 plus the sum of the scores on the neighboring edges immediately below it (i.e., those with which it shares a common vertex), all multiplied by w(i)/w(j).

4. Repeat from step 3 until vertex s is reached.

次に、リンクのshortest-path betweennessを計算する。s

e

d

b

f

[0,1]

[1,1]

[2,1]

[3,3] [3,1]

表記：[d(i), w(i)]

[2,2]1

(0+1)*1/3=1/3

(0+1)*2/3=2/3

((1/3+1)+1)*1/1=7/3

(2/3+1)*1/2=5/6 (2/3+1)*1/2

=5/6

((7/3+5/6)+1)*1/1=25/6

(5/6+1)*1/1=11/6

[1,1] a

c


A. Shortest-path betweenness時間計算量は、最悪のケースでも

O(m^2n)。◆ ネットワーク内の総ノード数をn、総リンク数をmとすると、! あるノードsに関しての計算は、O(m)。! 全ノードに関しての計算（＝Shortest-path

betweennessの1回の計算）は、O(mn)。! 最悪のケース（全エッジを切るために再計算をm回繰り返す場合）でも、O(m^2n) or O(n^3)。


B. Resistor networks, C. Random walks

キルヒホッフ法則の考え方。

( )( )

( ) sADV

sVAD

VVA

otherwisetiforsifor

s

kDD

jiAiV

itisj

jiij

i

iii

ij

i

1

)1(

011

:

),(::

−−=⇔

=−⇔

−=−

=−=+

=

=

∑ 　　

とするとき、

　

　　

　　

対角行列

成分隣接行列の

における電圧

δδ •左辺：the net current flow out of vertex i along edges of the network•右辺：the source and sink.


B. Resistor networks, C. Random walks

◆ 方法：! あるノードvに対して、電圧ベクトルVが決まる。! 全てのノードに関してのVを合わせれば、edge

betweenessが計算できる。◆ Random walk法の詳細は略。◆ 計算量は、shortest-path法の場合よりも一桁多く、小規模ネットワークにしか、現実的には適用できない。


21

4. Quantifying the Strength of Community Structure


評価関数の導入

上述の方法でdendrogramは作れるが、どこで切ったら良いのか?

→評価関数が必要。

どこで切るべき?


Modularity Q

( )∑

∑

−=−=

≡

iiii

jiji

ij

eeTraeQ

ularityQ

ieaeTr

jiee

22 )(

mod

::)(

:,

を、とした場合に

）内でのリンク数（割合クラスター

）ながるリンク数（割合同じクラスター内でつ　

）の間のリンク数（割合とクラスター　行列

定義

◆ Qが表すのは、A-B。! A: the fraction of the edges in the network that connect vertices of the

same type (i.e., within community edges)! B: the expected value of the same quantity in a network with the same

community divisions but random connections between the vertices.◆ クラスター内リンク数がランダムの場合と変わらなければQ=0。◆ 強いクラスター構造の場合は、Q=1。◆ 現実は、Q=0.3~0.7で、あまり高い値にはならない。


Qと分割方法

Qが計算できれば、Qが最大（極大）のところで分割する。


25

5. Applications


A. Tests on computer-generated networks始めに、コンピューターで生成したランダムネットワーク（n=64,k=8）で実験し

た。


A. Tests on computer-generated networks

shortest-path法を推奨する。◆ Q~0.5で分割すべきで、その結果16ノードずつ4クラスターに分かれた。（上手く行った。）

◆ shortest-path法よりも、random walk法よりも、適切にノードがクラスタリングされているため、 shortest-path法の法を推奨する。


B. Zachary’s karate club network

空手クラブのネットワーク。

◆ 1:管理者。◆ 33:インストラクタ－。◆ ○：インストラクター派。◆ □：管理者派。



A

BC



現実ネットワークからの考察。◆ 前頁の考察：

! A: shortest-path法では、ノード3のみ間違ってクラスタリングされた。

! B: random walk法では、Qの極大値が1つしか存在せず（左の赤点線）、2つに分割するということが否定される。

! C: recalculationなしの場合、Qの値が低すぎて、不適切である。


C. Collaboration network

科学者のコラボレーションネットワーク。

Q=0.72±0.0213クラスターに分割


32

6. Conclusions


結論

◆ これまで解決されてこなかったネットワークのクラスタリングに関して、新しい方法を提案した。

◆ その方法を、現実のネットワークに適用して、効果と実用性を確認した。

◆ また、その方法は、O(n^3)という計算量であるため、比較的現実的な時間での計算が可能である。


34

Fast algorithm for detecting community structure in

networks (Jun. 2004)


35

1. Introduction


GN法よりも早く

新クラスタリング手法の提案。◆ 前述のshortest-path法（以下、発明者の名前にちなみ、GN法とする。）は、 O(m^2n) or O(n^3)の計算量が必要で、時間がかかる。! そのため、大規模ネットワークへの適用が困難である。

◆ 本稿では、GN法よりも高速で、GN法と似た結果を導く、新クラスタリング手法を提案する。


37

2. The Algorithm


アルゴリズムの考え方

modularity Qに着目する。GN法

（切断リンク候補選定→Q→切断リンク決定）新手法

（Qの増減→残すリンク決定）

1. 全リンクのedge betweennessを計算する。Qを計算する。

2. 最もedge betweennessの高いリンクを切る。

3. 1,2を繰り返す。Qが最大（極大）になった時点でリンク切断を中止する。

1. 全リンクに対して、そのリンクを入れた場合のQの増減を計算する。

2. Qの増加が最も大きくするリンクを残す。

3. 1,2を繰り返す。Qが最大（極大）になった時点でリンク残しを中止する。

◆ アイディア! GN法において、実際のリンク切断は、Qの値に基づいている。! それなら、最初からQの増減だけで切断リンクを決めればよいのでは?


アルゴリズム

[Algorism.] Newman法[考え方]全てのノードについて「リンク先と合わさって１つのクラスターになるべきか」を

計算していく。ある集団と別の集団とを分ける方法として、集団間のリンクに対して集団内部のリンクの密度の濃さで評価する方法が考えられる。この度合いをモジュール性Qという値で定義している。

[アルゴリズム]

1. 最初に全てのノードを構成要素が１のクラスターと再定義し、クラスターを結合しながら更新していく。

2. 初期クラスターはノードと同数で、ノードのリンクと同じ初期クラスター間の隣接行列上に、一つのクラスターとして更新する場合の変化が計算される。

3. 全隣接行列の中で一番ΔQの値を上げるペアが選ばれて１つのクラスターとして、比較的少ない計算量で再計算される。

4. この時、総クラスター数が１つ減る。計算過程で再編される隣接行列上のΔQはターン毎に変わっていき、最終的にどのペアを１つにしてもがΔQマイナスになる時点で終了となる。


Modularity Q

( )

( )jiijjijiij

iiii

jiji

ij

aaeaaeeQ

eeTraeQ

ularityQ

ieaeTr

jiee

−=−+=∆

−=−=

≡

∑

∑

22

)(

mod

::)(

:,

22

となり

を、とした場合に

）内でのリンク数（割合クラスター

）ながるリンク数（割合同じクラスター内でつ　

）の間のリンク数（割合とクラスター　行列

定義


計算量

新手法の方が、1桁少ない時間計算量。◆ GN法は、 O(m^2n) or O(n^3)の計算量が必要である。

◆ 新手法は、! eijが更新される際に、最大O(n)。! 従って、1ステップで、O(m+n)。! 全ステップで、最悪でも、O((m+n)n) or O(n^2)。


42

3. Applications


A. Tests on computer-generated networks

GN法の方が優れている。◆ 始めに、コンピューターで生成したランダムネットワーク（n=128,k=16）で実験した。

◆ 新手法の法が、GN法よりも、適切にノードがクラスタリングされている。



◆ 新手法でも、GN法と同程度に適切にクラスタリングできた。

! 1つのノード（#10）のみが事実と異なった。! Q=0.381（GN法と同程度）


C. network representing the schedule of games between American college football teams

◆ チームは“conferences”に属しており、conferences内での試合は、conferences間での試合よりもより頻繁であるため、チームはどのコミュニティに属するのが最適なのかを発見することができるのではないかと考えた。

! ノード：チーム

! エッジ：試合（をしたかどうか）


C. network representing the schedule of games between American college football teams

新手法の方が、実用的なクラスター抽出に適している。

Some of them correspond to single conferences, but most correspond to two or more.

60.546新手法

independent teams that belong to no conference.

110.601GN法

クラスターの表すものクラスター数Qの最大値


D. Collaboration network

大規模ネットワークにも適用可能。◆ 科学者のコラボレーションネットワークに適用した。

N=56276。◆ 新手法はデスクトップマシンで42分で終了した。他方、

GN法を用いていたら、3-5年待たねばならなかっただろう。

Q=0.713 Q=0.807


48

4. Conclusions


結論

◆ ネットワークのクラスタリングの新手法を提案した。

◆ この手法は、! GN法よりも適切にクラスターを抽出でき、! GN法よりもより計算量の少ない手法である。

◆ 新手法を約50,000の大規模ネットワークにも適用した。

◆ 気になる発言。。。

! We ..., but will also provide a useful tool for visualizing and understanding the structure of these networks, whose daunting size has hitherto made many of their structural properties obscure.

Social Network Analysis輪読会ークラスタリング手 …アルゴリズム [Algorism.]...

Documents

Transcript of Social Network Analysis輪読会ークラスタリング手 …アルゴリズム [Algorism.]...

Social Network Analysis輪読会 ークラスタリング手 …アルゴリズム [Algorism.]...

Documents

Transcript of Social Network Analysis輪読会 ークラスタリング手 …アルゴリズム [Algorism.]...

Social Network Analysis輪読会ークラスタリング手 …アルゴリズム [Algorism.]...

Transcript of Social Network Analysis輪読会ークラスタリング手 …アルゴリズム [Algorism.]...