Multiplicative Attribute Graph Model of Real-World Networks

Abstract

Large scale real-world network data such as social and information networks are ubiquitous. The study of such social and information networks seeks to find patterns and explain their emergence through tractable models. In most networks, and especially in social networks, nodes have a rich set of attributes (e.g., age, gender) associated with them. Here we present a model that we refer to as the Multiplicative Attribute Graphs (MAG), which naturally captures the interactions between the network structure and the node attributes. We consider a model where each node has a vector of categorical latent attributes associated with it. The probability of an edge between a pair of nodes then depends on the product of individual attribute-attribute affinities. The model yields itself to mathematical analysis and we derive thresholds for the connectivity and the emergence of the giant connected component, and show that the model gives rise to networks with a constant diameter. We analyze the degree distribution to show that MAG model can produce networks with either log-normal or power-law degree distributions depending on certain conditions.

33 pages, 6 figures

References in corpus (6)

• Kronecker Graphs: An Approach to Modeling Networks
• Core-periphery organization of complex networks
• Multiplicative Attribute Graph Model of Real-World Networks
• Multifractal Network Generator
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• Moment based estimation of stochastic Kronecker graph parameters

Cited by in corpus (30)

• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Multiplicative Attribute Graph Model of Real-World Networks
• SNAP: A General Purpose Network Analysis and Graph Mining Library
• An In-Depth Analysis of Stochastic Kronecker Graphs
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• Co-clustering separately exchangeable network data
• Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+
• Latent Multi-group Membership Graph Model
• On MultiAspect Graphs
• Dimensionality of social networks using motifs and eigenvalues
• Nonparametric Multi-group Membership Model for Dynamic Networks
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Learning multifractal structure in large networks
• Graphlet decomposition of a weighted network
• Graph Generators: State of the Art and Open Challenges
• sGrapp: Butterfly Approximation in Streaming Graphs
• Evaluating Social Networks Using Task-Focused Network Inference
• Edge Union of Networks on the Same Vertex Set
• Testing and Modeling Dependencies Between a Network and Nodal Attributes
• Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs
• Modeling Graphs Using a Mixture of Kronecker Models
• Node isolation in large homogeneous binary multiplicative attribute graph models
• Stochastic Opinion Dynamics for Interest Prediction in Social Networks
• On the log-normality of the degree distribution in large homogeneous binary multiplicative attribute graph models
• Modeling Transitivity in Complex Networks
• A Threshold For Clusters in Real-World Random Networks
• Inferring Network Structure From Data
• LlamaFur: Learning Latent Category Matrix to Find Unexpected Relations in Wikipedia
• On The Network You Keep: Analyzing Persons of Interest using Cliqster
• Connectivity and giant component in random distance graphs