Community detection in attributed networks considering both structural and attribute similarities: two mathematical programming approaches

摘要

Community detection is one of the most well-known and emerging research topics in the area of social network analysis. There are a wide variety of approaches to find communities in the literature, each with its own advantages and disadvantages. A majority of these approaches tend to detect communities by only using the network topology. However, the distribution of the node attributes is correlated with the community structure in many real networks. Therefore, the quality of the discovered partitions can be enhanced by considering node attributes. In this study, two novel mathematical programming approaches are proposed to integrate the topological structure and node similarities, in which first the primary attributed network is converted into a secondary non-attributed network. Then, a mathematical model will be developed to find communities in the secondary network. Thanks to the fact that the objective function and constraints of the proposed model are defined linear, the global optimality of the obtained solutions is guaranteed. In order to validate the proposed approaches, they are applied to both real-world and benchmark networks. Computational results of two well-known evaluation measures including Rand index and normalized mutual information demonstrate the efficiency of the proposed approaches in discovering better partitions.