Source-linked AI summary
Community detection in node-attributed social networks: a survey
Petr Chunaev
TL;DR
Community detection in node-attributed social networks must integrate graph structure with actors’ attributes, but the expanding literature lacks a comprehensive synthesis. This survey exhaustively searches the field, classifies methods by when and how they fuse these information sources, and analyzes evaluations. It concludes that current comparisons are insufficient to identify state-of-the-art methods.
Problem
Existing overviews are partial, while the growing number of methods creates methodological repetition and uncertainty about practical choices.
Method
The survey exhaustively searches known methods, classifies them by when and how structure and attributes are fused, and reviews technical approaches, evaluations, datasets, and quality measures.
Results
The survey concludes that current comparison studies are too incomplete and inconsistent to determine state-of-the-art methods for node-attributed social networks.
Takeaways & Limitations
The proposed early-, simultaneous-, and late-fusion classification helps estimate methodological variety and the relative ease of software implementation.
Takeaways & Limitations
The survey excludes multi-layer network methods, which require specialized analysis of heterogeneous vertices and edges across layers.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Community detection in node-attributed social networks combines network structure with node attributes to identify socially and structurally coherent groups. This survey organizes the expanding methodology, evaluates how fusion affects results, and highlights unresolved theoretical and practical issues.
- Problem definition: Node-attributed networks represent actors through graph structure and attribute vectors, adding information such as age, gender, or interests beyond connections.The graph is represented as G = (V, E, A), where V contains nodes, E edges, and A node-associated attribute vectors.
- Survey scope: The survey addresses the field’s growth through an exhaustive method search, a fusion-based classification, technical descriptions, and analysis of methods, datasets, and quality measures.It also identifies current problems and topics that require future investigation, including when fusing structure and attributes is worthwhile.
- Problem definition: Community detection partitions social actors into densely connected, well-separated groups, using structural closeness and attribute homogeneity as complementary objectives.Communities may be disjoint or overlapping, and the number of communities may be known beforehand or determined automatically.
- Motivation: Attribute homogeneity is motivated by homophily, the tendency for like-minded actors to have a higher likelihood of being connected.Using attributes alongside structure may therefore produce higher-quality communities, although the paper presents this as a motivation rather than a universal guarantee.
- Fusion effects: Structure and attributes often provide complementary information: attributes can offset structural sparsity, while structure can help with missing or noisy attributes.Other studies find that the sources may instead be orthogonal or contradictory, with relationships that are highly nonlinear and difficult to analyze.
3. RELATED WORKS AND PROCESSING THE RELEVANT LITERATURE
The survey extends earlier partial and sometimes inconsistent reviews by systematically searching relevant literature and defining a broader scope for node-attributed network methods. It excludes multi-layer networks and treats subspace-based approaches as a related but distinct area.
- Related surveys: Earlier reviews and Related Works sections were often partial, repetitive, or contradictory, motivating a more comprehensive survey of node-attributed community detection.The authors identify the 2015 survey as the only dedicated prior survey while noting that many newer and previously omitted methods had appeared.
- Literature search: The literature search used regular and scientific search engines with multiple terminology variants, then followed references until no new relevant papers were found.The search covered related areas including attributed information networks, annotated document networks, multi-layer networks, and subspace-based clustering.
- Reporting conventions: The survey uses method names with reference numbers and marks dataset variants that differ from tabulated descriptions with an asterisk.This naming scheme distinguishes multiple methods from one paper and helps readers identify dataset descriptions and variants.
- Scope boundaries: Multi-layer network community detection is excluded because heterogeneous vertex and edge types across layers require specialized analysis and a separate comparative study.Node-attributed networks can be viewed as a special case of multi-layer networks, but that connection is rarely discussed in the surveyed papers.
- Scope boundaries: The survey mainly covers methods using the full attribute space and communities covering the whole network, while subspace- and subgraph-based methods remain a distinct class.The authors describe a separate survey on subspace-based community detection as a valuable complement, while noting that some included methods partly use this idea.
4. OUR CLASSIFICATION OF COMMUNITY DETECTION METHODS FOR NODE-ATTRIBUTED SOCIAL NETWORKS
The survey classifies methods by when and how they fuse network structure with node attributes, then organizes each class by fusion technique and practical implementation considerations.
- Fusion timing: Methods are grouped at the upper level into early, simultaneous, and late fusion according to when structure and attributes are combined.Early fusion precedes community detection, simultaneous fusion occurs during detection, and late fusion combines separately obtained partitions.
- Practical implementation: Early fusion commonly preprocesses structure and attributes into a representation that existing classical community detection algorithms can process.Weight-based early fusion, for example, merges structure- and attribute-aware graphs into a weighted graph.
- Subclass organization: Within each timing class, subclasses are organized primarily by fusion technique rather than by the downstream clustering algorithm.Weight-based methods remain so classified even when their weighted graph is converted into a distance matrix.
- Survey coverage: The survey tables describe each method’s algorithm, input, community type, evaluation datasets, quality measures, and related methods.This information is provided for methods in the classes and subclasses covered in Sections 6–8.
5. MOST USED NODE-ATTRIBUTED NETWORK DATASETS AND QUALITY MEASURES FOR COMMUNITY DETECTION EVALUATION
The survey covers node-attributed datasets from social, document, and citation networks, distinguishes them by size, and summarizes quality measures for settings with or without ground truth.
- Datasets: Popular evaluation datasets include social networks such as Facebook, LastFM, and Twitter, alongside document or citation networks such as DBLP, Wiki, and Patents.The survey notes that its methods can generally be applied beyond social networks to node-attributed networks of different natures.
- Dataset sizes: Datasets are categorized as small, medium, or large when they contain < 10^3, 10^3 ...10^5, or > 10^5 nodes, respectively.
- Quality measures: Without ground truth, structural closeness and attribute homogeneity are evaluated separately, most commonly with Modularity, Density, and Entropy.
- Quality measures: With ground truth, commonly used measures include Accuracy, Normalized Mutual Information, Adjusted Rand Index, Rand Index, and F-measure.
6. EARLY FUSION METHODS
Early fusion methods combine structure and attributes before community detection, producing weighted graphs, distances, augmented graphs, or other representations for classical clustering procedures.
- Overview: Early fusion converts structure and attributes into data suitable for classical community detection algorithms before clustering begins.This preprocessing can allow reuse of existing software implementations.
- Open issues: The survey identifies unresolved choices concerning topology modification, similarity functions, and the appropriate balance between structure and attributes.No study has established whether fixed or non-fixed topology is preferable, and systematic effects of similarity-function choices remain unstudied.
- Weight-based methods: Weight-based methods merge structural and attributive graphs into a weighted graph, typically assigning w(vi,vj) = αwS(vi,vj)+(1−α)wA(vi,vj).The parameter α controls the balance between structural and attributive similarity.
- Distance-based methods: Distance-based methods fuse structural and attributive distances into a distance matrix, often using Dα(vi,vj) = αdS(vi,vj)+(1−α)dA(vi,vj).The resulting matrix can be used by distance-based clustering algorithms such as k-means or k-medoids.
- Node-augmented graph methods: Node-augmented graph methods add attribute-value nodes and connect each structural node to nodes representing its attribute values before applying community detection.Random walks may produce a distance matrix for subsequent clustering.
- Limitations: Node augmentation does not apply to continuous attributes and can become computationally expensive because it substantially increases nodes and edges.
7. SIMULTANEOUS FUSION METHODS
Simultaneous fusion methods combine structure and attributes within the community detection process through adapted objectives, metaheuristics, matrix techniques, pattern mining, probabilistic models, or dynamical systems.
- Overview: Simultaneous fusion often requires specialized software because structure and attributes are fused jointly with community detection.This contrasts with early and late fusion methods that can partly reuse classical implementations.
- Objective-function methods: Some methods modify objective functions and iterative procedures of classical algorithms such as Louvain, Normalized Cut, k-means, k-medoids, and kNN.The adapted optimization process uses both network structure and attributes.
- Metaheuristic methods: Metaheuristic methods use evolutionary algorithms or tabu search to seek partitions optimizing structural closeness and attribute homogeneity measures.Examples of such measures include Modularity and Attributes Similarity.
- Matrix methods: NNMF-based methods adapt nonnegative matrix factorization to fuse the adjacency matrix and node-attribute matrix for community detection.Their notation includes S, A, the requested cluster count N, and a cluster membership matrix U.
- Matrix compression: PICS simultaneously compresses the adjacency and attribute matrices, treating homogeneous rectangular blocks as communities.Communities found by PICS may not contain densely connected nodes because of its definition based on matrix blocks.
- Other subclasses: Other simultaneous-fusion subclasses extract patterns, infer memberships probabilistically, or model interactions through dynamical and multi-agent systems.Pattern-mining methods may detect communities only in part of a network, while probabilistic models require chosen prior distributions.
8. LATE FUSION METHODS
Late fusion methods detect communities separately from network structure and node attributes, then combine the resulting partitions. The survey distinguishes consensus-based approaches from switch-based selection.
- Late fusion framework: Late fusion first detects communities separately from structure and attributes, then fuses the resulting partitions into one structure- and attributes-aware partition.Examples include Louvain for structure and k-means for attributes.
- Implementation: Late fusion can reuse existing implementations of classical community detection and consensus clustering algorithms.
- Consensus-based methods: Consensus-based methods aggregate an ensemble of structure- and attribute-derived partitions into a single consolidated partition.Consensus clustering is designed to combine separately or jointly obtained partitions.
- Switch-based methods: Switch-based methods choose a preferable partition rather than computing consensus between separately obtained structure- and attribute-based partitions.Selection switches from the structure-based partition to the attributes-based partition when the estimated mixing parameter falls below µlim.
9. ANALYSIS OF THE OVERALL SITUATION IN THE FIELD
The survey finds that current comparisons do not support a reliable state-of-the-art ranking. Influential methods are identifiable, but heterogeneous evaluation practices and missing complexity information leave practical superiority uncertain.
- Influential methods: The survey identifies influential methods using a method-comparison graph and PageRank, but does not equate influence with state-of-the-art performance.The listed influential methods span weight-based, graph-based, objective-modification, matrix-factorization, pattern-mining, and probabilistic approaches.
- Comparison coverage: The comparison graph is sparse, disconnected, and omits 29 methods, so comparison coverage remains incomplete.Different datasets, quality measures, and hyperparameter-tuning strategies further limit direct comparisons.
- Computational complexity: Computational-complexity comparison is impossible for most methods because authors often omit estimates.Reported examples include CODICIL at O(n^2 logn), SA-Cluster at O(n^3), and CESNA at O(m).
- Hyperparameters: Hyperparameter tuning lacks a common procedure, and α = 1/2 does not generally establish equal structural and attributive impact.The survey questions this choice because structural and attributive information can have different statistical characteristics.
- Evaluation practice: Different datasets and quality measures prevent unified comparison across published experiments, while missing software and data hinder reproducibility.The survey notes that reproducing results may be time-consuming or impossible when implementations are unavailable.
- Quality measures: Quality measures based on structural closeness and attribute homogeneity may create a logical gap when optimized objectives lack a mathematically established connection.Methods that directly optimize these measures are exceptions, though their optimization precision still matters.
- Quality measures: Ground-truth agreement measures are more defensible for synthetic networks, whereas real-world ground truths may reflect only one view of community structure.
- Overall conclusion: The survey concludes that the available evidence does not permit determining state-of-the-art methods.Simply listing recent methods would not satisfy the stronger meaning of state-of-the-art.
10. CONCLUSIONS
The survey organizes 75 relevant methods for community detection in node-attributed social networks and examines their evaluation practices. Its analysis finds that the field lacks sufficient evidence to identify state-of-the-art methods, despite the practical usefulness of combining network structure with attributes.
- 75 relevant methods are described, alongside many additional methods partly related to node-attributed community detection.
- The proposed classification separates methods into early, simultaneous, and late fusion according to when structure and attributes are combined.The survey also uses lower-level subclasses to characterize fusion-technique variety.
- The survey records the datasets and quality measures used to evaluate methods, supporting comparison of experimental practices across the field.
- State-of-the-art methods cannot currently be determined because terminology, fusion effects, comparison methodology, equal structural-attribute impact, and links between algorithms and evaluation quality remain unresolved.The survey specifically notes missing unified datasets, measures, computational-complexity estimates, and justified hyperparameter tuning procedures.
- The comparison study remains incomplete, while methods using both network structure and attributes remain useful tools that can provide insights into node-attributed social networks.