Content-Structural Graph Clustering and a New Measure for Its Evaluation

Today, with the spread of social networks, the opposition's efforts to chill out people from government (known as “soft war”) are increased. Therefore, dealing with this type of networks is important for military and security organizations. Graph clustering is one of the first attempts toward analyzing social networks which can appropriately be modeled by a content graph. In contrast, most of the existing graph clustering methods independently focused on one of the content or structural aspects of a graph. The aim of this paper (implemented as CS-Cluster algorithm) is to achieve well connected clusters while their nodes benefits from homogeneous attribute values (content). In the second step of our research, after an intensive search, no measure has found which could simultaneously consider content and structural features of clustering algorithms. So to be able to appropriately evaluate our algorithm, a new content-structural measure (so-called “CS-Measure”) is proposed. Our experimentation shows that the proposed clustering algorithm outperforms two other well-known content-structural clustering algorithms, using the new content-structural, average similarity, and Error link measure as well as the previous content and structural measures, And it also performed relatively well in density measure.