Community detection in node-attributed social networks: a survey

Abstract

Community detection is a fundamental problem in social network analysis consisting in unsupervised dividing social actors (nodes in a social graph) with certain social connections (edges in a social graph) into densely knitted and highly related groups with each group well separated from the others. Classical approaches for community detection usually deal only with network structure and ignore features of its nodes (called node attributes), although many real-world social networks provide additional actors' information such as interests. It is believed that the attributes may clarify and enrich the knowledge about the actors and give sense to the communities. This belief has motivated the progress in developing community detection methods that use both the structure and the attributes of network (i.e. deal with a node-attributed graph) to yield more informative and qualitative results. During the last decade many such methods based on different ideas have appeared. Although there exist partial overviews of them, a recent survey is a necessity as the growing number of the methods may cause repetitions in methodology and uncertainty in practice. In this paper we aim at describing and clarifying the overall situation in the field of community detection in node-attributed social networks. Namely, we perform an exhaustive search of known methods and propose a classification of them based on when and how structure and attributes are fused. We not only give a description of each class but also provide general technical ideas behind each method in the class. Furthermore, we pay attention to available information which methods outperform others and which datasets and quality measures are used for their evaluation. Basing on the information collected, we make conclusions on the current state of the field and disclose several problems that seem important to be resolved in future.

arXiv commentThis is an essentially revised version of the manuscript

References in corpus (24)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Inductive Representation Learning on Large Graphs
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Variational Graph Auto-Encoders
• Social Structure of Facebook Networks
• Community Detection in Networks with Node Attributes
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• A Classification for Community Discovery Methods in Complex Networks
• Community detection in networks: Structural communities versus ground truth
• Covariate-assisted spectral clustering
• Empirical Comparison of Algorithms for Network Community Detection
• Attributed Graph Clustering: A Deep Attentional Embedding Approach
• Fast consensus clustering in complex networks
• Towards Linear Time Overlapping Community Detection in Social Networks

Cited by in corpus (8)

• A Comprehensive Survey on Community Detection with Deep Learning
• Effective and Scalable Clustering on Massive Attributed Graphs
• Community detection for weighted bipartite networks
• A Generative Node-attribute Network Model for Detecting Generalized Structure
• Effective and Efficient Core Computation in Signed Networks
• Graph Neural Network Encoding for Community Detection in Attribute Networks
• Measuring Proximity in Attributed Networks for Community Detection
• FastAMI -- a Monte Carlo Approach to the Adjustment for Chance in Clustering Comparison Metrics