Graph Databases for Analytics (Part 3 of 4): The Basics of Graph Structure and Analytics
If you have an application for graph databases, what does the graph structure actually look like? We go further in-depth into the parts of a graph database and the purposes of common graph analytics.
- By David Loshin
- July 27, 2016
As we saw in the examples in Part 2, graph databases model the connections between entities. Now let’s go further in-depth into the parts of a graph database.
As you’ll recall from Part 1, a vertex (also called a node) represents an entity modeled within your environment. Vertices can include people, organizations, products, parts, or any other thing which has attributes and relationships to manage. Vertices are connected by edges (also called links), which represent relationships between the entities.
Figure 1: An example graph.
The combination of vertices and edges define a network whose connections can be queried and mined for meaningful patterns. Unlike the way a relational database models connections, the edges are first-class objects in a graph.
Both vertices and edges can have descriptive attributes, and these attribute values are used for specialized analyses and searches within the graph. Edges can be undirected when the relationship is mutual (such as “Joe is the sibling of Jane”). Alternatively, the edge can be directed, which means that the relationship flows differently according to its direction. An example is “Joe is the brother of Jane” and “Jane is the sister of Joe.”
One method for representing graphs uses the W3C’s Resource Description Framework, called RDF. In RDF, you specify triples that follow a subject-predicate-object format, such as “Larry Brown is-employed-by Millipede Electronics.” In this example, “Larry Brown” is the subject, “Millipede Electronics” is the object, and “is-employed-by” is the predicate that relates the subject to the object.
In effect, the RDF triple defines a directed edge between the subject and the object. A collection of RDF triples can capture the format of a graph. Within the graph database, various data structures represent the graph. Some are straightforward, such as Java objects linked with pointers, and others are optimized using different types of data structures, such as a sparse matrix data structure.
Graphs are queried using a graph query language such as SPARQL -- a recursive acronym for SPARQL Protocol and RDF Query Language. SPARQL is a semantic query language, allowing queries based on the attributes of the vertices, the attributes of the edges, and the structure of the connections. For example, you can query the graph for “all individuals who have three outgoing edges that connect to companies that have more than 500 employees.”
Search is just one analytics algorithm that you can apply to graphs. Others include:
-- Partitioning isolates portions of the graph into smaller pieces with particular properties. Example uses include partitioning a telecommunications network based on serving particular geographic regions or organizing sales territories by the location of the sales staff.
-- Shortest path analysis seeks the most efficient path between two nodes. A good example is examining all the delivery points for a parcel delivery company each day to determine routes that require the least amount of fuel.
-- Analysis can locate connected components, subgraphs in which all the vertices can be reached from any other member of the connected component. Connected components often represent distinct clusters of entities, and you can use them for segmentation.
-- Page rank characterizes the importance of a vertex within the graph. The algorithm, named after Google founder Larry Page, is part of how search engines rank websites based on their content and connections to other websites.
-- Centrality is another algorithm used to identify the most important or most influential entities within the graph.
The availability of graph analytics algorithms, semantic searching, and the graph representation within the database provide the fundamental building blocks for graph processing and analytics applications. In the final part of this series, we’ll discuss troubleshooting performance challenges in graph processing.
About the Author
David Loshin is a recognized thought leader in the areas of data quality and governance, master data management, and business intelligence. David is a prolific author regarding BI best practices via the expert channel at BeyeNETWORK and numerous books on BI and data quality. His valuable MDM insights can be found in his book, Master Data Management, which has been endorsed by data management industry leaders.