A Clustering Algorithm

This section is based on the work of Carlos I.G. Fernandez (1998). Another useful extension to Frnandez work can be found in Thebeau (2001).

The original goal of clustering (in graph theory) was to find similarity between elements and group them together based on a threshold of similarity between the elements. A good review of the basic clustering approaches/algorithms with different applications can be found in: Hartigan, John A., "Clustering Algorithms," John Wiley & Sons, New York, 1975. 

There are many clustering algorithms when the size and the number of clusters are known in advance. However, in the case of DSM clustering, the number and size of the clusters are not known in advance. Therefore, traditional clustering approaches fail to solve the DSM clustering problem.

The goal of clustering in DSM applications is to group the DSM elements into clusters (i.e. teams, modules,…).

The following observations / assumption will help in understanding the proposed clustering algorithm:

• The time and cost of addressing an interaction is proportional to the frequency or importance of the interaction.
• It is easier for team members to interact in smaller teams, rather large ones.
• The difficulty of managing a development team increases with the number of team members.
• The interaction / coordination cost among members of the same cluster is less expensive than the interaction / coordination between members belonging to different clusters.

A simple coordination cost function can be developed to evaluate different clustering arrangements within the DSM. The total coordination cost is the sum of all the individual tasks coordination costs. Each coordination cost takes into account the strength of interdependencies between two tasks, and the number of tasks in the smallest cluster that contain the two tasks. The coordination cost equations are as follows:

Total Coordination Cost (taski)=

Coordination Cost (taski)

Coordination Cost (taski) =

{DSM(i,j) + DSM(j,i)}*(sizei,j)2

Where:

size_i,_j = is the total number of tasks in the DSM if i and j do not belong to the same cluster, else it is the size of the smallest cluster containing both.

DSM(i,j) = is the value of the interaction in the DSM between element i and j.

The algorithm proceeds as follows. Initially, there are as many clusters as there are DSM elements. Then, the algorithm randomly selects an element and calculates a bid from clusters. The highest bid is chosen, and if there is an improvement in the total coordination cost, the task is added to the bidding cluster. This process continues until, after several attempts, there is no further improvement in the coordination cost.

Back to Tutorial Index