Graph theory and link chart concepts

It can help to understand some concepts related to graph theory when determining which methods to use when manipulating or analyzing link charts that include content from a knowledge graph, and when evaluating the results of those methods.

A link chart's content is managed as a graph. Discussions of graph theory often refer to nodes and edges. A node in a graph corresponds to an entity in the knowledge graph. An edge in a graph corresponds to a relationship in the knowledge graph.

Calculate an entity's degree or reduced degree

The degree of an entity is calculated as the number of relationships in which the entity participates. An entity's degree is calculated in the context of the link chart. That is, only relationships present in the link chart are used to calculate an entity's degree.

In contrast to an entity's degree, its reduced degree is calculated as the number of entities to which the entity is related. Consider the scenarios below.

Many relationships exist between two entities—For example, an entity Employee A is connected to another entity Employee B by a WorksFor relationship and a TeamLeader relationship. The degree for Employee A is two. However, the reduced degree for Employee A is one. In the diagram below, see relationships labeled A for an illustration of this example.

Relationship groups—In the previous example, suppose the WorksFor and TeamLeader relationships are grouped between Employee A and Employee B. The degree and reduced degree calculations treat the relationship group as if it doesn't exist. When determining Employee A's degree, each relationship in the group is considered individually and the degree is two. However, for the reduced degree, the relationship group only connects Employee A to Employee B, and the reduced degree is one. In the diagram below, see the relationship groups labeled Group (2) and Group (4) for an illustration of this example.

Recursive relationships—A recursive relationship exists when an entity is both the origin and the destination of a relationship. For example, Employee C is a project leader and also works on the project, so they are their own TeamLeader. Employee C's degree is two because the entity participates in an outgoing and an incoming relationship. However, Employee C's reduced degree is zero because the entity isn't related to any other entities. In the diagram below, see relationships labeled B for an illustration of this example.

For typical relationships where a single relationship connects two entities, an entity's degree and its reduced degree are the same. For example, an entity Employee A is connected to Employee B by a WorksFor relationship and connected to Employee C by a TeamLeader relationship. The degree for Employee A is two and the reduced degree for Employee A is also two, because Employee B participates in two relationships and is related to two entities. If employees B and C are grouped on the link chart, which also causes the two relationships to be grouped together, the degree and reduced degree for Employee A remain the same because they still participate in two individual relationships and are related to two individual entities.

The diagram below shows the reduced degree (R:x) and degree (D:y) for each entity in a sample link chart. Pink entities have reduced degree 1 (R:1), blue entities have reduced degree 2 (R:2), and green entities have reduced degree 3 or more (R:x).

Reduced degree and degree for entities in a sample link chart

Use an entity's degree or reduced degree

Some link chart operations are based on the degree or reduced degree of the entities that are processed. An entity's degree is considered when computing the following centrality scores:

  • Degree
  • In-degree
  • Out-degree

An entity's reduced degree is considered when the following methods are used with a link chart:

  • Organic layouts—When you change the way in which entities and relationships are visualized by applying an organic layout, entities with a reduced degree of one, two, or three are postprocessed.
  • Trim operation—The trim method is used to remove leaf entities from a link chart. Leaf entities are defined as entities with a reduced degree of one.

The same knowledge graph entities can be added to link charts where different relationships associated with those entities are included. In each link chart, the degree and reduced degree of an entity are calculated specific to the link chart, not for the underlying knowledge graph.

Related topics