WOLFRAM

Wolfram Language & System Documentation Center

GraphDensity[g]

gives the graph density of the graph g.

GraphDensity[{vw,…}]

uses rules vw to specify the graph g.

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

GraphDensity

GraphDensity[g]

gives the graph density of the graph g.

GraphDensity[{vw,…}]

uses rules vw to specify the graph g.

Details and Options

  • GraphDensity is the ratio of the number of edges divided by the number of edges of a complete graph with the same number of vertices.
  • A simple undirected graph with vertices and edges has graph density .
  • A simple directed graph with vertices and edges has graph density .

Examples

open all close all

Basic Examples  (2)

Compute the density of a graph:

Wolfram Language code: GraphDensity[[image]]

Graph density distribution of the Bernoulli graph model:

Wolfram Language code: 𝒟 = GraphPropertyDistribution[GraphDensity[g], gBernoulliGraphDistribution[100, 0.3]];
Wolfram Language code: Histogram[RandomVariate[𝒟, 10000], 20]

Scope  (6)

GraphDensity works with undirected graphs:

Wolfram Language code: GraphDensity[[image]]

Directed graphs:

Wolfram Language code: GraphDensity[[image]]

Multigraphs:

Wolfram Language code: GraphDensity[[image]]

Mixed graphs:

Wolfram Language code: GraphDensity[[image]]

Use rules to specify the graph:

Wolfram Language code: GraphDensity[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 3 -> 5, 5 -> 2}]

GraphDensity works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: GraphDensity[g]//Timing

Applications  (4)

Find the proportion of games between teams during an American college football season:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "AmericanCollegeFootball"}]
Wolfram Language code: N[GraphDensity[g]]

Compute the probability that two randomly chosen friends in a network are connected:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}]
Wolfram Language code: GraphDensity[g]

Model a social network:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: 𝒢 = BernoulliGraphDistribution[VertexCount[g], GraphDensity[g]];

Simulate the model:

Wolfram Language code: RandomGraph[𝒢, 4]

Analyze the model:

Wolfram Language code: Mean[GraphPropertyDistribution[EdgeCount[h], h𝒢]]

The expected number of edges matches the original graph:

Wolfram Language code: EdgeCount[g]

Distribution of density in BernoulliGraphDistribution[n,p]:

Wolfram Language code: 𝒟 = GraphPropertyDistribution[GraphDensity[g], gBernoulliGraphDistribution[30, 0.7]];
Wolfram Language code: Histogram[RandomVariate[𝒟, 1000]]

The expected value is p:

Wolfram Language code: NExpectation[x, x𝒟]

Properties & Relations  (6)

GraphDensity measures the density of the AdjacencyMatrix:

Wolfram Language code: g = AdjacencyGraph[(| | | | | - | - | - | | 0 | 1 | 1 | | 1 | 1 | 0 | | 1 | 1 | 0 |), DirectedEdges -> True]
Wolfram Language code: GraphDensity[g, SelfLoops -> True]

Get the density from AdjacencyMatrix:

Wolfram Language code: Flatten[Normal[AdjacencyMatrix[g]]]
Wolfram Language code: Count[%, x_ /; x ≠ 0] / Length[%]

The graph density is between 0 and 1:

Wolfram Language code: Graph[{12, 13, 14, 23}]
Wolfram Language code: GraphDensity[%]

The density of an empty graph is 0:

Wolfram Language code: g = Graph[{1, 2, 3, 4}, {}]
Wolfram Language code: GraphDensity[g]

Use EmptyGraphQ to test for emptiness:

Wolfram Language code: EmptyGraphQ[g]

The density of a complete graph is 1:

Wolfram Language code: g = CompleteGraph[9]
Wolfram Language code: GraphDensity[g]

Use CompleteGraphQ to test for complete graphs:

Wolfram Language code: CompleteGraphQ[g]

Converting an undirected graph to a directed graph does not change the density:

Wolfram Language code: g = GridGraph[{2, 3}]; graphs = {g, DirectedGraph[g]}
Wolfram Language code: GraphDensity /@ graphs

Unless self-loops are taken into consideration:

Wolfram Language code: GraphDensity[#, SelfLoops -> True]& /@ graphs

LocalClusteringCoefficient gives a local measure of density:

Wolfram Language code: g = CirculantGraph[6, {1, 2}, VertexShapeFunction -> "Name"]
Wolfram Language code: h = VertexDelete[NeighborhoodGraph[g, 1], 1]
Wolfram Language code: {GraphDensity[h], LocalClusteringCoefficient[g, 1]}
Wolfram Research (2012), GraphDensity, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphDensity.html (updated 2015).

Text

Wolfram Research (2012), GraphDensity, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphDensity.html (updated 2015).

CMS

Wolfram Language. 2012. "GraphDensity." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/GraphDensity.html.

APA

Wolfram Language. (2012). GraphDensity. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GraphDensity.html

BibTeX

@misc{reference.wolfram_2026_graphdensity, author="Wolfram Research", title="{GraphDensity}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDensity.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_graphdensity, organization={Wolfram Research}, title={GraphDensity}, year={2015}, url={https://reference.wolfram.com/language/ref/GraphDensity.html}, note=[Accessed: 12-June-2026]}