두 그래프에서 속성을 고려해서 Node/Edge를 맞추고 싶은데 가능한 문제인지 궁금합니다.

Question

안녕하세요? 가입해서 첫 글이 질문글이라 민망합니다..그래프 매칭(Graph Matching) 문제라고 봐야 할지, 개념적인 부분부터도 이해가 안가서 선배님들께 도움을 요청합니다. 일단 두 개의 그래프가 존재하고, 두 그래프에는 Node나 edge에 여러 속성들이 존재합니다.이 상황에서 해당 문제를 보는 사람은 몇 번 해보면 속성 등을 고려해서&#34;아, 1번 그래프의 B 노드가 2번 그래프의 4번 노드와 대응하는구나!&#34;라고 생각할 수 있는 정도의 비슷함입니다. 예를 들어 아래 그래프 두 개를 비교한다고 가정하면 각각의 대응 관계는 이러합니다.Type과 Name을 고려했을 때 일단 A&#61;1, D&#61;5, C&#61;8입니다.1번 그래프의 B-C 엣지는 2번 그래프의 4-6-8의 엣지에 해당하는 상황입니다. 6번, 7번 node가 원래 1번 그래프에 없었는데 2번 그래프에 추가되어 있는 상황인거죠.마찬가지로 1번 그래프의 A-B 엣지는 2번 그래프의 1-2-4 엣지에 해당합니다.2번 노드가 A-B 엣지를 잘라놓고 있는 상황입니다. (included를 보면 a, b가 각각 a / b로 나뉘어서 included에 들어가 있음) 이런 식으로 그래프의 노드/엣지의 대응 관계를 찾고 싶은데..일단은 그래프가 서로 작아질수록 (Type과 Name을 고려해서 대응시킬 수 있는 엣지가 줄어들수록) 풀기가 어려워진다 -> 즉 위의 예시는 가장 난해한 예시일 것이라고 믿으면서 짜고 있습니다ㅠㅠ실제로는 저것보다는 좀 더 큰 그래프들을 다룰 것 같아요. (node가 각각 15~30개 정도 될 것 같습니다. 엣지도 20~50개 정도?) 이리저리 궁리를 해보는데 graph edit distance를 구하는 알고리즘/패키지를 쓰면서 cost 결정 시 속성을 고려하도록 코딩을 잘 하면 대응 관계를 잘 찾았을 때 cost가 최소화되도록 할 수 있지 않을까싶은 생각이 들다가.. 이 방법으로는 A~B 엣지 (&#61;1~2~4엣지)를 대응시킬 수가 없지 않을까 싶은 생각도 들고.. 여러가지로 난해한 기분이 듭니다. 1. 혹시 이미 어느정도 정립된 알고리즘 & github 코드 중에 이 문제에 적합한 것이 있을까요? 현재는 networkx의 graph edit distance쪽 함수에서 cost를 만지작거리고 있습니다.2. 요즘에는 graph matching에 딥러닝까지 도입하던데.. 거기까지 도입을 해야 하는 문제인지 궁금합니다.3. 그리고 어느쪽이든 해당 문제를 풀 코드를 짜는데에 팁을 조금 주시면 감사하겠습니다ㅠ_ㅠ

kenu,전독시 · Accepted Answer

영어로 검색하시면

지니야힘을줘 · Answer

혹시 어떤 키워드로 검색을 의미하신 것인지 조금만 여쭤봐도 될까요?ㅠㅠ

두 그래프에서 속성을 고려해서 Node/Edge를 맞추고 싶은데 가능한 문제인지 궁금합니다.

2개의 답변

#networkx 목록