ラ ンダ ム行列 を用 いた社 会 ネ ツ ト ワー ク上 の情 報伝 播 特 性 の分 析

修士論文

ラ ンダ ム行列 を用 いた社 会 ネ ツ ト ワー ク上 の情 報伝 播 特 性 の分 析

16892511亀 山 元

指導教員 會田 雅樹 教授

2018年1月

首都大学東京大学院 システムデザ イン研究科 システム デザイ ン専攻 経営 システムデザイ ン学域

Copyrigllt◎2018,KameyamaTsukasa.

一i一

目次

章1231LLL第 章123章123章123章2Z2233a344445辞第第第第謝

序 論

背 景.層....,..』 幽 幽...『 『 層 層

目 的 層 層,,,,幽 幽....引 引 引 引....,,,.

構 成 』...『,.,』...幽....

準 備

ラ プ ラ シ ア ン 行 列...,.,

ERネ ッ ト ワ ー ク とBAネ ッ ト ワ ー ク...

Wi9■erの 半 円 則...+一 』 』 』....一+.一+

ラ ン ダ ム 行 列 の 適 用 可 能 性 の 検 証

概 要...層 層 層 咽,,幽 』.幽 幽...層 『,

ネ ッ ト ワ ー ク 構 造 を 表 し た ラ ン ダ ム 行 列 の 生 成 法

検 証 結 果 と 適 用 条 件̲...,.,,,

情 報 伝 播 特 性 の 分 析

情 報 伝 播 特 性 の 評 価 指 標.,.,.,.,,,,,,

ラ ン ダ ム 行 列 の 性 質 の 適 用,,,,...

妥 当 性 の 検 証,、...,.,,,,.

結 論

参 考 文 献

付 録A正 規 化 ラ プ ラ シ ア ン行 列 の 最 大 固 有 値 と他 の パ ラ メ ー タ の 関 係 性 付 録BWignerの 半 円 則 を 用 い た 初 回 到 達 時 間 の 期 待 値 の 導 出

‑ ⊥ 1 0 0 0 0

一iii一

図 目次

1,1 社 会 ネ ッ ト ワ ー ク の 例 2

■⊥ 9 富 3 4 r O 内り 7 1

9 ρ り 自 9 自 9 白 り 白 り 白 り 白

単 純 な ネ ッ ト ワ ー ク の 例...,....,...

ERネ ッ ト ワ ー ク の 例...,,.,..,...

ERネ ッ ト ワ ー ク の 次 数 分 布.,...,..,...

BAネ ッ ト ワ ー ク の 例...,.,,...

BAネ ッ ト ワ ー ク の 次 数 分 布.,....,...,...,

ラ ン ダ ム 行 列 の ス ペ ク ト ル 密 度 分 布 とWignerの 半 円 分 布..,..,,,..

正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布 ρ(λ)とWignerの 半 円 分

布 双 λ),...,昏...,...̲,,,..

p O O O O O Q σ ∩ U ‑ ⊥ ‑ ⊥ ‑

12

て ⊥ り 自 り 0

り 0 9 0 0 0

3.4

3.5

3.6

ワ ー D 6

り O q σ

3,9

g・=O.5,0.7に 対 す るBAネ ッ ト ワ ー ク の 次 数 分 布,,,....,..

ERネ ッ ト ワ ー ク に 対 す る 最 小 次 数 の2乗 と 平 均 次 数...,

リ ン ク の 重 み を 指 数 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布...,.,,,.,,...

リ ン ク の 重 み を 一 様 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布...,..,,,.,,..,...

リ ン ク の 重 み を カ イ ニ 乗 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布.,...,.,,,

ERネ ッ ト ワ ー ク に 対 す る1E規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ〔λ)と 半 円 分 布 双 λ)の 誤 差 率 ∈...,...,,,,,

BAネ ッ ト ワ ー ク に 対 す る 最 小 次 数 の2乗 と 平 均 次 数+一,...,..,..

リ ン ク の 重 み を 指 数 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布...,,.,,.,,...

リ ン ク の 重 み を 一 様 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列1Vの ス ペ ク ト ル 密 度 分 布,..,...,.,,

' 4 匡 リ

ー ⊥ ‑ ⊥

16

17

17

0 0 ⑪ り ー ⊥ ‑ ⊥

20

20

一iv一 図 目 次

3.10

3.11

リ ン ク の 重 み を カ イ ニ 乗 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布...,,...

BAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布 ρ(λ)と 半 円 分 布 戸(λ)の 誤 差 率 ξ̲...̲.̲.̲...̲̲

21

21

‑ ⊥ り 白 q δ

ネ ッ ト ワ ー ク の 例...,,,,.

ERネ ッ ト ワ ー ク に お け る 誤 差 率e.、.,

BAネ ッ ト ワ ー ク に お け る 誤 差 率E....

0 0 ワ ー 7 り 白 9 ﹄ り 白

‑ ⊥ 9 自 A A

正 規 化 ラ プ ラ シ ア ン 行 列Nの 最 大 固 有 値 λ,、と リ ン ク の 重 みWijの 関 係 性 ・ 平 均 μ の 変 化 に 対 す る リ ン ク の 重 み を ボ ア ソ ン 乱 数 で 与 え た 正 規 化 ラ プ ラ シ ア ン 行 列Nの 最 大 固 有 値 λnの 変 化..,,,.,...,,,.,,,.

36

38

一V一

表 目次

‑ ⊥ り 倉 り O

乱 数 ご と の 歪 度 と 尖 度...,,..,...

ERネ ッ ト ワ ー ク に 対 す る 最 大 固 有 値 λnと 歪 度 及 び 尖 度 の 関 係 性 BAネ ッ ト ワ ー ク に 対 す る 最 大 固 有 値 λ,zと 歪 度 及 び 尖 度 の 関 係 性

7 可 ⑪ り Q り り 0 3 り 0

1

第1章

序論

1.1背 景

近 年 の イ ン タ ー ネ ッ トサ ー ビ ス の 発 達 と ス マ ー ト フ ォ ン ・パ ソ コ ン の 普 及 に よ り,個 人 に よ る 情 報 の 発 信 や そ の 情 報 の 収 集 が 手 軽 に 行 え る よ う に な っ た[1].現 代 社 会 で は,ス マ ー ト フ ォ ン ・パ ソ コ ン を 通 じ て 個 人 か ら個 人 へ の 連 鎖 的 な 情 報 伝 播 に よ っ て 社 会 全 体 に 情 報 が 拡 散 し や す く な っ て い る.そ の 結 果,新 商 品 や 新 名 所 な ど の 情 報 が,日 常 会 話 だ け で な くSNS (TwitterやInstagram等)を 通 じ て 個 人 間 で 連 鎖 的 に 伝 播 し,社 会 の 中 で 注 目 を 集 め る よ う

に な っ て い る.し た が っ て,こ の よ う な 情 報 伝 播 の 特 性 を 分 析 す る こ とが で き れ ば,新 商 品 や 新 名 所 に 対 す る 宣 伝 戦 略 の 立 案 な ど 様 々 な 局 面 で 役 立 つ と考 え ら れ る,

友 人 間 や 企 業 間 な ど の 情 報 の や り と りを 分 析 す る 手 段 と し て,ネ ッ トワ ー ク で モ デ ル 化 す る 方 法 が し ば し ば 用 い ら れ る.ネ ッ ト ワ ー ク と は ノ ー ド 〔node}と 辺(edge)に よ っ て 構 成 さ れ る シ ス テ ム で あ る.実 世 界 に は,人 や 事 物 を ノ ー ド,そ れ ら の 関 係 性 を 辺 と み な す こ と に よ り ネ ッ トワ ー ク と し て 捉 え ら れ る 構 造 が 数 多 く存 在 す る(ex,WWW,イ ン タ ー ネ ッ ト,友 人 関 係,神 経 回 路,交 通 網 な ど 〉.こ れ ら の ネ ッ ト ワ ー ク は 一 般 に,大 規 模 か っ 複 雑 な 構 造 を し て い る こ と か ら複 雑 ネ ッ ト ワ ー ク(complexnetwork)[2]と 呼 ば れ,情 報 学[3,4,5,6]を は じ め,工 学[7,8,9],社 会 学[10,11,12],生 物 学[13,14,15,16,17]な ど分 野 を 問 わ ず 盛 ん に 研 究 さ れ て い る,特 に,こ れ ら の ネ ッ ト ワ ー ク の 中 で も 友 人 関 係 の ネ ッ トワ ー ク や 企 業 間 の 取 引 ネ ッ ト ワ ー ク の よ う に,我 々 の 社 会 活 動 と密 接 に 関 わ っ て い る ネ ッ トワ ー ク は 社 会 ネ ッ ト ワ ー ク と 呼 ば れ る[18,19].ネ ッ ト ワ ー ク で は 一 般 に,構 成 要 素 単 体 の 性 質 で は な く,こ れ ら の 相 互 関 係 に よ っ て 生 み 出 さ れ る性 質 が 本 質 的 に な る こ とが 多 い.そ の た め,我 々 の 社 会 活 動 と 密 接 に 関 わ っ て い る社 会 ネ ッ トワ ー ク は 興 味 深 い 研 究 対 象 で あ り,そ の 構 造 的 特 性 や 動 的 特 性 を

分 析 す る 研 究 が 精 力 的 に 行 わ れ て い る[20,21,22,23,24,25,26,27,28,29].

ネ ッ ト ワ ー ク の 構 造 的 特 性 や 動 的 特 性 を 分 析 す る 手 段 と して,ス ペ ク ト ラ ル グ ラ フ理 論 が 広

く用 い ら れ て い る[30,31,32,33].ス ペ ク ト ラ ル グ ラ フ 理 論 で は ネ ッ ト ワ ー ク 構 造 を 隣 接 行 列

2第1章 序論

:短靴 賛 握 難

寄r喰 ・'

'瞥 ■「.

咽劇'

ヨ 喘 ・ ︑ " 二 . 5 ﹂ 隔 { = ー ド ・ . ・ 島

; . 噂 ㍗ 論

・ 國 . ︑ , . { 欝 ^3︑

篶  灘

鎌幹 .■口・■.

︑ 噛 ㌧ 國 ︑ 噛 開 ■ ・ . ・ 詫 ・ ︑ " ・ ・ 聾 ㌔ . .

図1.1:社 会 ネ ッ トワ ー ク の 例

や ラ プ ラ シ ァ ン行 列 な どで 表 し,そ の 固有 値 や 固 有 ベ ク トル を分 析 す る こ とで ネ ッ トワ ー ク の 特 性 を代 数 的 に分 析 す る こ とが で き る[37,38,39,40].こ の理 論 を社 会 ネ ッ トワ ー ク の特 性 分 析 に適 用 す る こ と を考 え る と,ま ず は社 会 ネ ッ トワー ク構 造 を 行 列 で 表 さ な けれ ば な らな い.

しか し,社 会 ネ ッ トワ ー ク は,一 般 に 図1.1の よ う に 大 規 模 で あ るた め に行 列 が 巨大 に な るだ け で な く,行 列 の成 分 を 決 め る た め に必 要 とな る リ ン ク の 重 み(個 人 間 の 関 係 の 強 さ)は 単 純 に 個 人 間 で や り と りす る量 や 回 数 で 与 え る こ とが で きな い.そ の た め,ス ペ ク トル グ ラ フ理 論 の 適 用 以前 に,社 会 ネ ッ トワ ー ク構 造 を 行 列 で 表 す 段 階 で 困難 を抱 え て い る こ とに な る.

ラン ダ ム行 列 とは行 列 の 成 分 が 乱 数 で 与 え られ る行 列 で あ り,量 子 力 学 に お い て大 規 模 ・複 雑 な構 造 を分 析 す る際 に用 い られ て きた[43,44].量 子 力 学 で は,原 子 核 の周 りに存 在 す る電 子 の軌 道 を計 算 す る際 に,行 列 を用 い た 定 式 化 が 利 用 され る.し か し,ウ ラ ニ ウ ム の よ うな原 子 番 号 の 大 き な 原 子 で は電 子 が 多 数 存 在 し,電 子 間 の 相 互 作 用 が 複 雑 で あ るた め,軌 道 計 算 に 必 要 とな る行 列 の成 分 を決 め る こ とが 難 しい.そ こで,複 雑 な 相 互 作 用 を正 確 に記 述 す る こ と

を放 棄 し,行 列 の成 分 を乱 数 で 与 え た 上 で,大 規 模 ・複 雑 な構 造 が 持 っ 普 遍 的 な 性 質 を 考 察 し て い る.

前 述 した よ う に,社 会 ネ ッ トワ ー ク にお い て も行 列 の 成 分 を決 め る こ とは 難 しい.そ こ で, 量 子 力 学 と同様 に ネ ッ トワ ー ク構 造 を正 確 に与 え る こ とを放 棄 し,ネ ッ トワ ー ク構 造 を ラ ンダ ム 行列 で 表 した 際 に現 れ る普 遍 的 な性 質 を考 察 す れ ば,社 会 ネ ッ トワー ク を含 む 様 々 な ネ ッ ト ワ ー ク が 共 通 して持 っ 特 性 を 明 らか にで き るの で は な い だ ろ うか.

1.2目 的3

1.2目 的

本 稿 で は,社 会 ネ ッ トワー ク上 の 情 報 伝 播 特 性 の 分 析 を 目的 と して い る.ネ ッ トワ ー ク構 造 が 既 知 で あ るな らば,ネ ッ トワ ー ク上 の 情 報 伝 播 特 性 を分 析 す る こ と は容 易 で あ る.し か し, 前 述 した よ う に社 会 ネ ッ トワ ー ク は,リ ン ク の 重 み を含 め た 詳 細 な ネ ッ トワー ク構 造 を得 る こ とは 困難 で あ る た め,構 造 を既 知 と した 分 析 は 現 実 的 で は な い.そ こで,ま ず は,ネ ッ トワ ー ク構 造 を適 当 に与 え た ラ ン ダ ム行 列 を用 い て社 会 ネ ッ トワ ー ク を 含 む 様 々 な ネ ッ トワ ー ク に 対 して共 通 す る普 逓 的 な性 質(ネ ッ トワー ク構 造 に依 ら な い性 質)が 存 在 す るか ど うか を 明 らか に す る.

次 に,明 らか に した 普 遍 的 な 性 質 を 用 い て,社 会 ネ ッ トワ ー ク 上 の 情 報 伝 播 特 性 を 分 析 す る,こ こで は,情 報 伝 播 特 性 と して,社 会 ネ ッ トワー クに お け る情報 の 伝 わ り易 さ を対 象 とす る.情 報 の 伝 わ り易 さ を ラ ン ダ ム ウ ォー ク の初 回 到 達 時 間 の 期 待 値 で 定 量 化 し,普 遍 的 な 性 質 を 用 い れ ば 期 待 値 が 簡 単 な式 で 計 算 で き る こ とを 示 す.

1.3構 成

本 稿 の 構 成 は以 下 の 通 りで あ る.2章 で は,本 研 究 で 扱 う基 礎 知 識 と して,情 報 伝 播 特 性 に 関 係 す る ラ プ ラ シ ア ン行 列,複 雑 ネ ッ トワ ー ク の 代 表 的 な モ デ ル で あ るERネ ッ トワ ー ク と BAネ ッ トワ ー一ク,及 びWigllerの 半 円 則 を 説 明 す る.3章 で は,ネ ッ トワー ク構i造を 表 す ラ ン ダ ム 行 列 の 生 成 方 法,及 び 社 会 ネ ッ トワー ク分 析 に適 用 で き るか ど うか(普 遍 的 な 性 質 が 存 在 す るか ど うか 〉 の 検 証 結 果 を 説 明 す る.4章 で は,本 研 究 で 用 い る情 報 伝 播 特 性 の 指 標 につ い て説 明 した 後,3章 の 結 果 を用 い て 社 会 ネ ッ トワ ー ク上 の 情 報 伝 播 特 性 を分 析 す る.5章 で は,本 稿 の ま とめ と今 後 の 課 題 につ い て 説 明 す る.

4

第2章 準 備'

本 章 で は,本 研 究 で 用 い る幾 つ か の基 礎 知 識 を説 明 す る.

2.1ラ プ ラ シ ア ン 行 列

グ ラ フ に は,リ ン ク の 向 き を 考 慮 し な い 無 向 グ ラ フ(undirectedgraph)と リ ン ク の 向 き を 考 慮 し た 有 向 グ ラ フ(directedgraph)が 存 在 す る.ま た,グ ラ フ は ネ ッ ト ワ ー ク と も 呼 ば れ る.ネ ッ ト ワ ー ク の 構 造 的 特 性 や 動 的 特 性 を 分 析 す る 上 で は,ネ ッ ト ワ ー ク を 代 数 的 に 扱 う た め に,隣 接 行 列(adjacencymatrix)や ラ プ ラ シ ア ン 行 列(Laplacianmatrix)を 用 い て ネ ッ ト ワ ー ク 構 造 を 表 す こ と が 一 般 的 で あ る.こ の と き,こ れ ら の 行 列 は,ネ ッ ト ワ ー ク が 無 向 ネ ッ トワ ー ク の 場 合 は 対 称 行 列(symmetricmatrix)に な り,有 向 ネ ッ ト ワ ー ク の 場 合 は 非 対 称 行 列(asymmetricmatrix)に な る,対 称 行 列 は,非 対 称 行 列 に 比 べ て 代 数 的 な 取 り扱 い が 容 易 で あ る た め,ネ ッ ト ワ ー ク の 特 性 を 分 析 す る 上 で は,無 向 ネ ッ ト ワ ー ク を 仮 定 す る こ と が 多 い.そ の た め,本 稿 で は 無 向 ネ ッ ト ワ ー ク を 扱 う,

ノ ー ドの 集 合 をV={1,2,.,.,n},リ ン ク の 集 合 をEと す る.こ こ で,π 個 の ノ ー ドか ら な る 無 向 グ ラ フG(V,E)を 考 え る,グ ラ フGの リ ン ク構 造 を 表 す 正 方 行 列Aを 隣 接 行 列 と い い,グ ラ フaの 隣 接 行 列A=[Aij]は 以 下 の よ う に 定 義 さ れ る.

A・」 ・ 一{:1'i」 ((氏 ゴ)∈E)

〔(i,の ≠E)

そ の 際Wij>0は リ ン ク(i,の の 重 み を 表 す.ま た,Gは 無 向 グ ラ フ な の で 隣 接 行 列Aは 実 対 称 行 列AijニAjtで あ る.次 に,ノ ー ドi(iニ1,2,̲,n)の 重 み 付 き 次 数 を 偽 と し た と き,グ ラ フGの 次 数 行 列(degreematrix)D=[D￠ ゴ]は 以'下の よ う に 定 義 さ れ る.

砺 一{誹ゴ

^(琶=ゴ)

(琶 ≠ ゴ)

2,1ラ プ ラ シ ア ン行 列5

/0

岬譜

㌦ 凋＼

㍉^'ウ

、

図2.1:単 純 な ネ ッ トワ ー ク の 例

図2.1で 表 さ れ る よ うな グ ラ フが 与 え られ た とき,こ の グ ラ フ の隣 接 行 列A及 び 次 数 行 列D は 以 下 の よ う に な る.

A一齢D‑(繭

隣 接 行 列A及 び 次 数 行 列Dを 用 い て,ラ プ ラ シ ア ン 行 列Lを 以 下 の よ う に 定 義 す る, Ll=D‑A(2.3)

ラ プ ラ シ ア ン 行 列 は グ ラ フ ラ プ ラ シ ア ン(graphLaplacian)と も呼 ば れ る,図2.1で 表 さ れ る よ う な グ ラ フ の ラ プ ラ シ ア ン 行 列Lは 以 下 の よ う に な る.

L‑(=ili勤

前 述 した よ う に,隣 接 行 列Aは 実 対 称 行 列 で あ るの で,そ こか ら定 義 され る ラ プ ラ シ ア ン行 列Lは 実 対 称 行 列 で あ る.し た が っ て,ラ プ ラ シ ア ン行 列Lは 以 下 の性 質 が成 り立 つ.

・ 固 有 値 は π 個 あ り(重 複 す る場 合 あ り),全 て 実 数 で あ る.

6第2章 準 備

・ 異 な る固 有 値 に属 す る固 有 ペ ク トル は互 い に 直 交 す る.

。n本 の長 さ1の 固 有 ベ ク トル に よ っ て,n次 元 空 間 の 正 規 直 交 基 底 を張 る こ とが 可 能 . ま た,ラ プ ラ シ ア ン行 列 五 の 固有 の 性 質 と して 以 下 が成 り立 っ こ とが 知 られ て い る.

・ 最 小 固 有 値 は0で あ り,そ の 固 有 値 に 属 す る 固 有 ベ ク トル は 全 要 素 が 等 し いn次 元 ベ ク トル で あ る.

・ 非 連 結 グ ラ フ の 場 合,最 小 固 有 値0の 重 複 数 は グ ラ フ の 連 結 成 分 の 数 と一 致 す る ,

・ 第2最 小 固 有 値 は グ ラ フ の つ な が りの 強 さ を 表 し,代 数 的 連 結 度(algebraicconnec‑

tivity)と 呼 ば れ る.ま た,第2最 小 固 有 値 がoに 近 い ほ ど グ ラ フ の 連 結 性 が 弱 い [33].

。 第2最 小 固 有 値 に 属 す る 固 有 ペ ク トル は フ ィ ー 一 ド ラ ー ベ ク トル(Fiedlervector)と 呼 ば れ,フ ィ ー ド ラ ー ベ ク トル を 分 析 す る こ とで ク ラ ス タ 構 造 を 抽 出 し た り,ク ラ ス タ 問 を 結 ぶ リ ン ク を 特 定 す る こ とが で き る[34,35,36].

ネ ッ ト ワ ー ク 上 の 拡 散 現 象 や 同 期 現 象,及 び ラ ン ダ ム ウ ォ ー ク な ど の ネ ッ トワ ー ク 上 の 動 的 特 性 を 分 析 す る 上 で は,ラ プ ラ シ ア ン 行 列Lを 次 数 行 列Dで ス ケ ー リ ン グ し た 正 規 化 ラ プ ラ シ ア ン 行 列(110rmalizedL,aplaciallmatrix)NがJ・1iい られ る こ とが あ る[37,47,48,49] .正 規 化 ラ プ ラ シ ア ン 行 列Nは,ラ プ ラ シ ア ン 行 列L及 び 次 数 行 列Dを 用 い て 以 下 の よ う に 定 義 す る.

N:=D‑1/2.LD‑1/2

=■̲D‑1/2AD‑1/2 (2.4)

た だ し,1は 単 位 行 列 で あ る.式(2.4)よ り,正 規 化 ラ プ ラ シ ア ン行 列Nは 隣接 行 列A及 び次 数 行 列Dに よ っ て定 義 され て い る た め,正 規 化 ラ プ ラ シ ア ン 行 列Nは ネ ッ トワー ク構 造 を表 した 行 列 で あ る.ま た,隣 接 行 列Aは 実 対 称 行 列 で あ る の で,そ こか ら定 義 され る正 規 化 ラ プ ラシ ア ン行 列Nは 実 対 称 行 列 で あ る.図2.1で 表 さ れ る よ うな グ ラ フの 正 規 化 ラ プ ラ シァ ン行 列Nは 以 下 の よ うに な る,

N‑(1‑1/3‑2/>廊o‑1/31‑2/>/150

‑2/VI5‑2/>廊1‑1/・/5 00‑1〈/唇1)

正 規 化 ラ プ ラ シ ア ン行 列Nは 実 対 称 行 列 で あ るた め,正 規 直 交 固 有 ベ ク トルqsを 並 べ た 直 交 行 列Pに よ っ て 対 角 化 が 可 能 で あ る.

」P‑1NP=diag(A.)1≦s≦‑nニA

2、2ERネ ・ ン ト ワ ー ク とBAネtン ト ワ ー ク7

た だ し,正 規 化 ラ プ ラ シ ア ン 行 列Nの 第5番 目 の 固 有 値 を λs(λ1≦ … ≦ λs≦ … ≦ λn) ,λsに 対 す る 固 有 ベ ク ト ル を 規 格 化 し た も の をqsと す る.し た が っ て,正 規 化 ラ プ ラ シ ア ン 行 列Nは そ の 固 有 値 λ を 対 角 成 分 に 並 べ た 対 角 行 列Aと 直 交 行 列Pを 用 い る こ と で,以 下

の よ う に 表 現 で き る,

N:=PAP‑1

式 〔2,6)よ り,正 規 化 ラ プ ラ シ ア ン行 列Nは そ の 固 有 値 と固 有 ベ ク トルで 表 せ るた め,正 規 化 ラ プ ラ シ ア ン行 列Nの 固 有 値 及 び 固 有 ベ ク トル を 解 析 す る こ とは ネ ッ トワ ー ク構 造 を 分 析 す る こ と と 同 義 で あ る.ま た,正 規 化 ラ プ ラ シ ア ン行 列Nの 固 有 値 は,ネ ッ トワ ー ク の情 報 伝 播 特 性 に大 き く影 響 す る こ とが 知 られ て い る[50].詳 し くは4章 で 議 論 す る,

2.2ERネ ッ ト ワ ー ク とBAネ ッ ト ワ ー ク

ERネ ッ トワ ー ク とBAネ ッ ト ワ ー ク は,複 雑 ネ ッ ト ワ ー ク を 表 す 代 表 的 な ネ ッ トワ ー ク モ デ ル で あ り,多 く の 研 究 で 用 い られ て い る[51,52,53,54,55].

ERネ ッ トワ ー ク はERモ デ ル[22]に よ り 生 成 さ れ た ネ ッ ト ワ ー ク で あ り,ノ ー ド間 の リ ン ク が 一 定 の 確 率Pで 張 ら れ た ネ ッ ト ワ ー ク で あ る.ERネ ッ ト ワ ー ク は 以 下 の 手 順 で 生 成 さ れ る.

1.ノ ー ド数nと 平 均 次 数 〈k>を 指 定 す る.

2.ノ ー ド間 の リ ン ク を 張 る 確 率Pを 以 下 の よ う に 定 義 す る.

P=n

‑1

3.各 ノ ・ 一 ド間 の リ ン ク を 確 率pに よ っ て リ ン ク を 張 る か ど う か 決 定 す る.

(2.7)

上 記 の 手 順 に よ っ て 生 成 さ れ たERネ ッ ト ワ ー ク の 次 数 分 布 を 図2.3に 示 す.た だ し,ノ ー一ド 数 η=1000,ノ ー ド間 の リ ン ク を 張 る 確 率P=0.03と し た,図2.3よ り,ERネ ッ ト ワ ー ク

の 次 数 分 布 は 釣 り鐘 状 を して お り,次 数300付 近 の ノ ー ドが 多 数 存 在 す る こ とが わ か る.こ の こ と か ら,ERネ ッ トワ ー ク は 特 別 な ノ ー ドが 存 在 し な い ラ ン ダ ム な ネ ッ ト ワ ー ク で あ る と い え る.そ の た め,ERネ ッ ト ワ ー ク は ネ ッ ト ワ ー ク の 特 性 を 比 較 す る 際 の 基 準 と し て よ く用 い ら れ る ネ ッ ト ワ ー ク で あ る.

BAネ ッ トワ ー ク はBAモ デ ル[25]に よ り生 成 さ れ た ネ ッ トワ ー ク で あ り,ERネ ッ ト ワ ー 一

ク と は 異 な り,ス ケ ー ル フ リ ー 性 を 有 す る ネ ッ ト ワ ー ク で あ る.ス ケ ー ル フ リ ー 性 は,社 会

ネ ッ ト ワ ー ク が 持 つ 重 要 な 特 性 の 一 つ で あ り,次 数 分 布 が ベ キ 則P(k)ock‑Vに 従 う と い う

性 質 が あ る[56].特 に,BAネ ッ トワ ー ク の 次 数 分 布 はP(k)ock‑3に 従 う こ と が 知 ら れ て い

る,ま た,次 数 が 極 端 に 大 き い ノ ー ド(ハ ブ ノ ー ド)が 存 在 す る.ハ ブ ノ ー ド は ネ ッ ト ワ ー ク

8第2章 準備

図2.2:ERネ ッ ト ワ ー ク の 例

35

30

25

20

15

lo

5

150 200 250 ヨoo 350 400 450

図2.3:ERネ ッ ト ワ ー ク の 次 数 分 布

上 を 伝 播 す る 感 染 症 に 対 して も 重 要 な 役 割 を も つ こ とが 報 告 さ れ て い る[57,58].さ ら に,こ れ ら の 特 徴 か ら ス ケ ー ル フ リ ー ネ ッ ト ワ ー ク は 頑 強 性 と脆 弱 性 を 併 せ 持 つ こ と が 知 ら れ て い る [59].BAネ ッ トワ ー ク は 以 下 の 手 順 で 生 成 さ れ る.

1.no個 の ノ ー ドか ら な る 完 全 グ ラ フ を 生 成 す る.

2,2ERネ ッ ト ワ ー ク とBAネ ッ ト ワ ー ク9

図2.4:BAネ ッ ト ワ ー ク の 例

2.現 時 点 の ノ ー ド数 をntと し た と き,既 存 の ノ ー ド の 中 か らnm個 の ノ ー ド を 以 下 の 確 率 恥 で 選 択 す る.

砺(2 .8>

Hiニ

Σ 払 、海、

こ こ で,た 勉は ノ ー ド 歪の 次 数(リ ン ク 数)を 表 す.

3.nm本 の リ ン ク を 持 つ 新 た な ノ ー ド を 追 加 す る.

4.n,,,本 の リ ン ク を 手 順2で 選 択 さ れ たn、n個 の ノ ー ドに 接 続 す る.

5.手 順2〜 手 順4を 目 的 の ノ ー ド数 η に な る ま で 繰 り返 す.

上 記 の 手 順 に よ っ て 生 成 さ れ たBAネ ッ ト ワ ー ク の 次 数 分 布 を 図2.5に 示 す.た だ し,ノ ー

ド数 π=1000,nm=20と し,両 対 数 表 示 で 分 布 を プ ロ ッ ト し た.ま た,比 較 の た め に ベ キ

指 数 一3の 直 線 、 を 同 時 に プ ロ ッ ト し た.図2.5よ り,BAネ ッ ト ワ ー ク の 次 数 分 布 は べ キ 則

P(k)ock‑3に 従 う こ とが 確 認 で き る.

10第2章 準 備

103

102

101

100

100 101 102 103

Degree

図2.5:BAネ ッ トワ ー ク の 次 数 分 布

2.3Wignerの 半 円 則

Wignerの 半11]則 は,ラ ン ダ ム 行 列 の ス ペ ク トル 密 度 分 布 に 見 ら れ る 普 遍 的 な 性 質 の 一 一 っ で あ り,E.P.Wigllerに よ っ て 提 唱 さ れ た[44].ラ ン ダ ム 行 列 と は,行 列 の 成 分 が 確 率 変 数 で 与 え られ た 行 列 で あ る.こ こ で は,n×nの 実 対 称 行 列Xニ[Xiゴ]の 成 分Xij(ゴ ≧i)が そ れ ぞ れ 独 立 で 同 一 な確 率 分 布 関 数 に 従 う 乱 数 で 与 え ら れ て い る と す る.す な わ ち,以 下 の よ う な 行 列Xに つ い て 考 え る.

一一(驚:ii∫カ:…i‑iiξカ:3)四

た だ し,Xiゴ の 奇 数 次 の モ ー メ ン ト は0で,分 散 を σ2と す る,ま た,行 列Xが 与 え ら れ た と き,そ の 固 有 値 の サ ン プ ル を λi(i=1,̲,n)と す る.こ の と き,λi/〉 「nの 密 度 関 数 を 考 え る.こ の 量 は,行 列Xの 各 成 分 を 全 て1/V5i倍 し た 行 列X/vXiiの 固 有 値 で も あ る,し た が っ て,,x,/VEの 値 の 分 布 を 表 す 密 度 関 数 ρ(λ〉 は 以 下 の よ う に 書 け る.

ρ(λ)一去書 δ(λ一涯)

こ こ で .δ は デ ィ ラ ッ ク の デ ル タ関 数 で あ る.

(2.10)

2.3Wignerの 半 円 則11

0.010

0,008

>0、006 .配

2

ω 00.004

0.002

EigenvalueofRandomMatrix

図2.6:ラ ン ダ ム 行 列 の ス ペ ク ト ル 密 度 分 布 とWignerの 半 円 分 布

ラ ン ダ ム 行 列 の 次 元 数 が 十 分 に大 きい 場 合,一 つ の ラ ンダ ム行 列 に お い て も平 均 的 な性 質 が 実 現 され る 自 己平 均 性 が成 り立 つ こ とが 知 られ て い る.こ の とき,規 格 化 条 件 鳶 ρ(λ)dλ=

1が 成 り立 つ た め,ρ(λ)を 確 率 密 度 関 数 とみ な す こ とが で き,ρ(λ)は 以 下 の 式 で 近 似 す る こ とが で き る.

ρ(λ)・・{t■・a・vii'3i一期1嬬) (2.11)

式(2.11)の1λ1<2V伊 に お け る,右 辺4σ2一 λ2が 半 円 の 式 の 形 を し て い る こ と か ら,こ れ をWignerの 半 円 則 と い う.図2.6に,行 列 の 成 分 を 一 様 乱 数[0,4]で 与 え た ラ ン ダ ム 行 列

の ス ペ ク トル 密 度 分 布 ρ(λ)とWig皿erの 半 円 分 布 万(λ)を 示 す.図2.6よ り,行 列 の 成 分 を 一 様 乱 数[O,4]で 与 え た ラ ン ダ ム 行 列 の ス ペ ク トル 密 度 分 布 ρ(λ)はWignerの 半 円 則 に 従 っ て

い る こ と が 確 認 で き る.

文 献[55]で は,あ る 条 件 下 に お い て,ERネ ッ ト ワ ー ク とBAネ ッ ト ワ ー ク に 対 す る正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)がWignerの 半 円 則 に 従 う こ とが 報 告 さ れ て い る.図2.7に そ れ ぞ れ の ネ ッ ト ワ ー ク に お け る正 規 化 ラ プ ラ シ ア ン行 列 の ス ペ ク トル 密 度 分 布 とWigenrの 半 円 則 の 例 を 示 す.た だ し,ネ ッ ト ワ ー一ク の ノ ー ド数 は1000と し,ERネ ッ

ト ワ ー ク の パ ラ メ ー タ をPニ0.3,BAネ ッ ト ワ ー ク の パ ラ メ ー タnm=10と し た,図2、7よ

り,ど ち ら の ネ ッ ト ワ ー ク に お い て も 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)

が 固 有 値1を 中 心 と し たWignerの 半 円 分 布 戸(λ)に ほ ぼ 等 し い こ とが 確 認 で き る.

12

3.5

3,0

2,5

岬2.o'函

Φ1 .50

1,0

0,5

0・8

'■ ■ 一 戸い)

■ ∫,い)

2、5

2,0

>1,5 .ピ

仁 Φ 01.0

0,5

O.O .70.80.91.Ol.112130.60,81.0121、4

EigenvalueofnormalizedLapla〔ianMatrixEigenvalueofnormalizedLapla⊂ianMatrix

(a>ERネ ッ トワ ー ク(b)BAネ ッ トワ ー ク

図2.7=正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布p(λ)とWignerの 半 円 分 布 万(λ〉

13

第3章

ランダム行列 の適用可能性 の検証

3.1概 要

本 節 で は,ラ ン ダ ム 行 列 に よ っ て ネ ッ ト ワ ー ク構 造 を 表 し た 行 列 が 社 会 ネ ッ トワ ー ク 分 析 に 適 用 で き る か ど う か を 検 討 す る,社 会 ネ ッ トワ ー ク の リ ン ク に は 重 み が あ る が,リ ン ク の 重 み を 含 め た ネ ッ ト ワ ー ク 構 造 を 得 る こ と は 困 難 で あ る.そ こ で,リ ン ク の 重 み を ラ ン ダ ム で 与 え,普 遍 的 な 性 質 が 存 在 す る か ど う か を 考 察 す る.も し,普 遍 的 な 性 質 が 存 在 す れ ば,詳 細 な ネ ッ トワ ー ク 構 造 を 得 な く て も,普 遍 的 な 性 質 に 基 づ い て 社 会 ネ ッ トワ ー ク を 分 析 で き る.

文 献[55]で は,リ ン ク に 重 み の な いERネ ッ ト ワ ー ク 及 びBAネ ッ トワ ー ク に お け る 普 遍 的 な 性 質 を 明 ら か に し て い る,そ の 性 質 と は,ネ ッ トワ ー ク に お け る 最 小 次 数 及 び 平 均 次 数 を そ れ ぞ れkmi、 及 びkav,と し た と き,嶋i、 》kav,を 満 た す 場 合 に 正 規 化 ラ プ ラ シ ァ ン 行 列N の ス ペ ク トル 密 度 分 布 がWignerの 半 円 則 に 従 う と い う も の で あ る.

本 稿 で は,社 会 ネ ッ ト ワ ー ク へ の 適 用 可 能 性 を 明 ら か に す る た め に,リ ン ク に 重 み が あ る ERネ ッ ト ワ ー ク及 びBAネ ッ トワ ー ク に 対 して 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 がWignerの 半 円 則 に 従 う か ど う か をi凋査 す る.

3.2ネ ッ トワ ー ク 構 造 を 表 した ラ ン ダ ム 行 列 の 生 成 法

本 稿 で は,リ ン ク の 重 み を 乱 数 で 与 え たERネ ッ トワ ー ク 及 びBAネ ッ ト ワ ー 一ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nを ラ ン ダ ム 行 列 と し て 扱 う.そ の よ う なNを 以 下 の 手 順 で 生 成

す る.

1,文 献[22]も し く は[25]の 生 成 ア ル ゴ リ ズ ム に 従 っ て,リ ン ク の 重 み が 全 て1と な る ERネ ッ ト ワ ー ク ま た はBAネ ッ ト ワ ー ク を 生 成 す る.た だ し,BAネ ッ トワ ー ク の 場 合,生 成 し た ネ ッ ト ワ ー ク の リ ン ク を 確 率1‑qで ラ ン ダ ム に 削 除 す る.

2,手 順1で 生 成 し た リ ン ク(i,の の 重 み ω毎 を,あ る確 率 分 布 に 従 う 乱 数 で 与 え る.

14第3章 ランダム行列 の適用 可能性の検証

3.リ ン クの 重 み 物 に 従 っ て 隣 接 行 列A,次 数 行 列D及 び 正 規 化 ラ プ ラ シ ア ン行 列N を構 成 す る.

元 々 の 生 成 ア ル ゴ リ ズ ム[25]に 従 っ た 場 合,BAネ ッ ト ワ ー ク で は 最 小 次 数 及 び 平 均 次 数 が 一 定 値 と な る.一 方 で,ERネ ッ ト ワ ー ク で は 最 小 次 数 及 び 平 均 次 数 は 確 率 的 に 変 化 す る と い う 性 質 が あ る.手 順1で,BAネ ッ ト ワ ー ク の リ ン ク を 確 率1‑qで ラ ン ダ ム に 削 除 す る 操 作

を 加 え る こ と で,ERネ ッ ト ワ ー ク と 同 様 に 最 小 次 数 及 び 平 均 次 数 を 確 率 的 に 変 化 さ せ ら れ, ERネ ッ ト ワ ー ク とBAネ ッ ト ワ ー ク の 結 果 を 同 条 件 で 比 較 で き る.た だ し,BAネ ッ ト ワ ー

ク の リ ン ク を 削 除 す る 操 作 は,BAネ ッ ト ワ ー ク が 有 す る ス ケ ー ル フ リ ー 性 を 消 失 さ せ な い こ と を 調 査 す る 必 要 が あ る.前 述 し た よ う に,BAネ ッ トワ ー ク が 有 す る ス ケ ー ル フ リ ー 性 の 特 徴 と し て,BAネ ッ ト ワ ー ク の 次 数 分 布 が 、P㈹ 〔xK'‑3に 従 う と い っ た 性 質 が あ る.そ こ で, BAネ ッ トワ ー ク の リ ン ク を 削 除 す る操 作 を 加 え て も 次 数 分 布 がIP㈹ 〔xk‑‑3に 従 うか ど うか を 調 査 す る.図3.1は,qニ0.5,0.7に 対 す るBAネ ッ トワ ー ク の 次 数 分 布 を 示 し た も の で あ る.た だ し,ネ ッ トワ ー ク は 連 結 で あ り,ノ ー ド数 は1000と し た.ま た,比 較 の た め の 実 線 はq=1に 対 す る次 数 分 布1〕 ㈹(x鳶 一3で あ る.図3.1を み る と,リ ン ク を 削 除 す る 本 数 が 増

103

102

10ユ

100

1eO 101

Degree

102

lO3

102

10ユ

loo loolO3

＼ ・ ㌔ ず ︑ .

Degree

103

(a)q=0.5(b)q=O.7

図3,1=qニ0.5,0.7に 対 す るBAネ ッ ト ワ ー ク の 次 数 分 布

加 す る と最 小 次 数 を は じ め,平 均 的 に 次 数 は 減 少 し て い る が,次 数 分 布 の 裾 の 傾 き は 削 除 す る 前 と ほ ぼ 等 し い こ とが わ か る.し た が っ て,BAネ ッ ト ワ ー ク の リ ン ク を 削 除 す る操 作 を 行 っ

て も,BAネ ッ ト ワ ー ク が 有 す る ス ケ ー ル フ リ ー 性P(k)ock‑3は 消 失 し な い と い え る.

3.3検 証 結 果 と適 用 条 件15

3.3検 証 結 果 と適 用 条 件

本 節 で は,3.2節 で 説 明 し た 生 成 手 順 に 従 う ラ ン ダ ム 行 列 の ス ペ ク トル 密 度 分 布 がWigner の 半 円 則 に 従 うか ど う か を 実 験 的 に 調 査 す る と と も に,Wigllerの 半 円 則 に 従 う た め の 条 件 を 明 ら か に す る.そ の 際 に,リ ン ク の 重 み が 従 う 確 率 分 布 と し て,一 様 乱 数[0,4]お よ び 平 均2

の 指 数 乱 数 を 用 い る.異 な る 乱 数 の 結 果 を 比 較 す る こ とで,乱 数 に 依 ら な い 普 遍 的 な 性 質 を 明 ら か に す る.分 析 結 果 は1000x1000の ラ ン ダ ム 行 列 を50回 生 成 し,そ の 平 均 を と っ た も の で あ る,ま た,非 連 結 な ネ ッ ト ワ ー ク と な る こ と を 防 ぐた め にP≧0,01及 びq≧0.5と す る.

図3.2は,ERネ ッ ト ワ ー ク に 対 す る リ ン ク 存 在 確 率Pを 変 化 さ せ た 時 の 最 小 次 数 の2乗 嶋i、 と平 均 次 数 ん乱v.を 示 し た も の で あ る,pが 大 き く な る に っ れ て 礪i、 とka。eは 共 に 増 加 し て い る が,礪inはkav.に 比 べ て 増 加 速 度 が 大 き い こ と が わ か る.ま た,文 献[55]で 明 ら か に さ れ て い る条 件 嶋i、 》kav.を 満 た す に は,少 な く と も 峨in>kav.で な け れ ば な ら な い た め,p≧0,03と な る 必 要 が あ る,本 稿 で は,リ ン ク の 重 み を 乱 数 で 与 え る 際 に,平 均 値 が1以 上 と な る よ う に 設 定 し て い る.そ の た め,重 み 無 し の 次 数 条 件 嶋in》kav。 を 満 た せ ば,重 み 付 き の 次 数 条 件d孟i、 》dav已 を 平 均 的 に 満 た す.し た が っ て,重 み 付 き で あ っ て も 重 み 無 し の 次 数 条 件 嶋h、 》kav.を 考 え れ ば よ い と い え る.

図3.3〜 図3.5は,ERネ ッ トワ ー ク に 対 す る リ ン ク 存 在 確 率P=0.Ol,O.1と し た 時 に リ ン ク の 重 み を 指 数 乱 数,一 様 乱 数[0,4]及 び カ イ ニ 乗 乱 数 で 与 え た 際 の そ れ ぞ れ の 正 規 化 ラ プ ラ

0000000000000000ら    ΦΦ﹂OΦ℃ωO応﹂①﹀価Φ5︑

8﹂09∈コ⊆⊆∈Φ5もΦ﹂価コσのΦ5

thesquareofthemlnlmumdegree theaveragedegree

0.020.040.060、08

ExistingProbabilitypoflinks inERnetwork

0,10

図3.2:ERネ ッ ト ワ ー ク に 対 す る最 小 次 数 の2乗 と 平 均 次 数

16第3章 ランダム行列 の適用 可能性 の検証

シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布P(λ)を ヒ ス ト グ ラ ム で 示 し た も の で あ る.そ の 際 ビ ン のtanh及 び ビ ン の 幅Whは そ れ ぞ れ50及 び(λn一 λ2+o.2)/nhと し た.ヒ ス ト グ ラ ム で は,見 や す さ の た め に 正 規 化 ラ プ ラ シ ア ン 行 列Nの 最 小 固 有 値 λ1=0は 除 外 し て い る.ま た 比 較 の た め,こ れ ら の 図 で は 次 式 で 与 え ら れ る 半 円 分 布 を 実 線 で プ ロ ッ ト し て い る.

P(λ)一{8(蒋(牌 《圃1繍 詔(3・ ・)

式(3,1)は 半 円 の 中 心 が λ=1に 変 更 さ れ て い る だ け で,本 質 的 に 式(2.11)と 等 価 で あ る.

そ の た め,本 研 究 で は,正 規 化 ラ プ ラ シ ア ン 行 列Nに 対 す る ス ペ ク トル 密 度 分 布 ρ(λ)が 式 (3,1)で 与 え ら れ る 戸(λ)で 近 似 で き る こ と を,Wignerの 半 円 則 に 従 う と表 現 す る.ま た, Wignerの 半 円 分 布 万(λ)は 正 規 化 ラ プ ラ シ ア ン 行 列Nの 最 大 固 有 値 λnを 用 い た 式(3.1)で 表 記 し た が,固 有 値1を 中 心 と し て 対 称 と な っ て い る こ とか ら,第2最 小 固 有 値 λ2を 用 い て 半 円 分 布 を 描 く こ と も 可 能 で あ る.図3.3〜 図3.5を み る と,pニO.Olで は ス ペ ク トル 密 度 分 布 がWignerの 半 円 則 を 破 っ て い る こ とが わ か る.一 ・ 方,pニ0.1で は ス ペ ク トル 密 度 分 布 が Wignerの 半 円 則 に よ く従 っ て い る の が わ か る.し た が っ て,正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)がWignerの 半 円 則 に 従 う た め に は,pが 大 き い 値 で な い と い け な い こ と が 予 想 さ れ る.

o、9

o.B O.7

石 占 4 3 n U n U n U O

02 0ユ

EigenvalueofnormalizedLaplacianMatrix

2.5

2,0

︻ ﹂ ハ U

‑ ⊥ ‑ 占

O.5

EigenvalueofnormalizedLaplacianMatrix

(a)pニ0,01(b)p=0.1

図3.3:リ ン ク の 重 み を 指 数 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列

Nの ス ペ ク ト ル 密 度 分 布

3.3検 証 結 果 と 適 用 条 件17

1.03.0

。,、 二 ＼ 旦   25b'邑:1

,

■

2、O 首o・6亘

221s

{りu OO.40

1.O

o,20

.5

0・B2

、.、 、.。u,,L,、.、 、.,、.。1.80B.6。 、7u,。,.,、.VL.⊥ ⊥.、1.31.4

EigenvalueofnormalizedLapla〔ianMatrixEigenvalueofnormalizedLaplacianMatrix

(a)pニ0.01(b)p=0.1

図3.4=リ ン ク の 重 み を 一 様 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列 Nの ス ペ ク ト ル 密 度 分 布

0,93.O

一 戸〔λ}

一 戸〔λ)

e、S 團 ρ(λ) ̲一 ■lP〔 λ)

開2.5'

一 、 ■ 「 ・

.7 1■o

1:i:II

倉:::lIl〜0

21.51

⊂IIl

8。 ・411181、

1.OIo3・

02

iI!iO・5 0.1

1 :i'i!1::1:

。・B

.。 、.コ 、',、'"i,⊃2.0。 ・B.6。 、7。.80.91.11ユ1.21.ヨ1,4

EigenvalueofnormalizedLaplacianMatrixEigenvalueofnormalizedLaplacianMatrix

(a)p=0.01(b)pニ0.1

図3.5:リ ン ク の 重 み を カ イ ニ 乗 乱 数 で 与 え たERネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン

行 列Nの ス ペ ク ト ル 密 度 分 布

18第3章 ランダム行列 の適 用可 能性の検証

図3.6は,ERネ ッ ト ワ ー ク の リ ン ク 存 在 確 率Pを 変 化 さ せ た 時 に,リ ン ク の 重 み を 固 定 値 (Wiゴ ニ1),指 数 乱 数(平 均2),一 様 乱 数(範 囲[0,4])及 び カ イ ニ 乗 乱 数 乱 数(平 均2)で そ れ ぞ れ 与 え た 場 合 の ス ペ ク トル 密 度 関 数 の 誤 差 率 ξを 示 し た も の で あ る.そ の 際 に,ス ペ ク ト ル 密 度 関 数 の 誤 差 率 ξ は 次 式 で 計 算 し た.

・一毒 茎1ρ俵 穿)1× … _(3.2)

た だ し,鳶 はs番 目 の ビ ン の 高 さ で あ り,xsは,s番 目 の ビ ン の 中 心 点 ωh(s‑1)+Xlで あ る.図3.6よ り,リ ン ク の 重 み の 与 え 方 に依 ら ずpが 大 き くな る に つ れ,誤 差 率Eは 減 少 す る こ とが 分 か る,ま た,硯i、 》kav,を 満 た すPの 範 囲 で は,誤 差 率 ∈ は リ ン ク の 重 み の 与 え 方 に 依 ら ず 低 い 値 と な っ て い る た め,図3.6の 結 果 が 示 す 精 度 で 正 規 化 ラ プ ラ シ ア ン 行 列N の ス ペ ク トル 密 度 分 布p(λ)がWignerの 半 円 則 に 従 う こ と が 分 か る,

図3.7は,BAネ ッ ト ワ ー ク に 対 す る リ ン ク 存 在 確 率qを 変 化 さ せ た 時 の 最 小 次 数 の2乗 礪i、、と平 均 次 数 た。v,の 変 化 を 示 し た も の で あ る.こ こ で,BAネ ッ ト ワ ー ク はno=・ninニ20 のBAモ デ ル で 生 成 し た ネ ッ ト ワ ー ク で あ る.qが 大 き くな る に つ れ て 裾 、i、 とkaveは 共 に 増 加 して い る が,klt、ir、は た。v.に 比 べ て 増 加 速 度 が 大 き い こ と が わ か る,ま た,文 献[55]で 明 ら か に さ れ て い る 条 件 礪ilエ 》k。v.を 満 た す に は,少 な く と も 裾 、h上>kav,で な け れ ば な ら な い た め,9≧0.7と な る 必 要 が あ る.

16 14

夏 ・2 Vlo

Φ 8  

一の﹂﹂O﹂﹂山

6 4 2 0

HI〃,」=1f。r己IIIink5

theexpone[tialdistiributionwiththeavrage2 theuniformdistributionwiththerangelo,4]

th巳chisquar巳di5tributionwithth已averag∈2

0.020.040,060.080.10

ExistingProbabilityPoflinks inERnetwork

図3.6:ERネ ッ トワ ー ク に対 す る正 規 化 ラ プ ラ シ ア ン行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)と 半 円分 布 万い)の 誤 差 率c

3.3検 証 結 果 と適 用 条 件19

(一U(UAhり(一U{HU{n︾{UハHUO5050505             

ΦΦ﹂OΦで①O価﹂Φ﹀のὼ剃︑

ΦΦ﹂OΦO⊆﹂コ⊆と⊂一⊆﹂Φ=一﹂OΦ﹂価コσ切Φ=一

thesquareoftheminimumdegree theaveragedegree

8,50.60.70.80,9

Remainingprobabilitygoflinks inBAnetwork

1,0

図3.7=BAネ ッ ト ワ ー ク に 対 す る 最 小 次 数 の2乗 と平 均 次 数

図3,8〜 図3.10は,BAネ ッ ト ワ ー ク に 対 す る リ ン ク 存 在 確 率q=O,5,0,9と し た 時 に リ ン ク の 重 み を 指 数 乱 数,一 様 乱 数[0,4]及 び カ イ ニ 乗 乱 数 で 与 え た 際 の そ れ ぞ れ の 正 規 化 ラ プ ラ シ ァ ン行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)を ヒ ス ト グ ラ ム で 示 し た も の で あ る.た だ し,ヒ ス ト グ ラ ム の 表 示 方 法 は 図3.3と 同 じ で あ る.図3.8〜 図3.10を み る と,q=0.5で は ス ペ ク ト ル 密 度 分 布 がWignerの 半 円 則 を 破 っ て い る こ と が わ か る.一 方,qニ0.9で は ス ペ ク トル 密 度 分 布 がWignerの 半 円 則 に よ く従 っ て い る の が わ か る.し た が っ て,正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(A>がWignerの 半 円 則 に 従 う た め に は,qが 大 き い 値 で な い と

い け な い こ と が 予 想 さ れ る.

図3.11は,BAネ ッ ト ワ ー ク の リ ン ク 存 在 確 率qの 変 化 さ せ た 時 に,リ ン ク の 重 み を 固 定 値(ωij=1),指 数 分 布(平 均2),及 び 一 様 分 布(範 囲[0,4Dで そ れ ぞ れ 与 え た 場 合 の ス ペ ク トル 密 度 関 数 の 誤 差 率̀を 示 し た も の で あ る.そ の 際 に,ス ペ ク トル 密 度 関 数 の 誤 差 率 ∈ は 式(3,2)で 計 算 し た も の で あ る.図3.11よ り,リ ン ク の 重 み の 与 え 方 に 依 ら ずqが 大 き く な

る に つ れ,誤 差 率 ξ は 減 少 す る こ とが 分 か る.ま た,礪i、 》kav.を 満 た すqの 範 囲 で は,誤

差 率6は リ ン ク の 重 み の 与 え 方 に 依 ら ず 低 い 値 と な っ て い る た め,図3,11の 結 果 が 示 す 精 度

で 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク ト ル 密 度 分 布 ρ(λ)がWignerの 半 円 則 に 従 う こ と が

分 か る.

20第3章 ラ ン ダ ム 行 列 の 適 用 可 能 性 の 検 証

1.21.6

髄L一 戸い)一 戸い)

■1回ρい)1、4 團 回 ρ{λ 〕

1'o

I.1/1,1,2

首 α8';、 …'1:,堂 工・

ll:…1‑i lilvil: 1…IIIl:::

0.4 G.2

艦 …1   1認 …翻8::140,… ∴ ・1,.L211h6

EigenvalueofnormalizedLaplacianMatrixEigenvalueofnormalizedLapladanMatrix

(a)qニ0,5(b)qニ0.9

図3.8=リ ン ク の 重 み を 指 数 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列 Nの ス ペ ク ト ル 密 度 分 布

1.2

1,0

0.8

盈 2。 、6 呂

OA

o.2

0・8

1.8

1.6

1.4

1.2

>

ゼ 1.0 仁 ΦO.8

∩ O.6

0,4

0,2

。・B

.20.4U.bU.ti⊥,U⊥.∠ ⊥、4⊥,61.8.40、bu.if⊥.u⊥,∠ ⊥、41.6

EigenvalueofnormalizedLaplacianMatrixEigenva[ueofnormalizedLaplacianMatrix

(a)qニ0.5(b)qニO,9

図3.9:リ ン ク の 重 み を 一 様 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列

Nの ス ペ ク ト ル 密 度 分 布

3.3検 証 結 果 と遺 用 条 件21

12

1,0

Ol8

倉 20.6 呂

o.4

02

置

''

■ ＼

一 戸{λ)

■ ρい)

0・82。

,40.6。.81.OL21.41.6L8

EigenvalueofnormalizedLaplacianMatrix (a)q=0.5

1、6

1.4

12

>、1・O

、紀 20.8 Φ 00 .6

0.4

02

0・B .4

ノ ^{馳 ・}

L

一 戸い〕

■ 姻

0.60.81,0121.41.6

EigenvalueofnormalizedLaplacianMatrix (b)q=0.9

図3.10:リ ン ク の 重 み を カ イ ニ 乗 乱 数 で 与 え たBAネ ッ ト ワ ー ク に 対 す る 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布

8 7

ま6 V5

Φ 据4

」

」3

9 缶2

1

8

H吻=1f。ra111ink5

■・一■th已 ∈xponentialdi5tiributionw陀hth已avrag已2

■theuniformdistributionwiththerang色[O,4]

●thechisquヨr巳di5tributionwithth已average2

▲●

‑︑︑

●

■

●一̲

=ン ー■ 一 一 一 一 … ● 『 一

● 一● 一

.50.60.70、80.9

Remainingprobabilityqoflinks inBAnetwork

1,0

図3.11:BAネ ッ トワー ク に 対 す る正 規 化 ラ プ ラ シ ア ン行 列Nの ス ペ ク トル密 度 分 布p(λ)と 半 円分 布 万(λ)の誤 差 率6

22第3章 ランダム行 列 の適 用可能 性 の検 証

以 上 の 結 果 よ り,次 数 条 件 嶋i、 》kaveを 満 た す 場 合,ERネ ッ ト ワ ー ク 及 びBAネ ッ ト ワ ー ク の 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)は,リ ン ク の 重 み の 与 え 方 に 依 らず 式(3.1)で 与 え られ るWignerの 半 円 則 に 従 う こ とが わ か る.ま た,式(3.1)よ り, Wignerの 半 円 分 布 は 正 規 化 ラ プ ラ シ ア ン 行 列Nの 最 大 固 有 値 煽 ま た は 第2最 小 固 有 値 λ2 の み で 描 く こ とが で き る.し た が っ て,硯i.》 砿v.を 満 た す 場 合,正 規 化 ラ プ ラ シ ア ン行 列 Nの ス ペ ク トル 密 度 分 布p(A)は リ ン ク の 重 み の 与 え 方 に 依 らず λnま た は λ2の み で 求 め る

こ とが で き る.λnま た は λ2に 関 して の 考 察 は 付 録Aで 述 べ る,

23

第4章

情報伝播特性の分析

本 章 で は,次 数 条 件 礁i、 》 梶v.を 満 た す 社 会 ネ ッ トワー ク上 の情 報 伝 播 特 性 を 分 析 す る.

次 数 条 件 を満 た さ な い 場 合 に は,知 人 が 極 端 に 少 な い個 人(リ ン ク数 が 極 端 に 少 な い ノー ド) の 存 在 が 考 え られ る(図4,1(a)).し か し,そ の よ うな 個 人 が 社 会 ネ ッ トワ ー ク の 大 半 を 占 め る とは考 え に く く,ま た,情 報 伝 播 へ の 寄 与 は 小 さい.そ の た め,本 研 究 で は,そ の よ う な ノ ー ドは 無 視 し,図4.1(b)の よ う な次 数 条 件 を 満 た す 社 会 ネ ッ トワ ー ク を 分 析 の 対 象 とす る.本 章 の流 れ は 以 下 の 通 りで あ る.ま ず,本 研 究 で 用 い る情報 伝 播 特 性 の 評 価 指 標 に つ い て

(a)次 数 条件 を満 た さ な い ネ ッ トワ ー ク (b)次 数 条 件 を 満 た す ネ ッ トワ ー ク 図4.1:ネ ッ ト ワ ー ク の 例

説 明 した後,3章 で 明 らか に した 普 遍 的 な 性 質 に基 づ い て 社 会 ネ ッ トワー ク上 の 情 報 伝 播 特 性 を 分 析 す る.さ ら に,分 析 結 果 の 妥 当性 を検 証 す る.

24第4章 情報伝播 特性の分 析

4.1情 報 伝 播 特 性 の 評価 指 標

本 研 究 で は,新 しい 商 品 の情 報 な どが 個 人 の ロ コ ミの 連 鎖 に よ って 広 が って い く よ うな情 報 伝 播 を 想 定 して い る.ロ コ ミの よ う な情 報 伝 播 で は,知 人 の 多 い個 人(次 数 の 大 き な ノー ド)

ほ ど情 報 が 伝 わ りや す い.

ネ ッ トワ ー ク上 の ラ ン ダ ム ウ ォ ー ク は,到 達 確 率 が ノー ドの 次 数 に 比例 す る とい う性 質 が あ る.そ の た め,想 定 す る情 報 伝 播 の 特 性 を 分 析 す る た め に情 報 伝 播 を ネ ッ トワー ク 上 の ラ ン ダ ム ウ ォ ー ク と し て モ デ ル化 す る.社 会 ネ ッ トワ ー ク上 の 情 報 伝 播 に お い て は,情 報 が初 め て 到 達 す る時 間(初 回 到 達 時 間)が 重 要 で あ る.そ の た め,社 会 ネ ッ トワ ー ク上 の情 報 伝 播 特 性 の 評 価 指 標 と して,ネ ッ トワ ー ク ヒの ラ ン ダ ム ウ ォ ー ク に 対 す る初 回 到 達 時 間 の 期 待 値 を用 い る.

文 献[50]で は,ネ ッ ト ワ ー ク 上 の ノ ー ドiか ら 開 始 した ラ ン ダ ム ウ ォ ー ク が ノ ー ド 」 に 初 め て 到 達 す る 時 間 ∫η の 計 算 式 と し て 次 式 が 示 さ れ て い る.

ん 一2E嘘 素(q書(ゴ)q,s(i)q,,(ゴ)d

、 〉偏) (4.1)

こ こで,蝋 の は正 規 化 ラ プ ラ シ ア ン行 列Nの5番 目の 固 有 値 に対 す る固 有 ベ ク トル の 第i成 分 で あ る.ま た,ノ ー ド ぜか ら他 の 全 て の ノ ー ド ゴへ の初 回 到 達 時 間 の 期 待 値 視 は次 式 で 求 め る こ とが で き る.

て 

一 碧2結1ん

一獣(π π¥ω一慰 卿 可) 一詳  

(42)

(43)

上 式 の 期 待 値 で は ノ ー ド ゴ へ の 情 報 の 到 達 し や す さ を 更 に 加 味 し,ノ ー ド ゴ へ の 到 達 確 率dj/2Eを 用 い て 初 回 到 達 時 間 の 期 待 値mを 計 算 し て い る.式(4.2)か ら 式(4.3) へ の 計 算 は,qsが 正 規 直 交 固 有 ベ ク ト ル で あ る こ と,及 び λ1に 対 す る 固 有 ベ ク トル が q1=(v研,...,〜 砺)で あ る こ と を 利 用 し て い る,式(4.3)を み る と,初 回 到 達 時 間 の 期 待 値mはNの 固 有 値 λ,の み に よ っ て 計 算 で き る こ と が わ か る,ま た,初 回 到 達 時 間 の 期 待 値 祝 は 出 発 ノ ー ド 琶に 依 存 し な い た め,任 意 の ノ ー ドの 組@,の に 対 す る 初 回 到 達 時 間 の 期 待 値

と 同 値 で あ る.

4.2ラ ン ダ ム 行 列 の 性 質 の 適 用25

4.2ラ ンダ ム 行列 の性 質 の 適用

本 節 で は,3章 で 明 らか に した 普 遍 的 な性 質(正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 がWignerの 半 円則 に従 う性 質)を 用 い て 社 会 ネ ッ トワ ー ク上 の 初 回 到 達 時 間 の 期 待 値 mを 分 析 す る.

正 規 化 ラ プ ラ シ ア ン行 列Nの ス ペ ク トル 密 度 分 布 がWignerの 半 円 則 で 与 え られ る 場 合, 初 回 到 達 時 間 の 期 待 値mは 次 の よ う に 計 算 さ れ る.た だ し,詳 細 な 導 出 過 程 は 付 録 で 説 明

す る.

一 獄

濃(n‑・)ρ(λ)dλ(4・4)

藷 ≡ 跡 去(An‑1)2‑(λ 一1)・dλ

一2(㌻1)f

。"(An一 鑑 θ+、dθ 一 許 尋(1‑・ 一(An‑・)2)(4・5)

式(4.5)を み る と,初 回 到 達 時 間 の 期 待 値mは 正 規 化 ラ プ ラ シ ア ン 行 列Nの ス ペ ク トル 密 度 分 布 ρ(λ)の 半 径 λ,、‑1と ノ ー ド数 η で 決 定 さ れ る こ と が 分 か る.ま た,半 径 煽 一1に 対 す る 初 回 到 達 時 間 の 期 待 値mの 微 分 係 数 を 計 算 す る と,mは 半 径 λn‑1に 対 す る 増 加 関 数 で あ る こ とが 分 か る.し た が っ て,正 規 化 ラ プ ラ シ ア ン 行 列Nの ρ(λ)の 半 径 λn‑1が 増 加 す る とネ ッ ト ワ ー ク 上 の 情 報 伝 播 速 度 が 遅 くな る と い え る.ま た,正 規 化 ラ プ ラ シ ア ン行 列 Nの ス ペ ク ト ル 密 度 分 布 の 半 径 は0<λn‑1<1で あ る た め,初 回 到 達 時 間 の 期 待 値mの 上 限inf伽 と 下 限supmは 以 下 の よ う に な る.

infmニ2(n‑1)

supm=(71‑1> (4.7)

そ の た め,ノ ー ド数 π が 同 じで あれ ば社 会 ネ ッ トワー クの 構 造 が 異 な っ て も初 回 到 達 時 間 の期 待 値 鵠 は最 大 で2倍 しか 変 わ ら な い こ とが 分 か る.