Before revision:  We provide approximations to the algorithmic probability and Kolmogorov complexity of motifs connected to the asymptotic topological propertiesof networks .
After revision:  We provide approximations to the algorithmic probability and Kolmogorov complexity for different types of graphs characterizing their variant and invariant properties. We introduce formal definitions of complexity for both labelled and unlabelled graphs and prove that the Kolmogorov complexity of a labelled graph is a good approximation of the Kolmogorov complexity of the unlabelled graph .