Many algorithms and procedures require graphs with certain properties. These can be basic properties, such as being undirected, or deeper topology properties, such as being connected or acyclic. In some areas, a key problem is to decide whether two graphs are the same if the vertex names are replaced, i.e. to test whether they are isomorphic.

The Wolfram Language supports a broad range of measures that characterize graphs, from simple measures, such as the number of vertices and edges, which tell the size and sparsity of a graph, to vertex degrees, which tell how locally well connected each vertex is. Other measures include the geodesic distances in a graph or centrality measures, which give a measure of how central in the overall graph each vertex is; for example, PageRank and HITS are measures used to order web page importance as returned from a search engine.

Basic Properties

GraphQ — test whether an expression is a graph object

DirectedGraphQ, UndirectedGraphQ — test whether a graph is directed or undirected

MultigraphQ, MixedGraphQ — test whether a graph is a multigraph or a mixed graph

EdgeQ  ▪  VertexQ  ▪  EmptyGraphQ  ▪  WeightedGraphQ  ▪  CompleteGraphQ

Structural Properties

SimpleGraphQ — test whether a graph is simple

AcyclicGraphQ — test whether a graph is acyclic

BipartiteGraphQ  ▪  ConnectedGraphQ  ▪  EulerianGraphQ  ▪  HamiltonianGraphQ  ▪  PathGraphQ  ▪  PlanarGraphQ  ▪  TreeGraphQ  ▪  LoopFreeGraphQ

Graph Isomorphism

IsomorphicGraphQ — test whether two graphs are the same after vertex renaming

FindGraphIsomorphism — find the graph isomorphism as a list of rules

FindSubgraphIsomorphism — find the subgraph isomorphism

IsomorphicSubgraphQ  ▪  FindIsomorphicSubgraph  ▪  CanonicalGraph  ▪  GraphAutomorphismGroup  ▪  VertexTransitiveGraphQ  ▪  EdgeTransitiveGraphQ

Graph Coloring

FindVertexColoring — find minimal vertex coloring

FindEdgeColoring — find minimal edge coloring

FindPlanarColoring — find face coloring for a planar graph layout

VertexChromaticNumber  ▪  EdgeChromaticNumber  ▪  ChromaticPolynomial

Basic Measures

VertexCount, EdgeCount — give the number of vertices and edges in a graph

VertexDegree — give the number of edges for each vertex

VertexInDegree  ▪  VertexOutDegree  ▪  GraphHub

Distance Measures

GraphDistance — the length of the shortest path between two vertices

MeanGraphDistance  ▪  GraphDistanceMatrix  ▪  VertexEccentricity  ▪  GraphRadius  ▪  GraphDiameter

Connectivity Measures

VertexConnectivity — the number of vertex-independent paths between two vertices

EdgeConnectivity — the number of edge-independent paths between two vertices

GraphDensity — fraction of edges to the possible edges in a graph

GraphLinkEfficiency — how tightly connected a graph is compared to number of edges

Centrality Measures

ClosenessCentrality — inverse average distance to every other vertex

BetweennessCentrality — fraction of shortest paths that pass through the vertex

DegreeCentrality  ▪  EigenvectorCentrality  ▪  KatzCentrality  ▪  PageRankCentrality  ▪  HITSCentrality  ▪  RadialityCentrality  ▪  StatusCentrality  ▪  EdgeBetweennessCentrality  ▪  LinkRankCentrality

Reciprocity and Transitivity

GraphReciprocity — fraction of directed edges that are reciprocated

GlobalClusteringCoefficient — fraction of length-two paths that are closed

MeanClusteringCoefficient  ▪  LocalClusteringCoefficient

Homophily, Assortative Mixing, and Similarity

GraphAssortativity — within-group connectivity minus between-group connectivity

VertexCorrelationSimilarity — correlation similarity between actors

MeanNeighborDegree  ▪  MeanDegreeConnectivity  ▪  VertexDiceSimilarity  ▪  VertexJaccardSimilarity  ▪  VertexCosineSimilarity