小特集 5. メンバー間の距離が小さいコミュニティの発見

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 5.

メンバー間の距離が小さいコミュニティの発見

Finding a Community with Small Diameter

朝廣雄一 宮野英次

朝廣雄一 九州産業大学理工学部情報科学科

宮野英次 正員 九州工業大学大学院情報工学研究院システム創成情報工学研究系

Yuichi ASAHIRO, Nonmember (Faculty of Science and Engineering, Kyushu Sangyo University, Fukuoka-shi, 813-8503 Japan) and Eiji MIYANO, Member (Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology, Fukuoka-shi, 820-8502 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.262-266 2018年3月

©電子情報通信学会2018

abstract

 人を頂点,友人関係を辺で表すことにより,人的ネットワークに対応するグラフ構造を考える.このようなグラフ構造に対して,緊密な関係にある人々のグループの中で大きなものを求めたい.緊密さとして様々な条件を考え得るが,グループに属する人々はお互いに直接の友人である,あるいは例えば友人の友人のように友人関係をたどると距離が小さい(math以下)という二つの条件に対応するクリーク問題とmath-クラブ問題が知られている.本稿では近似アルゴリズムの観点から,これらの二つの問題,特にmath-クラブ問題に関する研究動向について紹介する.

キーワード:クリーク,クラブ,近似下界,近似アルゴリズム

1.はじめに――クリークとクラブ――

 人を頂点,友人関係を辺で表したグラフ構造を考える.図1がその例で,例えば,mathさんとmathさんやmathさんとmathさんは直接の友人であるが,mathさんとmathさんは直接の友人ではないことを表している.ソーシャルネットワークサービスの利用者が持つ友人関係から,このようなグラフ構造が定義できる.今,何らかの理由で(例:ターゲット広告),友人関係が緊密なグループ(頂点集合の部分集合,簡単に頂点部分集合と呼ぶ)のうちできるだけ大きなものを発見したい.緊密であることの定義方法はいろいろあると思うが,その頂点部分集合に属している人たちはお互いに直接の友人であると定義してみる.図1では,頂点部分集合mathが,そのような構造を持っているもののうち最大のものである.この構造はクリークと呼ばれ,最大のクリークを求めることを目的とするクリーク問題は理論計算機科学では超有名である.

fig_1.png


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。