大規模ネットワークの性質と先端グラフアルゴリズム

本日，PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました．スライドは以下になります．

大規模ネットワークの性質と先端グラフアルゴリズム
View more presentations from iwiwi


Ustream の録画もあります．


内容としては，以下のようになっています．

  1. 現実世界のネットワークの特徴量と性質
    1. 次数分布
    2. 平均距離
    3. クラスター係数
    4. その他の特徴量
    5. 木っぽさ
  2. それらの性質を活用したグラフアルゴリズム
    1. セオリー方面
      1. 近接中心性の近似
      2. コンパクトルーティング
      3. 支配集合問題の近似
    2. プラクティカル方面
      1. 最短路
      2. 密部分グラフ列挙
      3. 可視化


タイトルは 1 年前にやった PFI セミナーと似ていますが，内容はあまりかぶっていません．今回は，グラフの性質とアルゴリズムの関係に焦点を置き，まずソーシャルネットワーク等のグラフが典型的に持つ性質を述べ，そのあとで，そういった性質を活用して良い性能を達成するアルゴリズムを紹介しています．

グラフの性質として述べたものは，基礎的なものが多いので，スケールフリーやスモールワールドといったキーワードなど，こっち方面の専門じゃない方でも聞いたことがある人も多いんじゃないかと思います．一方で，紹介したアルゴリズムは新しめのものとかちょっとマニアなものとかになってると思います．実際，僕が知る範囲では，こういったグラフの性質を活用したアルゴリズムというのはあまり多く無いと感じられ，かき集めるのが少し大変でした．