041 MOC Graph Theory

up:: 040 MOC Complex Systems

Types of Graphs

• Simple Graph
• Multi-layer graph
• Hypergraph

Graph Theory Measures

Descriptive Measures

• Adjacency Matrix
  • Supra-Adjacency Matrix
• Laplacian Matrix

Centrality Measures

• Node Degree
  • In Degree
  • Out Degree
  • Average Network Degree
  • Average Nearest Neighbors’ Degree
• Network Density
• Node Betweenness
• Shortest Path Distance
  • Average Shortest Path Distance
  • Graph Diameter
• Graph Efficiency
• Graph Clustering

Similarity Measures

• Cosine Similarity
• Jaccard Similarity
  • Jaccard Similarity is a lower-bound for Cosine Similarity
• Pearson Coefficient

Famous Graphs

• Erdős-Rényi Model
• Barabási-Albert Graph
• Watts-Strogatz Graph

Famous Models

• Winfree’s Model of Synchronization
• Kuramoto Model

---

References

• NEWMAN, Mark. Networks. Oxford University Press, 2018.
• Casas, Alberto Aleta. “Networks, epidemics and collective behavior: from physics to data science”. PhD Thesis, Universidad de Zaragoza, 2019. https://dialnet.unirioja.es/servlet/tesis?codigo=300533.
• BOCCALETTI, S. et al. Complex networks: Structure and dynamics. Physics reports, v. 424, n. 4–5, p. 175–308, 2006.
• STROGATZ, S. H. Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering. 3. ed. CRC Press, 2019.