博 士 （ 情 報 科 学 ） 原 田 恵 雨 学 位 論 文 題 名
Extracting h/Iany ‐ to ― many Related Communities in Bipartite Graph
（ 二 部 グ ラ フ に お け る 多 対 多 に 関 係 す る コ ミ ュ ニ テ イ の 抽 出 ）
学位論文内容の要旨
現実世 界には ，二部グラフで表すことの出来る関係が多数存在する．これらの中に，コミュニテイ と 呼ば れる、 その外 部と比 較し てっ内 部では 隣接関 係が大 きく類似しているノード集合が存在して い る． コミュ ニテイを発見することが，システムの関係構造を理解するのに貢献している，従来のコ ミ ュニ テイ抽 出方法では，非常に高速にコミュニテイ構造が得られる一方，二部グラフの一部グラフ 変 換や コミュ ニテイ外部の無視など，精度に問題点がある．そこで，本論文では，一部グラフ変換せ ず ，多 対多の コミュ ニテイ 対応 関係を 考慮す ること で，二 部グラフにおけるより精度の高いコミュ ニ テイ 分割を 得る方法を提案した，まず，二部グラフのコミュニテイ分割問題をっノードにおける巡 回 セー ルスマ ン問題 に置き 換え ，ノー ド間コ スト関 数と局 所クラスタリング組織化法による巡回経 路 コス 卜最適 化を用いて，コミュニティ間コストによるコミュニテイ分割方法を提案した．さらに，
二 部グ ラフに おける 複数の 生成 モデル に対し て提案 方法の 有効性を検証した，次に，二部グラフに お ける 多対多 のコミ ュニテ ィ対 応関係 を考慮 したモ ジュラ リテイを提案した．提案指標を様々な二 部 グラ フとコ ミュニティ分割に対して適用し，有効性を確認した．与えられた二部グラフに対して。
提 案指 標が大 きな値 を得る コミ ュニテ ィ構造 を実質 的な計 算時間で発見する方法を提案した．数千 ノ ード ．一万 リンク程度の現実二部グラフをコミュニティ分割して，有効性を示した．応用として。
有 向グ ラフを 出部と 入部の 二部 グラフ とみな してコ ミュニ テイ分割する方法を示した．また得られ た コミ ュニテ イ構造 から， コミ ュニテ イの機 能を同 定する 方法を示した，現実の有向グラフとして C.elegansの 神 経 細 胞 網 を 解 析 し ， そ の コ ミ ュ ニ テ イ 機 能 を 明 ら か に し た ． 第1章では ，研究 背景と して， 複雑 ネットワーク科学の始まり，複雑ネットワークとしての二部グ ラ フ， コミュ ニテイ分割における関連研究，さらに研究目的について述べた．二部グラフにおける多 対 多に 関係し あうコ ミュニ テイ 構造を 抽出す る方法 を確立 し，現実の二部グラフのコミュニティ間 関 係を 明らか にする ことを 研究 目的と 述べた
第2章では 。隣接 ノード 関係を 用い たノー ド問コ スト関 数と 巡回経 路コス ト最適 化法に基づくコ ミ ュニ テイ分 割方法 を提案 した ．ノー ド間コ スト関 数には コサイン類似度，巡回経路コスト最適化 法 に 局 所 ク ラ スタ リ ン ク 組 織化 法を採 用した ，二部 穴居人 モデ ル及び により 二部CNNモデ ルに よ り 生成 した二 部グラ フに対 して 提案方 法を適 用した 結果， ノード間コストの頻度分布が多峰的とな り ，コ ミュニ テイ内コストとコミュニティ境界が生じ，コストのしきい値を設定することでコミュニ テ イ分 割でき ること を明ら かに した．
第3章では ，一部 グラフ で用い られ るコミ ュニテ イ内リ ンク 密度に 基づく コミュ ニティ構造評価 指 標で あるモ ジュラ リテイ を二 部グラ フ用に 改良し た，モ ジュラリテイはコミュニテイ間のりンク 密 度を 考慮し ていないため．多対多の関係を考慮できない．そのため，コミュニティ間対応度を導入 し ．全 コミュ ニテイ間リンク密度を評価に組み込んだ指標を提案した．多対多のコミュニテイ関係を 持 つ 最 も シ ン プル な モ デ ル であ るW型 二部 グラフ に対し て様々 なコミ ュニ テイ構 造にお ける提 案
一693―
指 標の 値 を 計 測 した 結 果 ， 多 対 多の コ ミ ュ ニ ティ 関 係 を 表 して い る 構 造 に対 し て は 最 大値を とるこ と を明 ら か に し ，提 案 指 標 の 有 効性 を 示 し た ．
第4章 で は ， 提 案し た 指 標 を 最大 化 さ せ る コ ミュ ニ テ イ 構 造を 高 速 に 得 る方 法 を 凝 集 的貪 欲 法 に 基 づき 提 案 し た ．ま ず ， 多 対 多 のコ ミ ュ ニテ ィ対 応関係 を持つ 小さな 二部 グラフ におけ る．コ ミュニ テ ィ数 と 提 案 指 標の 値 の 関 係 を 解析 し ． 各 コ ミュ ニ テ ィ 数 にお け る 最 大 値が 全 体 の 最 大値に 向かっ て 山状 に な る 一 方， コ ミ ュ ニ テ ィ数 に 関 わら ず広 い範囲 で指標 値が分 散す ること を明ら かにし た，そ の 結果 に 支 持 さ れて ， 凝 集 的 貪 欲法 を 提 案し ，そ の計算 量を結 合ペア の限 定と差 分計算 により 削減す る 方法 を 提 案 し た．
第5章 で は ， 有 向グ ラ フ を 出 部集 合 と 出 部 集 合で 構 成 さ れ る二 部 グ ラ フ に変 換 す る こ とで ， 類 似 し た受 信 コ ミ ュ ニテ ィ に り ン ク が存 在 す る 送 信コ ミ ュ ニ テ ィ， ま た そ の 逆を 得 る こ と が可能 となる 方 法を 提 案 し た ．ま た ， 受 信 コ ミュ ニ テ ィと 送信 コミュ ニテイ との対 応関 係から コミュ ニティ の機能 を 同定 す る 方 法 も提 案 し た.C.elegansの 神経 細胞網 に対し て提 案方法 を適用 した結 果，収 集， 拡散，
蓄 積， 伝 達 の 機 能を 抽 出 し ， か つ蓄 積 機 能を 持つ コミュ ニティ は同時 に収 集や拡 散の機 能を持 ち合わ せ てい る 場 合 が 多い こ と を 明 ら かに し た ，
第6章 で は ，こ こ ま で の 結論 を 取 り ま とめ た ，
‑ 694―
学位論文審査の要旨
学 位 論 文 題 名
Extracting IVIany − to‑many Related Communities in Bipartite Graph
（二部グラフにおける多対多に関係するコミュニテイの抽出）
本学位論文では，一 部グラフ変換せず ，多対多のコミュ ニティ対応関係を考慮することで，二部グ ラ フ にお ける よ り精度の高いコミ ュニティ分割を得 る方法を提案し．そ の有効性を検証す ることを 目 的としている，
異 なる ニつ の 集合間の対応をグ ラフで表現したも のは二部グラフと呼 ばれる．グラフで 表現した そ れぞれの集合には， コミュニティと呼 ばれる，別の集合 の部分集合との対応関係が類似した部分集 合 が存在している，こ のようなコミュニ ティの発見は、シ ステムの内在する関係構造を理解するのに 貢 献している．従来の 二部グラフにおけ るコミュニティ抽 出方法は，非常に高速にコミュニティ構造 を 得ることができたが ，一方で二部グラ フの一部グラフ変 換やコミュニティ外部の無視など，精度に 問 題があることが指摘 されていた．そこで本論文では，まず，二部グラフのコミュニティ分割問題を，
ノ ー ドに おけ る 巡回 セー ル スマ ン問 題に置 き換え，/一ド間コスト関数 と局所クラスタリ ング組織 化 法 によ る巡 回 経路コスト最適化 を用いて，コミュ ニティ間コストによ るコミュニティ分 割方法を 提 案している，さらに ，二部グラフにお ける複数の生成モ デルに対して提案方法の有効性を検証して い る．次に、二部グラ フにおける多対多 のコミュニティ対 応関係を考慮したモジュラリティの指標を 新 た に提 案し て いる．また，提案 指標を様々を二部 グラフとコミュニテ ィ分割に対して適 用するこ と で，その有効性を確 認している，さら に，与えられた二 部グラフに対して提案指標が極大となるコ ミ ュニティ構造を実質 的な計算時間で発 見する方法を提案 している．これを用いて数千ノード．一万 リ ン ク程 度の 現 実二部グラフをコ ミュニティ分割し て，その有効性を明 らかにしている， 応用とし て は，有向グラフを出 部と入部の二部グ ラフとみをしてコ ミュニティ分割する方法を提案している，
ま た この 方法 か ら得られたコミュ ニティ構造から， コミュニティの機能 を矧定する方法を 示してい る ．具体的な適用とし て現実に有向グラ フとして知られるC.elegansの神経細胞網を解 析し，そのコ ミ ュニティ機能を明確 にしている．
第1章では ，研究背景として ，複雑ネットワーク 科学の始まり，複 雑ネットワークと しての二部グ ラ フ，コミュニティ分 割における関連研 究，さらに研究目 的について述べた，研究目的として二部グ ラ フ にお ける 多 対多に関係しあう コミュニティ構造 を抽出する方法を確 立し．現実の二部 グラフの コ ミュニティ間関係を 明らかにすること を述べている．
第2章 で は、 隣接 ノ ード 関係 を 用い たノード間コ スト関数と巡回経路 コスト最適化法に 基づくコ
―695―
志 仁 二 雄 人 正 正 恵 哲 雅 川 原 木 野 本
． 古
栗 鈴
小 山
授 授
授 授
授
教
教 教
教 教
准
査 査
査 査
査
主 副
副 副
副
ミュニティ分割方法を提案している，ノード問コスト関数にはコサイン類似度，巡回経路コスト最適 化 法 に局 所クラスタ リンク組織化法を採用した ，二部穴居人モデル及びによ り二部CNNモデルに よ り生成した二部グラフに対し て提案方法を適用した結果，丿ード間コストの頻度分布が多峰的と をり，コミュニティ内コストとコミュニティ境界が生じ，コストのしきい値を設定することでコミュ ニティ分割可能をことを明らかにしている，
第3章では，一部グラフで用 いられるコミュニティ内リン ク密度に基づくコミュニティ構造評価 指 標であるモジュラリティを二 部グラフ用に改良した．モジュラリティはコミュニティ間のりンク 密度を考慮していないため，多対多の関係を考慮できをい．そのため，コミュニティ間対応度を導入 し，全コミュニティ間リンク密度を評価に組み込んだ指標を新たに提案している．多対多のコミュニ テ ィ 関係 を持つ最も シンプルなモデルであるW型 二部グラフに対して様々な コミュニティ構造に お ける提案指標の値を計測した 結果，多対多のコミュニティ関係を表している構造に対して提案指 標は極大値をとることを明らかにし，提案指標の有効性を示している．
第4章では，提案した指標を 最大化させるコミュニティ構 造を高速に得る方法を凝集的貪欲法に 基づぃて提案している．まず，多対多のコミュニティ対応関係を持つ小さを二部グラフにおける、コ ミ ュニティ数と提案指標の値の 関係を解析して，各コミュニティ数における最大値が全体の最大値 に 向かって山状に分布するが， 一方でコミュニティ数に関わらず広い範囲で指標値が分散すること を明らかにしている，その結果を実現するよう極凝集的貪欲法を提案し，その計算量を結合ベアの限 定と差分計算により削減する方法を提案レている．
第5章では，有向グラフを出 部集合と入部集合で構成され る二部グラフに変換することで．類似 し た受信コミュニティにりンク が存在する送信コミュニティ，またその逆を得ることが可能とをる 方法を提案している．また，受信コミュニティと送信コミュニティとの対応関係からコミュニティの 機 能を同定する方法も提案して いる．これらの方法をC.elegansの神経細胞網に対して適用した結 果，収集，拡散，蓄積，伝達の機能が抽出でき，かつ蓄積機能を持つコミュニティは同時に収集や拡散 の機能を持ち合わせている場合が多いことを明確にしている．
第6章では，本論文のまとめと今後の展望が述べられている．
これを要するに，本論文では，従来は一部グラフに変換しをければ行えをかったコミュニティ分割 に対し，数理最適化の方法と二部グラフのための新規なモジュラリティ指標が提案され，それらの有 効性が検証されている．このことは大規模を二部グラフの高速を解析とその応用を可能とするため，
複雑ネットワークの理論および複雑系工学に寄与するところ大であり，博士（情報科学）の学位を授 与するに値するものと認める，
