Big Data/Analytics Zone is brought to you in partnership with:

John Cook is an applied mathematician working in Houston, Texas. His career has been a blend of research, software development, consulting, and management. John is a DZone MVB and is not an employee of DZone and has posted 175 posts at DZone. You can read more from them at their website. View Full User Profile

Three Properties of Real-World Graphs

07.22.2013
| 1531 views |
  • submit to reddit

From Graph Theory in the Information Age by Fan Chung:

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 β.
Published at DZone with permission of John Cook, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)