特許ウォッチ

公開番号2024172295
公報種別公開特許公報(A)
公開日2024-12-12
出願番号2023089910
出願日2023-05-31
発明の名称探索装置、探索方法及びプログラム
出願人日本電信電話株式会社,国立大学法人筑波大学
代理人弁理士法人志賀国際特許事務所
主分類G06F 16/28 20190101AFI20241205BHJP(計算;計数)
要約【課題】与えられたグラフにおける最大の「k-plex」を探索する速度を向上させることが可能である探索装置、探索方法及びプログラムを提供する。
【解決手段】探索装置は、グラフにおける1以上の部分グラフのうちの最大の部分グラフのサイズを決定する決定部と、いずれの部分グラフにも含まれないノードをグラフから削除する削除部と、ノードが削除されたグラフにおいて、サイズの部分グラフを探索する探索部とを備える。探索部は、ノードが削除されたグラフにおけるノード対を併合し、ノード対が併合されたグラフにおいて、サイズの部分グラフを探索する。
【選択図】図1
特許請求の範囲【請求項１】
グラフにおける１以上の部分グラフのうちの最大の前記部分グラフのサイズを決定する決定部と、
いずれの前記部分グラフにも含まれないノードを前記グラフから削除する削除部と、
前記ノードが削除された前記グラフにおいて、前記サイズの前記部分グラフを探索する探索部と
を備える探索装置。
続きを表示（約 470 文字）【請求項２】
前記探索部は、前記ノードが削除された前記グラフにおけるノード対を併合し、前記ノード対が併合された前記グラフにおいて、前記サイズの前記部分グラフを探索する、請求項１に記載の探索装置。
【請求項３】
探索装置が実行する探索方法であって、
グラフにおける１以上の部分グラフのうちの最大の前記部分グラフのサイズを決定するステップと、
いずれの前記部分グラフにも含まれないノードを前記グラフから削除するステップと、
前記ノードが削除された前記グラフにおいて、前記サイズの前記部分グラフを探索するステップと
を含む探索方法。
【請求項４】
コンピュータに、
グラフにおける１以上の部分グラフのうちの最大の前記部分グラフのサイズを決定する手順と、
いずれの前記部分グラフにも含まれないノードを前記グラフから削除する手順と、
前記ノードが削除された前記グラフにおいて、前記サイズの前記部分グラフを探索する手順と
を実行させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、探索装置、探索方法及びプログラムに関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
ソーシャルネットワークにおけるユーザの行動分析に用いられる技術の一つとして、最大の密部分グラフをソーシャルネットワークのモデルとしてのグラフから抽出する技術がある。その最も代表的な技術として、与えられたグラフにおける最大のクリークを探索する技術がある。クリークとは、ノードの集合における任意の２ノードの間にエッジが存在するという部分グラフである。したがって、クリークは、頑健な密部分グラフの一つである。最大クリーク探索は幅広い分野で応用されているが、最大クリーク探索には二つの問題点がある。
【０００３】
実世界のソーシャルネットワークにはスケールフリー性があることから、ソーシャルネットワークにおけるコミュニティ（部分グラフ）が多様な密度を持つという点が、第１の問題点である。その結果として、最大クリーク探索の既存技術では、実世界のソーシャルネットワークにおけるコミュニティを正確に発見することが困難である。
【０００４】
最大クリーク探索の既存技術では、実世界のソーシャルネットワークにおけるコミュニティの密度及びサイズに対して非常に密度が高く且つ非常に小さい部分グラフが同定されてしまうという点が、第２の問題点である。その結果として、最大クリーク探索の既存技術では、実世界のソーシャルネットワークにおけるコミュニティを正確に発見することが困難である。
【０００５】
これらの問題を解決する技術として、最大の「ｋ－ｐｌｅｘ」を探索する技術がある（非特許文献１参照）。「ｋ－ｐｌｅｘ」（ｋ－網）は、一般化されたクリークである。具体的には、「ｋ－ｐｌｅｘ」は、ｎ個のノードから構成された部分グラフの各ノードが、その部分グラフにおける「ｎ－ｋ」個以上のノードに隣接するという、部分グラフ（密部分グラフ）である。ここで、「ｋ」は、正の整数である。「ｋ－ｐｌｅｘ」は密度及びサイズのバランスに優れているので、実世界のソーシャルネットワークにおける大きな密部分グラフを最大のｋ－ｐｌｅｘの探索によって抽出することが可能である。
【先行技術文献】
【非特許文献】
【０００６】
B. Balasundaram, S. Butenko, I. V. Hicks, and S. Sachdeva, "Clique Relaxations in Social Network Analysis: The Maximum k-plex Problem", Operations Research, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
与えられたグラフにおける最大の「ｋ－ｐｌｅｘ」を見つけるという問題はＮＰ困難問題（Non-deterministic Polynomial Time Hard Problem）であることが知られている。具体的には、最大の「ｋ－ｐｌｅｘ」の探索において、素朴なアルゴリズムが用いられた場合、「Ｏ（２
｜ＶＧ｜
｜Ｖ
Ｇ
｜）」という計算時間が必要である。ここで、「Ｖ
Ｇ
」は、グラフ「Ｇ」におけるノードの集合を表す。また、「｜Ｖ
Ｇ
｜」は、「Ｖ
Ｇ
」に含まれるノードの個数を表す。
【０００８】
しかしながら、近年のソーシャルネットワークのサイズは巨大である。このため、最大の「ｋ－ｐｌｅｘ」の探索には、数日程度の計算時間を要することがある。このように、与えられたグラフにおける最大の「ｋ－ｐｌｅｘ」を探索する速度を向上させることができないという問題がある。
【０００９】
上記事情に鑑み、本発明は、与えられたグラフにおける最大の「ｋ－ｐｌｅｘ」を探索する速度を向上させることが可能である探索装置、探索方法及びプログラムを提供することを目的としている。
【課題を解決するための手段】
【００１０】
本発明の一態様は、グラフにおける１以上の部分グラフのうちの最大の前記部分グラフのサイズを決定する決定部と、いずれの前記部分グラフにも含まれないノードを前記グラフから削除する削除部と、前記ノードが削除された前記グラフにおいて、前記サイズの前記部分グラフを探索する探索部とを備える探索装置である。
（【００１１】以降は省略されています）

関連特許