Structure and inference in annotated networks

By Mark Newman, Aaron Clauset. 2015

364 citations recorded by the source corpus.

For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network. Here we demonstrate how this ‘metadata’ can be used to improve our understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead, the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological and technological domains. Analysis of network structure is usually based on knowledge of connections alone, ignoring additional information such as gender or age of individuals in social networks. Here the authors devise an approach that incorporates such metadata and uses it to improve the detection of network communities.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Prioritizing network communities (2018, methodology): “However, when domain-speci ﬁ c supervised information is available, CR ANK can integrate this extra information to boost performance (Supplementary Notes 9 and 10).”
Latent Space Model for Multi-Modal Social Data (2015, background): “Such an approach can generate a more comprehensive understanding of users and their preferences [57, 48, 46].”
Graph Clustering with Graph Neural Networks (2020, methodology): “[39] shows that using features allows their estimation-based approach to overcome the spectral “detectability” limit for graphs [35], a result that we replicate in this study.”
Bayesian Robust Attributed Graph Clustering: Joint Learning of Partial Anomalies and Group Structure (2018, methodology): “Among the non-robust methods, PICS (Akoglu et al. 2012), CESNA (Yang, McAuley, and Leskovec 2013) and SIAN (Newman and Clauset 2016) only derive point-estimates of the learned parameters.”
Community detection in Attributed Network (2018, background): “Recently, only few recent studies have addressed the problem of clustering in attributed networks [24]; [4]; [21].”
Community detection in networks: A user guide (2016, methodology): “…that also belong to a set of valid solutions, according to the algorithm22, but happen to be better correlated with the 22 For instance, for clustering methods based on optimisation, there are many partitions corresponding to values of the quality func- annotations (Newman and Clauset, 2016).”