그래프 중심성들을 이용한 그래프 유사도 측정
Measurement of graphs similarity using graph centralities
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (16)
- Sanfeliu, Alberto, "A distance measure between attributed relational graphs for pattern recognition", IEEE transactions on systems, man, and cybernetics, 3, pp.353~362 (1983)
- Pignolet, Yvonne Anne, "The many faces of graph dynamics", Journal of Statistical Mechanics: Theory and Experiment, 2017, pp.063401~ (2017)
- Newman, Mark, "Networks" (2018), Oxford university press
- Roy, Matthieu, "Modeling and measuring graph similarity: The case for centrality distance", Proceedings of the 10th ACM international workshop on Foundations of mobile computing. ACM (2014)
- Mheich, A., "A novel algorithm for measuring graph similarity: application to brain networks", Neural Engineering (NER), 2015 7th International IEEE, 2015, ~
- Freeman, Linton C., "A set of measures of centrality based on betweenness", Sociometry, pp.35~41 (1977)
- Sabidussi, Gert, "The centrality index of a graph", Psychometrika, 31(4), pp.581~603 (1966)
- Havel, Václav, "A remark on the existence of finite graphs", Casopis Pest. Mat, 80, pp.477~480 (1955)
- Ronqui, José, "Analyzing complex networks through correlations in centrality measurements", Journal of Statistical Mechanics: Theory and Experiment, 2015(5), pp.P05030~ (2015)
- ERDdS, P., "On random graphs I", Publ. Math. Debrecen, 6, pp.290~297 (1959)
- Albert, Réka, "Statistical mechanics of complex networks", Reviews of modern physics, 74(1), pp.47~ (2002)
- Erdős, Paul, "Asymmetric graphs", Acta Mathematica Academiae Scientiarum Hungarica, 14(3-4), pp.295~315 (1963)
- Prüfer, H., "Neuer Beweis eines Satzes über Permutationen", Arch. Math. Phys, 27, pp.742~744 (1918)
- Newman, Mark EJ, "Finding and evaluating community structure in networks", Physical review E, 69(2), pp.026113~ (2004)
- Lusseau, David, "The emergent properties of a dolphin social network", Proceedings of the Royal Society of London B: Biological Sciences, 270(Suppl 2), pp.S186~S188 (2003)
- Watts, Duncan J., "Collective dynamics of ‘small-world’networks", nature, 393(6684), pp.440~ (1998)