A pyramidal community detection algorithm based on a generalization of the clustering coefficient

• Published in: Journal of ambient intelligence and humanized computing 2021-10, Vol.12 (10), p.9111-9125
• Main Authors: Midoun, Mohamed Amine, Wang, Xingyuan, Talhaoui, Mohamed Zakariya
• Format: Article
• Language: English
• Subjects: Accuracy; Algorithms; Artificial Intelligence; Clustering; Coefficients; Computational Intelligence; Connectivity; Engineering; Methods; Modularity; Networks; Original Research; Robotics and Automation; Social networks; User Interfaces and Human Computer Interaction
• ISSN: 1868-5137; 1868-5145
• DOI: 10.1007/s12652-020-02608-5

The detection of community structure has aroused wide attention since it can reveal the underlying properties of complex networks in biology, as well as physical and social sciences. Many community detection algorithms have been proposed to detect the communities in the un-weighted networks. However, the recently high-level of interest in complex weighted networks gives rise to a need to develop new methods and measures to take the weights of links into account. To fulfill the above needs, we propose a new generalization of the clustering coefficient that retains the information encoded in the weights of links and thus fully capture the richness of the information contained in the data. We also define a new generation of the complete graph (CG) of a weighted network based on the maximal weight attached to each node. Furthermore, we use the weighted clustering coefficient (WCC) and CG to design a novel community detection algorithm based on a proposed pyramidal clustering. It performs in three main steps. In the first step, the CG is generated, and the WCC is computed for all the nodes. The second step uses CG and WCC to divide the network into a set of pyramidal clusters (PCs), where each PC has a score. For the final steps, we propose a measure for the clusters, called connectivity, that computes the degree of connectivity between the PCs. Pairs of PCs with high connectivity are merged until the degree of connectivity between all the clusters is low. The experiment results on weighted and un-weighted real-world networks show that the proposed method outperforms other state-of-art algorithms in terms of normalized mutual information and modularity.