Detection of Outliers and Hubs Using Minimum Spanning Tree based on Node Connectivity

Abstract

In data mining detection of anomalous pattern in data is more interesting than detecting inliers. Minimum Spanning Tree based Clustering is
an important task for the discovery of underlying structures in graph. Many algorithms find clusters by maximizing the number of intra-cluster edges.
While such algorithms find useful and interesting structures, they tend to fail to identify and isolate two kinds of vertices that play special roles –
vertices that bridge clusters (hubs) and vertices that are marginally connected to clusters (outliers). In this paper, we model hubs as high-degree nodes
having high Node Connectivity Factor (NCF) value. Identifying hubs is 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 many may be isolated as noise in the data. In this
paper we propose an algorithm called Minimum Spanning Tree based Algorithm for Outliers and Hubs based on Node Connectivity (MSTOHNC),
which detect outliers and hubs in graph.

Keywords: Euclidean minimum spanning tree; Degree; Outliers; Hub, Node Connectivity Factor;