Homophily and transitivity in dynamic network formation

1 A dynamic network formation model

• The model observes undirected networks over periods t = 0, 1, . . . , T and leaves the initial network D0 unrestricted.Agents maximize per-period payoff functions by adding, subtracting, or maintaining links.Source: §1 · pp. 6, 8
• Pairwise stability with transfers requires present edges to generate nonnegative joint marginal utility and absent edges to generate negative joint marginal utility.Transferable utility lets each dyad freely share surplus from an edge.Source: §1 · p. 7

Some observations

• The nuisance parameter space is enormous because A contains real-valued unknown heterogeneity and Π0 assigns mass across all possible initial network configurations, while θ has only two elements.Conditional on A, the network is a heterogeneous Markov process, but it is generally not Markov unconditionally.Source: Some observations · p. 8
• The transition process combines state dependence through α, triadic closure through β, and unobserved dyad-specific fundamentals Aij that may encode homophily or degree heterogeneity.A link is more likely when the pair was previously connected, when it closes prior two-stars, or when its unobserved fundamentals are favorable.Source: Some observations · pp. 8–9
• Both structural transitivity β0 and homophily in A can produce clustered networks, making their separate identification difficult.The model therefore permits dependence among dyad-specific heterogeneity terms, including dependence induced by shared latent attributes.Source: §1 · p. 7, Some observations · p. 9
• Time variation solves the unrestricted-heterogeneity problem: without restrictions on A, any network configuration could be generated by a suitable A, but repeated observations exploit A’s time invariance.This is the model’s central route to learning about θ without specifying the joint distribution of initial networks and heterogeneity.Source: Some observations · pp. 9–10

Likelihood

• A parametric integrated likelihood requires specifying both the innovation distribution and the initial network distribution, even though the transition rule provides little guidance for the latter.This is the initial network problem, analogous to issues in dynamic discrete-choice and panel models.Source: Likelihood · pp. 10–11
• Integrated likelihood estimation also entails high-dimensional integration over correlated heterogeneity and leaves large-sample inference unclear for a single network.These computational and inferential difficulties motivate the paper’s frequentist approach with a delicate asymptotic argument.Source: Likelihood · p. 11

2 Conditional likelihood analysis

• Proposition 1 establishes that d0, cumulative link decisions, and within-dyad counts mij(δ, ρ; d3) are sufficient for A and π, with B∗(d3) = B(d3).Conditioning on these statistics yields a likelihood indexed only by the finite-dimensional parameter θ and free of nuisance parameters.Source: §2 · p. 13
• Because enumerating B(d3) may be intractable, the analysis conditions on an explicitly enumerable subset BK(d3) generated by swapping identifying star systems, sacrificing information for analytical and computational tractability.Uniformly sampling the full conditioning set is difficult because valid swaps may require simultaneous changes across many movers.Source: §2 · pp. 14–15, Star systems · p. 15

Star systems

• Identifying p-star systems require changing spoke links embedded in a stable neighborhood, and their swaps generate |BK(d3)| = 2^m2:K,N reachable network sequences.The stable-neighborhood conditions fix links surrounding the star through two degrees, while all star-system spokes move between periods 1 and 2.Source: Star systems · pp. 15–16
• Agent and dyad separation imply that each belongs to at most one identifying star system, limiting the number of such systems to at most N^2.Distinct identifying star systems also have invariant links between their agents, so informative networks contain separated link clusters rather than only hairball structure.Source: Star systems · pp. 16–18

Permutation Lemmas

• The permutation lemmas formally define BK(d3) by simultaneously swapping period-1 and period-2 decisions for identifying star systems while holding all other link decisions fixed.These swaps are guaranteed to remain in B(d3), overcoming the constraint violations that arbitrary dyad swaps can induce.Source: Permutation Lemmas · pp. 18–19
• Permutation Lemma 3 shows that swapping all identifying star-system edges also swaps common-friends terms and leaves many likelihood multiplicands identical after permutation.This reduces the conditional likelihood analysis to a tractable comparison across edge-swapped network configurations.Source: Permutation Lemmas · p. 20

Conditional star system likelihood

• Theorem 1 gives a conditional likelihood representation invariant to fixed effects A, enabling identification of θ0 = (α0, β0)′.The representation controls cascading interdependence by swapping period-1 and period-2 edges within identifying star systems; only dyads involving their neighborhoods contribute differently, while A cancels.Source: Conditional star system likelihood · pp. 21–23
• The conditional likelihood’s product structure yields conditionally independent multiplicands, supporting single-network, many-agent sampling-distribution approximations.Instead of enumerating the intractable conditioning set, the log-likelihood can be evaluated using a sum over identifying star systems, while the surrounding neighborhood architecture contributes to identification.Source: Conditional star system likelihood · p. 22

Examples of identifying star systems

• Identifying star-system examples show that relative frequencies of swapped sequences reveal transitivity β and state dependence α when the relevant payoff components are held fixed.A two-star example contrasts links formed before versus after a common friend appears, while a three-star example varies transitivity payoffs across dyads and periods.Source: Examples of identifying star systems · pp. 24–26
• With multiple identifying star systems, the reference set contains every combination of edge swaps, and the MLE favors parameter values making the observed network relatively more likely than its permutations.In the combined example, four networks share statistics sufficient for A and π but differ in consecutive links and triangle-closing attempts, which inform α and β.Source: Examples of identifying star systems · p. 26

Exact inference on α and β

• Exact inference conditions on D3 ∈BK (d3), whose distribution is a parametric family indexed only by θ, enabling similar tests despite unrestricted nuisance parameters.The exact method follows Fisher (1922) and enumerates BK (d3) by simulation.Source: §3 · p. 27, Exact inference on α and β · p. 30

Asymptotic inference on α and β

• Asymptotic consistency and normality of the conditional-likelihood estimator rely on conditionally independent identifying star systems whose number diverges as N →∞.The single-network setting observes only T = 3 periods, so this growth condition imposes restrictions on the population network-generating process and nuisance parameters.Source: §3 · p. 28, Notation and setup · pp. 34–35

A Metropolis-Hastings algorithm

• Algorithm 1 samples the null conditional distribution by randomly swapping period-1 and period-2 edges within stable star systems, accepting proposals by their conditional likelihood ratio.The resulting Markov chain visits every sequence in BK (d3) with positive probability and, for sufficiently large σ, yields a draw from ℓcss (·; θ0).Source: A Metropolis-Hastings algorithm · pp. 30, 32
• The confidence set obtained by inverting two-sided conditional tests has coverage exactly 1 −α, up to simulation and numerical approximation error, uniformly over nuisance parameters.A practical limitation is that σ must be large enough; a rule of thumb is to swap each identifying star system’s edges at least twice.Source: A Metropolis-Hastings algorithm · pp. 32–33

Notation and setup

• The effective sample size and attainable precision depend on the distribution of fixed effects and the initial network, even though identification holds for any nuisance parameters.Some heterogeneity distributions prevent consistent estimation, while the number of identifying star systems is at most of order N.Source: Notation and setup · pp. 35–36

Single network estimation: examples

• The examples show that identifying stars may disappear asymptotically: with compact fixed effects and a dense Erdos-Renyi initial graph, β0 > 0 produces nearly complete networks and few transitions.When β0 < 0, D1 = 0 with high probability and the required identifying configuration occurs with vanishing probability.Source: Single network estimation: examples · pp. 36–37
• In Example 1, the total number of identifying stars vanishes as the network size N grows.This result is stated as Proposition 2, with the complete proof in Appendix B.6.Source: Single network estimation: examples · p. 37
• In the random geometric graph example, the expected number of stable systems of any fixed size grows linearly with N.The result follows from identifying-star probabilities that decay as N^−(K−1), offset by O(N^K) possible node combinations.Source: Single network estimation: examples · pp. 37–38
• The linear growth rate is the fastest possible because identifying-star probabilities shrink rapidly when spokes must switch, while isolated-bubble constructions provide matching lower bounds.The upper bound requires leaves to cluster near the center; the lower bound isolates the star from outside interference and specifies internal link dynamics.Source: Single network estimation: examples · p. 38

• The design uses a random geometric opportunity graph with agents uniformly scattered in the plane and links restricted by distance.Initial links occur with probability 0.75 within radius r and probability zero beyond it.Source: §4 · p. 38
• Initial networks are sparse, with average degree calibrated to 2, 3, or 4, producing respectively disconnected components, emerging giant connectivity, or a giant component containing over half of agents.Average degree is approximately 0.75πr^2 and does not increase with network size.Source: §4 · pp. 38–39
• Location-based homophily generates high initial clustering despite no network effects, while subsequent links increase transitivity and degree through state dependence and triadic closure.The initial clustering coefficient exceeds 0.4 in all designs, making the simulations test cases for Theorem 4.Source: §4 · p. 39
• With N = 5,000 and B = 1,000 replications, stable 2-star systems outnumber stable 3-star systems, limiting exploration of larger identifying systems.Stable 2-star systems average 136–290, while stable 3-star systems range from 32–60, or about 20–24% as many.Source: §4 · p. 40
• Pooling 2- and 3-star systems yields greater precision than the conditional 2-star estimator across all designs, with lower mean absolute error and mean standard deviation.Both estimators are approximately mean and median unbiased, and Wald confidence intervals achieve close to nominal 95% coverage.Source: Table 2 · p. 40, §4 · p. 40

• The study models annual co-authorship links among 56,156 authors from EconLit during 1996–1999, using four network snapshots that are sparse, highly fragmented, and mostly isolated.Average degree ranges from 0.36 to 0.43, while the share of isolates remains above 70%.Source: §5 · p. 42, Table 3 · p. 42
• The application is presented as a proof-of-concept because many observed triangles come from triple-authored papers, making the collaborator-choice microfoundations of the model uncertain.The authors therefore treat the exercise as a worked example on a real-world dataset rather than a definitive structural account of co-authorship formation.Source: §5 · p. 42
• The data contain 3,798 identifying 2-star systems, 560 identifying 3-star systems, and 61 identifying 4-star systems, providing a substantial but rapidly declining effective sample.Including stable 4-star systems changes parameter estimates and standard errors only modestly relative to using identifying 2- and 3-star systems.Source: §5 · p. 43, Table 4 · p. 43
• In the standard logistic regression, positive α indicates high bilateral-link persistence, whereas negative β indicates that links closing prior-period open two-stars are relatively infrequent.Some of these patterns may reflect weaker persistence of three-way collaborations than two-way collaborations across periods.Source: §5 · p. 43
• CSS-MLE estimates suggest that the high transitivity index, approximately 0.5, is mainly driven by homophily rather than an intrinsic preference for transitive triplets.The standard logit coefficient is considerably larger, or less negative, because it fails to account for homophily-driven clustering.Source: Table 4 · p. 43, §5 · p. 43

• Dynamic network formation models with rich heterogeneity can be identified from a single network sequence, with consistent estimation and large single-network inference feasible in some settings.These conclusions rely consequentially on logit errors, although aspects of the analysis may extend beyond that assumption.Source: §6 · p. 44
• The estimator’s convergence rate and information accumulation depend on the heterogeneity distribution and initial network configuration, making asymptotic efficiency delicate.The conditional star-system maximum likelihood estimator reaches a rate analogous to the traditional single-agent panel setting, but the supplied passage does not fully display the formula.Source: §6 · p. 44
• Researchers can count identifying star-systems, and global concavity with a two-parameter θ suggests asymptotic theory may guide finite-network inference even with modest numbers of such systems.Whether identifying star-systems occur in real-world networks remains open, although the empirical illustration is hopeful.Source: §6 · p. 44
• The CSS-MLE uses only part of the full conditional likelihood, leaving the magnitude and structure of information loss—including differences across star-system sizes—as open questions.Source: §6 · p. 44
• Future research could examine other link-formation preferences, time-varying regressors, and identification of average effects.The paper’s focus on transitivity is motivated by social and economic network research; related directions include Pelican and Graham (2026), Dano (2023), Dano et al. (2025), and Gao and Niu (2026).Source: §6 · p. 44

Supplemental Web Appendices

• The supplemental web appendices contain proofs of the theorems stated in the main text.Source: Supplemental Web Appendices · p. 48
• They also include statements and proofs of supplemental lemmata.Source: Supplemental Web Appendices · p. 48
• Notation in the appendices follows the main text unless otherwise stated.Source: Supplemental Web Appendices · p. 48
• Equation numbering continues sequentially from the main text.Source: Supplemental Web Appendices · p. 48

A Preliminary results

• Appendix A proves selected main-text lemmas and develops supplemental results needed for the main theorems proved in Appendix B.Source: A Preliminary results · p. 48
• Appendix A defines C as a generic constant whose magnitude may vary throughout the proofs.Source: A Preliminary results · p. 48
• The appendix abbreviates Triangle Inequality, Cauchy-Schwarz Inequality, Hoeffding, Markov Inequality, Jensen’s Inequality, and the Law of Iterated Expectations as TI, CSI, MI, HI, JI, and LIE.Source: A Preliminary results · p. 48

Stationary distribution

• A finite, irreducible, ergodic Markov chain has stationary distribution π when π is nonnegative, sums to one, and satisfies detailed balance, π_l p_lm = π_m p_ml.This criterion is invoked in proving Theorem 2.Source: §A.1 · p. 48

MLE consistency

• The conditional star-system MLE is shown consistent under compactness, uniform approximation of the target criterion, and identification.The result uses a variant of the standard M-estimation consistency theorem and is applied to Theorem 3.Source: §A.1 · pp. 48–49
• Under these approximation and identification conditions, any maximizer of the sample criterion lies near the true parameter with probability approaching one.Uniform laws of large numbers or stochastic equicontinuity can provide the required approximation.Source: §A.1 · p. 49

A.2 Proofs of preliminary results appearing in the main text

• Lemma 3’s Part (A) shows that each identifying star’s two relevant relationships either preserve their ordering or swap consistently under admissible permutations.The conclusion follows by considering the two possible alignments of (B_ik1, B_ik2) with (D_ik1, D_ik2).Source: §A.2 · p. 50
• Lemma 3’s Part (B) extends the same preservation-or-swapping correspondence to dyads between two members of an identifying star system.Both star members must follow the same alignment for the corresponding S and R components to match or swap.Source: §A.2 · p. 51
• Lemma 3’s Part (C) handles agents outside the identifying star by separating neighboring agents, agents in another identifying star, and agents in neither structure.The proof uses the relevant neighborhood and star conditions to show either correspondence, swapped correspondence, or invariant links.Source: §A.2 · pp. 51–52
• The conditional-independence proof introduces stability indicators Z_pi, tuples Q_pi, and the remaining dyads Q_-Z to factor the network-sequence probability.For fixed D0, D3, Z, and A, the map from network sequences and the summation over Q_-Z yield the required factorization.Source: §A.2 · pp. 52–53
• Conditional on D0, D3, Z, and A, the tuples (Z_pi, Q_pi) are independent across p and i, with the marginal obtained after summing over Q_-Z.The proof factors the joint probability mass function and sums over all potential values of Q_-Z.Source: §A.2 · pp. 52–53

B.1 Proof of Proposition 1

• Proposition 1 proves that any b3 in the admissible set preserves each pair’s relevant membership counts because b0 is fixed and the two later components may only match or swap.The proof first establishes equality of the cardinalities of m_ij(δ,ρ; b3) and m_ij(δ,ρ; d3).Source: §B.1 · p. 53
• The converse concludes that d3 = b3: equality of the aggregate sums over t=1,2 together with b0 = d0 identifies the remaining network component.The final step uses the equality of the summed dyadic quantities for all i,j.Source: §B.1 · p. 53

Likelihood-ratio decomposition

• Initial-condition and non-identifying-dyad likelihood contributions cancel because the compared networks share d_0 and d_3, while swapping identifying-star edges leaves their systematic utilities unchanged.The denominator and numerator are decomposed using the dyad partition, with common initial-condition factors and identical contributions from dyads outside identifying star systems.Source: §B.2 · pp. 54–55

Identifying-star dyads

• For dyads within an identifying star system, swapping edges produces the logit factor b_10(q_ij; θ), which does not depend on A_ij.The expression is obtained using b_0 = d_0, b_3 = d_3, Lemma 3, and a conditional-likelihood argument based on Honoré and Kyriazidou (2000).Source: §B.2 · p. 56

Cross-star dyads

• Dyads connecting two different identifying star systems have identical numerator and denominator contributions, so their likelihood-ratio factor equals one.This follows from d_ij1 = d_ij2 = b_ij1 = b_ij2 = 0 and the relevant parts of Lemma 3.Source: §B.2 · pp. 57–58

Partial star dyads

• In the logit case, when (dij1, dij2) = (1, 1), c11(qij; θ) = exp(β(1 − dij3)(rij2 − rij1)); for dyad ij ∈ Dpd, c(qij; θ) = b(qij; θ).Source: §B.2 · p. 59

Within-star non-star dyads

• The same c(q_ij; θ) = exp(β(d_ij1 − d_ij3)(r_ij2 − r_ij1)) expression applies to non-star dyads whose agents belong to the same identifying star system.The proof treats the (1,1) and (0,0) configurations separately and obtains the same factors as for partial star dyads.Source: §B.2 · pp. 59–60

Assembly of the ratio

• All dyad contributions therefore either equal one or b(q_ij; θ), allowing the likelihood ratio to be written as a sum over edge-swap configurations in which each identifying star contributes one or a product of b(q_ij; θ) terms.The contribution depends on the dyad class and on whether each identifying star system is swapped; the resulting product has one term for every element of B_K(d_3).Source: §B.2 · pp. 60–61

B.2 Proof of Theorem 1 (Conditional Star-System Likelihood)

• The derivation completes when inversion yields equation (19).Source: §B.2 · p. 61

Graph construction

• The state-transition graph has one vertex for every network sequence in B_K(d_3), with self-loops and neighbors obtained by swapping one stable star system.Each vertex has m_{2:K,N} such neighbors because Algorithm 1 selects one stable star system uniformly at random.Source: §B.3 · p. 61

Ergodicity

• Positive-probability paths between every pair of vertices, together with self-loops, make the finite chain irreducible and aperiodic, hence ergodic with a unique stationary distribution.Any network sequence can be reached through finitely many stable-star-system swaps; self-loops ensure the graph is not bipartite.Source: §B.3 · p. 62

Stationary distribution

• The proof applies Theorem 5 with π_l = δ(v_ϕ); because ℓ_css(·; θ_0) is a probability mass function supported on B_K(d_3), detailed balance yields a stationary distribution for the Markov chain.Source: §B.3 · pp. 62–63

Step 2: Separation

• A lower Hessian bound makes θ0 a well-separated maximizer of ˜QN, completing the conditions required for consistency.Concavity, the multivariate mean value theorem, and Assumptions 1–3 are combined to obtain the required separation bound.Source: §B.4 · pp. 64, 66, 67

Step 1.b: Uniform convergence

• Uniform convergence follows from stochastic equicontinuity applied to ∆QN := bQN −˜QN, using Newey’s Corollary 2.2 and uniformly bounded moments.Assumptions 1 and 3 provide the bounds needed to apply Corollary 2.2 in Newey (1991).Source: §B.4 · pp. 64–65

Step 2: Identification

• The population criterion ˜QN is maximized at θ0 for every N, establishing the proof’s identification step.The argument uses the conditional likelihood of d3 given D0, D3, Zp, and A, and shows the resulting function is maximized at θ0.Source: §B.4 · pp. 65–66

Consistency conclusion

• The estimator is consistent: ˆθ →p θ0 after all conditions of Lemma 5 are verified.The proof concludes that the sample estimator converges in probability to the true parameter.Source: §B.4 · p. 68

Score and Hessian requirements

• Asymptotic normality reduces to proving a normalized score limit and convergence of the Hessian to a positive definite matrix.These are identified as the two requirements for asymptotic normality of ˆθ.Source: §B.5 · p. 69

Score asymptotics

• The score’s normality is established with the Wald device by arranging score contributions as martingale differences and verifying McLeish’s conditions.The proof defines a filtration, controls the martingale increments, and invokes Hall and Heyde (1980) for the central limit result.Source: §B.5 · pp. 69–70

Conclusion

• Slutsky’s lemma and the information matrix inequality combine the score and Hessian limits to complete the asymptotic-normality result.The argument concludes after establishing the limit for arbitrary λ and the relevant matrix convergence equations.Source: §B.5 · pp. 71–73

Hessian convergence

• The Hessian converges by combining conditional score properties, conditional independence, moment bounds, and pointwise convergence of the conditional star-system log-likelihood.Assumptions 4 and 5 supply the required bounds and curvature conditions.Source: §B.5 · p. 72

Case 1: β0 ≥ 0

• For β0 ≥ 0, edge-swapping probabilities decay exponentially in N because common-neighbor counts exceed linear thresholds with exponentially high probability.The tail bounds fail with probability at most N^2 exp(−γ0N) and N^2 exp(−γ1N).Source: §B.6 · p. 73
• For β0 ≥ 0, the expected number of identifying stars converges to zero after bounding their contributions by polynomial factors times exponentially decaying terms.The argument uses separation to control identifying stars and shows both resulting terms converge to zero.Source: §B.6 · pp. 75–76

Case 2: β0 < 0

• For β0 < 0, the period-1 graph is empty with overwhelming probability, reducing period-2 links conditional on this event to independent dyad-specific outcomes.The proof first bounds period-1 link probabilities using β0 < 0, then establishes the empty-graph event for large N.Source: §B.6 · pp. 76–77
• On EN, a given candidate star is exponentially unlikely to be identifying.If S is identifying and D1 = 0, Definitions 4 and 5 imply period-2 requirements.Source: §B.6 · p. 77

Proof of Proposition 3

• In sparse geometric graphs, the raw common-neighbor count is Op(1) because relevant neighbors lie in the intersection of two radius-r balls.The dominating binomial count has success probability at most πr^2/N and is therefore tight.Source: §B.7 · p. 80
• A K-star is identifying when its center is interior, leaves lie within r/2, no outside agent lies within 3r/2, and the required spoke and leaf-leaf edges realize the event.These conditions eliminate outside feasible neighbors, make the period-1 neighborhood empty, and ensure non-spoke internal dyads are stable.Source: §B.7 · p. 81
• The event constructing an identifying star has probability bounded below by a positive constant depending on K and a, multiplied by N^{-(K−1)}.The geometric isolation probability is bounded below uniformly for large N, while the internal edge configuration contributes a strictly positive factor depending only on K and a.Source: §B.7 · p. 82
• For every fixed K̄, the expected number of identifying K-systems is of order N after summing over K = 2, …, K̄.The proof counts candidate stars and lower-bounds their identification probability by a positive geometric factor times the relevant link-probability terms.Source: §B.7 · pp. 82–83