Clustering uncertain graphs using ant colony optimization (ACO)

In deterministic graphs, an edge between two vertices denotes a certain link. In contrast, in probabilistic graph, a link between two vertices merely implies the possibility of its existence based on probability. Probabilistic data results from uncertainties due to the preprocessing, data collection process, or the inherent nature of the problem which results in uncertain outcomes. These types of graphs are common in the real-world applications such as protein–protein interactions and identifying links in social media. Clustering probabilistic graphs is a challenging task since computing traditional metrics (like distance, paths, etc.) will all be probabilistic. Therefore, determining a valid clustering or making the data deterministic is an important research problem. We propose a new clustering algorithm for probabilistic graphs using the ant colony optimization (ACO) technique. The algorithm uses multiple versions of the probabilistic graph and employs a modified ACO to optimize the objective function. Moreover, heuristics are proposed to guide the algorithm for better accuracy and faster convergence. The proposed approach is tested against two real-world probabilistic graphs and five synthetic datasets using multiple cluster validity indices. Results show that ACO with heuristic guidance can produce good solutions that are comparable to or better than other traditional approaches.