Graph Algorithms

AnzoGraph includes built-in graph algorithms for exploring and computing metrics for graphs, nodes, and relationships. This topic describes the graph algorithms that AnzoGraph supports. Click an algorithm name below to view details about the syntax to use in queries and usage examples.

Centrality Algorithms

Centrality algorithms identify important nodes in a graph:

  • PageRank: Ranks the nodes in a graph by their relative importance or influence. Google uses PageRank to rank websites in their search engine results.
  • Betweenness Centrality: Detects the amount of influence a vertex has over the flow of information in a graph.

Community Detection Algorithms

Community detection algorithms evaluate clusters of nodes and determine whether they have a tendency to strengthen or break apart:

  • Connected Components: Identifies the connected nodes in an undirected graph.
  • Label Propagation: Detects structures in a graph by propagating labels throughout the graph and forming groups based on the label propagation.
  • Triangle Enumeration: Identifies each triangle in a graph.
  • Triangle Count: Determines the number of triangles that a graph includes and calculates the average clustering coefficient for the resulting network of nodes.
  • Vertex Triangle Count: Determines the number of triangles that a vertex is a member of and computes the clustering coefficient for the vertex.

Path Finding Algorithms

Path finding algorithms identify the shortest path or evaluate the availability and quality of paths:

  • All Paths: Lists all of the paths that exist between two nodes in a graph.
  • Shortest Path: Finds the shortest path (the path with the least cost) from a source node to the other nodes in a graph.

Sample Data for Graph Algorithm Examples

All of the example queries for the graph algorithms run against a sample airline flight network data set, which includes a 10,000 row subset of flight data from the Department of Transportation and airport data with information about airports and their locations. If you would like to load the sample data so that you can run the example queries in the documentation, click the link below to download the airline_flight_network.zip file, which contains the load file, airline_flight_network.ttl.

Download the Airline Flight Network Sample Data

Extract the .zip file and place airline_flight_network.ttl in a location that your AnzoGraph server can access. Then run the following query to load the sample data into a graph called <http://anzograph.com/airline_flight_network>.

LOAD <file:/path_to_file/airline_flight_network.ttl> INTO GRAPH <http://anzograph.com/airline_flight_network>

After loading the data, run the following query to create RDF* properties in the <http://anzograph.com/airline_flight_network> graph. The query adds a distanceMiles property and value to each of the <http://anzograph.com/flights/Airport/origin_airport> <http://anzograph.com/flights/hasRouteTo> <http://anzograph.com/flights/Airport/destination_airport> triples in the graph.

prefix fl: <http://anzograph.com/flights/>

INSERT { GRAPH  <http://anzograph.com/airline_flight_network> {
    << ?origin fl:hasRouteTo  ?destination >> fl:distanceMiles ?distance .
  }
}
WHERE { GRAPH  <http://anzograph.com/airline_flight_network>  {
    ?flight fl:departsFrom ?origin;
            fl:arrivesAt ?destination;
            fl:distanceMiles ?distance .
  }
}