A Glossary of the Top 15 Graph Analytics Terms

Graph analytics products cover a wide range of topics and end users, so terms can often be used by one group of users but not by another. In the spirit of helping everyone understand graph analytics better, here are the top 15 terms worth knowing.

Structure

Topology - the form of elements within a graph, how they are structured and how they relate to one another.

Node - a single atomic unit within a graph. In a line drawing this is analogous to a point.

Edge - a connection between two nodes delineating a relationship. In a line drawing this is analogous to a line between those points.

Attribute or Property - a stored data element that relates to a specific node or edge. An attribute may be of a string (text) or numeric data type, but may also identify other objects, may include binary data, or it may assign directionality in a relationship.

Types

Directionality - an attribute that describes the intended flow of information through a graph or relationship. Directionality is important to guide analytic algorithms in the correct order or operations.

Directional Graph (di-graph) - a form that describes relationships using one node as a source and another as a target. Similar to: “Node A is connected to Node B through Property X” or, for example, “Person A is the owner of Car B” where the property lies between the nodes and implies a direction. Note that Car B cannot be the owner of Person A in a directional graph.

Bi-directional Graph - a directional graph that allows relationships to flow in both directions. Multiple relationships can exist between the same two nodes. For example, “Person A is a sibling of Person B” can be used in both directions.

Non-directional Graph - a directionless graph that allows relationships to flow in any direction.

Cyclic Graphs - graphs where edges can connect in directions that allow a full loop, non-hierarchical and non-terminating flow. Child nodes can link back to parent nodes (which obviously breaks the strong sense of the parent-child metaphor).

Acyclic Graphs - graphs that enforce a specific direction and hierarchy, with a clear point of termination and no looping between children back to their parents.

Social Graph - a graph that represents relationships between people and/or organizations. The graph topology used behind social network platforms.

Algorithms & Operations

Topological Operations - a process that reduces, combines, unions, or selects a subset (subgraph) of nodes and edges in a graph.

Graph Algorithm - a process that applies particular topological analysis to a graph and produces a variety of types of outputs including new graph structure, a coefficient, or a ratio describing a particular property. For example, an algorithm may analyze a graph to find the node that has the highest number of connections to other nodes. Common algorithms are based on centrality calculations.

• Centrality - calculates a node property that counts its edge connections. Many variations exist: degree, closeness, PageRank and more (see figure below). Some specific algorithms help the analyst to identify nodes that are hubs among many nodes, or that bridge between distinct subnetworks, etc. Centrality determines how important a specific node is to a network.
• Other algorithms include graph traversal, nearest neighbor, network flow, A* search, and many more.

Graph Traversal - moving through a network of nodes using specific edges to get from one node to another. Usually describing the process of finding a path, one step at a time, through a graph. Shortest and longest path algorithms will do graph traversal starting and ending at a particular point.

Graph Visualization Techniques

Graph visualization is the process of creating a visual representation of the graph topology, including various graphic settings for nodes, edges, and properties. Basic techniques include changing the shape, sizes, line thickness, fill, and outline colors and text labels based on element properties.

Graph Layout - a key stage in any graph visualization, usually automating the distance between nodes to optimize the image for communicating a particular topic. Layout algorithms use concepts such as gravity that draws nodes closer together and force-directed properties that push them apart. Options usually include adjusting these parameters to create a custom layout depending on the scale and quantity or the graph data.