KGraph: isolated and highly connected community detection in graphs

Abstract

Current network analysis algorithms are of seminal importance because they are able to detect patterns in networks with a variety of classes and sizes that are of vital importance in multiple fields of research. Highly connected communities whose vertices are closely related to each other and have only a few external relations are one such key pattern. Most community detection algorithms in graphs guarantee that each community is relatively isolated but not highly cohesive. This can generate many irrelevant communities for large networks. In this paper we propose KGraph, an efficient highly connected community detection algorithm that takes a density-based approach using the k-core of the graph and can also establish a community hierarchy for improved visualization. KGraph has been compared with Dengraph, the best-known density-based algorithm in the literature both run on the Netscience network.