Network structure, metadata and the prediction of missing nodes and annotations

Abstract

The empirical validation of community detection methods is often based on available annotations on the nodes that serve as putative indicators of the large-scale network structure. Most often, the suitability of the annotations as topological descriptors itself is not assessed, and without this it is not possible to ultimately distinguish between actual shortcomings of the community detection algorithms on one hand, and the incompleteness, inaccuracy or structured nature of the data annotations themselves on the other. In this work we present a principled method to access both aspects simultaneously. We construct a joint generative model for the data and metadata, and a nonparametric Bayesian framework to infer its parameters from annotated datasets. We assess the quality of the metadata not according to its direct alignment with the network communities, but rather in its capacity to predict the placement of edges in the network. We also show how this feature can be used to predict the connections to missing nodes when only the metadata is available, as well as missing metadata. By investigating a wide range of datasets, we show that while there are seldom exact agreements between metadata tokens and the inferred data groups, the metadata is often informative of the network structure nevertheless, and can improve the prediction of missing nodes. This shows that the method uncovers meaningful patterns in both the data and metadata, without requiring or expecting a perfect agreement between the two.

15 pages, 6 figures, 1 table

References in corpus (14)

• Benchmark graphs for testing community detection algorithms
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• Learning Latent Block Structure in Weighted Networks
• Clique Graphs and Overlapping Communities
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• A network inference method for large-scale unsupervised identification of novel drug-drug interactions
• Community Structure Detection in Complex Networks with Partial Background Information
• Phase transitions in semisupervised clustering of sparse networks
• Predicting future conflict between team-members with parameter-free models of social networks

Cited by in corpus (18)

• The ground truth about metadata and community detection in networks
• Bayesian stochastic blockmodeling
• Reconstructing networks with unknown and heterogeneous errors
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Universality of the stochastic block model
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Estimating the outcome of spreading processes on networks with incomplete information: a mesoscale approach
• Optimal prediction of decisions and model selection in social dilemmas using block models
• Sampling networks by nodal attributes
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Missing links as a source of seemingly variable constants in complex reaction networks
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• A network community detection method with integration of data from multiple layers and node attributes
• Network compression with configuration models and the minimum description length
• Block-corrected Modularity for Community Detection