CLUSTER Algorithm Design and Analysis

CLUSTER Algorithm Design and Analysis

Algorithm's Design:

1. A graph G is constructed using the adjacency matrix which is obtained from applying a similarity threshold SIMILARITY_THRESHOLD on the similarity matrix simMat.
2. Since the graph is not guaranteed to be connected, the algorithm divides the graph into its connected components connectedComponents first.See, Finding Connected Components
3. For each graph G’ in the connectedComponents, the algorithm lists all maximal cliques using Tomita et al’s variation (Tomita, 2006) of Bron-Kerbosch algorithm (Bron, 1973). ** See, Enumerating Maximal Cliques
4. From the list of all maximal cliques (cliques), the algorithm picks representatives using a heuristic based on the number of cliques each vertex is within. See, Picking Cluster Representatives

---

• Tomita, E. a. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1), 28--42.
• Bron, C. a. (1973). Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9), 575--577.