Beyond Assortativity: Proclivity Index for Attributed Networks (ProNe)

Abstract

If Alice is majoring in Computer Science, can we guess the major of her friend Bob? Even harder, can we determine Bob’s age or sexual orientation? Attributed graphs are ubiquitous, occurring in a wide variety of domains; yet there is limited literature on the study of the interplay between the attributes associated to nodes and edges connecting them. Our work bridges this gap by addressing the following questions: Given the network structure, (i) which attributes and (ii) which pairs of attributes show correlation? Prior work has focused on the first part, under the name of assortativity (closely related to homophily). In this paper, we propose ProNe, the first measure to handle pairs of attributes (e.g., major and age). The proposed ProNe is (a) thorough, handling both homophily and heterophily (b) general, quantifying correlation of a single attribute or a pair of attributes (c) consistent, yielding a zero score in the absence of any structural correlation. Furthermore, ProNe can be computed fast in time linear in the network size and is highly useful, with applications in data imputation, marketing, personalization and privacy protection.