関係 性 の検 討

修士論文

ラ プ ラ シア ン行 列 の最 大 固有 値 に属 す る固有 ベ ク トル とグ ラ フ構 造 の

関係 性 の検 討

14892514柴 田 理 史

指導教員 會田 雅樹 教授

2016年1月

首都 大学東 京大学院 システムデザイ ン研 究科

システム デザ イ ン専攻 経 営 システム デザ イ ン学域

Copyright@2016,ShibataSatos

一i一

目次

第1章 1.1 1.2 1.3

第2章 2.1 2.2 2.3

第3章

¶⊥り白

り000

第4章 4.1 4.2

序 論 研 究 背 景...

研 究 目 的...

構 成....

ラ プ ラ シ ア ン 行 列 の 概 要 ラ プ ラ シ ア ン 行 列 の 基 礎.̲...

ラ プ ラ シ ア ン 行 列 の 固 有 値 問 題....

代 数 的 連 結 性 と フ ィ ー ド ラ ー ベ ク トル..

ラ プ ラ シ ア ン 行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル が 表 す グ ラ フ 構 造 の 実 験 的 考 察

リ ン ク の 存 在 に 関 す る 予 想 と 実 験̲...

リ ン ク の 存 在 に 関 す る 実 験 結 果...

最 大 固 有 値 に 属 す る 固 有 ベ ク トル と グ ラ フ 構 造 の 関 係 に 関 す る 予 想 ラ プ ラ シ ア ン 行 列 の 最 大 固 有 値 に 関 す る 予 想...

パ ス グ ラ フ に お け る ラ プ ラ シ ア ン 行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル.

第5章 結論

謝辞 参考文献

‑凸‑占0045FOQU(U1 亡Uρ00◎1←‑⊥‑⊥ ︻﹂ビ0ρ0つ﹂り0り0

41

42

43

一iii一

図 目次

1

 1 ‑占20U4FOたU7・ り白り右り白り自りθりθりθ 012345671234567891111111133333333333333333

ノ ー ド と リ ン ク に よ っ て 記 述 さ れ た ネ ッ ト ワ ー ク

グ ラ フ...

長 さ2の ノ ー ド0か ら ノ ー ド4へ の 経 路....

ラ プ ラ シ ア ン 行 列 の 例...

代 数 的 連 結 性...

連 結 性 の 変 化...

3つ の ク ラ ス タ か ら な る グ ラ フ...

フ ィ ー ド ラ ー ベ ク ト ル の 成 分...

グ ラ フC...

モ デ ルC最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル1...

モ デ ル1最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル1.2...

モ デ ル1.2最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル..

グ ラ フ モ デ ル1.3...

モ デ ル1.3最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル..

グ ラ フ モ デ ル2...

モ デ ル2最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル3...

モ デ ル3最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル4...

モ デ ル4最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル5...

モ デ ル5最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル...

グ ラ フ モ デ ル6...

2678234577889900112233445111111111122222222222

一iv一 図 目 次

890123456789012341122222222223333333333333333333333

モ デ ル6最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル..

グ ラ フ モ デ ル7...

モ デ ル7最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル.

グ ラ フ モ デ ル8...

モ デ ル8最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル.

グ ラ フ モ デ ル9...

モ デ ル9最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル..

グ ラ フ モ デ ル10...

モ デ ル10最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル グ ラ フ モ デ ル11...

モ デ ル11最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル グ ラ フ モ デ ル12...

モ デ ル12最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル グ ラ フ モ デ ル13..

モ デ ル13最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル グ ラ フ モ デ ル14...

モ デ ル14最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

...25 ..26

...26 ..27 ...27 .28

...28 .29 .29

.30 .30 ...31

.31 .32

32 .33

.33

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

重 み 付 き ノー ドの 集 合..

パ ス グ ラ フの 作 成 イ メ ー ジ...

ノー ド数2の 重 み の 差 の 自乗 和 最 大 配 置 ノー ド数3の 重 み の 差 の 自乗 和 最 大 配 置 検 討..

ノー ド数4の 重 み の 差 の 自乗 和 最 大 配 置 検 討.

ノー ド数5の 重 み の 差 の 自乗 和 最 大 配 置 検 討.

ノー ド数6の 重 み の 差 の 自乗 和 最 大 配 置 ノー ド数2kの 重 み の 差 の 自乗 和 最 大 配 置, ノ ー ド数2k+1の 重 み の 差 の 自乗 和 最 大 配 置

ノー ド数2k+2の 重 み の 差 の 自乗 和 最 大 配 置

363737373838393939如

1

第1章

序論

1.1研 究 背 景

近 年 の 情 報 通 信 ネ ッ トワ ー ク技 術 の 目 覚 ま しい 発 展 と普 及 に伴 い,個 人 が 場 所 や 時 間 を 問 わ ず イ ン タ ー ネ ッ トに 接 続 で き る デ バ イ ス を 常 に 携 帯 す る こ とが 当 た り前 に な っ て い る.ま た,

ソー シ ャル ネ ッ トワ ー キ ン グ サ ー ビ ス な ど の 利 用 の 高 ま りよ っ て 巨 大 な 社 会 ネ ッ トワ ー クの 構 造 を 観 測 す る こ とが 可 能 に な っ て い る 国.そ の よ う な 巨 大 で 複 雑 な ネ ッ トワ ー ク は 複 雑 ネ ッ

トワ ー ク と呼 ば れ,複 雑 ネ ッ トワー ク を 対 象 と した 研 究 は 一 つ の 研 究 学 問 と して 多 くの 研 究 者 を 魅 了 し,情 熱 を 注 が せ る 対 象 で あ る[2].複 雑 ネ ッ トワ ー クは 数 学,社 会 学,生 物 学 な ど様 々 な 分 野 か ら研 究 対 象 と して ア プ ロ ー チ さ れ て い る[3,4].そ の 中 で も,グ ラ フ 理 論 を 基 礎 と し た ネ ッ トワ ー ク分 析 に 対 す る ア プ ロ ー チ は ネ ッ トワ ー ク グ ラ フ の 普 遍 的 な 性 質 を 明 らか に す る の に 効 果 的 な 手 法 で あ る[5,6,7].

グ ラ フ理 論 で の グ ラ フ と は,ノ ー ド(点)と リ ン ク(辺)に よ っ て ネ ッ トワ ー ク を 記 述 した も の で あ る(図1.1).グ ラ フ理 論 は1736年 に オ イ ラ ー が ケ ー ニ ヒ ス ベ ル ク問 題 を 証 明 す る 際 に グ ラ フ を 用 い た こ と に よ っ て 切 り開 か れ た 分 野 で あ る[8,9].グ ラ フ理 論 に よ っ て グ ラ フ の 解 析 的 な取 り扱 い が 可 能 に な り,1959年 に エ ル デ シ ュ とア ル フ レ ッ ド ・レ ー ニ ィが 考 案 した ラ

ン ダ ム グ ラ フ(ERモ デ ル)な ど は 興 味 深 い 性 質 を 有 して い た[10】.

一 方 で,現 実 社 会 の ネ ッ トワ ー クの 構 造(社 会 ネ ッ トワ ー ク)を 探 る研 究 は 社 会 学 分 野 を 中 心 に 行 わ れ た.1960年 代 に ハ ー バ ー ド大 学 の 社 会 心 理 学 者 ミル グ ラ ム に よ る 大 量 の サ ン プ ル 実 験 に よ っ て ス モ ー ル ワ ー ル ド現 象 を 確 認 した 実 験 が 行 わ れ た.こ の 実 験 は 全 く面 識 の な い 二 人 が 何 人 の 知 人 を 辿 っ て い く とつ な が る こ とが で き る か を調 べ た 社 会 実 験 で,平 均 で6人 の 知 人 を介 す る だ け で つ な が る こ とが で き る とい う結 果 を 得 た.こ れ は 「六 次 の 隔 た り」 と い わ れ,最 も有 名 な ス モ ー ル ワ ー ル ド現 象 の 一i例で あ る[11】.

ま た1970年 代 に ハ ー バ ー ド大 学 の 大 学 院 生 の グ ラ ノ ベ ッ タ ー の 転 職 に 関 す る実 験 に よ っ て も社 会 ネ ッ トワ ー ク分 析 は 発 展 を み せ た.こ れ は,人 々 が 職 探 しを す る 際 に 有 効 な 紹 介 者,情

2第1章 序 論

図1.1=ノ ー一 ド と リ ン ク に よ っ て 記 述 さ れ た ネ ッ ト ワ ー ク

報 提 供 者 とな る こ とが 多 い の は,家 族 や 会 社 の 同 僚 の よ うな 普 段 親 密 に接 して い る身 近 な 人 間 との つ な が りで あ る 「強 い 紐 帯 」 で は な く,学 生 時 代 の 古 い 友 入 や 取 引 先 の 数 回 しか 話 した こ との な い よ う な普 段 あ ま り接 す る こ と無 い 人 間 との つ な が りで あ る 「弱 い 紐 帯 」 で あ る こ と を 明 らか に した.こ れ は 「弱 い 紐 帯 の 強 み 」 と言 わ れ る[12】.

社 会 学 分 野 で 様 々 な 社 会 ネ ッ トワ ー ク に 共 通 す る 性 質 が 発 見 さ れ る 一 方 で,1990年 代 に コ ー ネ ル 大 学 の 大 学 院 生 の ワ ッ ツ と同 大 学 教 官 の ス トロ ガ ッ ツ に よ っ て 「ワ ッ ツ ・ス トガ ッ ツ モ デ ル 」(WSモ デ ル)と い う グ ラ フ の 数 学 モ デ ル が 考 案 さ れ る.こ れ は ス モ ー ル ワ ー ル ド現 象 へ の 理 論 的 な 解 析 を 試 み る こ と を可 能 に した そ れ 以 前 に は な い 数 学 的 手 法 を 取 り入 れ た 研 究 で あ る.こ れ は 現 実 社 会 の 様 々 な ネ ッ トワー ク に 対 して 共 通 な 性 質 で あ る,ス モ ー一ル ワ ー ル ド 性 と 「友 達 の 友 達 は 友 達 」 と い っ た ク ラス タ性 の 両 方 の 性 質 を 満 た す 数 学 モ デ ル で あ る[13].

この モ デ ル の 構 築 は様 々 な 分 野 で の ネ ッ トワ ー クを 考 え る上 で 大 き な 注 目 を 集 め,複 雑 ネ ッ ト ワー ク の 研 究,グ ラ フ 理 論 に お い て ひ とつ の ブ レイ ク ス ル ー とな っ た.

1.2研 究 目 的3

さ らに,ほ ぼ 同 時 期 に バ ラバ シ に よ っ て 「バ ラバ シ ・ア ル バ ー トモ デ ル 」(BAモ デ ル)が 考 案 さ れ る.現 実 の 複 雑 ネ ッ トワ ー クが もつ ス モ ー ル ワー ル ド性 と ク ラ ス タ性 以 外 の 重 要 な性 質 で あ る ス ケ ー ル フ リー 性 を もつ グ ラ フ の 数 学 モ デ ル で あ る[14].ス ケ ー ル フ リー 性 とは グ ラ フ の 次 数 分 布 に 関 す る性 質 で あ る.グ ラ フの 次 数 とは 各 ノ ー ドが もつ リ ン ク数 で あ る.グ ラ フ の 次 数kと 正 の 定 数 α とす る と,次 数 分 布P㈹ がP(k)(xk一 α に 比 例 す る と き ス ケ ー ル フ リー 性 を もつ(ス ケ ー ル フ リー グ ラ フ).ス ケ ー ル フ リー 性 を 有 す る ネ ッ トワ ー ク は様 々 な 具 体 例 が 見 つ か っ て い る.男 女 の 性 的 関 係,WWW,学 術 論 文 の 共 同 執 筆 数 な どで が あ り,こ の モ デ ル は 前 述 のWSモ デ ル に 比 べ,社 会 学 的 な ネ ッ トワ ー ク構 造 の 観 点 か ら意 義 の 強 い モ デ

ル で あ る とい え る.

WSやBAモ デ ル の も つ 性 質 は ネ ッ トワー クの 性 質 は 社 会 ネ ッ トワー ク 以 外 の 様 々 な 分 野 の 大 規 模 複 雑 ネ ッ トワ ー ク に も確 認 され,様 々 な ネ ッ トワ ー ク研 究 の 基 礎 とな っ て い る.グ ラ フ 理 論 は 生 物 学,化 学,物 理 学,社 会 学 な ど,分 野 を 問 わ ず 様 々 な ネ ッ トワ ー ク を考 え る 上 で 応 用 され て い る[21,22,23].

1.2研 究 目 的

ス ペ ク トル グ ラ フ理 論 で は ラ プ ラ シ ア ン 行 列 と呼 ば れ る ネ ッ トワー ク の グ ラ フ構造 を 含 ん だ 行 列 の 固 有 値,固 有 ベ ク トル が グ ラ フ 分 析 に 利 用 され る[15].行 列 の 固 有 値 や 固 有 ベ ク トル を 利 用 した グ ラ フ分 析 の 基 礎 は ホ フ マ ン と ドナ ー ト らに よ っ て 考 案 さ れ た[16].

ス ペ ク トル グ ラ フ理 論 で は0で な い 最 小 固 有 値 と固 有 ベ ク トル が グ ラ フの 連 結 性 を 示 す 指 標 と して 知 られ て い る.例 え ば,第2章 で も論 じ るが,ラ プ ラ シ ア ン行 列 の 最 小 の 固 有 値 は0 に な り,最 小 固 有 値 の 重 複 数 が グ ラ フの 連 結 数 に 一 致 す る こ とが 知 られ て い る.さ ら に,2番

目 に小 さ い0で な い 固 有 値 に属 す る 固 有 ベ ク トル は フ ィ ー ドラ ー ベ ク トル(Fiedlervector)と 呼 ば れ る.フ ィー ドラ ー ベ ク トル を 分 析 す る こ とで あ る特 定 の リ ン ク を抽 出 す る こ とが で き る [17,18,19].フ ィー ド ラー ベ ク トル は グ ラ フの ク ラ ス タ構 造 を抜 き 出 す こ とが で き・ グ ラ フ分 割 問 題 に も応 用 さ れ る[20].

ま た,フ ィ ー ドラ ー ベ ク トル に よ っ て 抽 出 で き る リ ン ク は社 会 ネ ッ トワ ー ク分 析 に 利 用 さ れ,上 述 し た 社 会 学 的 に 重 要 な ク ラ ス タ 間 を 結 ぶ リ ン ク(弱 い 紐 帯)の 特 定 に 利 用 す る こ とが で き る.

ラ プ ラ シ ア ン 行 列 の 小 さ な 固 有 値 や フ ィ ー ドラー ベ ク トル を用 い た 社 会 ネ ッ トワ ー ク分 析 へ の 応 用 が 進 ん で い る一 方 で,ラ プ ラ シ ア ン行 列 の 大 きな 固 有 値 や そ れ に 属 す る 固 有 ベ ク トル の 社 会 ネ ッ トワ ー ク 分 析 へ の 応 用 は 十 分 に 行 わ れ て い な い とい え る.そ れ は,未 だ に ラ プ ラ シ ア ン行 列 の 固 有 値 や 固 有 ベ ク トル の 性 質 と対 応 す る社 会 ネ ッ トワ ー ク を 記 述 した グ ラ フ構 造 との 関 係 の 理 解 が 不 十 分 な為 だ と考 え られ る.

そ こで,本 稿 で は ラ プ ラ シ ア ン行 列 の 正 の最 大 固 有 値 に 属 す る 固 有 ベ ク トル を 分 析 し,実 際

4第1章 序 論

の グ ラ フ構 造 との 関 係 を 明 らか に す る こ とを 目的 とす る.

1.3構 成

本 論 文 の 構 成 は 以 下 の 通 りで あ る.第2章 で は,ラ プ ラ シ ア ン行 列 の 概 要 に つ い て 述 べ, ネ ッ トワ ー ク グ ラ フ を 代 数 的 に取 り扱 う方 法 を 述 べ る.ま た ラ プ ラ シ ア ン 行 列 の 固 有 値 や 固 有 ベ ク トル を 分 析 す る こ とで 得 られ る グ ラ フの 性 質 に つ い て も述 べ る.さ ら に ラ プ ラ シ ア ン行 列 の 固 有 値 問 題 と ラ プ ラ シ ア ン行 列 の 二 次 形 式 の 関 係 に つ い て 論 じ る.第3章 で は,ラ プ ラ シ ア ン行 列 の 固 有 値 問 題 を 踏 ま え,ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る固 有 ベ ク トル が ど の よ う な グ ラ フの 構 造 を 表 して い る か を 実 験 に よ っ て 調 査 した 結 果 を 示 す.第4章 で は,ラ プ ラ シ ア ン行 列 の 固 有 値 問 題 とパ ス グ ラ フの ノー ドの 重 み の 最 適 配 置 を 証 明 を 行 う.第5章 に 結 論 を 述 べ る.

5

第2章

ラ プ ラ シ ア ン行 列 の概 要

本 章 で は,本 稿 で 用 い る ラ プ ラ シ ア ン行 列 の 定 義 や 性 質 に つ い て[15]に 基 づ き 述 べ る.次 に,ラ プ ラ シ ア ン行 列 の ス ペ ク トル と ノ ー ドの 重 み の 関 係 に 関 して 述 べ る.

2.1ラ プ ラ シ ア ン 行 列 の 基 礎

2.1.1ラ プ ラ シ ア ン 行 列 の 定 義

グ ラ フ を 代 数 的 に 扱 う 方 法 の 一 つ と し て 行 列 を 用 い て グ ラ フ 構 造 を 表 現 す る 方 法 が 存 在 す る.本 稿 で は 無 向 グ ラ フ を 分 析 に 用 い る.無 向 グ ラ フ をGと し,n佃 の ノ ー ド の 集 合 を V={0,1,̲,n‑1},リ ン ク の 集 合 をEと す る.ノ ー ドiか ら ノ ー ド 」 を つ な ぐ リ ン ク が 存 在 す る と き(i,の ∈Eで あ る.こ の と き 隣 接 行 列(adjacencymatrix)Aは 以 下 の よ う に 定 義 さ れ る.

ん・一{1撫i二E

隣 接 行 列 は グ ラ フGの リ ン ク情 報 を 記 述 し た 行 列 で あ る.例 え ばAk(k=0,1,2,3,...)の

(i,」)成 分 は,グ ラ フG上 の ノ ー ドiか ら ノ ー ド 」 へ の 長 さkの 経 路 数 を 表 し て い る.図2.1 の よ う な グ ラ フ の ノ ー ド0か ら ノ ー ド4へ の 長 さ2の 経 路 数 は 図2.1の 隣 接 行 列 の 式2.3の (1,5)成 分 を 見 れ ば 知 る こ と が で き る.式2・3の(1,5)成 分 は3な の で ノ ー ド0か ら ノ ー ド4 へ の 長 さ2の 経 路 数 は3で あ る.実 際 の 経 路 は 図2.2で あ る.

A=

01⊥‑⊥‑∩) ‑⊥01⊥01← ■⊥00(U■⊥

‑←‑⊥(UO‑← 01⊥‑⊥‑⊥∩)

(2.2)

6第2章 ラ プ ラ シア ン行列 の概 要

A2=

001←10り0

0り白り白り白0

1⊥り白QUり白11

1←り0り白り白‑⊥

001⊥‑⊥03

(2.3)

図2.1:グ ラ フ

2.1ラ プ ラ シ ア ン 行 列 の 基 礎7

(a)経 路1 (b)経 路2

(c)経 路3

図2.2:長 さ2の ノ ー ド0か ら ノ ー ド4へ の 経 路

こ の よ う に,隣 接 行 列 は グ ラ フ の 性 質 を 代 数 的 に 調 べ る こ と に 利 用 可 能 で あ る.

次 に,ノ ー ドi(i=0,1,̲,n‑1)の 次 数 をdiと し た と き,次 数 行 列(degreematrix)D は 以 下 の よ う に 定 義 さ れ る.

Diゴ=diδiゴ

δ乞ゴ は ク ロ ネ ッ カ ー の デ ル タ で,

喝一{1翻

とな る 関 数 で あ り,単 位 行 列1の 成 分 で あ る.

以 上 の 隣 接 行 列 と次 数 行 列 か ら ラ プ ラ シ ア ン行 列 五 は 以 下 の よ う に 定 義 さ れ る.

(2.4)

8第2章 ラプ ラ シア ン行 列の概 要

五:=五)‑A(2.5)

ラ プ ラ シ ア ン 行 列 は グ ラ フ ラ プ ラ シ ア ン(graphlaplacian)と も 呼 ば れ る .ラ プ ラ シ ア ン 行 列 も 隣 接 行 列 同 様 に,グ ラ フ の 性 質 を 代 数 的 に 調 べ る 際 に 有 用 な 行 列 で あ る.図2.3は ノ ー ド数 4の グ ラ フ か ら な る ラ プ ラ シ ア ン 行 列 の 例 で あ る .

ー

例0030列フ一丁そラ0200数グ3000次

の ー の

=

D

ー

1101列行1010接

隣01←■⊥‑⊥

ー 切

=/1

ー

d2do"

プ3dd4ラ

ー の

図2.3:ラ プ ラ シ ア ン 行 列 の 例

2.1.2ラ プ ラ シ ア ン行 列 の 性 質

無 向 グ ラ フ か ら定 義 さ れ る ラ プ ラ シ ア ン行 列 は 実 対 称 行 列 とな る.実 対 称 行 列 の 性 質 と して 以 下 の も の が あ る.

● 固 有 値 は,重 複 す る(縮 退 す る)場 合 で も 区別 して 数 え れ ば,全 て 実 数 で η 個 存 在 す る.

● 異 な る 固 有 値 に 属 す る固 有 ベ ク トル は 直 交 す る.

● 同 じ固 有 値 に属 す る固 有 ベ ク トル も,適 当 な 方 法 で 直 交 化 す る こ とが で き,π 本 の 長 さ 1の 固 有 ベ ク トル はn次 元 空 間 の 正 規 直 交 基 底 を張 る.

さ ら に ラ プ ラ シ ア ン 行 列 の 他 の 性 質 を 以 下 に示 す.

ラ プ ラ シ ア ン行 列 の0固 有 値 の 重 複(縮 退)に つ い て,以 下 の 式

五記=λ 忽 (2.6)

2.2ラ プ ラ シ ア ン行 列 の 固 有 値 問 題9

に つ い て 考 察 す る.ラ プ ラ シ ア ン 行 列 の 定 義 よ り,各 行 の 行 和 が0に な る の で,x=

t(1,1,1,...,1)は 固 有 値0の 固 有 ベ ク トル で あ る.グ ラ フGが 非 連 結 で あ る と き,ラ プ ラ シ ァ ン 行 列 の 成 分 を連 結 成 分 ご とに ブ ロ ッ ク 対 角 化 で き る の で,固 有 値0の 重 複 数 は グ ラ フG の 連 結 成 分 数 に 等 し くな る.

ま た,固 有 値 の 範 囲 に つ い て,ラ プ ラ シ ア ン行 列 の 固 有 値 は 全 て0以 上 の 実 数 で 与 え ら れ, 以 下 の よ う に 示 す こ とが で き る.ノ ー ドi(iニ0,1,̲,n‑1)に 重 みCiを 与 え,隣 接 す る ノー ド(i‑」)の 重 み の 差(Xi一 餌ゴ)を 考 え る.グ ラ フG全 体 で の 重 み の 差 の 自 乗 和 を 以 下 の よ うに 定 義 す る.

F({Vi})・ 一 Σ(Xi‑xゴ)2≧0(2・7)

(i"')∈E

和 の 範 囲(i,の はGの 全 て の リ ン ク に 関 す る和 を 表 す.次 に 各 ノー ドの 重 み を 成 分 に もっ 列 ベ ク トル 忽 を 以 下 の よ う に定 義 す る.

X:=t(XO,ω1,ω2,̲,Xn̲1)

こ こ でt(・)は 転 置 を 表 し て い る.ま た,2Xirj=ω 乞賜+銑 賜 と 分 解 す る と

F({Vi})一 Σ((Vi)2+@ゴ)2‑2鋤)

(z,3)∈E

一 Σdi(Xi)2一 Σ ・・吻 一 Σ 雛

i∈E(t,3)∈E(i,ゴ)∈E

す な わ ちF({ci})は ラ プ ラ シ ア ン 行 列 の 二 次 形 式(quadraticform)で

F({ω 乞})=txLx

(2.8)

(2.9)

と 記 述 で き る.式(2.7)か ら ラ プ ラ シ ア ン 行 列Lは 固 有 値 が 全 て 非 負 で あ る 非 負 定 値 行 列 (non‑negativedefine)で あ る.

2.2ラ プ ラ シ ア ン 行 列 の 固有 値 問 題

本 節 で は,本 稿 の 分 析 の 主 題 で あ る ラ プ ラ シ ア ン行 列 の 最 大 の 固 有 値 に 属 す る固 有 ベ ク トル と式(2.7)の 対 応 関 係 に つ い て 述 べ,本 稿 の 主 題 で もあ る ラ プ ラ シ ア ン 行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル を 分 析 す る意 義 に つ い て 論 じ る.

ノ ー ドの 重 み を 成 分 に も つ ベ ク トルxの 大 き さ をlxl=1と し た 制 約 条 件 下 に お け る

10第2章 ラ プ ラ シア ン行列 の概 要

F({Xi})の 停 留 値 問 題 を 考 え る.ラ グ ラ ン ジ ュ未 定 乗 数 法 を導 入 し

を 定 義 し, で あ る.

Φ(x・λ):‑F({Ci})一 λ(ぴ 一1)

一 晶 幅 声 一λ(Σ ω…‑1 i∈v)

∂Φ/∂ri=0と ∂Φ/∂λ=0を 解 け ば よ い.こ こ で λ は ラ グ ラ ン ジ ュ の 未 定 乗 数

∂響 一黒2幅)‑2Axi‑・

∂響 一ぴ 一1‑・

こ こ で,∂ 乞 は ノ ー ド 乞の 隣 接 ノ ー ドの 集 合 で あ る.整 理 す る と

Σ(伽 ㊥ 一 λXi,Σ ω暑一1

ゴ∈∂ii∈v さ ら に

Σ@仁 吻 一DiXi一 Σxゴ ー λVi

ゴ∈∂乞 ゴ∈∂芭

とな る の で,ラ プ ラ シ ア ン 行 列 を 用 い る と制 約 条 件1副=1の も とで Lx=λx(2.10)

を 満 た す λ と 記 を 求 め る 問 題 に,す な わ ち ラ プ ラ シ ア ン行 列 の 固 有 値 問 題 に 帰 着 す る.ラ グ ラ ン ジ ュ の 未 定 乗 数 λ は ラ プ ラ シ ア ン行 列 の 固 有 値 に な っ て お り,最 大 固 有 値 と最 小 固 有 値 は そ れ ぞ れF({Ci})の 最 大 値 と最 小 値 に 対 応 す る.ま た,式(2.10)を 満 た すxは 固 有 値 λ に 属 す る 固 有 ベ ク トル で あ る.

本 稿 で は,ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 とそ れ に 属 す る固 有 ベ ク トル に つ い て グ ラ フ構 造 と の 関 係 を 調 査 す る実 験 を 行 う.ま た,関 数F({Xi})と ラ プ ラ シ ア ン行 列 の 固 有 値 問 題 との 対 応 関 係 に よ っ て 実 験 結 果 の 理 論 的 考 察 を 行 い,ラ プ ラ シ ア ン行 列 の 固 有 ベ ク トル と グ ラ フ 構 造 との 対 応 関 係 を 明 らか に す る.

2.3代 数 的 連 結 性 と フ ィ ー ドラ ー ベ ク トル

本 節 で は,ラ プ ラ シ ア ン行 列 の 固 有 ベ ク トル を用 い た グ ラ フ構 造 の 分 析 例 と して,「 代 数 的 連 結 性 」 と ラ プ ラ シ ア ン行 列 の0で な い 最 小 固 有 値 と そ れ に 属 す る 「フ ィー ド ラー ベ ク トル 」

2.3代 数 的 連 結 性 と フ ィ ー ドラ ー ベ ク トル11

と呼 ば れ る固 有 ベ ク トル に 関 して 述 べ,ラ プ ラ シ ア ン 行 列 の 小 さ い 固 有 値 に属 す る 固 有 ベ ク ト ル の 分 析 例 と グ ラ フ構 造 の 関 係 に つ い て 紹 介 す る.

あ る無 向 グ ラ フGに つ い て 考 え る.(7ラ プ ラ シ ア ン 行 列 の 固 有 値 を 小 さ い 順 に 番 号 を っ け て

0=λo≦ λ1≦ λ2≦ … ≦ λn̲1

とす る.も し グ ラ フGが 連 結 で あ る場 合,ラ プ ラ シ ア ン 行 列 の 固 有 値0の 重 複 数 は1,λo=0, λ1>0と な る.こ の λ1と そ れ に 属 す る 固 有 ベ ク トル に 関 して,グ ラ フ の 連 結 性 を 変 化 させ

た と きの 値 の 変 化 を 分 析 す る.

仮 に,リ ン ク を 除 去 す る こ と に よ っ て グ ラ フGを2つ に分 割 した とす る.す る と グ ラ フ の 連 結 成 分 は2で あ り λ1=0と な る は ず で あ る.強 固 に 結 び つ い た グ ラ フで は λ1の 値 は大 き く,2つ の ク ラ ス タ 同 士 を 結 ぶ リ ン ク が1本 しか な い よ う な 分 割 が 容 易 に 行 え る グ ラ フ で は λ1が 小 さ くな る.つ ま り,λ1は グ ラ フ の 連 結 の 強 さ を 表 す 指 標 と して み な す こ とが で き る.

連 結 で あ る グ ラ フ の0で な い 最 小 固 有 値 λ1は 代 数 的 連 結 性(algebraicconnectivity)と 呼 ば れ る[17].

図2.4は 図2.5の よ う に グ ラ フの 連 結 性 の 強 さ を 変 化 させ た と き の 代 数 的 連 結 性 λ1の 値 の 変 化 を 示 し た も の で あ る.連 結 性 の 強 さ に応 じて λ1が 変 化 して お り,最 終 的 に 完 全 に 分 割 さ れ た グ ラ フで は 代 数 的 連 結 性 の 値 が0に な る様 子 を 示 して い る.

12第2章 ラ プ ラシ ア ン行 列 の概 要

1.2

加 864む ねむ

惹≧七Φ⊆⊆8∪ σ﹂ΩΦ9σ

0.2

0.0 A BC

graph」D

図2.4:代 数 的 連 結 性

D

2.3代 数 的 連 結 性 と フ ィ ー ド ラ ー ベ ク トル13

(a)グ ラ フA (b)グ ラ フB

(c)グ ラ フC (d)グ ラ フD

図2.5:連 結 性 の 変 化

ま た,λ1に 属 す る 固 有 ベ ク ト ル は フ ィ ー ド ラ ー ベ ク トル と 呼 ば れ る.フ ィ ー ド ラ ー ベ ク ト ル を 分 析 す る こ と で ク ラ ス タ 構 造 を 抽 出 し た り,ク ラ ス タ 問 を 結 ぶ リ ン ク を 特 定 す る こ と が で き る.図2.6,2.7は フ ィ ー ド ラ ー ベ ク トル の 分 析 例 で あ る.図2.6の グ ラ フ に 対 す る フ ィ ー ド ラ ー ベ ク トル の 計 算 結 果 が 図2.7で あ り,ベ ク トル 成 分 を 各 ノ ー ドの 対 応 し て 並 べ た も の で あ る.ベ ク トル 成 分 は3つ の グ ル ー プ に 分 か れ て い る.図2.7の フ ィ ー ド ラ ー ベ ク トル に よ る グ ル ー プ が 図2.6の ク ラ ス タ 群 に 対 応 し て い る.

グ ラ フ 構 造 の 観 点 で は フ ィ ー ド ラ ー ベ ク ト ル を 利 用 し た 分 析 が 広 く 知 ら れ,グ ラ フ 分 割 は 画 像 処 理 な ど の 様 々 な 分 野 に 応 用 さ れ て い る[24].

ラ プ ラ シア ン行列 の概 要 第2章

図2.6:3つ の ク ラ ス タ か ら な る グ ラ フ 14

2.3代 数 的 連 結 性 と フ ィ ー ドラ ー ベ ク トル 15

0.4

0.3

0.2

0.1

0.0

‑0 .1

‑0 .2

‑0 .3

‑0 .4

‑O .50

1 234567

NodeID

図2.7:フ ィ ー ド ラ ー ベ ク ト ル の 成 分

8 9 10

16

第3章

ラ プ ラ シア ン行 列 の最 大 固 有 値 に属 す る 固 有 ベ ク トル が 表 す グ ラ フ構 造

の 実 験 的考 察

本 章 で は,ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に 属 す る固 有 ベ ク トル が 表 す グ ラ フ構 造 を 実 験 に よ っ て 調 査,考 察 した 結 果 を述 べ る.

3.1リ ン ク の 存 在 に 関 す る 予 想 と実 験

ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る 固 有 ベ ク トル の 性 質 と して 以 下 の 性 質 が 成 り立 つ と 予 想 した.

● ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル に つ い て,そ の 要 素 が 最 大 と最 小 とな る 要 素 に 対 応 す る ノ ー ド間 に は リン クが 存 在 して い る.

3.1リ ン ク の 存 在 に 関 す る 予 想 と 実 験17

図3.1:グ ラ フC

86﹂4200ハUOOO 2﹂400一一 fO800一一

eigenvector

41025673

Node」D

図3.2:モ デ ルC最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

図3.1の グ ラ フ を用 い て 実 験 の 手 順 と見 方 につ い て 説 明 す る.図3.1の グ ラ フ に 対 応 す る ラ プ ラ シ ア ン行 列 を 作 り,最 大 固 有 値 に 属 す る 固 有 ベ ク トル を 計 算 す る(数 値 計 算 に はPytllon

18第3章 ラ プラ シア ン行 列 の最 大固 有値 に属 す る固有 ベ ク トル が表 す グ ラ フ構 造 の 実験 的考 察

の 拡 張 モ ジ ュ ー ルNumPyで 行 っ た).図3.2は 計 算 した 固 有 ベ ク トル を ソ ー ト して プ ロ ッ ト し た もの で あ る.た だ し,図3.2の 横 軸 は 固 有 ベ ク トル の 要 素 と対 応 す る ノ ー ドのIDで あ る.

そ の 固 有 ベ ク トル 要 素 の 最 大 と最 小 に 対 応 す る ノー ド間 に リ ン ク が 存 在 す る か を 確 認 す る.図 3.2の 最 大 要 素 に 対 応 す る ノ ー ドIDは ノ ー ド3,最 小 要 素 に 対 応 す る ノ ー ドIDは4で あ る.

図3.1で 確 認 す る と実 際 に 固 有 ベ ク トル の 最 大 と最 小 要 素 の ノ ー ド3‑4間 に リ ン ク が 存 在 し て い る こ とが 確 認 で き る.

以 上 の よ う に様 々 な ノ ー ド数 や トポ ロ ジ で リ ン ク の 存 在 に 関 す る実 験 を 行 っ た 結 果 を 次 節 で 示 す.

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果

本 節 で は3.1節 に従 い,様 々 な グ ラ フ で ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る固 有 ベ ク ト ル の 最 大 と最 小 要 素 に 対 応 す る ノ ー ド間 に リ ン クが 存 在 す る こ と を 確 認 した 実 験 結 果 を 示 す.

実 験 は そ れ ぞ れ,ノ ー ド数 や トポ ロ ジ の 異 な る15の グ ラ フ に 対 して 行 っ た.

図3.3〜 図3.33は 実 験 を 行 っ た15の グ ラ フ と そ れ ぞ れ の 最 大 固 有 値 に属 す る固 有 ベ ク トル を プ ロ ッ トし た 結 果 で あ る.ま た 実 験 結 果 の 確 認 項 目 を 表3.1に ま と め た.

図3.3:グ ラ フ モ デ ル1

8642000000 2400一一 6800一一

NodeID

図3.4:モ デ ル1最 大 固 有 値 に 属 す る 固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果19

図3.5:グ ラ フ モ デ ル1.2

0.6

0.4

0.2‑

0,0

‑0 .2・

‑0 .4

‑0 ・655170624

Node ‑ID

図3.6:モ デ ル1.2最 大 固 有 値 に 属 す る 固 有 ベ ク トル

20第3章 ラ プラ シア ン行列 の最 大固 有値 に属 す る固有 ベ ク トル が表 すグ ラ フ構造 の実 験 的考 察

図3.7:グ ラ フ モ デ ル1.3

o.4

o.3

o.2

O,1

O.0

一〇ユ

一〇2

一 〇.3

一θ』

eigenvector

79511313115014

Node」D

21241068

図3.8:モ デ ル1.3最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果21

図3.9:グ ラ フ モ デ ル2

6圃20α0αα 2400一一 6R︾00

一一 01︒

一

eigenvector

●

●

● ●

●

20341

Node ̲iD

図3.10:モ デ ル2最 大 固 有 値 に 属 す る固 有 ベ ク トル

22第3章 ラ プラ シア ン行 列 の最大 固有 値 に属 する 固有ベ ク トル が表 す グ ラ フ構 造 の 実験 的考 察

図3.11:グ ラ フ モ デ ル3

0.8

0.6

0.4

0。2

0.0

一 〇 .2

一 〇.4・

一 〇.6・

一 〇.8

1 3 45

Node」D

0 2

図3.12:モ デ ル3最 大 固 有 値 に属 す る 固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果23

図3.13:グ ラ フ モ デ ル4

eigenvector O.6

0.4

0.2

0.0

‑0 .2・

‑O .4

‑0・6

665432i

Node ‑ID

図3.14:モ デ ル4最 大 固 有 値 に 属 す る固 有 ベ ク トル

24第3章 ラ プラ シ アン行 列 の最 大固 有値 に属 す る固有 ベ ク トルが 表す グ ラ フ構 造 の 実験 的 考察

図3.15:グ ラ フ モ デ ル5

08642010α000 20一 40一

130i

Node」D

図3.16:モ デ ル5最 大 固 有 値 に 属 す る 固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果25

図3.17:グ ラ フ モ デ ル6

fO4へ∠

0︒0︑α 0 0 920一 4 0一 6 0一

eigenve⊂tor

042913

Node」D

図3.18:モ デ ル6最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

26第3章 ラプ ラ シア ン行 列 の最大 固 有値 に属 す る固有 ベ ク トル が 表す グ ラ フ構 造 の 実験 的考 察

図3.19:グ ラ フ モ デ ル7

0.6

O.4

0.2

0.0

一〇 .2

一 〇.4

一 〇.6

0 4 25

Node ̲ID

1 3

図3.20:モ デ ル7最 大 固 有 値 に 属 す る固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果27

図3.21:グ ラ フ モ デ ル8

eigenvector 1.0

0.8

0.6

0.4・

0.2・

O.O・

‑0 .2・

‑0 .4

‑0 .62356104

Node ̲ID

図3.22:モ デ ル8最 大 固 有 値 に属 す る 固 有 ベ ク トル

28第3章 ラ プラ シア ン行 列 の最 大固 有値 に属 す る固 有ベ ク トルが 表 す グ ラフ構 造 の実 験 的考 察

図323:グ ラ フ モ デ ル9

α価

e.4

02

o.o

一e .2

一 〇.4・

一 〇.6

eigenve⊂tor

4870311122

Node」D

951016

図3.24:モ デ ル9最 大 固 有 値 に属 す る固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果29

図3.25:グ ラ フ モ デ ル10

eigenve⊂tor O.4

0.2

0.0・

‑O .2

‑O .4

‑0.6・

‑0 .8

‑1 .0213761289111631910511517181440

NodelD

図3.26:モ デ ル10最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

30 第3章 ラ プ ラシ ア ン行 列 の最 大 固有値 に属 す る固有 ベ ク トルが 表 す グラ フ構造 の実験 的考察

図3.27:グ ラ フ モ デ ル11

eigenvector O.4

0.2

0.0・

‑0 .2

‑0 .4・

‑0.6

‑0 .8

‑1 ・00420三12…252923101526181281319121624627179142711853 Node ̲ID

図3.28:モ デ ル11最 大 固 有 値 に 属 す る 固 有 ベ ク トル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果 31

図3.29:グ ラ フ モ デ ル12

eigenvector O.6

0.4

0.2

0.0

‑O .2

‑O .4

‑0 .6

‑0 ・8911213左60182171614515871119103

Node ̲ID

図3.30:モ デ ル12最 大 固 有 値 に 属 す る 固 有 ベ ク トル

32 第3章 ラプ ラ シア ン行列 の 最大 固有 値 に属 する固 有ベ ク トル が表 す グ ラ フ構 造 の 実験 的 考察

図3.31:グ ラ フ モ デ ル13

4一﹂﹁∠‑ゐ

000,α 0100

一 ﹁∠300

一一 4500一一

●

●

●

●

● ● ● ●

●

●

●

eigenvec隼0「

● ● ● ● ●

●

● ● ●

● ●

● ● ●

●

● ●

・ 「

き16112215142言252162317292847101202δf52724613213ξ18 Node」D

図3.32:モ デ ル13最 大 固 有 値 に 属 す る 固 有 ベ ク ト ル

3.2リ ン ク の 存 在 に 関 す る 実 験 結 果33

図3.33:グ ラ フ モ デ ル14

eigenvector O.4

0.2・

0.0

‑0.2・

‑O .4

‑0 .6・

‑0 .8

‑1.0

913171861171521031619124511480

Node」D

図3.34:モ デ ル14最 人 固 有 値 に 属 す る 固 有 ベ ク ト ル

図3.25〜 図3.28は,そ れ ぞ れ ノ ー ド数20と30で 生 成 し たBAグ ラ フ で あ る.図3.25,図 3.27の グ ラ フ は ど ち ら と も 次 数 分 布 が ・P(k)(xk一 α(α=2)に 従 う よ う 生 成 し た.さ ら に,図

34第3章 ラプ ラ シア ン行 列 の最大 固有 値 に属 する固 有 ベ ク トル が表 す グ ラ フ構 造 の実 験 的考 察

表3.1:各 グ ラ フモ デ ル の 実 験 結 果

グ ラ フ モ デ ル1 固 有 ベ ク トル 最 小 固 有 ベ ク トル 最 大 対 応 ノ ー ド間 の リ ン ク

1 1 2 有

1.2 3 4 有

1.3 7 8 有

2 2 1 有

3 1 2 有

4 6 1.2 有

5 1 2 有

6 0 3 有

7 0.4 1.3 有

8 2 4 有

9 4 6 有

10 2 0 有

11 0 3 有

12 9 3 有

13 8 18 有

14 9 0 有

3.25の ノ ー ド0と ノ ー ド2,図3.27の ノ ー ド0と ノ ー ド3は そ れ ぞ れ の グ ラ フの ハ ブ ノー ド (最 大 次 数 ノ ー ド)で あ る.

図3.29〜 図3.32は,そ れ ぞ れ ノ ー ド数20と30で 生 成 したWSモ デ ル で あ る.図3.29,図 3.31の グ ラ フ は ど ち ら と も初 期 次 数4で リ ン ク の 張 り替 え 確 率0.2の パ ラ メ ー タで 生 成 し た.

図3.33は ノ ー ド数20,2点 間 の 接 続 確 率0.3の パ ラ メ ー タ で 生 成 し た ラ ン ダ ム グ ラ フ で あ る.

どの 実 験 結 果 に お い て も固 有 ベ ク トル 要 素 の 最 大 と最 小 要 素 に 対 応 す る ノ ー ド問 に リ ン ク が 存 在 して い る こ とが 確 認 で き る.実 験 に よ っ て 確 認 した 全 て の 結 果 で,ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る 固 有 ベ ク トル 要 素 の 最 大 と最 小 に 対 応 す る ノ ー ド間 に リ ン クが 存 在 す る こ と が い え る.

ま た,本 稿 に 示 した 実 験 よ りノ ー ド数 の 大 き い大 規 模 グ ラ フで の 実 験 結 果 は 確 認 済 み で は あ るが,結 果 を 視 覚 的 に 分 か りや す く確 認 す る た め に 適 切 で な い こ と,ま た そ の 結 果 を視 覚 的 に 分 か りや す く表 示 す る方 法 は グ ラ フの ノ ー ド配 置 問 題 の 領 域 で あ り,本 稿 の 目 的 と は 外 れ る た

め ノ ー ド数30以 上 で の グ ラ フモ デ ル で の 実 験 結 果 は本 稿 で は 割 愛 す る.

35

第4章

最 大 固 有 値 に属 す る固有 ベ ク トル と グ ラ フ構 造 の 関係 に関 す る 予 想

本 章 で は,第2章 で 述 べ た ラ プ ラ シ ア ン行 列 の 二 次 形 式 と固 有 値 とそ れ に 属 す る 固 有 ベ ク ト ル の 対 応 関 係 を 踏 ま え,ラ プ ラ シ ア ン 行 列 の 固 有 値 が 最 大 に な る とき の 固 有 ベ ク トル の 条 件 を パ ス グ ラ フ に 対 して 証 明 す る.

4.1ラ プ ラ シ ア ン行 列 の 最 大 固有 値 に関 す る予 想

第3章 で,ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル に つ い て,そ の 要 素 が 最 大 と最 小 とな る要 素 に 対 応 す る ノー ド間 に は リン クが 存 在 して い る.と い う予 想 を実 験 に よ っ て 確 認 した.

さ らに,パ ス や ツ リー な どの 循 環 しな い グ ラ フ構 造 に お い て は 固 有 ベ ク トル 要 素 は グ ラ フ の 中心 か ら順 に絶 対 値 で 大 き くな る傾 向 もみ られ た.

また,BAモ デ ル に よ っ て 生 成 した 図325,図3.27で は 生 成 ア ル ゴ リズ ム の 性 質 よ り,ノ ー ド番 号 の 小 さ い ノー ドが ハ ブ に な りや す い.ハ ブ ノー ドに 対 応 す るベ ク トル 要 素 が 絶 対 値 で 最 大 に な る こ とか ら,グ ラ フ の 何 か 意 味 の あ る,な ん ら か の 中 心 的 な 指 標 を 多 く も っ ノ ー ドが ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル の 最 大,最 小 値 と して 表 れ る と考 え ら れ る.

次 節 で は,「 ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る 固 有 ベ ク トル に つ い て,そ の 要 素 が 最 大 と最 小 とな る要 素 に 対 応 す る ノ ー ド間 に は リ ン クが 存 在 して い る.」 と い う予 想 を 最 も単 純

な グ ラ フ構 造 で あ るパ ス グ ラ フ を用 い て 証 明 した.

36第4章 最 大 固有 値 に属 す る固 有 ベ ク トル とグ ラ フ構造 の関係 に関 す る予想

4.2パ ス グ ラ フ にお け る ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 に属 す る 固 有 ベ ク トル

式(2.9)の ラ プ ラ シ ア ン 行 列 の 二 次 形 式 と 固 有 値 の 関 係 と第2.3節 よ り 関 数F({Xi})を 最 大 に す る 重 み 錫 の 配 置 問 題 を パ ス グ ラ フ で 考 え る.

今,そ れ ぞ れ 重 み を 与 え ら れ た2n個 の ノ ー ドか らパ ス グ ラ フ を 作 る こ と を 考 え る.パ ス グ ラ フ の 重 み は グ ラ フ の 対 称 性 か ら 重 み の 正 負 に よ っ て 図4.1の よ う な2つ の 集 合 に 分 け る こ と が で き る.正 の 重 み をVi(iニ1,2,̲,n),負 の 重 み をyi(i=1,2,̲,n)と す る.正 の 重 み

ノ ー一 ドの 集 合 をVxニ{Xl,x2̲,Xn}負 の 重 み ノ ー ドの 集 合 をV,」={‑Yl,‑Y2̲,‑Yn}

と す る.

正 の 重 み ノー ドの 集 合Vx

●

X1

●

x2

● ●

● ●9

負 の 重 み ノ ー ドの 集 合V}一

● ● ●

‑V2

9● ● 勲

図4.1:重 み 付 き ノ ー ドの 集 合

ノ ー ドの 重 み の 大 小 関 係 は 以 下 の よ う に 決 め て お く.

Xl≧x2≧1;11≧ … ≧Xn̲1≧O

Y1≧Y2≧IJ3≧ … ≧Yn̲1≧0

2つ の 集 合 の い ず れ か か ら1つ ず つ ノ ー ドを 選 択 し て い き,図4.2の よ う に パ ス グ ラ フ を 拡 張 し て 作 る こ と を 考 え る.

(1)ノ ー ド数2の と き

関 数F({Xi,yi})を 最 大 に す る ノ ー ドの 選 び 方 は 明 ら か に 重 み の 最 大 と最 小 のXlと 一Y1の 組 み 合 わ せ で あ る.図4.3,そ の と き

F({Vi,yi})■(x、 一(一 〃、))2(4・1)

(2)ノ ー ド数3の と き

4.2パ ス グ ラ フ に お け る ラ プ ラ シ ア ン 行 列 の 最 大 固 有 値 に 属 す る 固 有 ベ ク トル37

9● ●1● ●

9● ●、 ●9QVi● ● ● 戴

、

、

、も

、 馬

㌔

、、

、ぬ ヤ

● トー● ■レ ● 一一● ・● ■レ ● 一一● 一{}一 ●

図4.2:パ ス グ ラ フ の 作 成 イ メ ー ジ

的

XI‑VI

図4。3:ノ ー ド数2の 重 み の 差 の 自 乗 和 最 大 配 置

ノ ー ドの 選 び 方 は 残 りの ノ ー ドのrliiで重 み が 最 大 か 最 小 の ノ ー ド の い ず れ か で,仮 に 図4.4 の 左 側 の よ う に 玲 か ら ノ ー ド を 選 択 し,最 大 の 重 みx2の ノ ー ド を 先 に 加 え る と す る と,そ の と き

F({Vi,3/i})一@一(‑Yi))2+←y、 一.z'・)2(4・2)

● 一● ・● ● ・ ● 一●

X1‑YlX2‑Y2Xl‑y1

図4.4:ノ ー ド数3の 重 み の 差 の 自 乗 和 最 大 配 置 検 討

(3)ノ ー ド数4の と き

ノ ー ドを 加 え る 場 所 は 図4.5の2通 り考 え られ る..z'1≧ ω2よ りXl側 に 加 え て パ ス グ ラ フ を 拡 張 し た 方 が 加 え る ノ ー ド関 係 な くF({Xi})を よ り大 き く す る.さ ら に ノ ー ド の 選 択 の 仕