バージニア大学工学応用科学部のニコラオス・シディロプロス教授は、新しい計算アルゴリズムの開発によりグラフマイニングに画期的な進歩をもたらしました。

グラフマイニング、ソーシャルメディア接続などのネットワークを分析する方法生物学的システムは、研究者がさまざまな要素がどのように相互作用するかについて意味のあるパターンを発見するのに役立ちます。新しいアルゴリズムは、大規模ネットワーク内で密接に接続されたクラスター (三角形密サブグラフとして知られる) を見つけるという長年の課題に対処します。この問題は、不正行為検出、計算生物学、データ分析などの分野で重要な問題です。

この研究は、知識およびデータエンジニアリングに関するIEEEトランザクションは、ベルギーのルーヴェン大学の電気工学助教授で、以前は UVA の研究員だったアリトラ・コナール氏が率いる共同研究でした。

グラフ マイニング アルゴリズムは通常、ソーシャル メディアで頻繁に通信する 2 人の人物など、ポイントの個々のペア間の密なつながりを見つけることに重点を置いています。しかし、Triangle-Densest-k-Subgraph問題として知られる研究者の新しい方法は、接続の三角形、つまり各ペアがリンクされている3点のグループを調べることによってさらに一歩進んでいます。このアプローチは、相互作用する友人の小グループや、生物学的プロセスで連携して機能する遺伝子のクラスターなど、より密接に結びついた関係を捉えます。

「私たちの手法は、単一の接続だけを調べるのではなく、3 つの要素のグループがどのように相互作用するかを考慮します。これは、より多くのことを理解するために重要です」複雑なネットワーク電気・コンピュータ工学科教授のシディロプロス氏は、「これにより、たとえ大規模なデータセットであっても、より意味のあるパターンを見つけることができるようになります」と説明した。

三角形が密集した部分グラフを見つけることは、従来の方法では効率的に解決することが難しいため、特に困難です。しかし、新しいアルゴリズムは、サブモジュラー緩和と呼ばれるものを使用します。これは、重要な詳細を失うことなく問題をより迅速に解決できる程度に問題を単純化する賢いショートカットです。

このブレークスルーにより、より深い複数の接続関係に依存する複雑なシステムを理解するための新たな可能性が開かれます。サブグループとパターンを特定すると、発見に役立つ可能性があります不審な活動詐欺の場合、コミュニティの動向を特定するソーシャルメディア、または研究者がタンパク質の相互作用や遺伝的関係をより正確に分析できるように支援します。

詳細情報:Aritra Konar et al、固定サイズの三角形密度の高いサブグラフのマイニング: 硬度、ロヴァシュ拡張、および「アプリケーション」、知識およびデータエンジニアリングに関するIEEEトランザクション（2024年）。DOI: 10.1109/TKDE.2024.3444608