그래프 중심성들을 이용한 그래프 유사도 측정 (Measurement of graphs similarity using graph centralities)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 23권 / 12호 / 57 ~ 64페이지
· 저자명 : 조태수, 한치근, 이상훈

초록

In this paper, a method to measure similarity between two graphs is proposed, which is based on centralities of the graphs. The similarity between two graphs G₁ and G₂ is defined by thedifference of distance(G₁, GR1) and distance(G₂, GR2), where GR1 and GR2 are set of random graphs that have the same number of nodes and edges as G₁ and G₂, respectively. Each distance (G*, GR*) is obtained by comparing centralities of G* and GR*. Through the computational experiments, we show that it is possible to compare graphs regardless of the number of vertices or edges of the graphs. Also, it is possible to identify and classify the properties of the graphs by measuring and comparing similarities between two graphs.

영어초록

In this paper, a method to measure similarity between two graphs is proposed, which is based on centralities of the graphs. The similarity between two graphs G₁ and G₂ is defined by thedifference of distance(G₁, GR1) and distance(G₂, GR2), where GR1 and GR2 are set of random graphs that have the same number of nodes and edges as G₁ and G₂, respectively. Each distance (G*, GR*) is obtained by comparing centralities of G* and GR*. Through the computational experiments, we show that it is possible to compare graphs regardless of the number of vertices or edges of the graphs. Also, it is possible to identify and classify the properties of the graphs by measuring and comparing similarities between two graphs.

참고자료

· 없음