Graph density measures how many edges a graph contains relative to the total number of possible edges. For an undirected graph with n nodes, compute it as actual edges divided by n(n−1)/2. Use it during structural exploratory data analysis to judge sparsity before graph neural network training or link prediction. section 4.2.3 section 5.2.1
Interpret density alongside other graph statistics rather than treating it as a complete description:
- A value near zero indicates that actual connections are far fewer than possible connections, so the graph is sparse. section 4.2.3 section 5.2.1
- Compare density with average degree, connected components, clustering coefficient, and degree distribution to expose topology and possible modeling constraints. section 4.2.3 section 5.2.1
- Check whether disconnected components change the interpretation: a dominant sparse component can determine the overall density. section 4.2.3
Fraud-network and product-network examples
A fraud graph with 45,954 nodes and 3,892,933 edges has density close to 0.00, despite an average degree of 84.71. The Amazon Electronics co-purchaser graph has 7,650 nodes and more than 143,000 edges, producing density 0.0049; both graphs are sparse, while their degree distributions reveal additional structure. section 4.2.3 section 5.2.1
