Graph Theory - Maple Help

 Graph Theory

There have been several updates for the GraphTheory package in Maple 2016, including an update to the DrawGraph command such that the display for vertices uses round rather than rectangular background shapes. Maple 2016 also introduces nine new commands:

 •
 •
 •
 •
 •
 •
 •

Example: Clustering Coefficients

In analyzing a connected graph, particularly one arising naturally from empirical data, it is often worthwhile to know the degree to which nodes cluster together. Clustering coefficients aim to measure both the local clustering within a graph and the overall clustering across the graph.

 ${\mathrm{Graph 1: an undirected unweighted graph with 6 vertices and 8 edge\left(s\right)}}$ (1)

The LocalClusteringCoefficient command computes a number between 0 and 1 measuring how close the neighborhood of a particular vertex is to being a clique. You can compute the coefficient for a specified vertex:

$\mathrm{LocalClusteringCoefficient}\left(G,4\right)$

 $\frac{{2}}{{3}}$ (2)

Alternatively you can compute the list of all coefficients for the graph in vertex order:

$\mathrm{LocalClusteringCoefficient}\left(G\right)$

 $\left[\begin{array}{cccccc}{1}& {1}& {1}& \frac{{2}}{{3}}& {1}& \frac{{3}}{{10}}\end{array}\right]$ (3)

The GlobalClusteringCoefficient command computes a measure of how close $G$ is to being a complete graph.

$\mathrm{GlobalClusteringCoefficient}\left(G\right)$

 $\frac{{9}}{{17}}$ (4)

An alternate definition of the global clustering coefficient is the mean of all local clustering coefficients.

$\mathrm{GlobalClusteringCoefficient}\left(G,\mathrm{method}=\mathrm{Mean}\right)$

 $\frac{{149}}{{180}}$ (5)

Clustering coefficients can be also be computed for larger graphs.
Here we illustrate that invoking RandomGraph with probability $p$ generates a graph with mean clustering coefficient approaching $p$.

$H≔\mathrm{RandomGraph}\left(500,0.2\right)$

 ${\mathrm{Graph 2: an undirected unweighted graph with 500 vertices and 24897 edge\left(s\right)}}$ (6)

$\mathrm{dataplot}\left(\mathrm{LocalClusteringCoefficient}\left(H\right),\mathrm{histogram}\right)$

$\mathrm{evalf}\left(\mathrm{GlobalClusteringCoefficient}\left(H,\mathrm{method}=\mathrm{Mean}\right)\right)$

 ${0.2001778096}$ (7)