Three Properties of Real-World Graphs
Empirically, most real-world graphs have the following properties:
- sparsity — The number of edges is within a constant multiple of the number of vertices.
- small world phenomenon — Any two vertices are connected by a short path. Two vertices having a common neighbor are more likely to be neighbors.
- power law degree distribution — The degree of a vertex is the number of its neighbors. The number of vertices with degree j (or having j neighbors) is proportional to j-β
for some fixed constant β.