Attributed graph models: Modeling network structure with correlated attributes

Joseph J. Pfeiffer, Sebastian Moreno, Timothy La Fond, Jennifer Neville, Brian Gallagher

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

88 Scopus citations

Abstract

Online social networks have become ubiquitous to today's society and the study of data from these networks has improved our understanding of the processes by which relationships form. Research in statistical relational learning focuses on methods to exploit correlations among the attributes of linked nodes to predict user characteristics with greater accuracy. 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 correlations in the observed network and exploits a generative 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 combines the attribute correlations with the structural probabilities 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 sampling method based on Accept-Reject sampling to generate edges with correlated attributes. We demonstrate the efficiency 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. Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Original languageEnglish
Title of host publicationWWW 2014 - Proceedings of the 23rd International Conference on World Wide Web
PublisherAssociation for Computing Machinery
Pages831-841
Number of pages11
ISBN (Electronic)9781450327442
DOIs
StatePublished - 7 Apr 2014
Externally publishedYes
Event23rd International Conference on World Wide Web, WWW 2014 - Seoul, Korea, Republic of
Duration: 7 Apr 201411 Apr 2014

Publication series

NameWWW 2014 - Proceedings of the 23rd International Conference on World Wide Web

Conference

Conference23rd International Conference on World Wide Web, WWW 2014
Country/TerritoryKorea, Republic of
CitySeoul
Period7/04/1411/04/14

Keywords

  • Attributed graph models
  • Network analysis
  • Network modeling

Fingerprint

Dive into the research topics of 'Attributed graph models: Modeling network structure with correlated attributes'. Together they form a unique fingerprint.

Cite this