Download
as PDF

Automatic Grouping

This tool allows you to automatically group the nodes of a graph in accordance with one of the following criteria:

The chapter Settings of Section 'Grouping' gives a description of all controls which affect the grouping. The computed groups can be depicted as group nodes and by using shared visual properties, the details are described in Settings of Section 'Presentation'.

Definitions

Member of a Group
A node which is part of a group is called member of this group.
Path
A path is a sequence of nodes in which two consecutive nodes are connected by an edge of the graph.

Grouping Types

Connected Components

A group is called connected, if there is a path from every member to every other member and all intermediate nodes are also members of the group. The connected components of a graph are connected groups of maximum size, i.e., all nodes which are reachable from any member must be also members of the group. Every node of the graph is a member of exactly one connected component.

Biconnected Components

Biconnected components are similar to (single) connected components but there must be two independent paths instead of one between every pair of members. Unlike connected components which form distinct groups, two biconnected components can share a common node. Since group nodes cannot be used in this case, yEd assigns such nodes to only one component.

Natural Clusters

A grouping into natural clusters should fulfill the following properties:

  • each node is a member of exactly one group,
  • each node should have many edges to other members of its group, and
  • each node should have few or even no edges to nodes of other groups.

yEd features a general purpose clustering algorithm whose only setting allows you to adjust the weighting between the quality of the grouping and the calculation time.

Details of the Algorithm. The algorithm is based on Edge Betweenness Clustering proposed by Girvan and Newman. For the highest quality setting, it is used almost unmodified. In the central, recommended position, the fast betweenness approximation of Brandes und Pich (Centrality Estimation in Large Networks) is employed. Typically, this results in a tiny decrease in quality but a great increase in speed. To achieve the lowest running time, a local betweenness calculation is used (Gregory: Local Betweenness for Finding Communities in Networks).

Sub-Trees

A sub-tree is a group characterized by following two properties. Its internal structure is a tree and at most one of its members has edges to outside nodes. By definition, single nodes are not sub-trees. Optionally, the direction of edges can be considered. In this case, the internal structure of the group must be a directed tree and the member which has edges to outside nodes must be its root. Each node can be member of at most one sub-tree.

Chains

Chains are paths whose inner nodes have degree equal to 2, i.e., each inner node has exactly two edges, one to its predecessor and one to its successor in the path. By definition, the first and the last node of the path are not part of a chain. Optionally, the direction of edges can be considered. In this case, edges can only be used in their direction. Each node can be member of at most one chain.

Settings in Section 'Grouping'

Grouping Type

Selects the grouping type. The options are described in Grouping Types.

Consider Direction

Specifies whether the direction of edges should be considered for Sub-Trees and Chains.

Existing Groups

Defines how to handle existing groups. The alternatives are to ungroup all or the keep closed folders. It is possible to preserve closed folders, since they can be treated like regular nodes. In general, open groups do not conform to the selected grouping criterion and, therefore, must be ungrouped. The only exception is the Refinement of Existing Groups.

Quality/Time Ratio

Controls the weighting between the quality of the grouping and the calculating time when computing natural clusters. The central position is recommended for most graphs since it combines very good quality with low running time. For large graphs, it may be required to switch to an even faster setting. Higher quality settings may be used for small graphs but calculating time will increase significantly.

Refine Existing Groups

Allows you to use the existing groups as a starting point for further refinements. In this process, existing groups are sub-divided into smaller groups but nodes which initially belonged to different groups will never be assigned to the same group. This setting is available only for natural clusters.

Settings in Section 'Presentation'

Node Label Text

Assigns to all members of a group the same label text. This consists of the grouping type and a group ID. If the setting Group Label Text is appropriately set, the ID is adopted from the group node.

Node Fill Color

Uses the node fill color to depict groups, i.e., only members of the same group are tinted with the same color. If the setting Group Color is also activated, the color of a group node and its members is the same.

Group Nodes

Defines the type of group node to use. The available options are Opened Group, Closed Folder, and None.

Group Label Text

Defines the text of the group label. Optionally, there is no label at all or the text consists of a combination of group ID and member count. If the setting Node Label Text is also activated, the group ID is adopted by its members.

Group Color

Sets different background colors for the labels of different group nodes. If the setting Node Fill Color is also activated, the color of a group node and its members is the same.