D-041 大規模社会ネットワークからのクラスタ構造の抽出(D分野:データベース)
スポンサーリンク
概要
- 論文の詳細を見る
Clauset, Newman, Mooreはネットワークをボトムアップかつ貪欲に解析する手法(CNMアルゴリズム)を提案し、50万ノード程度までの社会ネットワーク解析を可能としたが、それ以上の規模については実用的な時間内での解析は困難であった。そこでCNMアルゴリズムの合併の過程を観察した。その結果合併するクラスタサイズの不均衡が計算コストに大きく影響していることが明らかとなった。この観測から、合併するクラスタサイズの均衡がアルゴリズムの速度向上につながると考えた。本稿では、合併時のクラスタのサイズを考慮することにより合併比率を向上させる3種類の手法を提案する。提案手法の実験データセットとして、国内最大級のソーシャルネットワーキングサービスより2006年10月に取得した550万ユーザーの友人関係のネットワークを使用した。提案した3つの手法を用いたところ、CNMアルゴリズムに比べ劇的なスケーラビリティの向上がみられた。もっとも速度向上がみられた手法では、100万ノードに対して5分、400万ノードに対しては35分程度で解析する事に成功した。また別の手法では、50万ノードに対して50分(CNMアルゴリズムより7倍早い)で解析でき、モジュール性の向上にも成功した。
- 2007-08-22
著者
関連論文
- 彩色意図にもとづく色覚障害者のための再配色システム(セッション2:インタラクションデザイン:理論と実践(2))
- 属性文法に基づくテストプログラム生成器の設計と実装
- 仮想機械の仕様記述に基づくバイトコードインタプリタ生成系
- 仮想機械の仕様記述に基づくバイトコードインタプリタ生成系
- D-041 大規模社会ネットワークからのクラスタ構造の抽出(D分野:データベース)
- システムXEROにおける高水準データ定義/操作言語
- 一級継続の並行言語への導入
- Java言語上の細粒度マルチスレッドフレームワークにおける問題点の考察
- メモリ管理の性能評価基盤
- 属性文法の系統的デバッグ法におけるバグ絞り込みの効率化(プログラミングおよびプログラミング言語)
- アセンブリ言語上でのプログラム特化
- 10-217 東京工業大学におけるOCWの活用(口頭発表論文,オーガナイズドセッション「オープンコースウエアとその活用」-I)
- O-011 大規模スパムフィルタと実験環境の構築手法の提案(O分野:情報システム)
- 並列オブジェクト指向言語への安全な継承の導入について
- OOPSLA '89に参加して
- POPL2002/PEPM2002/PADL2002報告(プログラミング及びプログラミング言語)
- 属性文法に基づくグラフィカルユーザインタフェース生成系とその評価
- 仮想機械の仕様記述に基づくバイトコードインタプリタ生成系
- SSA形式を利用したPredicated Execution向け命令スケジューリング手法
- SSA形式を利用したPredicated Execution向け命令スケジューリング手法
- バッファ溢れ攻撃とその防御(コンピュータセキュリティシリーズ(1))
- メモリ管理機能のモジュラーかつ効率的な実装手法
- ウィルスをはじめとする悪性ソフトウエア
- ウィルスをはじめとする悪性ソフトウエア
- Java, C#の次に来るのは?(インタラクティブ・エッセイ)
- 属性文法に対するデバッガ
- 循環属性文法に基づく生成系Junについて
- 属性文法に対するデバッグ方式の構想
- 木属性文法とGUI生成系を利用したデバッガの作成
- 異機種分散環境上でのDcamlバイトコードコンパイラの設計と実現
- 異機種分散環境上でのDcamlネイティブコンパイラの設計と実現
- 異機種分散環境上のアプリケーション開発環境Dcamlシステムの構想
- 並行言語Harmony/2とその一級継続機構
- 東日本大震災 危機発生時の対応について考える:9.危機に試されるスマートフォンのアプリケーション
- 並行言語Harmony/2とその一級継続機構
- データベース指向OS XEROのデータベースシステム実現モデル
- データベース処理を指向した分散OS XEROの永続オブジェクト管理
- データベース処理を指向した分散オペレーティング・システムXEROの設計
- プログラミング言語処理系SqueakのSHARP Zaurusへの移植とその評価
- 低レベル命令セット仮想計算機を利用した混成環境におけるプロセス移送
- 高速実行可能な低レベル命令セット仮想計算機の設計
- 「情報処理学会論文誌 : プログラミング」の編集について
- 多言語に対応した自己記述をもったバイナリデータ形式
- 並行トランザクション機構の実装
- Actorモデルにもとづいた非同期並列プログラミング言語ActGPUのコンパイラの実装とその評価
- Actorモデルにもとづいた非同期並列プログラミング言語ActGPUのコンパイラの実装とその評価
- 解析表現文法とSchemeマクロ展開器を用いたJavaScript向けHygienic構文マクロシステムの実装