Multiplicative Attribute Graph Model of Real-World Networks

Myunghwan Kim; Jure Leskovec

Source-linked AI summary

Multiplicative Attribute Graph Model of Real-World Networks

Myunghwan Kim, Jure Leskovec

arXiv:1009.3499v3Sep 17, 2010cs.SIphysics.soc-ph

TL;DR

Real-world network models must explain connectivity while incorporating rich node attributes, but prior approaches often trade analytical tractability against statistical expressiveness. The paper introduces MAG, which multiplies attribute-specific affinities to generate edge probabilities and analytically studies its resulting networks. MAG exhibits densification, a giant connected component, small diameter, and either log-normal or power-law degree distributions, while parameter fitting remains future work.

Problem
Network modeling seeks to explain connectivity patterns while jointly accounting for network structure and rich node attributes, despite a gap between tractability and statistical expressiveness.
Method
MAG assigns categorical latent attributes to nodes and defines each edge probability as the product of attribute-specific affinities selected from matrices Θi.
Results
MAG obeys the Densification Power Law, has a unique giant connected component and small diameter, and can generate log-normal or power-law degree distributions.
Takeaways & Limitations
MAG provides an analytically tractable and statistically interesting framework in which networks with different structural properties emerge from model parameters.
Takeaways & Limitations
The paper leaves MAG parameter fitting, underlying-structure recovery, and inference of partially observed node attributes for future work.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses a gap between analytically tractable but simplistic network models and statistically powerful but analytically difficult models. It proposes MAG to jointly represent node attributes and network structure while analyzing several real-world network properties.

Real-world network research seeks models that explain connectivity patterns, graph evolution, realistic synthesis, and algorithmic consequences.
Rich node attributes, including age, gender, workplace, and habits, must be considered simultaneously with network structure, especially in social networks.
Existing mechanistic models are analytically tractable but often statistically uninteresting, whereas statistical models capture network features but are generally analytically intractable.
MAG combines categorical node attributes to model link formation and captures both homophily and heterophily through feature interactions.
The paper analyzes densification, connectivity, giant-component emergence, diameter, and degree distributions in MAG networks.The model can produce log-normal or power-law degree distributions under different conditions.
MAG is positioned as a tractable and statistically interesting model for studying heterogeneous real-world networks.

2 Formulating of the Multiplicative Attribute Graph (MAG) model

MAG assigns categorical attributes to nodes and combines attribute-specific affinities multiplicatively to determine edge probabilities. Its flexible formulation includes homophily, heterophily, directed or undirected graphs, and connections to Kronecker graphs, while analysis focuses on a simplified version.

2.1 General considerations: Each node has a vector of l categorical attributes, such as binary answers to multiple-choice questions.
2.1 General considerations: For each attribute, an affinity matrix Θi maps the two nodes’ attribute values to a link-forming affinity.
2.1 General considerations: Homophily corresponds to larger diagonal affinities, while heterophily favors links between nodes with different attribute values.
2.1 General considerations: MAG supports richer categorical cardinalities and asymmetric affinity matrices, allowing directed and more complex network structures.
2.2 The Multiplicative Attributes Graph (MAG) model: The edge probability P[u, v] equals the product of the affinities selected by the attribute values of nodes u and v.
2.2 The Multiplicative Attributes Graph (MAG) model: Edges appear independently once node attributes and affinity matrices determine their probabilities.
2.2 The Multiplicative Attributes Graph (MAG) model: The model’s multiplicative construction is motivated by attribute dimensions in Blau spaces and their effects on social interaction.
2.3 Simplified version of the model: The paper analyzes a simplified undirected model with binary attributes, shared symmetric affinity matrices, and l = ρ log n attributes.The general model’s parameter-estimation and latent-attribute inference questions remain future work.

3 The Number of Edges

The MAG model derives the expected number of edges and shows that its attribute dimension supports the Densification Power Law under the relevant scaling conditions.

Expected number of edges: Theorem 3.1 derives the expected number of edges in MAG, separating contributions from distinct-node edges and self-edges.Excluding self-edges leaves the first term of the expression.
Expected number of edges: The edge-count analysis uses node weights, weight classes W_j, nested sets S_j, and expected edge probabilities and degrees conditioned on weight.Expected degrees are summed over the binomial weight distribution to obtain the total edge count.
Scaling of attributes: The expected-edge formula supports the assumption l = ρ log n and yields bounds excluding both m ∈ o(n) and m ∈ Θ(n^2−o(1)) regimes for social networks.The lower and upper bounds follow from Corollaries 3.3.1 and 3.3.2.
Interpretation: The model’s interpretation links independently distributed attributes at node arrival with later dependence between attributes and network structure as the network grows.The number of attributes grows slowly relative to the number of nodes.
Densification Power Law: For ρ = 1 and µ = 0.5, MAG has densification exponent a = log(|Θ|), where |Θ| is the sum of all entries in Θ.This agrees with the Densification Power Law m(t) ∝ n(t)^a for a > 1.

4 Connectivity

MAG connectivity is governed by node weights: larger-weight nodes are more likely to connect, while giant-component and full-connectivity thresholds depend on strategically chosen weight classes.

Giant component: With high probability, MAG has exactly one connected component of size Θ(n) under the criterion in Theorem 4.1.The theorem states this condition is necessary and sufficient as n →∞.
Connectedness: MAG is connected with high probability when Fc(M) > 1 and disconnected with high probability when Fc(M) < 1.The criterion separates the two asymptotic connectivity regimes.
Weight structure: A node’s connection probability is monotone in its weight, so larger-weight nodes occupy a core role while smaller-weight nodes form the periphery.This monotonicity affects both connectedness and giant-component emergence.
Connectedness: The connectivity criterion depends on the minimum-weight node, with separate cases determined by whether the expected number of weight-0 nodes exceeds 1.The proof evaluates the expected degree of the minimum-weight node.
Giant component: The giant component criterion relies on the median-weight node, while its uniqueness is established by showing that two Θ(n)-sized connected subgraphs connect with high probability.The analysis examines weights µl, µl + l^1/6, and µl + l^2/3.

5 Diameter

MAG can maintain a bounded diameter as the network grows, provided the stated condition holds; a dense core and its links to peripheral nodes establish this result.

Constant diameter: Under the condition in Lemma 5.2, MAG has constant diameter with high probability as n →∞.The theorem guarantees bounded diameter but does not specify its exact value.
Core subgraph: The high-weight subset S_λl has constant diameter with high probability under the lemma’s condition.This subset functions as the bounded-diameter core used in the argument.
Core-to-periphery links: All nodes outside S_λl are directly connected to S_λl with high probability as n →∞.These links connect the remainder of the graph to the core.
Constant diameter: The entire graph’s diameter is at most 2 plus the diameter of S_λl, and is therefore constant under the lemma’s condition.The bound follows by routing through the core.

6 Degree Distribution

Under stated parameter conditions, the simplified MAG model produces an approximately log-normal degree distribution. This behavior follows from the relationship between node weights and expected degrees.

The simplified model excludes self-edges, both for computational simplicity and consistency with other models.
Theorem 6.1 establishes that the degree-distribution tail follows a log-normal form under the section’s assumptions.
The log-normal result appears as a quadratic relationship on a log-log degree-distribution plot.The authors relate this pattern to observations from social networks such as LiveJournal.
The expected degree grows exponentially with node weight, while node weights follow a binomial distribution approximated by a normal distribution for large l.Therefore, logarithmic degree values are approximately normal, yielding an approximately log-normal degree distribution.
The analysis concerns the degree-distribution tail above the median degree and assumes a condition associated with the existence of a giant component.The condition also ensures that at least half the nodes have sufficiently large degrees.

7 Extensions: Power-Law Degree Distribution

The paper extends MAG by relaxing shared-parameter constraints across attributes to obtain power-law degree distributions. The extension is motivated by the prevalence of power-law structure in social networks and is supported by theoretical intuition and simulation.

The extended MAG model produces power-law degree distributions by allowing attribute-specific Bernoulli parameters and affinity matrices.Attributes remain binary and independently sampled, but their parameters need not be identical.
The power-law result is presented as an intuitive, non-rigorous argument and is additionally verified by simulation in Figure 5.
The extension has 4l parameters, comprising the Bernoulli parameters and affinity matrices for all l attributes.
Lemmas 7.2 and 7.3 characterize attribute-vector probabilities and expected node degrees, providing the ingredients for the power-law analysis.
The proposed mechanism links the probability of sharing an attribute vector to a negative power of expected degree, with a further factor arising from Stirling approximation.

8 Simulation

Simulations show that MAG network structure changes systematically with its parameters and reproduces several real-world network patterns. The model also matches many Yahoo!-Flickr properties qualitatively, while its simplified form misses the observed clustering trend.

8.1 MAG model parameter space: Varying µ, α, f, or n in the simplified model changes edges, largest-component size, and effective diameter; the experiments fix all other parameters.The affinity matrix is Θ = [α β; β γ], with f scaling a fixed base matrix.
8.1 MAG model parameter space: Increasing parameters produces polynomial rather than exponential network-size growth; for l = 8, size varies with the eighth power of f and degree 2 over n.
8.1 MAG model parameter space: The largest connected component exhibits a sharp threshold, with at least half the network in the giant component at the theoretical threshold.
8.1 MAG model parameter space: The effective diameter rises near giant-component formation, then drops rapidly and approaches a constant.This reproduces the reported gelling-point behavior of real-world network evolution.
8.2 Network evolution: With n and l increased together at fixed ratio, simulations reproduce densification power law and shrinking-diameter behavior.
8.3 Comparison to Real-world Networks: The simplified and power-law MAG variants exhibit log-normal and power-law degree distributions, respectively, in the Figure 5 simulations.The figure compares both PDF and CCDF representations.
8.3 Comparison to Real-world Networks: Against Yahoo!-Flickr, the MAG plots qualitatively resemble nearly all examined properties, but the simplified model reverses the observed degree–clustering relationship.Using one shared core-periphery affinity matrix yields higher clustering for higher-degree nodes, unlike Yahoo!-Flickr.
8.3 Comparison to Real-world Networks: Mixing core-periphery and homophily affinity matrices in the general model captures a heavy-tailed clustering-coefficient distribution.

9 Conclusion

The paper presents MAG as a network model combining categorical node attributes with attribute-dependent link affinities. It establishes analytical properties, empirically verifies them, and identifies parameter fitting and latent-attribute recovery as future work.

9 Conclusion: MAG combines categorical node attributes with an attribute-attribute affinity matrix governing link formation.The affinity matrix provides flexibility in the resulting network structure.
9 Conclusion: MAG is analytically tractable and statistically interesting, supporting analysis of several properties observed in real-world networks.The paper also reports empirical verification of its analytical results.
9 Conclusion: The model proves the Densification Power Law, a unique giant connected component, and small diameter.These are among the network properties established analytically for MAG.
9 Conclusion: MAG can generate either log-normal or power-law degree distributions under different conditions.The conclusion links the degree-distribution outcome to model conditions.
9 Conclusion: Parameter fitting, underlying-structure recovery, and missing-node-attribute inference remain future work.The paper specifically notes partially observed node attributes as an open setting.

B Appendix: Connectivity

The connectivity analysis identifies conditions under which MAG contains a connected linear-size subgraph, a unique giant component, or an entirely connected network. Outside the connectivity regime, most nodes can be isolated and no giant component emerges.

B Appendix: Connectivity: A linear-size attribute-weight subgraph is connected with high probability when its expected node degree is at least c log n.The connectivity lemma applies when the subgraph has Θ(n) nodes and sufficiently large constant c.
B Appendix: Connectivity: |S_{µl+l^1/6}| ∈ Θ(n) with high probability, whereas |S_{µl+l^2/3}| ∈ o(n).These size bounds separate the linear-size core from the asymptotically small high-weight region.
B Appendix: Connectivity: A giant connected component exists and is unique under the stated condition.The proof shows that two distinct Θ(n) components would connect with high probability, contradicting their separation.
B Appendix: Connectivity: When S_{µl} or S_{µl+l^1/6} satisfies the connectivity condition, it forms a component containing at least a linear fraction of the network.The proof identifies one of these sets as the Θ(n)-sized component when the giant component exists.
B Appendix: Connectivity: When the expected degree of nodes below weight µl+l^2/3 is o(1), most nodes are isolated and the largest component is not Θ(n).Because S_{µl+l^2/3} is o(n), n−o(n) nodes lie below this weight threshold.
B Appendix: Connectivity: The entire network is connected with high probability when the minimum-weight class meets the connectivity threshold; otherwise, some minimum-weight node is isolated with high probability.The two cases are established through the expected degree of nodes in the minimum-weight class.

C Appendix: Diameter

The diameter analysis reduces a suitable MAG subgraph to an Erdős–Rényi graph with a lower-bounded edge probability. This comparison yields a constant upper bound on the diameter with high probability.

C Appendix: Diameter: The analysis uses an Erdős–Rényi diameter theorem as the basis for bounding MAG distances.The theorem gives diameter d when the relevant edge-probability scaling crosses the stated thresholds.
C Appendix: Diameter: For nodes in S_{λl}, every pair has edge probability at least β^{λl}γ^{(1−λ)l}.This lower bound permits comparison with G(|S_{λl}|, β^{λl}γ^{(1−λ)l}).
C Appendix: Diameter: The comparison graph has diameter bounded by a constant with high probability as n →∞.The same constant bound transfers to S_{λl} because MAG contains at least the comparison graph's edges in the probabilistic ordering.

D Appendix: Degree Distribution

The degree-distribution analysis expresses degree probabilities as mixtures over attribute-weight classes and examines which terms dominate. Under the stated approximation regime, the distribution follows a log-normal form.

D Appendix: Degree Distribution: The degree probability p_k is expressed as a sum over attribute-weight classes with class-specific expected edge probabilities.For E_j=(µα+(1−µ)β)^j(µβ+(1−µ)γ)^{l−j}, Corollary D.1.1 gives the degree probability in M(n,l,µ,Θ).
D Appendix: Degree Distribution: The expected maximum degree is o(n) with high probability because the maximum-weight node's expected degree is O(n(µα+(1−µ)β)^l).This establishes the asymptotic regime used in the degree analysis.
D Appendix: Degree Distribution: For large l, the class-specific degree terms can be approximated using the normal approximation to the binomial distribution.The analysis then searches for the attribute-weight class j maximizing the dominant contribution.
D Appendix: Degree Distribution: When k∈Ω(l) and j,τ∈O(l), the dominant term occurs near j≈τ.The conclusion follows because otherwise the derivative magnitude grows as large as Ω(k).
D Appendix: Degree Distribution: For practical R values close to 1.6∼3, one dominant term effectively determines p_k.The analysis states that ln p_k is then roughly proportional to ln g_τ.
D Appendix: Degree Distribution: The degree distribution p_k approximately follows a log-normal distribution under the theorem's assumptions.The approximation is obtained after assigning τ according to ln k, ln n, and ln R.

E Appendix: Power-law Distribution

The appendix analyzes when the MAG degree distribution can exhibit a power law by expressing degree probabilities through ordered attribute-vector masses and average edge probabilities. It derives a sufficient condition and gives a feasible attribute configuration under which the resulting degree probability is approximately proportional to k^-1.

Expected degree formula: The expected degree formula is established for every number of attributes l ≥ 1.The proof proceeds inductively using the multiplicative update P_k+1(u, v) = P_k(u, v)Θ_k+1[a_k+1(u), a_k+1(v)].
Degree-probability representation: Degree probabilities are organized by ordering the 2^l attribute-vector masses p(j), with E_j denoting the corresponding average edge probability.The appendix illustrates this ordering by sorting example masses 0.1, 0.2, 0.3, and 0.4.
Degree-probability representation: When only a few terms dominate the degree-probability expression, p_k is approximated by the dominant term indexed by τ = arg max_j p(j)(E_j)^k(1 − E_j)^(n−1−k).This approximation is the basis for proposing a sufficient condition for a power-law degree distribution.
Power-law condition: If E_j+1/E_j ≥ 1 + z for a constant z > 0, the τ-th term dominates Equation (2) under the stated asymptotic condition.The appendix also notes that the relevant remainder is o(1) for Δ ≥ 1 as n → ∞.
Power-law consequence: For sufficiently large k and n, the resulting degree probability satisfies p_k approximately proportional to k^-1.The appendix concludes by showing that the conditions for this power-law behavior can be simultaneously feasible through an example configuration.
Power-law condition: A feasible configuration satisfies 1 − μ_i = (1 + z)^−2iδ, making the sufficient condition for a power-law degree distribution attainable.The construction relies on configuring μ_i and Θ_i independently.