メンバー間の距離が小さいコミュニティの発見
Vol.101 No.3pp.262-266
発行日:2018/03/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 グラフアルゴリズムの最先端
専門分野:
キーワード:
クリーク, クラブ, 近似下界, 近似アルゴリズム,
本文:PDF(427.7KB)>>
あらまし:
人を頂点,友人関係を辺で表すことにより,人的ネットワークに対応するグラフ構造を考える.このようなグラフ構造に対して,緊密な関係にある人々のグループの中で大きなものを求めたい.緊密さとして様々な条件を考え得るが,グループに属する人々はお互いに直接の友人である,あるいは例えば友人の友人のように友人関係をたどると距離が小さい(d以下)という二つの条件に対応するクリーク問題とd-クラブ問題が知られている.本稿では近似アルゴリズムの観点から,これらの二つの問題,特にd-クラブ問題に関する研究動向について紹介する.