Function Repository Resource:

# WolframHausdorffDimension

Compute the Wolfram–Hausdorff dimension of a graph and its associated properties

Contributed by: Jonathan Gorard

## Details and Options

The Wolfram–Hausdorff dimension is computed by extracting the leading-order exponent in the volume expansion for a finite geodesic ball in the graph (i.e. the discrete analog of the standard Hausdorff dimenson of a metric-measure space).
Wolfram–Hausdorff dimension represents one possible definition of discrete dimension for an arbitrary graph, based upon a discretization of the power series expansion of a continuous Riemannian volume element. This stands in contrast with other such definitions, such as the Myrheim–Meyer dimension estimator, which is based upon random sampling (defined in terms of the probability of a pair of randomly-chosen vertices being path-connected), and the spectral dimension, which is based upon linear algebraic techniques (defined in terms of spectral properties of the Laplacian/Kirchhoff matrix of the graph).
In ResourceFunction["WolframHausdorffDimension"][graph,], graph can be either directed or undirected, in which case the graph is treated as an approximation to either a Lorentzian or a Riemannian manifold, respectively.
ResourceFunction["WolframHausdorffDimension"] can compute the Wolfram–Hausdorff dimension at a given vertex by taking an average over geodesic balls of all radii, taking a minimum/maximum over all radii, or otherwise returning every possible result.
When no maximum or minimum radius is specified, ResourceFunction["WolframHausdorffDimension"] automatically uses the graph radius as the maximum radius.
For directed graphs, ResourceFunction["WolframHausdorffDimension"] computes volumes of finite geodesic cones, as opposed to geodesic balls.
The computed dimension can be any arbitrary real number (i.e. fractional-dimensional spaces are supported).
In ResourceFunction["WolframHausdorffDimension"][,"prop"], the following properties can be requested:
 "Volume" the volumes of geodesic balls of various radii around a given vertex "AllVolumes" an association showing the volumes of geodesic balls of various radii around each vertex "Dimension" the Wolfram–Hausdorff dimension at a given vertex "AllDimensions" an association showing the Wolfram–Hausdorff dimension at each vertex "HighlightedGraph" a highlighted graph depicting how the Wolfram–Hausdorff dimension is computed
The default property for ResourceFunction["WolframHausdorffDimension"] is either "Dimension" (if a vertex v is specified) or "AllDimensions" (if a vertex v is not specified).
Options for ResourceFunction["WolframHausdorffDimension"] include:
 "TransitivelyReduce" False whether to use the transitive reduction of the input graph "UndirectedGraph" False whether to use the undirected form of the input graph "VolumeMethod" Mean whether to take a maximum, minimum or mean over geodesic balls of different volumes (or simply return all values) "DimensionMethod" Mean whether to take a maximum, minimum or mean over geodesic balls yielding different dimensions (or simply return all values) "VertexMethod" Identity whether to take a maximum, minimum or mean over all vertices in the input graph (or simply return all values)
The possible values for the options "VolumeMethod", "DimensionMethod" and "VertexMethod" are Max, Min, Mean and Identity. For each of the options, Identity will return a list of all possible values, while Max, Min and Mean will return a maximum, minimum or mean of the elements of the resulting list, respectively.

## Examples

### Basic Examples (4)

Compute the Wolfram–Hausdorff dimension at vertex 150 in a 20-by-20 2-dimensional grid graph:

 In[1]:=
 Out[1]=
 In[2]:=
 Out[2]=

Compute the maximum and minimum curvatures over geodesic balls with radii up to 8:

 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

Return a list of all dimensions for geodesic balls with radii up to 8:

 In[5]:=
 Out[5]=

Show the geodesic balls with radii up to 8 as a highlighted graph:

 In[6]:=
 Out[6]=

Return an Association showing the Wolfram–Hausdorff dimension at each vertex:

 In[7]:=
 Out[7]=

Compute the maximum and minimum dimensions across all vertices:

 In[8]:=
 Out[8]=
 In[9]:=
 Out[9]=

Compute the average dimension across all vertices:

 In[10]:=
 Out[10]=

Compute the average volume of geodesic balls around vertex 250 in a 10-by-10-by-10 3-dimensional grid graph:

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

Compute the maximum and minimum volumes of geodesic balls with radii between 3 and 9:

 In[13]:=
 Out[13]=
 In[14]:=
 Out[14]=

Return a list of volumes of geodesic balls with radii between 3 and 9:

 In[15]:=
 Out[15]=

Show the geodesic balls with radii between 3 and 9 as a highlighted graph:

 In[16]:=
 Out[16]=

Return an Association showing the geodesic ball volumes around each vertex:

 In[17]:=
 Out[17]=

Compute the maximum and minimum ball volumes across all vertices:

 In[18]:=
 Out[18]=
 In[19]:=
 Out[19]=

Compute the average ball volume across all vertices:

 In[20]:=
 Out[20]=

Compute the Wolfram–Hausdorff dimension at an arbitrary vertex in an approximately 3-dimensional graph (produced using the resource function FlatManifoldToGraph):

 In[21]:=
 In[22]:=
 Out[22]=

Show the geodesic balls with radii up to 3 as a highlighted graph:

 In[23]:=
 Out[23]=

Compute the Wolfram–Hausdorff dimension at an arbitrary vertex in an approximately 4-dimensional graph (produced using FlatManifoldToGraph):

 In[24]:=
 In[25]:=
 Out[25]=

Show the geodesic balls with radii up to 3 as a highlighted graph:

 In[26]:=
 Out[26]=

### Scope (4)

If given a graph, WolframHausdorffDimension returns an Association showing the Wolfram–Hausdorff dimension at each vertex, using the graph radius as the maximum geodesic ball radius:

 In[27]:=
 Out[27]=
 In[28]:=
 Out[28]=

Use geodesic ball radii between 3 and 5 instead:

 In[29]:=
 Out[29]=

If given a graph, a vertex and a maximum radius, WolframHausdorffDimension returns the Wolfram–Hausdorff dimension at that vertex:

 In[30]:=
 Out[30]=

#### Directed vs. Undirected Graphs (3)

WolframHausdorffDimension also supports directed graphs:

 In[31]:=
 In[32]:=
 Out[32]=

In the directed case, the Wolfram–Hausdorff dimension is computed using volumes of geodesic cones, as opposed to geodesic balls:

 In[33]:=
 Out[33]=

However, WolframHausdorffDimension can be made to treat directed graphs as though they were undirected (and hence revert to using geodesic balls) with the option "UndirectedGraph":

 In[34]:=
 Out[34]=
 In[35]:=
 Out[35]=

#### Fractional Dimensional Graphs (1)

WolframHausdorffDimension also supports dimension computations in graphs with non-integer dimensionality, such as this Sierpinski sieve graph:

 In[36]:=
 Out[36]=
 In[37]:=
 Out[37]=
 In[38]:=
 Out[38]=

### Options (14)

#### DimensionMethod (3)

Compute the average Wolfram–Hausdorff dimension for geodesic balls around vertex 150 with radii between 3 and 9 in a 20-by-20 2-dimensional grid graph with the option value "DimensionMethod"Mean (default):

 In[39]:=
 Out[39]=
 In[40]:=
 Out[40]=

Return a list of all dimensions for geodesic balls with radii between 3 and 9 instead:

 In[41]:=
 Out[41]=

Compute the maximum and minimum dimensions for geodesic balls with radii between 3 and 9 with the option values "DimensionMethod"Max and "DimensionMethod"Min, respectively:

 In[42]:=
 Out[42]=
 In[43]:=
 Out[43]=

#### TransitivelyReduce (3)

By default, directed graphs are not transitively-reduced:

 In[44]:=

Compute (and visualize) the Wolfram–Hausdorff dimension, assuming that the graph is not transitively-reduced:

 In[45]:=
 Out[45]=
 In[46]:=
 Out[46]=

WolframHausdorffDimension can be made to treat unreduced directed graphs as though they were transitively-reduced with the option "TransitivelyReduce":

 In[47]:=
 Out[47]=
 In[48]:=
 Out[48]=

#### UndirectedGraph (3)

By default, directed graphs are treated as directed (and so dimension computations use the volumes of geodesic cones, as opposed to geodesic balls):

 In[49]:=

Compute (and visualize) the Wolfram–Hausdorff dimension, assuming that the graph is directed:

 In[50]:=
 Out[50]=
 In[51]:=
 Out[51]=

WolframHausdorffDimension can be made to treat directed graphs as though they were undirected with the option "UndirectedGraph":

 In[52]:=
 Out[52]=
 In[53]:=
 Out[53]=

#### VertexMethod (2)

Return an Association showing the geodesic ball volumes around each vertex in a 20-by-20 2-dimensional grid graph (default):

 In[54]:=
 Out[54]=
 In[55]:=
 Out[55]=

Compute the average ball volume across all vertices with the option value "VertexMethod"Mean:

 In[56]:=
 Out[56]=

Compute the maximum and minimum ball volumes across all vertices with the option values "VertexMethod"Max and "VertexMethod"Min, respectively:

 In[57]:=
 Out[57]=
 In[58]:=
 Out[58]=

Return an Association showing the Wolfram–Hausdorff dimension at each vertex in a 20-by-20 2-dimensional grid graph (default):

 In[59]:=
 Out[59]=
 In[60]:=
 Out[60]=

Compute the average dimension across all vertices with the option value "VertexMethod"Mean:

 In[61]:=
 Out[61]=

Compute the maximum and minimum dimensions across all vertices with the option values "VertexMethod"Max and "VertexMethod"Min, respectively:

 In[62]:=
 Out[62]=
 In[63]:=
 Out[63]=

#### VolumeMethod (3)

Compute the average volume of geodesic balls around vertex 150 with radii between 3 and 9 in a 20-by-20 2-dimensional grid graph with the option value "VolumeMethod"Mean (default):

 In[64]:=
 Out[64]=
 In[65]:=
 Out[65]=

Return a list of volumes of geodesic balls with radii between 3 and 9 instead:

 In[66]:=
 Out[66]=

Compute the maximum and minimum volumes of geodesic balls with radii between 3 and 9 with the option values "VolumeMethod"Max and "VolumeMethod"Min, respectively:

 In[67]:=
 Out[67]=
 In[68]:=
 Out[68]=

Jonathan Gorard

## Version History

• 1.0.0 – 22 March 2021