Neteco08 Oral and Poster (Y.Hayashi)

第4回シンポ 招待講演概要

<招待講演1>
西口 敏宏 氏, 一橋大学イノベーション研究センター 教授
題目:遠距離交際と近所づきあい -成功する組織ネットワーク戦略-
概要: 本講演では, 拙著「遠距離交際と近所づきあい -成功する組織ネットワーク戦略-」 (2007年1月NTT出版)の内容を紹介し, その意義を探りたいと思います. 学術的水準を保ちながら, わかりやすい解説を目指します. 何の変哲もない個人, 組織, 地域が, 特に恵まれた環境でもないのに, 困難を乗り越え, 目立って繁栄する場合があります. 本書は, 世界各地から収集した独自の事例と最新のネットワーク理論から, その秘密と法則に迫ります. 四半世紀にわたる独自調査と研究に基づいて, ネットワーク理論の成果を平易に解説し, 社会や組織で成功するためにはといった実践面と, 社会ネットワーク論の学術的な論議の両面で, 知的刺激に富むお話をしたいと思います.

<招待講演2>
藤田 聡 氏, 広島大学大学院 工学研究科 情報工学専攻 教授
題目: 分散ネットワーク上の情報検索問題
概要: 本講演では,自律的に動作するノードが相互結合されたネットワーク上で, 必要な情報を効率よく検索する手法について解説します.

<最新報告>
金光 淳 氏, 京都産業大学 経営学部 ソーシャル・マネジメント学科 講師
題目: INSNA28からみた社会ネットワーク分析の動向
概要: INSNA28にフルに参加して得た世界の社会ネットワーク分析の動向を報告する. どのような分野まで応用が広がっているか, 注目すべき発表, テーマの分類, 何が問題になっているか, 注目人物は誰か, 新しい技法・新しいツール開発などの現状を報告します. また参与観察して得た社会ネットワーク分析界の交流関係などについても報告します.

<活動総括>
上林 憲行 氏(研究会主査), 東京工科大学 情報メディア学部 教授
題目: ネットワークからネットワーキングへ
-ネットワーク生態学研究グループのレビューとパースペクティブ-
概要: ここ数年, 世界を, ネットワークの視点を通じて解き明かす, ネットワークサイエンスの重要性・可能性の理解が深まり, 様々な分野での活用や浸透は確実に進行中である. そうした状況について, ネットワーク生態学研究グループの活動を基軸にしたレビューと, 今後のパースペクティブについて述べる.

ポスター発表1

P1-1: 小野 泰正, 林 幸雄(北陸先端科学技術大学院大学)
題目: 複雑ネットワーク上でのダイナミクス研究ツール
概要: 近年の複雑ネットワーク研究における分析・シミュレーションツールの動向をふまえて、ネットワーク構造とその上でのトラフィックなどのダイナミクスを調べるのに適した、シミュレーターを紹介する。

P1-3: 豊田 規人(北海道情報大学)
題目: 6次の隔りに関する理論的考察II
概要: I.半世紀前のPoolの6時の隔たりに関する理論的考察を,コンピューターを使って再考する. II. 我々の提案したPropagation Coefficient Modelを使いPoolの考察において平均クラスタリング係数を求め考察. III.クラスタリング係数の世代分布などについて考察

P1-4: 山出 真也, 白山 晋(東京大学)
題目: 複雑ネットワークを用いた群集シミュレーションによる動線計画支援
概要: 近年,群集シミュレーシュンによる動線計画が行われているが,その代表的手法であるセルオートマトン(CA)法には,空間分割と局所移動の制約のために適切な群集行動のパターンを得られないという問題点がある. 本研究では,CA法にネットワーク構造を導入し,エージェントの移動に多様性を持たせることで様々な群集行動パターンを表出させ,それを動線計画に利用することを提案する. 発表では,提案手法による群集行動に特徴的なパターンの表出,また提案手法による実際の動線計画例を紹介し,提案手法の有用性を示す.

P1-5: 松林 達史, 山田 武士(NTTコミュニケーション科学基礎研究所), 藤村 滋, 藤村 考(NTTサイバーソリューション研究所)
題目: ラベル付きグラフ可視化の新手法
概要: 本研究では,ラベル付きグラフ可視化のための,ラベル同士が重ならない効率的な可視化座標計算の手法を提案する.従来のラベル付きグラフ可視化の座標計算アルゴリズムはForce-directed 法やバネモデルといった,ノードを“点” として扱う座標計算を行うために,文字列や,異なるサイズのラベルを扱う時にはラベル同士が重なってしまうと言う問題が生じる.ラベルの重なりを回避する手法はいくつか提案されて来たが,いずれの手法も可視化計算を行った後に,再び座標計算処理を必要とする.これ等の手法では大規模なグラフ可視化では計算量が莫大になり,さらに元の可視化結果を破壊してしまうという問題も生じる.本研究では,各ノードにラベルサイズに依存した固有楕円ポテンシャルを与え,ラベルの大きさを考慮する事によって,ラベル同士の重なりを回避する手法を提案する.

P1-6: 坪坂 正志, 増田 直紀(東京大学大学院情報理工学系研究科)
題目: Group betweennessに基づく特徴的ノード抽出とその応用
概要: 最近, Puzisらが提案したGroup betweennessを用いた特徴的ノード集合の抽出アルゴリズム(Phys. Rev. E 76, 056709)の計算速度の改善とその応用例について述べる.

P1-7: 亀山 周明, 内田 誠, 白山 晋(東京大学)
題目: 部分グラフ構造を用いたコミュニティの分類について
概要: 多くのネットワーク型データのノードでは、それらのネットワーク上での役割・現象と構造・配置とに大きく関連がある。ネットワークの構造を調べ構造の似たノードを特定することは、ネットワークの特徴を捉えること、ネットワーク上で起きる現象について考えることにも、非常に重要な視座を与えると考えられる。 本稿では、部分グラフ構造から得られるノードの類似度を用いて、ネットワークの構造情報、具体的には(1)ネットワークモチーフ、(2)2部グラフ構造、(3)構造同値、を得る方法を紹介する。

P1-8: 濱岡 豊(慶應義塾大学商学部)
題目: オンライン・コミュニティの社会ネットワーク特性とイノベーションの普及パターン
概要: 本研究ではオンラインコミュニティのコミュニケーション特性と、そこでのソフトウエアの普及の関係を分析した。Sourceforge.netにおける236のオープンソース・ソフトウエア・プロジェクトにおいて開発されたソフトウエアの月次のダウンロード数にBassモデルをあてはめ、革新者係数、模倣者係数、潜在市場を推定した。さらに、各プロジェクトでのフォーラムでのコミュニケーションから、社会ネットワーク変数を算出した。推定されたBassモデルのパラメタを各オープンソース・ソフトウエア・プロジェクトの特性および社会ネットワーク変数によって説明した。プロジェクトの特性変数については、外部にリンク(ホームページ)をもつプロジェクトほど、革新者係数、模倣者が高いこと、遅く登録したプロジェクトほど模倣係数が高いことなどが示された。社会ネットワーク変数については、密度は潜在市場と正、多重性は革新者係数とは正、模倣者係数とは負、潜在市場とは負の相関があることなど、有意に説明することが示された。

P1-9: 上山 憲昭, 川原 亮一, 長谷川 治久(NTTサービスインテグレーション基盤研究所)
題目: コンテンツ並列配信に効果的な網トポロジに関する評価
概要: 高精細動画のビットレートは非常に高く,インターネット上で配信を行う場合,他のフローに与える影響が懸念される.この問題に対する一つの解決法は,ネットワーク内に多数のサーバを配置し一人のユーザに対して複数のサーバから並列配信を行うことである.本発表では,商用ISPの網トポロジを用いた評価を行い,並列配信の効果は網トポロジに強く依存することを示す.また,平均リンク負荷の増加を避けながらリンク負荷の偏りを低減するために,網トポロジとサーバ配置法に求められる条件を明らかにする.

P1-10: 高口 太朗(京都大学工学部情報学科 )
題目: Watts-Strogatzモデルにおける遷移確率行列の固有値統計
概要: ネットワークにおける遷移確率行列の固有値はネットワーク上の拡散現象と関連がある.本ポスターでは,スモールワールド性を示すネットワークモデルとして知られているWatts-Strogatzモデルにおいて遷移確率行列の固有値の統計解析を行い,ネットワーク上のランダムウォークの性質がどのように固有値の統計と関係しているかを調べた結果を報告する.本ポスターは特に,遷移確率行列の最近接固有値間隔に注目した.最近接固有値間隔は,遷移確率行列の固有値を実部の大きい順に並べたとき,隣り合う2固有値の実部の差として定義する. ノード数N=1000,平均次数k=10としたWatts-Strogatzモデルにおいて最近接固有値間隔を計算した結果,最近接固有値間隔の分布はつなぎ変え確率p=0の場合でも複雑な構造をもち,pの増大に伴いネットワークが十分ランダムなリンク構造に変わるpの前後で,明白に分布の概形が変わることがわかった.加えて,ネットワークがスモールワールド性を示すpの範囲では,最大固有値と第2固有値との間隔がpに対しべき的に変化することを見出した.さらにk=10に固定してネットワークサイズNを変え,スモールワールド性を示すpの範囲と,最大固有値と第2固有値との間隔のべき的変化との関係を調べた.その結果,クラスター係数C(p)と最短経路長L(p)の変化の仕方は前者はNにほとんど依存しないが後者はNに強く依存することから,スモールワールド性を示すpの範囲がL(p)の変化の仕方のみによって決まり,その範囲はNが大きくなるにつれて広がることが確認された.またそのpの範囲は,やはり最大固有値と第2固有値との間隔がpに対しべき的に変化する範囲と重なった.この事実から,スモールワールドネットワークはpの増加に従い格子ネットワークからランダムネットワークへ移り変わる間の臨界的な状態であり,最大固有値と第2固有値との間隔がその状態の変化をよく表していることを明らかにした.

P1-11: 馬 シャオジュン, 坪下 幸寛, 岡本 洋(富士ゼロックス(株)研究本部)
題目: 引用ネットワークにおける確率分布に基づく科学論文のランク付け
概要: Googleの RageRankアルゴリズムは、Webページ間のリンク関係が構成するネットワークにおける確率の再帰的伝播の平衡状態分布を用いて、個々のWebページの重要度判定およびランク付けを行う。論文引用関係とウェブページリンク関係との類似性から、PageRankアルゴリズムを科学論文引用ネットワークに適用し、個々の論文のランク付けを行うことが期待される。しかしながら、引用は常に過去に向かって一方向である。従って、論文引用ネットワークにおける確率伝播には平衡状態が存在せず、単純には、PageRankアルゴリズムアルゴリズムを適用できない。我々は引用ネットワークを適切に双方向化することにより、ネットワークを再帰的にし、確率伝播に平衡状態を持たせることを提案した。そして、このように双方向化された引用ネットワークにPageRank アルゴリズム適用して、個々の科学論文の重要度判定・ランク付けを試みた。

ポスター発表2

P2-2: レオン末松豊インティ(NiCT/ATR CIS 応用ネットワーク科学研究室)
題目: コミュニティ構造高速抽出プラットフォームの構築
概要: 大規模なネットワークから高速にコミュ二ティ抽出するために,従来法であるClauset, Newman, MooreによるCNM法の改良を図った.先行研究で個別に検討されていた複数のアルゴリズムの性能比較を実装レベルから可能にするため,コミュ二ティ抽出プラットフォームを構築した.この段階でデータ構造と実装上の改良から同じCNMアルゴリズムで7倍の性能向上が確認された.また先行研究のDanon, Diaz, ArenasによるDDA法では,抽出性能の指標であるQ値の向上が知られていたが,速度向上は無いと報告されていた.我々は,DDA法をプラットフォームに乗せるべく改良し,その結果,100万ノード規模で, 14分でQ値を向上させつつ抽出し,192倍の速度性能の向上を達成した.最大では1000万ノード規模まで適用した.

P2-3: 塚本 鋭, 白山 晋(東京大学)
題目: 集団における意思決定プロセスへのネットワーク構造の影響
概要: 集団における意思決定プロセスを分析するためにネットワーク構造を導入したN人版繰り返し囚人のジレンマ問題を扱う.協調戦略を選択する行動主体が集団の総意を左右するものとし,ネットワークの次数分布,平均次数,次数分散,次数相関,クラスター係数の違いが協調の進化(集団中の協調戦略を選択する行動主体が増加すること)へ与える影響を調べる.それぞれの影響を明らかにするとともに,従来研究では指摘されていない次数分散の影響が大きいことを示した.

P2-4: 杉山 浩平, 大崎 博之, 今瀬 真(大阪大学大学院情報科学研究科), 八木 毅, 村山 純一(NTT情報通信プラットホーム研究所)
題目: 複雑ネットワークのトポロジ構造を利用したネットワークマイニングフレームワーク
概要: 近年、リンクマイニングに代表される、複雑ネットワークのトポロジ構造を利用するさまざまな取り組みが活発に行われている。これまで数多くのリンクマイニング手法が提案されているが、これらは異なる分野でそれぞれ独立に研究されてきた。このため現状では、それらのリンクマイニング手法を相互に連携させて利用することは困難である。そこで本発表では、さまざまなリンクマイニング手法や従来のデータマイニング手法を統合的に扱うことができる、「ネットワークマイニング」のためのフレームワーク NMF (Network Mining Framework) を提案する。NMF は、入出力の形式が統一された 7 種類の機能ブロックによって構成され、これらの機能ブロックを自由に接続することにより、さまざまなネットワークマイニング手法の実現を可能とする。さらに本発表では、NMF の利用例を示し、NMF によって高度なネットワークマイニングが可能となることを示す。

P2-5: 松久保 潤(北九州工業高等専門学校 ), 林 幸雄(北陸先端科学技術大学院大学)
題目: リンクの重みを考慮したWebコミュニティ探索法
概要: Web上には類似する話題を扱う,または共通した事柄に興味のある頁同士が密に結合したリンク構造がある.このリンク構造をWebコミュニティと呼ぶ.本報告では,Webコミュニティの核となる頁を効率的に探索するために,探索中に発見された局所的なリンク構造から頁の重みを求めながら,最も価値が高いと思われる頁を探索する.提案手法を用いた実験の結果,異なる話題を扱うWebコミュニティを横断しながら探索することを発見した.

P2-6: 山田 泰寛(九州大学情報基盤研究開発センター), 飯野 由里江(九州大学大学院システム情報学府), 廣川 佐千男(九州大学情報基盤研究開発センター)
題目: マトリックス検索による特許発明者群の分析
概要: 検索結果を二つの観点から分類するマトリックス検索を用いて、特許情報における発明者群を分析する手法を提案する。分析対象の企業あるいは分野を限定し、発明者群とIPC、あるいは発明者群とキーワードの対応を見ることで、研究グループの特性を分析する。また、一方の観点を筆頭発明者、他方の観点を発明者とすることで、より詳細な研究体制を分析する。

P2-7: 多田翔太, 池田裕貴, 白坂龍平, 上林 憲行(東京工科大学メディア学部)
題目: 大学4年生を対象としたソシオセントリック・ネットワークの可視化と分析
概要: 500規模の大学4年生(東京工科大学メディア学部4年生)を対象とした、ソシオセントリック・ネットワークの生成とその可視化を行った。 分析の視点としては、 ・ネットワークの安定性を検証(多田) ・コミュニティとクリーク分析(池田) ・学生同士の関係を3種類に分類した目的別ネットワークの特徴(白坂) について発表を行う。

P2-8: 出尾 美佳, 江島 啓, 宮崎 修次(京都大学大学院情報学研究科複雑系科学専攻)
題目: 社会ネットワークの大偏差解析
概要: 本研究では,新たなネットワーク解析手法の提案を目標として,ネットワークに大偏差 統計理論を適用し,解析をおこなった. ネットワーク上のランダムウォークは,区分線形写像によって生成されるカオスに対応 付ける事ができる.さらに,その時系列に大偏差統計解析を適用する事により,特性関数・重み付き平均・重み付き分散などを導くことができる.これらは統計構造関数と呼ばれ,時系列の揺らぎの性質を取り出す道具である.まず,ノード数2 の簡単なネットワークを用いて,大偏差統計解析の例示を行った.次に,国内最大のソーシャル・ネットワーキング・サービスであるmixi(ミクシィ)から,適当なサイズの部分ネットワークを抽出し,解析をおこなった.その結果,重み付き平均の急峻な変化(q-相転移)が見られた.それぞれの相においては,ごく少数のノードのみが統計構造関数に寄与していることが確認された.また,強調されたノード同士は密なリンクを持っていたことから,q-相転移はクラスター構造が影響していると考えることができる.さらに,小規模なネットワークモデルを用いて,q-相転移とクラスター構造の関係,及びmixi ネットワークの特徴を考察する.

ポスター発表3

P3-1: 新井 賢一, 水谷 伸(NTTコミュニケーション科学基礎研究所), 荒川 伸一, 村田 正幸(大阪大学大学院情報科学研究科)
題目: ネットワークトラッフィクにおける自由相・混雑相の転移について
概要: 本発表では、ネットワークのパケット配送においてみられる自由相から混雑相への転移について報告する。各ノードでのパケット発生率が低いうちはほぼ一定の時間ラグでパケットは目的のノードに達する。しかし、ある程度以上のパケット発生率では、ネットワーク内のパケットは時間とともに増大していき、パケットは一定の時間内に目的ノードに到達することはできない。前者を自由相、後者を混雑相と呼ぶことにする。ここでは、ネットワークのトポロジーとして、格子状のネットワーク、ランダムネットワーク、Barabasi-Albert の方法により作成したスケールフリーネットワークの3種類を用い、配送経路として、よく使われる最短経路や混雑回避機構を追加したもので数値実験を行った。特に、臨界パケット発生率のネットワークサイズ依存性などに着目し、自由相から混雑相に転移する臨界点の振る舞いについて報告する。物理でいうところのいわゆる相転移現象との関連についても考察したい。

P3-2: 菅 あずさ, 綱脇 美栄香, 上林 憲行(東京工科大学メディア学部)
題目: ネットワーク分析を用いた恋人・異性親友・同性親友を対象としたパートナー研究
概要: 親しい2人を1組としたパートナー・ネットワークに着目し、研究を行った。具体的には恋人同士、異性親友同士、女性親友同士、男性親友同士の4タイプを対象とした。恋人同士、異性親友同士、女性親友同士はネットワーク密度や知人男性率が似ているネットワーク構造の人物同士がパートナーになっているという結果が得られた。また「夫婦の周囲の人同士が知り合いでない場合、夫婦は協力しあう」というボットの夫婦ネットワーク研究を踏まえ、恋人の共通の知人の多さと二人の協力度の関係を調べた。その結果、共通の知人、つまり互いの情報を間接的に伝えるチャンネルとなる人物が少ない恋人同士ほど、二人が協力しあっているということがわかった。

P3-3: 岡田 幸治(九州大学大学院数理学府), 井口修一, 溝口 佳寛(九州大学大学院数理学研究院), 廣川 左千男(九州大学情報基盤開発センター)
題目: リンク共起情報に基づく概念グラフの提案とWeb空間の解析
概要: Webページのリンクと被リンクによる有向グラフではなく、リンクの共起頻度を用いた概念グラフとして定式化し、それによるWeb空間の解析方法を提案する。あるキーワードの検索結果として得られるページ群を一つのWeb空間と捉え、そこに含まれるドメイン間の階層関係を概念グラフとして定式化する。通常の検索エンジンによるランキングとは異り、この階層は必ずしも全順序になるとは限らない。求まる階層関係の全順序の度合を表す線形度を定義し、いくつかの具体例について調査を行った。例えば、「国立大学」での検索結果のリンク構造を使い、大学間の階層関係を調べた結果、線形度は0.6となり単純なランキングとは異なることが分った。

P3-4: 中川 智晴, 奥矢 俊文, 上林 憲行(東京工科大学メディア学部)
題目: Yahoo!オークションの世界を対象としたネットワーキングの可視化と分析
概要: 本研究ではYahoo!オークションを研究対象とし、Yahoo!オークションで生成されるネットワーキングの特徴を、出品者と落札者の関係、カテゴリー同士の関係の2つの観点から調査、分析を行いましたので、発表いたします。

P3-5: 岡本 麻衣子(武蔵工業大学大学院工学研究科), 梶田 康博(武蔵工業大学工学部), 穴田 一(武蔵工業大学知識工学部)
題目: Bak-Sneppenモデルとネットワーク構造
概要: 複雑系に関する様々な研究が行われてきたが、相互作用が重要であると言われているにも関わらず、相互作用のネットワーク構造を考慮した研究は少ない。生物の進化モデルにBak-Sneppenモデルというものがある。このモデルは、相互作用しあう種同士の共進化を表したモデルであるが、ネットワーク構造を考慮していない。そこで、本研究では様々なネットワーク構造を用い、Bak-Sneppenモデルのネットワーク構造依存性について調べた。その結果、依存性があることが確かめられた。発表では、その結果とともに複雑系におけるネットワーク構造の重要性について述べる予定である。

P3-6: 藤村 滋, 藤村 考(NTTサイバーソリューション研究所), 松林 達史, 山田 武士(NTTコミュニケーション科学基礎研究所), 奥田 英範(NTTサイバーソリューション研究所)
題目: ブログのタグを基にした話題地形図の作成
概要: 本発表では,タグ同士の関連性をブログの記事集合を基にして算出した上で,関連するタグ同士をより近傍に配置し,背景画像として地形図のメタファを導入することによって,タグ間の関連を視覚的によりわかりやすく表示した話題地形図,Topigraphy(Topic + Topographyの造語)としてスクローラブルタグクラウドによって表示する手法を提案する.

P3-7: 内田 誠, 白山 晋(東京大学)
題目: 複雑ネットワークを導入したマルチエージェントモデルによる人工市場シミュレーション
概要: 携帯電話やEメールなどのコミュニケーションサービスに働くネットワーク外部性に関する研究は,マクロ統計的な分析から,マルチエージェントシミュレーションを利用した分析へと発展している.一方,マルチエージェントモデル等によって仮想的な市場を分析する場合,エージェントの相互作用をもたらす空間構造の影響が無視できないことも指摘されている.本研究では携帯電話市場を対象とし,ユーザーの意思決定をモデル化し複数のたマルチエージェントモデルを構築し,乗り換え費用が発生する2サービスが競合する市場におけるネットワーク外部性の効果を計算機シミュレーションによって調べる.この際,複雑ネットワークモデルによって市場のネットワーク構造をモデル化する.いくつかの異なるネットワークモデルを用いることで,ネットワークの空間構造が市場全体の振る舞いに及ぼす影響を分析する.さらに,現実のコミュニケーションネットワークのデータを用いて,提案モデルが現実の市場シミュレーションとしてどの程度有効であるか,および,携帯電話市場のモデルとしてどのようなネットワークが適当であるかを考察する.

P3-8: 高田 寛喜(奈良先端科学技術大学院大学), 山田 武士, 上田 修功(NTTコミュニケーション科学基礎研究所)
題目: ノードの機能特性に基づくクラスタリング
概要: 本研究では,ネットワークモチーフを用いてノードの特徴量を推定するための手法を提案する.実験ではカテゴリ情報が付与されたWikipediaの記事参照ネットワークを使用し,提案法と従来法の特徴量の違いによるクラスタリング結果の比較を行った.その結果,提案法による特徴量を用いたクラスタリングは,従来法に比べ人手に近い分類結果を獲得することが定量的に示された.

P3-9: 大竹 洋平(東京大学大学院・情報理工学系研究科)
題目: ネットワーク解析における集中性を測る指標の適用可能性
概要: ネットワークを分析する上で,ハブへの集中性を議論することは重要である.そのための指標として,様々な中心性やそれをもとにしたCentralizationが用いられてきている(Freeman, 1979). 本発表では,数学的な式展開とネットワークの例示を通して,Centralizationがハブへの一極集中のみしか測れず,多極集中の取り扱いには適用できないことを示す.さらに,同じ方法で,その点を補う指標として,ジニ係数の適用可能性を議論する. 現状では,ネットワーク解析において,Centralizationのみが使われているので,ジニ係数をはじめとした他の様々な指標も使っていくことが必要であると言える.

戻る