A pyramidal community detection algorithm based on a generalization of the clustering coefficient
- PDF / 5,355,876 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 84 Downloads / 176 Views
ORIGINAL RESEARCH
A pyramidal community detection algorithm based on a generalization of the clustering coefficient Mohamed Amine Midoun1 · Xingyuan Wang1,2 · Mohamed Zakariya Talhaoui1 Received: 16 March 2020 / Accepted: 10 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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. Keywords Complex network · Graph theory · Clustering coefficient · Weighted network · Community structure
1 Introduction The complex systems exist widely in the sociology, economics, biology, and technology fields. These networks can be represented as graphs that contain nodes (vertices) and edges (links). It has been found that complex networks often exhibit a community structure where vertices in a community are highly connected, and few links connect the different * Xingyuan Wang [email protected] Mohamed Amine Midoun [email protected] Mohamed Zakariya Talhaoui [email protected] 1
Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, 116024 Dalian, China
School of Information Science and Technology, Dalian Maritime University, 116026 Dalian, China
2
communities. A community detection algorithm aims to discover the communities by splitting the network into clusters or groups and guarantee that the nodes in each cluster have a dense connection, while the links between the clusters
Data Loading...
