あらまし

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

朝廣 雄一 宮野 英次 

Vol.101 No.3pp.262-266

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集 グラフアルゴリズムの最先端

専門分野:

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

本文:PDF(427.7KB)

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

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355