Recognizing Power-law Graphs by Machine Learning Algorithms using a Reduced Set of Structural Features

Abstract

The empirical study of large real-world networks in the last 20 years showed that a variety of real-world graphs are power-law. There are evidence that optimization problems seem easier in these graphs; however, for a given graph, classifying it as power-law is a problem in itself. In this work, we propose using machine learning algorithms (KNN, SVM, Gradient Boosting and RandomForests) for this task. We suggest a graph representation based on [Canninget al. 2018], but using a much simplified set of structural properties of the graph. We compare the proposed representation with the one generated by the graph2vecframework. The experiments attained high accuracy, indicating that a reduced set of structural graph properties is enough for the presented problem.