Graph Mining: Laws, Generators, and Algorithms by Deepayan Chakrabarti and Christos Faloutsos.
Abstract:
How does theWeb look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: “How can we generate synthetic but realistic graphs?” To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.
If any readers of this blog have doubts about the need for mappings between terminology in fields of research (topic maps), consider the authors remarking:
…we need to detect patterns in graphs and then generate synthetic graphs matching such patterns automatically.
This is a hard problem. What patterns should we look for? What do such patterns mean? How can we generate them? A lot of research ink has been spent on this problem, not only by computer scientists but also physicists, mathematicians, sociologists, and others. However, there is little interaction among these fields with the result that they often use different terminology and do not benefit from each other’s advances. In this survey, we attempt to give an overview of the main ideas. Our focus is on combining sources from all the different fields to gain a coherent picture of the current stateof-the-art. The interested reader is also referred to some excellent and entertaining books on the topic, namely, Barabási [2002],Watts [2003], and Dorogovtsev and Mendes [2003]. (emphasis added)
Extremely detailed survey with copious references. Dates from 2006.
Do you know of a later cross-field survey that updates this article?
This would make a good article for the Reading club on Graph databases and distributed systems.