社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

カオス回路の同期現象を用いた複雑ネットワークのクラスタリング
吾郷 健太†

上手

洋子†

西尾

芳文†

† 徳島大学工学部 〒 770–8506 徳島県徳島市南常三島 2–1
E-mail: †{kentago,uwate,nishio}@ee.tokushima-u.ac.jp
あらまし

本論文では，結合カオス回路の同期現象を用いた複雑ネットワークにおけるクラスタリング手法を提案する．提案手法はカオスのもつ非周期性および結合カオス回路で観測される位相同期現象に基づいており，最も非同期的に振る舞う回路間の結合から切断していくといった階層的クラスタリング手法である．この手法により検出されたそれぞれのクラスタの同期率およびネットワーク特徴量を調査することにより，提案手法がクラスタの判別に有効であることを示す．さらに，社会ネットワークで観測される実データセットに対して提案手法を適用し，クラスタリン
グの汎用性を確認する．
キーワード

クラスタリング，同期現象，カオス回路，複雑ネットワーク

Clustering using Synchronization of Chaotic Circuits
for Complex Networks
Kenta AGO† , Yoko UWATE† , and Yoshifumi NISHIO†† Dept. of Electrical and Electronic Engineering, Tokushima University
2–1 Minami–Josanjima, Tokushima, 770–8506 Japan
E-mail: †{kentago,uwate,nishio}@ee.tokushima-u.ac.jp
Abstract In this paper, an approach for clustering on complex networks by using synchronization phenomena of
coupled chaotic circuits is proposed. The proposed method is based on non–periodicity with the chaos and phasesynchronization phenomena of coupled chaotic circuits, is a hierarchical approach by cutting edges in the order fromthe most asynchronous coupling. The properties of detected clusters by its clustering method is investigated, thisapproach is shown to be eﬀective for cluster partition. Additionally, we apply the proposed method to realisticsocial networks, the applicability of clustering is confirmed.
Key words Clustering, Synchronization, Chaotic Circuit, Complex Networks

1. は じ め に
複雑ネットワークはスモールワールドネットワーク [1] やス

は，ネットワークにおける構造的な機能を理解するための重要な問題であり，データマイニングや画像処理といった多くの実用的なアプリケーションへの適用も期待される．

ケールフリーネットワーク [2] などの数理モデルが提案されて以一方，同期現象は自然科学の領域で観測される典型的な現象

来，現代科学を紐解く新たなパラダイムとして学際的に広く注の一つであり，結合発振器システムを用いた調査が精力的に行目を集めている．現実世界には，インターネット，交通網，脳われている．その中でも，カオス回路を用いた結合システムで神経細胞，人間関係など，多岐にわたるネットワークが存在すは，カオス同期 [6] をはじめ興味深い現象が報告されている．こる．これらのネットワークの多くは一見複雑な構造をしながられまで，結合カオス回路の大規模化システムにおける同期現象

も，特徴的な性質を共通して持つことが報告されている [3]- [5]．

の研究は，完全結合系，ラダー状，リング状，スター型など，

ネットワークの構造解析の一つとして，クラスタリング（コ結合形態においては規則的な場合についての調査が多く行われミュニティ抽出，分割）が挙げられる．ネットワークとは一般てきている．しかしながら，回路の結合形態が複雑なシステム

的にグラフとしてノードとエッジで表現され，その中にはクラについての調査はほとんど行われてきていない．現実世界で同スタと呼ばれる相互に密な接続を有するノードの部分集合が存期現象を引き起こす系は規則的な結合形態をとるとは考えられ在する．そのため，複雑ネットワークにおけるクラスタリング

ず，前述の複雑ネットワークの立場から議論する必要がある．

—1—

本論文では，ローカルブリッジ構造を有する複雑ネットワー

30

27

クを調査対象とし，カオス回路の同期現象を用いたクラスタ

28
26

リング手法を提案する．ローカルブリッジとは，異なるグルー

リッジ構造を有するカオス回路の複雑ネットワークにおける同

39

37

14

40

41

18
19
12

期現象の統計的調査を行ってきており，ローカルブリッジの非

15

13

21

35

34

23

22

文献 [7] で報告されている．我々は過去の研究で，ローカルブ

38

20

24

36

32

31

25

プに属しているノード間同士の橋渡し機能を持つ接続であり，

33

29

17 16

7
9

同期的な振る舞いを確認している [8], [9]．本研究では，より大1110規模なローカルブリッジ構造を有するカオス回路の複雑ネット

44
45

ワークを調査対象とする．コンピュータシミュレーションによ6
local bridge

り得られた全てのエッジにおける非同期率の計算結果より，複

47
1

4

8

42

43

46

5

R

2

3

図 2 ネットワークモデル (47 ノード，87 エッジ)．

雑ネットワークにおけるクラスタリング手法を提案する．提案
手法は，最も非同期的に振る舞う回路間の結合から切断していくといった階層的クラスタリング手法である．この手法により検出されたそれぞれのクラスタの同期率およびネットワーク特徴量を調査することにより，提案手法がクラスタの判別に有効であることを示す．さらに，社会ネットワークで観測される実データセットに対して提案手法を適用し，クラスタリングの汎

また，本カオス回路ネットワークのダイナミクスは次式 (2)のような常微分方程式により導出される．









din
dt
dv1n
C1
dt


L




 C2 dv2n

用性を確認する．

本研究で用いたカオス回路を図 1 に示す．この回路は負性抵
抗，1 つのインダクタ，2 つのキャパシタ，および双方向に結合されたダイオードにより構成される簡素な 3 次元自励振動回路であり，神力らによって提案された [10], [11]．この回路は負性抵抗の値の変化によって，周期倍分岐を経てカオスへ至る回路である．図 2 に，調査対象とするローカルブリッジ構造を有するネットワークモデルを示す．本モデルは 47 ノードおよ

R に対応している．本ネットワークモデルにおいて，ローカル
ブリッジは 1–47，4–5，10–16，11–12，15–39，16–21，20–25，

23–31，32–33，33–34，39–40 であると考えられる．

idn

n

-g

C1

C2

in

=

より構成される非線形抵抗の i − v 特性は式 (1) で区分線形近似される．なお，パラメータ Gd は非線形抵抗の傾きであり，t=√LC2 τ, “ · ” =

d

C2

C2


Gd (v1n − v2n − V ) (v1n − v2n > V )
Gd (v1n − v2n + V )(v1n − v2n < −V ).

, α=

C2

(3)

dτ
C1



√
√
√



L
L
1
L

 β=
Gd , γ =g, δ =,
RC2

次式 (4) の正規化された方程式が得られる．



x˙n






=

zn

y˙n

=

αγyn − αf (yn − zn ) − αδz˙n=f (yn − zn ) − xn ,∑(yn − yk ) (4)k∈Snβ(yn − zn − 1) (yn − zn > 1)







0

(|yn − zn | <= 1)

β(yn − zn + 1)

(yn − zn < −1).

(5)

3. クラスタリング
本研究では，回路パラメータを α = 0.4, β = 20, γ = 0.5,

δ = 1.0 として固定し，全ての回路に対して互いに異なる初期

添字 n はノード番号（n = 1, 2, 3, ..., 47）を示す．

(|v1n − v2n | <=V)−in + idn ,形関数であり，次式 (5) のように記述することができる．

まず，この回路に含まれる双方向に結合されたダイオードに

0(2)

また，式中の f (yn − zn ) はダイオードの特性に対応する非線

L

図 1 カオス回路．





1 ∑
(v1n − v1k )
R

√


C2

V xn , v1n = V yn , v2n = V zn
in =



L




f (yn − zn ) =idn =gv1n − idn −(3) に示す変数およびパラメータ変換を行うことによって，








v2n

v1n

=

ここで，Sn はノード n と隣接するノードの集合を示す．次式

び 87 エッジで構成される複雑ネットワークであり，ノードとエッジはそれぞれ図 1 に示したカオス回路と回路間の結合抵抗

v2n

k∈Sn

dt

2. ネットワークモデル=

値を与える．このとき観測されるアトラクタを図 3 に示す．図中の y と z はそれぞれ，図 1 の回路図における v1 と v2 に対応(1)

する変数である．なお，コンピュータシミュレーションは 4 次
ルンゲ＝クッタ法を用いて行う．

—2—

y

カオスのもつ非周期性および結合カオス回路で観測される位相1.5

同期現象に基づいており，最も非同期的に振る舞うノード間のエッジから切断していくといった，階層的クラスタリング手法
である．提案手法は以下に示す 3 つの工程から構成される．

1.5

-1.5
-1.5

1) Cutting - 非同期率が 50%以上のエッジにおいて，最もz

非同期率が高いエッジから順に切断する．

2) Grouping - ノード n が孤立した場合，最後に接続してい図 3 カオスアトラクタ．(α = 0.4, β = 20, γ = 0.5)．

た相手側のノードが属するクラスタにグループ化する．

3) Recoupling - 最後にエッジを切断した後，クラスタ分割

3. 1 同期の定義に不要なエッジを再接続する．

図 4 に，コンピュータシミュレーション結果の一例を示す．
縦軸はノード (1,2) 間の電圧差分（y1 − y2 ）を示しており，もし 2 つのノードが完全同期していればグラフは 0 の直線となる．

図 6 に，提案手法とその結果を示す．提案手法を適用することにより，本ネットワークモデルでは 8 クラスタが検出された．
本手法では，分割されたクラスタの数が 1 つずつ増えるといった点で興味深く，任意のクラスタ数を設定したクラスタリング

0.10が可能である．図 7 に，検出されたクラスタの数と平均同期率の関係を示す．この結果から，判別するクラスタの数が増える
0.01

ことにより，より密なクラスタを検出できることが確認される．

0

また，本手法では孤立する傾向にあるノードを検出することができる．本ネットワークモデルでは，33，10，39，4，40，-0.01

16，20，32，5，15，12，34 の順序で孤立ノードが検出された．
これらのノードは全てローカルブリッジを接続するノードであることから，ネットワークにおける重要なノードであると考え

-0.10

図4

られる．したがって，これらのノードはクラスタ間のジレンマ

位相差波形の例（y1 − y2 ）と同期の定義．

により孤立する傾向にあると言える．

本研究では，観測されるカオス回路の位相同期現象を定量的

3. 4 ネットワーク特徴量
さらに，本手法で検出された 8 クラスタのプロパティを調査に評価するため，同期状態を以下のように定義する．

する．表 1 に，それぞれのクラスタにおける同期率 p(s)，ノー|yn − yk | < 0.01

(k ∈ Sn ).

(6)

3. 2 非 同 期 率
次に，我々は一定の時間間隔 (τ = 10, 000，step = 0.01τ ) を設定し，上述の同期の定義式 (6) を用いて全てのエッジにおける非同期率を調査する．図 5 に，最も非同期率が高いエッジ
から順にソートされた，全てのエッジにおける非同期率の計

ド数 N ，エッジ数 E ，平均次数 k ，クラスタ係数 C ，およびパ
ス長 L を示す．以下にネットワーク構造の特徴を定量的に評価する指標である，クラスタ係数およびパス長について簡潔に述べる．
まず，ネットワークの「クラスタ性」を測るための特徴量であるクラスタ係数 C は式 (7) で定義される．

算結果を示す．この結果から，他のエッジと比較してローカル
ブリッジ（1–47，4–5，10–16，11–12，15–39，16–21，20–25，

23–31，32–33，33–34，39–40）における非同期率が高いことが確認できる．これは，ネットワーク全体において橋渡し機能を有するエッジは他のエッジと比較して非同期的に振る舞うことを表している．つまり，非同期率の高いエッジは，クラスタ間を接続するエッジである可能性が高いと考えられる．一方，

29–31，22–24，6–7，13–14，29–30 などのエッジは完全同期にC=考えられる．

3. 3 提 案 手 法
図 5 における全てのエッジの非同期率の計算結果より，我々はローカルブリッジがネットワークにおけるクラスタおよび重要なノードの検出に有効であると考える．そのため，複雑ネッ
トワークにおけるクラスタリング手法を提案する．提案手法は，

N

N

n=1

n=1

(7)

ここで，En はノード n と隣接する kn 個のノード間のエッジ数を表す．すなわち，クラスタ係数 C はネットワーク内の三角形構造の密度を示す．
次に，ネットワークの「スモールワールド性」を測るための特徴量であるパス長 L は式 (8) で定義される．

近い状態であることを示しており，これらは共通した隣接ノードを複数持つことから，クラスタ内部に属するエッジであると

1 ∑
1 ∑
2En
Cn =
,
N
N
kn (kn − 1)L=∑
2
N (N − 1)

N −1

N
∑

m=1

n=m+1

l(m, n),(8)

ここで，l(m, n) はノード (m, n) 間の最短距離を表す．すなわ
ち，パス長 L はネットワーク内の 2 ノード間の平均最短距離を示す．
一般的に密なネットワーク構造とは，大きいクラスタ係数と小さいパス長で評価される．表 1 より，それぞれのクラスタにおける同期率 Sp はクラスタ係数 C およびパス長 L に概ね依存—3—

表 1 検出されたクラスタの同期率およびネットワーク特徴量．

Cluster

1〜4

5〜11

12〜15

16〜20

21〜24

25〜33

34〜39

40〜47

1〜47

p(s)

0.16870.06240.22100.11420.35910.07810.08650.10720.0008

N

4

7

4

5

4

9

6

8

47

E

5

13

5

7

6

17

10

14

87

k

2.50

3.57

2.50

2.80

3.00

3.56

3.34

3.50

3.70

C

0.58

0.77

0.83

0.77

1.00

0.54

0.81

0.67

0.56

L

1.17

1.38

1.17

1.30

1.00

1.72

1.33

1.54

4.98

図5
initial state
30

27
28
26

28

36

32

38

22

25

39
1st
41
40

15

13
18
19

14

22

8

5
3rd
1
4

42

43

46
11

3

40

44

41

19
17 16

46
47
4

8

44

3

40

46

41

19

42

17 16

44

41

47
4

44

1
45

6

isolating node

42

43

46

8

2

cutting edge

図6

37

5
11

10

1
45

3

40

14
7
9

47
4

6

2

43

5

8

39

15

18
12

11

10

1
45

6

22

13

14
7
9

5
11

2

43

35

34

20
23

21

18

42

38

12

7

10

39

15

13

14

17 16
9

47
45

6

22

25
24
37

36

32

31

34

20

33

29

26

35

23

21

18
19

38

12

7
9

39

15

13
21

25
24
37

30

27
28

36

32

31

34

clustering result (8-clusters)

33

29

26

35

23

12
17 16
2nd
10

28

36

32

38

20

24
37

30

27

31

34

20

33

29

26

35

23

21

30

27

31

25
24

state after cutting last edge

2-clusters state3329

一定時間間隔における全てのエッジの非同期率．

3

2

recoupling edge

提案手法とクラスタリング結果．

していることがわかる．したがって，それぞれのクラスタの同

4. 1 Karate club network

期率はコミュニティ強度の指標として評価できると考えられる．

Zachary による Karate club network [12] は，1970 年代のある米国大学における空手クラブの 34 人のメンバーの交友関係を示す社会ネットワークである．本ネットワークは 34 ノード
および 77 エッジから構成され，2 つの派閥があることが確認されている．図 8 に，Karate club network におけるクラスタリ
ング結果を示す．提案手法では，2 つの派閥を正しく検出することができなかった．この場合，7 番目のエッジ 1–11 を切断
後，ネットワークは 2 分割される．しかしながら，ネットワー
クが 3 クラスタに分割されるまで提案手法を適用した場合，現実的な派閥（realistic partition）を検出することができた．また，孤立ノードは 17，12，20，3 の順序で検出された．この場

図 7 検出されたクラスタの数と平均同期率．

合，53 番目のエッジ 9–31 を切断後，ネットワークは 3 分割される．

4. 2 Dolphin social network

4. 社会ネットワークへの応用
本章では，社会ネットワークで観測された 2 つの実データセットに対して提案手法を適用し，クラスタリングの汎用性を確認する．2 つの現実ネットワークにおいて，2 クラスタに分割されるまで提案手法を適用し，その有効性について考察する．

Lusseau らによる Dolphin social network [13] は，ニュージーランドにおいて，ダウトフルとサウンドを用いて共同生活している 62 頭のイルカの社会的ネットワークである．本ネッ
トワークは 62 ノードおよび 159 エッジから構成され，2 つのコ
ミュニティの存在が確認されている．図 9 に，Dolphin social

—4—

27

16

15
24

5. ま と め

21

30
33

28
34

26
31

32

本論文では，結合カオス回路の同期現象を用いた複雑ネット

23
29

ワークにおけるクラスタリング手法を提案した．提案手法はカ1910

オスのもつ非周期性および結合カオス回路で観測される位相同

25
14

20
13

ら切断していくといった階層的手法である．この手法により検

8

4

18

期現象に基づいおり，最も非同期的に振る舞う回路間の結合か

9

3

2

12

1

22

出されたそれぞれのクラスタのプロパティを調査することによ

11

5
7

り，同期率がコミュニティ強度の指標になり得ることを示した．

6

さらに現実ネットワークに対して提案手法を適用し，クラスタ

17

cutting edge
realistic partition

図 8 Karate club network のクラスタリング結果．

リングの汎用性を確認した．
本研究は複雑ネットワークと非線形回路が関連する諸分野を繋げる試みであり，お互いの分野の手法を用いるための第一歩

network におけるクラスタリング結果を示す．提案手法では，2であると言える．今後の課題として，クラスタを判別するよりつの大きなコミュニティと孤立ノード 40 を検出することがで効率の良いアルゴリズムの開発と，様々なネットワークへの適きた．このノード 40 は 2 つのコミュニティ間を接続する，本用性の向上が考えられる．

ネットワークにおいて重要なノードである．この場合，11 番目

謝辞のエッジ 8–31 を切断後，ネットワークは 2 分割される．
本研究の一部は, JSPS 科研費 26540127 の助成を受けたも
isolating node

56
24
40

12

52

22

46

19

4
9

55

51

34

44

15

35

39

59

47

38

41

6

50

21

10
14
33

29

2

42

61

13

53

37

7

文

36
30

60
58

のである．

25

16

49
57

5

20
18

11

32

54

1
8

31

43

26

23

17
45

62

3

27

28

48
cutting edge

図 9 Dolphin social network のクラスタリング結果．

4. 3 考察

表 2 に，2 つの社会ネットワークのプロパティを示す．同パラメータであるにも関わらず，Karate club network はネット
ワーク全体が完全同期に近い状態であることがわかる．それはDolphin social network と比較して，大きいクラスタ係数 C と
小さいパス長 L も持ち，かつクラスタ間のエッジが多いためである．したがって，提案手法はローカルブリッジ構造を有する
複雑ネットワークにおけるコミュニティ検出により効果的であると考えられる．
表 2 2 つのネットワークの同期率およびネットワーク特徴量．

Network

Karate club

Dolphinp(s)0.99570.0426

N

34

62

E

77

159

k

4.59

5.13

C

0.57

0.26

L

2.41

3.36

献

[1] D. J. Watts and S. H. Strogatz, “Collective dynamics ofsmall-world,” Nature, vol. 393, pp. 440–442, 1998.
[2] A. L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509–512, 1999.
[3] R. Albert and A. L. Barabasi, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, pp. 47–97, 2002.
[4] M. Girvan and M. E. J. Newman, “Community structure
in social and biological networks,” Proc. Natl. Acad. Sci.,
USA 99, pp. 8271–8276, 2002.
[5] M. E. J. Newman, “The structure and function of complex
networks,” SIAM review, vol. 45, pp. 167–256, 2003.
[6] L. M. Pecora and T. L. Carroll, “Synchronization in chaotic
systems,” Phys. Rev. Lett., vol. 64, 821, 1990.
[7] M. S. Granovetter, “The strength of weak ties,” Am. Journ.
Soc., vol. 78, pp. 1360–1380, 1973.
[8] K. Ago, Y. Uwate and Y. Nishio, “Influence of Local Bridge
on a Complex Network of Coupled Chaotic Circuits,” Proc.
NOLTA’14, pp. 731–734, 2014.
[9] K. Ago, Y. Uwate and Y. Nishio, “Investigation of Partial
Synchronization in Coupled Chaotic Circuit Network with
Local Bridge,” Proc. NCN’14, pp. 64–67, 2014.
[10] M. Shinriki, M. Yamamoto and S. Mori, “Multimode Oscillations in a Modified van der Pol Oscillator Containing
a Positive Nonlinear Conductance,” Proc. IEEE, vol. 69,
pp. 394–395, 1981.
[11] N. Inaba, T. Saito and S. Mori, “Chaotic Phenomena in a
Circuit with a Negative Resistance and an Ideal Switch of
Diodes,” Trans. IEICE, vol. E70, pp. 744–754, 1987.
[12] W. W. Zachary, “An Information Flow Model for Conflictand Fission in Small Groups,” Journal of AnthropologicalResearch, vol. 33, pp. 452–473, 1977.
[13] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase,
E. Slooten and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of
long-lasting associations. Can geographic isolation explain
this unique trait?,” Behavioral Ecology and Sociobiology,
vol. 54, pp. 396–405, 2003.

—5—