Testing Alignment of Node Attributes with Network Structure Through Label Propagation

Abstract

Attributed network data is becoming increasingly common across fields, as we are often equipped with information about nodes in addition to their pairwise connectivity patterns. This extra information can manifest as a classification, or as a multidimensional vector of features. Recently developed methods that seek to extend community detection approaches to attributed networks have explored how to most effectively combine connectivity and attribute information to identify quality communities. These methods often rely on some assumption of the dependency relationships between attributes and connectivity. In this work, we seek to develop a statistical test to assess whether node attributes align with network connectivity. The objective is to quantitatively evaluate whether nodes with similar connectivity patterns also have similar attributes. To address this problem, we use a node sampling and label propagation approach. We apply our method to several synthetic examples that explore how network structure and attribute characteristics affect the empirical p-value computed by our method. Finally, we apply the test to a network generated from a single cell mass cytometry (CyTOF) dataset and show that our test can identify markers associated with distinct sub populations of single cells.

References in corpus (7)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Higher-order organization of complex networks
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm