Large Graph Models: A Review

Abstract

Large graphs can be found in a wide array of scientific fields ranging from sociology and biology to scientometrics and computer science. Their analysis is by no means a trivial task due to their sheer size and complex structure. Such structure encompasses features so diverse as diameter shrinking, power law degree distribution and self similarity, edge interdependence, and communities. When the adjacency matrix of a graph is considered, then new, spectral properties arise such as primary eigenvalue component decay function, eigenvalue decay function, eigenvalue sign alternation around zero, and spectral gap. Graph mining is the scientific field which attempts to extract information and knowledge from graphs through their structural and spectral properties. Graph modeling is the associated field of generating synthetic graphs with properties similar to those of real graphs in order to simulate the latter. Such simulations may be desirable because of privacy concerns, cost, or lack of access to real data. Pivotal to simulation are low- and high-level software packages offering graph analysis and visualization capabilities. This survey outlines the most important structural and spectral graph properties, a considerable number of graph models, as well the most common graph mining and graph learning tools.

We believe we have identified errors in equations (5), (10), (24), and (36) and we would like to remove this preprint

References in corpus (6)

• Kronecker Graphs: An Approach to Modeling Networks
• A Scalable Generative Graph Model with Community Structure
• Counting Triangles in Massive Graphs with MapReduce
• Using Triangles to Improve Community Detection in Directed Networks
• Degree Relations of Triangles in Real-world Networks and Models
• External Memory based Distributed Generation of Massive Scale Social Networks on Small Clusters