Newman is known for his research on complex networks, and in particular for work on collaboration patterns of scientists, random graph theory, assortative mixing, community structure, percolation theory, and network epidemiology. He was also co-inventor, with Michael Gastner, of a method for generating density-equalizing maps or cartograms, which forms the foundation for the Worldmapper web site. Their work gained attention following the 2004 US presidential election when it was used as the basis for a widely circulated map of the election results, which adjusted the size of states based on their population to give a more accurate sense of how many voters voted for each party.
Newman's network-based methods have been applied to a variety of fields, including psychology, sociology, economics and biology. The same basic methods have accurately predicted a wide variety of results, from relationships between organisms in an ecosystem to associations between terrorist organizations. Newman has also studied the risk of forest fires and the social behavior of dolphins in New Zealand, as well as the structure of the scientific community itself.
Newman has worked on power-law distributions in complex systems, including in the distribution of wealth, the sizes of cities, and the frequency of words in languages (see Zipf's Law). With collaborators Aaron Clauset and Cosma Shalizi, Newman developed statistical methods for analyzing power-law distributions and applied them to the study of a wide range of systems, in various cases either confirming or denying the existence of previously claimed power-law behaviors.
Newman's paper "The structure and function of complex networks" received the most citations of any paper in mathematics between 2001 and 2011.