Tolerance Methods in Graph Clustering: Application to Community Detection in Social Networks

摘要

This article introduces a novel approach to graph clustering based on tolerance spaces. From a graph theory perspective, a community is considered as a group or cluster of nodes with interconnections between them. The proposed approach to community detection uses a tolerance relation which provides a mechanism for clustering objects (nodes or vertices of a graph) into groups termed as tolerance classes inspired by near set theory. The proposed tolerance-based community detection (TCD) algorithm uses the shortest path as the distance function for creating tolerance classes, where a tolerance class represents members of the same community. For parameter selection, an objective function based on two well-known quality functions, modularity and coverage, is used. To demonstrate the robustness of the proposed method, sensitivity analysis of the parameters is given. The effectiveness of the TCD algorithm has been demonstrated by testing it on four real-world data sets. Experimental results include the comparison of the TCD algorithm with four other methods. TCD was able to achieve the best results with two data sets. The contribution of this work is a new tolerance-based method for community detection in social networks.