버지니아대학교 공학 및 응용과학대학의 Nikolaos Sidiropoulos 교수는 새로운 계산 알고리즘을 개발하여 그래프 마이닝에 획기적인 발전을 가져왔습니다.

그래프 마이닝은 소셜 미디어 연결이나 네트워크와 같은 네트워크를 분석하는 방법입니다.생물학적 시스템는 연구자들이 다양한 요소가 상호 작용하는 방식에서 의미 있는 패턴을 발견하는 데 도움이 됩니다.새로운 알고리즘은 사기 탐지, 전산 생물학, 데이터 분석과 같은 분야에서 중요한 문제인 대규모 네트워크 내에서 긴밀하게 연결된 클러스터(삼각형 밀도 하위 그래프라고 함)를 찾는 오랜 과제를 해결합니다.

에 발표된 연구지식 및 데이터 엔지니어링에 관한 IEEE 거래, 이전에는 UVA의 연구 과학자였던 벨기에 KU Leuven의 전기 공학 조교수인 Aritra Konar가 주도한 공동 작업이었습니다.

그래프 마이닝 알고리즘은 일반적으로 소셜 미디어에서 자주 소통하는 두 사람과 같은 개별 포인트 쌍 간의 밀집된 연결을 찾는 데 중점을 둡니다.그러나 Triangle-Densest-k-Subgraph 문제로 알려진 연구원의 새로운 방법은 연결의 삼각형, 즉 각 쌍이 연결된 세 점의 그룹을 살펴봄으로써 한 단계 더 나아갑니다.이 접근 방식은 서로 상호 작용하는 소규모 친구 그룹이나 생물학적 과정에서 함께 작동하는 유전자 클러스터와 같이 보다 긴밀하게 연결된 관계를 포착합니다.

"우리의 방법은 단일 연결만 보는 것이 아니라 세 가지 요소 그룹이 상호 작용하는 방식을 고려합니다. 이는 더 많은 것을 이해하는 데 중요합니다.복잡한 네트워크"라고 전기 및 컴퓨터 공학과 교수인 Sidiropoulos는 설명했습니다. "이를 통해 우리는 대규모 데이터 세트에서도 보다 의미 있는 패턴을 찾을 수 있습니다."

삼각형이 밀집된 하위 그래프를 찾는 것은 전통적인 방법으로는 효율적으로 해결하기 어렵기 때문에 특히 어렵습니다.그러나새로운 알고리즘중요한 세부 사항을 잃지 않고 문제를 더 빨리 해결할 수 있을 만큼 문제를 단순화하는 영리한 지름길인 하위 모듈 완화를 사용합니다.

이 획기적인 발전은 더 깊은 다중 연결 관계에 의존하는 복잡한 시스템을 이해할 수 있는 새로운 가능성을 열어줍니다.하위 그룹과 패턴을 찾으면 발견하는 데 도움이 될 수 있습니다.의심스러운 활동사기의 경우 커뮤니티 역학을 식별하십시오.소셜 미디어, 또는 연구자들이 단백질 상호작용이나 유전적 관계를 더 정확하게 분석하는 데 도움을 줍니다.

추가 정보:Aritra Konar 외, 고정 크기의 삼각형-밀도 하위 그래프 채굴: 경도, Lovasz 확장 및 응용 분야,지식 및 데이터 엔지니어링에 관한 IEEE 거래(2024).DOI: 10.1109/TKDE.2024.3444608