One way to find structure in a graph is by seeing it as a collection of clustered nodes, where two nodes within a single cluster are more connected to each other than two nodes in different clusters. In addition, in a lot of cases, there is a set of nodes that connect to many other nodes in the graph (or in terms of clusters, one cluster connects with many other clusters). Such a set of nodes is named a bus.
The DSM clustering tool aims to heuristically find such a bus and clusters. The implemented algorithm is based on [Wilschut et al. (2017)].
The clustering tool can be started in the following ways:
In Eclipse, right click a
.dsmfile in the Project Explorer tab or Package Explorer tab and choose Cluster a DSM….
Right click an open text editor for a
.dsmfile and choose Cluster a DSM….
dsmclusteringtool in a ToolDef script.
dsmclusteringcommand line tool.
Besides the general application options, this application has the following options:
Input file path: The absolute or relative file system path to the input DSM file.
Output file path: The absolute or relative file system path for writing the generated DSM output file. By default, the output file path is the same as the input file path, but with the
.dsmextension removed (if it exists), and the
_output.dsmextension added. By setting this option, the default is overridden by the given value.
Evaporation factor: Factor that influences when a node is considered to be part of a cluster. Higher values leads to higher connection requirements between nodes, which leads to fewer nodes in a single cluster and thus more (smaller) clusters. Between
10.0, default value is
Inflation factor: Factor that influences how fast large values increase and small values decrease, where the small values are eventually eliminated. Higher values of the factor speed up the process. Between
4.0, default value is
Bus detection algorithm: The bus detection algorithm to apply. By default, no bus is detected. See Bus detection algorithms below for more details.
Bus factor: Factor that influences when a node is considered to be part of the bus. The actual interpretation of this factor depends on the chosen bus detection algorithm. Default value is
2. For more information, see Bus detection algorithms below for more details.
Convergence limit: Allowed remaining numerical error before considering termination of the algorithm. Higher values end the computation sooner at the cost of less precision in the results. Values are between
0is not achievable, and
1is not precise enough). Default value is
Step count: Number of additional nodes to visit each iteration. Between
4, default value is
2. Changing this values is rarely needed.
Output groups: Whether to output the node numbers in the bus and each cluster. Default is
A Design Structure Matrix (DSM) file is an RFC-4180 compliant CSV file that contains an N times N matrix of values. Each line of the file contains a row of the matrix. Within the line, values are separated by commas, and leading and trailing white space around each value is discarded. Both integer and real values are supported, such as
1.5e-4. Negative values,
NaN and infinite values are not allowed. Before the first number at each row there should be a label indicating the name of the element of that row. Optionally, above the first line of data there may be a line of column labels as well. If column labels are present, the top-left cells of the matrix must be empty, and the row and column labels must match. Rows that are shorter than other rows are automatically extended with additional zero values. Zero values may be omitted. Labels that include a comma or space should be surrounded by double quotes, like
"Some text, and more text".
The following example shows a DSM for a two by two adjacency matrix of elements
B, with column labels:
, A , B A, 1 , 0 B, 0.5, 0.1
Since the DSM clustering tool is based on heuristics, and typically much of the input values in the graph are not hard numbers, there are often several valid answers where some of the answers match your expectations better.
It is therefore recommended to experiment with the various factors somewhat to see what other answers are possible, and whether they make sense.
Bus detection uses connectivity of the nodes, which is the sum of their in and out degrees.
Currently, the following bus detection algorithm options are available:
Fix-point algorithm, named
fix-pointin the tool. This is the fix-point algorithm as introduced in [Wilschut et al. (2017)]. The algorithm repeatedly adds new nodes to the bus with a connectivity higher than the median connectivity of non-bus nodes multiplied by bus factor. The final set of bus nodes is obtained when such new nodes no longer exist. The value of bus factor should be between
Top-k algorithm, named
top-kin the tool. This bus detection algorithm selects the nodes with the highest connectivity, where the number of nodes to select as bus nodes is bus factor. The value of bus factor should be an integer between
0and the number of elements in the DSM. Real numbers are truncated.
No bus, named
no-busin the tool. No bus detection mechanism is applied, so no bus elements are detected.
[Wilschut et al. (2017)] T. Wilschut, L.F.P. Etman, J.E. Rooda and I.J.B.F. Adan, "Multilevel Flow-Based Markov Clustering for Design Structure Matrices", Journal of Mechanical Design, volume 139, issue 12, 2017, doi:10.1115/1.4037626