그래프 중심성을 이용한 랜덤 그래프 모델 분류
The Classification of random graph models using graph centralities
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, a classification method of random graph models is proposed and it is based on centralities of the random graphs. Similarity between two random graphs is measured for the classification of random graph models. The similarity between two random graph models and is defined by the distance of and , where is a set of random graph that have the same number of nodes and edges as random graph . The distance( , ) is obtained by comparing centralities of and . Through the computational experiments, we show that it is possible to compare random graph models regardless of the number of vertices or edges of the random graphs. Also, it is possible to identify and classify the properties of the random graph models by measuring and comparing similarities between random graph models.
Abstract
In this paper, a classification method of random graph models is proposed and it is based on centralities of the random graphs. Similarity between two random graphs is measured for the classification of random graph models. The similarity between two random graph models and is defined by the distance of and , where is a set of random graph that have the same number of nodes and edges as random graph . The distance( , ) is obtained by comparing centralities of and . Through the computational experiments, we show that it is possible to compare random graph models regardless of the number of vertices or edges of the random graphs. Also, it is possible to identify and classify the properties of the random graph models by measuring and comparing similarities between random graph models.
참고문헌 (16)
- West, Douglas Brent, "Introduction to graph theory. Vol.2" (2001), Prentice hall
- Bollobás, Béla, "Modern graph theory", pp.215~252 (1998), Springer
- Sanfeliu, Alberto, "A distance measure between attributed relational graphs for pattern recognition", IEEE transactions on systems, man, and cybernetics, 3, pp.353~362 (1983)
- Akoglu, Leman, "Graph based anomaly detection and description: a survey", Data mining and knowledge discovery, 29(3), pp.626~688 (2015)
- Pignolet, Yvonne Anne, "The many faces of graph dynamics", Journal of Statistical Mechanics: Theory and Experiment, 2017, pp.063401~ (2017)
- 조태수, "그래프 중심성들을 이용한 그래프 유사도 측정", 한국컴퓨터정보학회논문지, 23(12), pp.57~64 (2018), 한국컴퓨터정보학회[DOI]
- Freeman, Linton C., "A set of measures of centrality based on betweenness", Sociometry, pp.35~41 (1977)
- Okamoto, "International Workshop on Frontiers in Algorithmics" (2008), Springer
- Freeman, Linton C., "Centrality in social networks conceptual clarification", Social networks, 1(3), pp.215~239 (1978)
- Bonacich, Phillip, "Some unique properties of eigenvector centrality", Social networks, 29(4), pp.555~564 (2007)
- Gilbert, Edgar N, "Random graphs", The Annals of Mathematical Statistics, 30(4), pp.1141~1144 (1959)
- ERDdS, P., "On random graphs I", Publ. Math. Debrecen, 6, pp.290~297 (1959)
- Watts, Duncan J., "Collective dynamics of ‘small-world’networks", nature, 393(6684), pp.440~ (1998)
- Bianconi, Ginestra, "Competition and multiscaling in evolving networks", EPL (Europhysics Letters), 54(4), pp.436~ (2001)
- Barabási, Albert-László, "Emergence of scaling in random networks", science, 286(5439), pp.509~512 (1999)
- Penrose, Mathew D, "On k‐connectivity for a geometric random graph", Random Structures & Algorithms, 15(2), pp.145~164 (1999)