Growing Attributed Networks through Local Processes

Abstract

This paper proposes an attributed network growth model. Despite the knowledge that individuals use limited resources to form connections to similar others, we lack an understanding of how local and resource-constrained mechanisms explain the emergence of rich structural properties found in real-world networks. We make three contributions. First, we propose a parsimonious and accurate model of attributed network growth that jointly explains the emergence of in-degree distributions, local clustering, clustering-degree relationship and attribute mixing patterns. Second, our model is based on biased random walks and uses local processes to form edges without recourse to global network information. Third, we account for multiple sociological phenomena: bounded rationality, structural constraints, triadic closure, attribute homophily, and preferential attachment. Our experiments indicate that the proposed Attributed Random Walk (ARW) model accurately preserves network structure and attribute mixing patterns of six real-world networks; it improves upon the performance of eight state-of-the-art models by a statistically significant margin of 2.5-10x.

11 pages, 13 figures

References in corpus (15)

• Emergence of scaling in random networks
• Assortative mixing in networks
• Clustering and preferential attachment in growing networks
• Growing Scale-Free Networks with Tunable Clustering
• Bose-Einstein condensation in complex networks
• Highly clustered scale-free networks
• Truncation of power law behavior in "scale-free" network models due to information filtering
• Temporal effects in the growth of networks
• Higher-order clustering in networks
• Scale-Free Networks Generated By Random Walkers
• Evolution of a large online social network
• Multiscale mixing patterns in networks
• Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+
• Relay-Linking Models for Prominence and Obsolescence in Evolving Networks
• Generating Scale-free Networks with Adjustable Clustering Coefficient Via Random Walks