Abstract: Finding situations where polynomial time algorithms are able to find good solutions for NP-Hard problems is of great practical interest, in fact, verifying this enhancement on complex networks unfolds several possibilities of research, applications, and improvements on a diverse number of fields. Thus, this paper seeks to examine the advantage of exploring the power law distribution of complex networks using greedy algorithms for finding approximate solutions for the Maximum Clique problem.