Network Clustering by Embedding of Attribute-augmented Graphs
  In this paper we propose a new approach to detect clusters in undirected
graphs with attributed vertices. The aim is to group vertices which are similar
not only in terms of structural connectivity but also in terms of attribute
values. We incorporate structural and attribute similarities between the
vertices in an augmented graph by creating additional vertices and edges as
proposed in [5, 27]. The augmented graph is embedded in a Euclidean space
associated to its Laplacian and apply a modified K-means algorithm to identify
clusters. The modified K-means uses a vector distance measure where to each
original vertex is assigned a vector-valued set of coordinates depending on
both structural connectivity and attribute similarities. To define the
coordinate vectors we employ an adaptive AMG (Algebraic MultiGrid) method to
identify the coordinate directions in the embedding Euclidean space extending
our previous result for graphs without attributes. We demonstrate the
effectiveness of our proposed clustering method on both synthetic and
real-world attributed graphs.
