Performance metrics for chromatic correlation clustering for social network analysis

The social network can be viewed as a chromatic graph of relations and entities. Thus, the community discovery in social network is essentially a problem of chromatic correlation clustering. This paper aims to develop metrics to measure the performance of community discovery algorithms in view of nonoverlapping strong communities. Three performance metrics, namely, chromatic density (CD), chromatic cut ratio (CCR) and chromatic conductance (CC), were proposed for thorough analysis on the output quality of chromatic clustering algorithms. In addition, synthetic graph generator was developed to generate sparse networks with few dense and strong communities. Five algorithms for chromatic correlation clustering, i.e. CB, ICB, LCB, OCB and RECB, were evaluated by the proposed metrics. The evaluation shows that the RECB is the most suitable algorithm for the discovery of strong communities in social network. The research results shed important new light on the detection of communities in social network. © 2019 Mattingley Publishing. All rights reserved.