Graph Clustering Based on Social Network Community Detection Algorithms

Session G2: Data Mining for Environmental Sciences (s-DMTES IV)

Graph network clustering has been an important field of investigation in recent years with a wide spectrum of applications, including environmental, genetic and engineering studies. There are two main types of applications; their suitability depends of the modeling context. Cases where the number of subdivisions is a priori known are tackled with different techniques than those where such number is not clearly evident. The second falls within the field of community detection, which has been broadly studied by social network scientists. Traditionally, community detection in graphs has been tackled by means of hierarchical clustering, which groups nodes based on their similarities. However, given the uncertainty that entails the determination of the number of clusters, other more accurate and efficient methods have been put forward. Specifically, the so-called walktrap algorithm aims to detect communities in graphs based on the idea that random walks tend to get trapped within communities (areas with higher density of links and separated by few connections). In this paper, an application of some social network concepts in the field of engineering is described. As an example, they are used to sectorize the water supply network of the Battle of the Water Calibration Networks.