Clustering attributed multi-graphs with information ranking

Abstract

Attributed multi-graphs are data structures to model realworld networks of objects which have rich properties/attributes and they are connected by multiple types of edges. Clustering attributed multigraphs has several real-world applications, such as recommendation systems and targeted advertisement. In this paper, we propose an efficient method for Clustering Attributed Multi-graphs with Information Ranking, namely CAMIR. We introduce an iterative algorithm that ranks the different vertex attributes and edge-types according to how well they can separate vertices into clusters. The key idea is to consider the ‘agreement’ among the attribute- and edge-types, assuming that two vertex properties ‘agree’ if they produced the same clustering result when used individually. Furthermore, according to the calculated ranks we construct a unified similarity measure, by down-weighting noisy vertex attributes or edge-types that may reduce the clustering accuracy. Finally, to generate the final clusters, we follow a spectral clustering approach, suitable for graph partitioning and detecting arbitrary shaped clusters. In our experiments with synthetic and real-world datasets, we show the superiority of CAMIR over several state-of-the-art clustering methods. © Springer International Publishing Switzerland 2015.