An Enhanced Conductance-Based Approach for Community Detection in Weighted Mobile Phone Networks

Abstract

Community Detection has gained a lot of attention in recent years due to its applications in studying human behaviour in various spheres of life and most especially in the analysis of criminal networks. In this era of Big Data Analytics, community detection has been made easier by the availability of huge sources of data such as the Call Detail Rec- ords (CDR) of the telephone networks. Recently, focus in community detection is gradually drifting from unweighted networks to weighted networks, where the strength of the link between each pair of connected nodes is considered rather than just the existence of a link. However, existing algorithms for community detection have focused only on direct links between pairs of nodes in a network. In this work, an Enhanced Conductance-based Algo- rithm (ECBA) was develop to detect communities in a network. This was done by synthesiz- ing the direct and indirect relationship strengths between all pairs of nodes on a weighted undirected graph. The algorithm was tested with CDR data using belonging degree and con- ductance as the decision metrics for community partitioning. Comparison with the original conductance-based algorithm shows significant improvement in quality of detection for communities of large sizes in terms of average shortest path distances, density, and how closely knit the connections are. Test results further show that using indirect relationships between pairs of nodes significantly reveals more information about community member- ship in large networks.