Minimum Spanning Tree-Resembling algorithm for Clusters, Outliers and Hubs

Abstract

Many systems in Science and Engineering can be modeled as graph. Clustering is a process of discovering group of objects such that the objects of the same group are similar, and objects belonging to different groups are dissimilar. A number of clustering algorithms exist that can solve the problem of clustering, but most of them are very sensitive to their input parameters. Graph-based clustering algorithms aimed to find hidden structures from objects. Graph-based clustering algorithm is capable of detecting clusters with irregular shape and sizes. In this paper we present a new algorithm MSTRCOH similar to Minimum Spanning Tree based clustering algorithm. Using this algorithm sub trees are automatically generated from high density region to low density of the graph, where each sub tree will be looked like minimum spanning tree is considered as cluster. The algorithm also detects outliers and hubs, which are present in the data set. Identifying hubs are useful for applications such as viral marketing and epidemiology since hubs are responsible for spreading ideas and disease. In contrast, outliers have little or no influence, and may be isolated as noise in the data. The newly proposed algorithm can find clusters, outliers and hubs without using any predefined input parameters.

Keywords:

• Euclidean minimum spanning tree
• Clustering
• core edge
• sub tree
• outliers
• hubs