Graphs are a tool used in a lot of fields to represent various kinds of concrete data. However, with the expansion in size of those data, it becomes harder and harder to process those graphs. Graph compression aims at shrinking and summarizing graphs so that standard algorithms can process them in a reasonable amount of time. There are currently several lossless and lossy methods to compress a graph, such as Shrink by Sadri et al. or Slashburn by Kang and Faloustos. A notable framework is WebGraph by Boldi and Vigna, which compresses the web graph using locality properties and hyperlinks similarity. Some other approaches are based upon modular decomposition which finds regularities within a graph. Generally, several compression methods are based upon finding regularities within graph such as frequent patterns. The main goal of this thesis is to explore regularities of large data graphs and use those regularities to summarize graphs efficiently. Hence, the first question to answer is how do we find efficiently regularities in a large graph, and what kind of regularities can you find in a reasonable amount of time. Next, once regularities are found, it will be crucial to find efficient ways to represent a graph based on those regularities. Another question this thesis will try to answer is what kind of graph parameters is it possible to estimate using a summarized graph.