Attributed graph models: modeling network structure with correlated attributes

Online social networks have become ubiquitous to today’s society and the study of data from these networks has im-proved our understanding of the processes by which relation-ships form. Research in statistical relational learning focuses on methods to exploit correlations among the attributes of linked nodes to predict user characteristics with greater ac-curacy. Concurrently, research on generative graph models has primarily focused on modeling network structure with-out attributes, producing several models that are able to replicate structural characteristics of networks such as power law degree distributions or community structure. However, there has been little work on how to generate networks with real-world structural properties and correlated attributes. In this work, we present the Attributed Graph Model (AGM) framework to jointly model network structure and vertex attributes. Our framework learns the attribute cor-relations in the observed network and exploits a genera-tive graph model, such as the Kronecker Product Graph Model (KPGM) [11] and Chung Lu Graph Model (CL) [2], to compute structural edge probabilities. AGM then com-bines the attribute correlations with the structural proba-bilities to sample networks conditioned on attribute values, while keeping the expected edge probabilities and degrees of the input graph model. We outline an efficient method for estimating the parameters of AGM, as well as a sam-pling method based on Accept-Reject sampling to generate edges with correlated attributes. We demonstrate the effi-ciency and accuracy of our AGM framework on two large real-world networks, showing that AGM scales to networks with hundreds of thousands of vertices, as well as having high attribute correlation