두 노드 사이에 다중 에지를 갖는 그래프 유사성

Question

버텍스 에지 오버랩, 자카드, 코사인, 편집 거리, 시그너처 유사성, 람다 거리, 델타콘 등과 같은 그래프 유사성 계산에 관한 많은 이론이 있습니다. 이러한 것들은 그래프의 단일 가장자리를 기반으로합니다. 그러나 현실 세계에는 여러 개의 가장자리를 갖는 그래프가 많이 있습니다.

위와 비슷한 두 개의 그래프가 주어지면 그래프의 유사도를 어떻게 계산할 수 있습니까? 이전의 그래프 유사도를 사용하면 2 차원 벡터 만 있고 항목은 숫자 인 스칼라 만이지만 여러 가장자리의 그래프에서 항목은 튜플이어야합니다. 노드 간에는 하나 이상의 작업이 있기 때문입니다. 이전의 방법에서는 누가 누구인지를 알 수 있었지만 후자의 그래프에서는 누가 알 수 있는지를 알 수있었습니다. 이전의 mothod는 여러 가장자리의 그래프에 쉽게 사용할 수 있으므로 논리 나 방법이 없다고 생각합니다. 미리 감사드립니다.

Answer 1

그래프의 유사성을 계산하는 "방법"이 없습니다.

데이터 및 문제에 따라 매우 다른 방법이 유용 할 수 있습니다. 대부분의 경우 두 가장자리를 하나로 합치면 완벽하게 이해할 수 있습니다. 예를 들어, 두 개의 도로 용량 x와 y를 사용하면 A에서 B로 이동합니다. 많은 분석에서이 값은 합산 된 용량과 함께 한 번 탔을 때와 비슷합니다.