Comparative analysis of sequential community detection algorithms based on internal and external quality measure

Abstract

Community detection is a dominant research field in social media mining. Numerous algorithms have been developed to detect community structure in network. Each of them focuses on different characteristic of data and generates different communities for same dataset. So cluster validation or comparative analysis of these algorithms is required to compare the efficiency of these algorithms. There are two known ways for cluster validation: Internal Quality Measure (IQM) and External Quality Measure (EQM). IQM evaluates the cluster without reference to external information while EQM requires already known clusters i.e. ground truth for comparison. Most of the researchers have compared Community Detection algorithms on the basis of either IQM or EQM but not both. In this paper, we have tried to compare nine existing sequential community detection algorithms on the basis of both IQM and EQM and we observed that overall performance of Louvain, Fastgreedy and Walktrap algorithm is more efficient than other algorithms. From this paper, researchers working in this area can get information about major sequential community detection algorithms and their efficiency on small real world datasets. They can incorporate the findings to develop more efficient algorithms.

Subject Classification:

• 68T09

Keywords:

• Community detection algorithms
• Community detection data sets
• Cluster validation
• Internal quality measure
• External quality measure