betaFeedback

WorksComputer Science

Triadic and assortative structure of absorbing states in the Axelrod model

Abstract

We study the Axelrod model of cultural dissemination, viewed as a finite-state Markov chain on an arbitrary finite graph, and classify its absorbing states. An absorbing configuration splits the edges into interior edges, whose endpoints share their whole culture, and boundary edges, whose endpoints share nothing. A partition of the vertices into connected blocks is the domain partition of some absorbing configuration exactly when its quotient graph is properly qq-colourable. The configurations with a given domain partition correspond to homomorphisms from the quotient into the FF-fold categorical power of KqK_q, so their total number is a sum of chromatic polynomials over connected partitions; this gives closed forms for trees and cycles and the value 2n+F−12^{n+F-1} for q=2q=2 on connected graphs. In absorbing configurations no triangle carries exactly one boundary edge, the open-wedge mass of the interior graph is at most that of the host graph, and Newman's assortativity coefficients for domains, cultures and single features are ordered. The feature counts are martingales and their sums of squares submartingales, which yields an absorption-time bound of order n2n^2 that is attained on paths. Exhaustive enumeration and simulations illustrate the results.

Introduction

Axelrod’s model of cultural dissemination [1] attaches to each individual a culture, that is, a vector of FF features, each taking one of qq values. Neighbours interact at a rate proportional to the number of features they share, and an interaction makes them agree on one further feature. The first mechanism is homophily and the second is social influence. Their combination produces a phenomenon absent from the voter model: two neighbours who share nothing never interact again, so the dynamics can freeze in a configuration in which several cultures coexist. The model has been studied extensively by simulation and mean-field methods in statistical physics [6, 31, 14, 5], and it remains a reference point for models of social influence [8]. The case F=q=2F=q=2 is closely related to the constrained voter model [29, 30].

Rigorous results are fewer. Lanchier [17] proved that the one-dimensional system with F=q=2F=q=2 clusters and that it fixates in a fragmented configuration when qq is sufficiently large relative to FF; Lanchier and Schweinsberg [22] extended clustering to q=2q=2 and arbitrary FF; Lanchier and Scarlato [20] proved fixation for F≤cqF \le cq with e−c=ce^{-c}=c and for F=2F=2, q≥3q \ge3; and Lanchier and Moisson [19] treated features with different numbers of values. A two-dimensional analysis is due to Li [24], and a related model with a confidence threshold was studied in [16]. On finite connected graphs, lower bounds on the probability of consensus that do not depend on the topology have been obtained for the multivariate Deffuant model [18] and for imitation and attraction processes with a confidence threshold on a general opinion graph [11], the latter building on the framework of [21]. These works concern the probability of consensus and do not describe the set of absorbing configurations as such. These results concern infinite lattices, mostly the line, where the dynamics of disagreements along edges can be compared with systems of annihilating random walks. Such methods depend on the geometry of Z\mathbb{Z} and do not extend directly to graphs with many short cycles.

The present paper takes a more modest route and works on an arbitrary finite graph. On a finite graph the process is absorbed almost surely [17 Lemma 6], and every absorbing configuration has the property that each edge joins two vertices that agree on all features or on none. Our aim is to describe exactly which configurations of this kind exist and what structure they force on the graph. The central result (Theorem 5.1) is a classification of the cultural domains of absorbing configurations: a partition of the vertices into connected blocks is realised as a domain partition if and only if its quotient graph admits a proper qq-colouring, and the absorbing configurations with a given domain partition are in bijection with graph homomorphisms from the quotient into the FF-fold categorical power of the complete graph KqK_q. Counting them gives the number of absorbing configurations as a sum of chromatic polynomials raised to the power FF (Corollary 5.4). The term of this sum for the partition into singletons is the number of proper qq-colourings of GG, that is, of zero-temperature ground states of the antiferromagnetic qq-state Potts model on GG [28], raised to the power FF; the counting of homomorphisms into complete graphs is classical [2, 12, 7]. For binary imitation dynamics on finite graphs, Li [23] observed that absorbing “alternating” states, in which every edge disagrees, exist exactly when the graph is bipartite; this is the special case of Theorem 5.1 with singleton blocks and q=2q=2. We have not found the quotient-colouring criterion, or the resulting enumeration, stated for the Axelrod model, although the frozen mixtures of the constrained voter model [29, 30] are absorbing configurations of exactly this type for F=q=2F=q=2. Colourings have been used before in this area: Lanchier [16] used the chromatic number to construct absorbing configurations in which many opinions coexist. Moreover, the absorbing configurations of the Axelrod model coincide with those of the imitation process of [11] on the Hamming opinion graph with threshold F−1F-1, and the argument of Theorem 5.1 applies to any threshold model of this kind (Remark 5.3).

The other results describe these absorbing configurations from two further angles, using tools developed in earlier work. The first is the two-walk operator W=A2−DW=A^2-D of the adjacency matrix and its unique decomposition into a part supported on edges, which counts triangles, and a part supported on non-edges, which counts open wedges [3]. The second is the description of the attribute assortativity of a partition through the split of edges into interior and boundary edges [4]. Both apply directly, since an absorbing configuration is an interior–boundary split of the edge set in which the boundary edges carry no shared features at all.

The paper is organised as follows. § 3 records conservation laws of the dynamics. The feature counts are martingales, which is the familiar voter-model property surviving in the presence of homophily, and the sums of their squares are submartingales; the drift of their total QQ is 2/F2/F times the total overlap on active edges. The second fact yields the explicit bound Eτ≤F2(Fn2−Q(σ0))\mathbb{E}\tau\le\frac{F}{2}(Fn^2-Q(\sigma_0)) on the absorption time, where QQ is the total pairwise overlap; this gives a quantitative version of almost sure absorption, whose order in nn is attained on paths. The same martingales determine the law of the final state when one feature is initially shared by all vertices. § 4 shows that in an absorbing configuration no triangle carries exactly one boundary edge, writes this as two Hadamard-product identities for the interior and boundary adjacency matrices, and compares the open-wedge mass of the interior graph with that of the host graph. § 5 contains the classification and the enumeration of absorbing configurations, with closed forms for trees and cycles, the asymptotics as q→∞q \to\infty, and a bound on the number of domains in terms of χ(G)\chi(G). § 6 treats the attribute assortativity of absorbing configurations with respect to domains, cultures and single features, and shows that the three coefficients are ordered. § 7 checks the enumeration exhaustively on small graphs and illustrates the remaining results by simulation, and § 8 lists open problems.

The individual arguments are elementary, and several of them will look familiar to readers who know the voter model. None of them uses lattice structure, so they apply to every finite graph.

The model and its absorbing configurations

Let G=(V,E)G=(V,E) be a finite simple graph with n=∣V∣≥2n=|V|\ge2 vertices and m=∣E∣≥1m=|E|\ge1 edges. Unless stated otherwise GG is connected, so every vertex has positive degree dxd_x. Write AA for the adjacency matrix and x∼yx\sim y when {x,y}∈E\{x,y\}\in E. Fix integers F≥2F\ge2 and q≥2q\ge2, and let [q]={1,…,q}[q]=\{1,\ldots,q\}. A configuration is a map σ:V→[q]F\sigma:V\to[q]^F; we write σf(x)\sigma_f(x) for the ff-th feature of the culture σ(x)\sigma(x). The overlap of two vertices is

oxy(σ)=∑f=1F1{σf(x)=σf(y)}∈{0,1,…,F},o_{xy}(\sigma)=\sum_{f=1}^{F}1\{\sigma_f(x)=\sigma_f(y)\}\in\{0,1,\ldots,F\},

and hxy=F−oxyh_{xy}=F-o_{xy} is the Hamming distance between σ(x)\sigma(x) and σ(y)\sigma(y). Since the Hamming distance is a metric on [q]F[q]^F,

oxz≥oxy+oyz−Ffor all x,y,z∈V.(1)o_{xz}\ge o_{xy}+o_{yz}-F \qquad\text{for all }x,y,z\in V. \tag*{(1)}

We use the continuous-time formulation of [17]. Each edge {x,y}\{x,y\} is activated at rate one; one of its endpoints, say xx, is chosen with probability 1/21/2; with probability oxy/Fo_{xy}/F the vertex xx then copies the value σf(y)\sigma_f(y) of a feature ff chosen uniformly among the F−oxyF-o_{xy} features on which xx and yy disagree, and nothing happens otherwise. Let σx←y,f\sigma^{x\leftarrow y,f} denote the configuration obtained from σ\sigma by setting σf(x)=σf(y)\sigma_f(x)=\sigma_f(y). The process (σt)t≥0(\sigma_t)_{t\ge0} is the continuous-time Markov chain on ([q]F)V([q]^F)^V with generator

Lφ(σ)=∑{x,y}∈E∑(u,v)∈{(x,y),(y,x)}c(oxy(σ))∑f:σf(u)≠σf(v)[φ(σu←v,f)−φ(σ)],(2)\mathcal{L}\varphi(\sigma)=\sum_{\{x,y\}\in E}\sum_{(u,v)\in\{(x,y),(y,x)\}}c(o_{xy}(\sigma))\sum_{f:\sigma_f(u)\ne\sigma_f(v)}[\varphi(\sigma^{u\leftarrow v,f})-\varphi(\sigma)], \tag*{(2)}

where c(o)=o/(2F(F−o))c(o)=o/(2F(F-o)) for $0\le o<F$; when oxy=Fo_{xy}=F the inner sum is empty. The rate c(oxy)c(o_{xy}) is symmetric in xx and $y, and this symmetry is behind the conservation laws of § 3.

An edge is interior if oxy=Fo_{xy}=F, boundary if oxy=0o_{xy}=0, and active otherwise. We write I(σ)I(\sigma), ∂(σ)\partial(\sigma) and Act⁡(σ)\operatorname{Act}(\sigma) for the three classes, so that E=I∪˙∂∪˙Act⁡E=I\mathbin{\dot\cup}\partial\mathbin{\dot\cup}\operatorname{Act}, and AIA_I, A∂A_{\partial} for the adjacency matrices of the spanning subgraphs GI=(V,I)G_I=(V,I) and G∂=(V,∂)G_{\partial}=(V,\partial). The total transition rate out of σ\sigma equals ∑{x,y}∈Act⁡oxy/F\sum_{\{x,y\}\in\operatorname{Act}}o_{xy}/F, because an active edge with overlap oo produces a change with probability o/Fo/F per activation. Hence σ\sigma is absorbing if and only if Act⁡(σ)=∅\operatorname{Act}(\sigma)=\varnothing, that is, if and only if every edge is interior or boundary. Let A\mathcal{A} denote the set of absorbing configurations and τ=inf⁡{t≥0:σt∈A}\tau=\inf\{t\ge0:\sigma_t\in\mathcal{A}\} the absorption time.

The cultural domains of σ\sigma are the connected components of GIG_I; this is the notion used in [17]. They form a partition Πdom(σ)\Pi_{\mathrm{dom}}(\sigma) of VV. We also use the partition Πcult(σ)\Pi_{\mathrm{cult}}(\sigma) of VV into classes of vertices with the same culture, and, for each feature ff, the partition Πf(σ)\Pi_f(\sigma) into classes of vertices with the same value of feature ff. Since σ\sigma is constant along interior edges, Πdom\Pi_{\mathrm{dom}} refines Πcult\Pi_{\mathrm{cult}}, and Πcult\Pi_{\mathrm{cult}} refines every Πf\Pi_f. Finally, for a configuration σ\sigma let Nf,s(σ)=∣{x∈V:σf(x)=s}∣N_{f,s}(\sigma)=|\{x\in V:\sigma_f(x)=s\}| be the number of vertices holding value ss in feature ff.

Conservation laws and a quadratic Lyapunov function

The first statement is the analogue of the classical martingale property of the voter model [25]; homophily changes the rates but not their symmetry.

Proposition 3.1. For every feature ff and every function g:[q]→Rg:[q]\to\mathbb{R}, the process ∑x∈Vg(σt,f(x))\sum_{x\in V}g(\sigma_t,f(x)) is a martingale. In particular each Nf,s(σt)N_{f,s}(\sigma_t) is a martingale and ENf,s(στ)=ENf,s(σ0)\mathbb{E}N_{f,s}(\sigma_\tau)=\mathbb{E}N_{f,s}(\sigma_0).

Proof. Let φ(σ)=∑xg(σf(x))\varphi(\sigma)=\sum_x g(\sigma_f(x)). A transition σ→σu←v,f′\sigma\to\sigma^{u\leftarrow v,f'} with f′≠ff'\ne f leaves φ\varphi unchanged. For an edge {x,y}\{x,y\} with σf(x)≠σf(y)\sigma_f(x)\ne\sigma_f(y), the two transitions x←yx\leftarrow y and y←xy\leftarrow x in feature ff occur at the same rate c(oxy)c(o_{xy}) and change φ\varphi by g(σf(y))−g(σf(x))g(\sigma_f(y))-g(\sigma_f(x)) and g(σf(x))−g(σf(y))g(\sigma_f(x))-g(\sigma_f(y)) respectively. Their contributions to (2) cancel, so Lφ≡0\mathcal{L}\varphi\equiv0. On a finite state space this makes φ(σt)\varphi(\sigma_t) a martingale. The process is bounded and τ<∞\tau<\infty almost surely (Corollary 3.3 below, or [17 Lemma 6]), so optional stopping gives the last identity.

Next consider, for each feature ff, the quantity

Qf(σ)=∑s∈[q]Nf,s(σ)2=∣{(x,y)∈V2:σf(x)=σf(y)}∣,Q_f(\sigma)=\sum_{s\in[q]}N_{f,s}(\sigma)^2=\left|\{(x,y)\in V^2:\sigma_f(x)=\sigma_f(y)\}\right|,
Q(σ)=∑f=1FQf(σ)=∑(x,y)∈V2oxy(σ),Q(\sigma)=\sum_{f=1}^{F}Q_f(\sigma)=\sum_{(x,y)\in V^2}o_{xy}(\sigma),

where the sums run over ordered pairs, diagonal included. Thus QQ is the total pairwise overlap of the population, taken over all pairs and not only over edges, and Qf/n2Q_f/n^2 is the Simpson concentration of feature ff. We call QQ a Lyapunov function in the stochastic sense: it need not increase along every sample path, but its generator drift is nonnegative and, as shown next, bounded away from zero before absorption.

Theorem 3.2. For every feature ff,

LQf(σ)=2F∑{x,y}∈Eσ(x)≠σ(y)oxyF−oxy≥0,andLQ(σ)=2F∑{x,y}∈Act⁡(σ)oxy.(3)\mathcal{L}Q_f(\sigma)=\frac{2}{F}\sum_{\substack{\{x,y\}\in E\\ \sigma(x)\ne\sigma(y)}}\frac{o_{xy}}{F-o_{xy}}\ge0,\qquad\text{and}\qquad\mathcal{L}Q(\sigma)=\frac{2}{F}\sum_{\{x,y\}\in\operatorname{Act}(\sigma)}o_{xy}. \tag*{(3)}

Consequently each Qf(σt)Q_f(\sigma_t) and Q(σt)Q(\sigma_t) is a bounded submartingale, and

EQ(στ)−EQ(σ0)=2FE∫0τ∑{x,y}∈Act⁡(σt)oxy(σt) dt.(4)\mathbb{E}Q(\sigma_\tau)-\mathbb{E}Q(\sigma_0)=\frac{2}{F}\mathbb{E}\int_0^\tau\sum_{\{x,y\}\in\operatorname{Act}(\sigma_t)}o_{xy}(\sigma_t)\,\mathrm{d}t. \tag*{(4)}

Proof. Suppose σf(u)=a≠b=σf(v)\sigma_f(u)=a\ne b=\sigma_f(v) and uu copies feature ff from vv. Then Nf,aN_{f,a} decreases by one and Nf,bN_{f,b} increases by one, so QfQ_f changes by (Nf,b+1)2−Nf,b2+(Nf,a−1)2−Nf,a2=2(Nf,b−Nf,a)+2(N_{f,b}+1)^2-N_{f,b}^2+(N_{f,a}-1)^2-N_{f,a}^2=2(N_{f,b}-N_{f,a})+2. The reverse transition, in which vv copies aa from uu, changes QfQ_f by 2(Nf,a−Nf,b)+22(N_{f,a}-N_{f,b})+2. Both occur at rate c(ouv)c(o_{uv}), so the edge contributes 4c(ouv)=2ouv/(F(F−ouv))4c(o_{uv})=2o_{uv}/(F(F-o_{uv})) to LQf\mathcal{L}Q_f. Summing over edges that disagree in ff gives the first formula; the terms with oxy=0o_{xy}=0 vanish. Summing over ff, an active edge disagrees in exactly F−oxyF-o_{xy} features, so it contributes (F−oxy)⋅2oxy/(F(F−oxy))=2oxy/F(F-o_{xy})\cdot2o_{xy}/(F(F-o_{xy}))=2o_{xy}/F to LQ\mathcal{L}Q, while boundary and interior edges contribute nothing. For the identity, Dynkin’s formula for the bounded stopping time τ∧t\tau\wedge t gives EQ(στ∧t)−EQ(σ0)=E∫0τ∧tLQ(σs) ds\mathbb{E}Q(\sigma_{\tau\wedge t})-\mathbb{E}Q(\sigma_0)=\mathbb{E}\int_0^{\tau\wedge t}\mathcal{L}Q(\sigma_s)\,\mathrm{d}s. As t→∞t\to\infty, the left side converges by bounded convergence, since τ<∞\tau<\infty almost surely by Corollary 3.3, whose proof uses only this display for finite tt, and the right side converges by monotone convergence. □

Corollary 3.3. For every initial configuration σ0\sigma_0,

Eτ≤F2(Fn2−Q(σ0))≤F2n(n−1)2.\mathbb{E}\tau\le\frac{F}{2}(Fn^2-Q(\sigma_0))\le\frac{F^2n(n-1)}{2}.

In particular the process is absorbed almost surely.

Proof. If σ∉A\sigma\notin A, at least one edge is active and its overlap is at least one, so LQ(σ)≥2/F\mathcal{L}Q(\sigma)\ge2/F by (3). Dynkin’s formula for τ∧t\tau\wedge t therefore gives 2FE[τ∧t]≤EQ(στ∧t)−Q(σ0)≤Fn2−Q(σ0)\frac{2}{F}\mathbb{E}[\tau\wedge t]\le\mathbb{E}Q(\sigma_{\tau\wedge t})-Q(\sigma_0)\le Fn^2-Q(\sigma_0), because Q≤Fn2Q\le Fn^2. Letting t→∞t\to\infty and using monotone convergence yields the first inequality. The second follows from Q(σ0)≥FnQ(\sigma_0)\ge Fn, the contribution of the diagonal pairs. □

Remark 3.4. Almost sure absorption on finite graphs is Lemma 6 of [17]; Corollary 3.3 adds an explicit bound of order F2n2F^2n^2, uniform over all graphs on nn vertices. The argument is the familiar quadratic-Lyapunov argument for voter-type models, with the homophily factor oxy/Fo_{xy}/F absorbed into the drift. The bound is crude; in the simulations of § 7 the mean absorption times are one to three orders of magnitude smaller. Proposition 3.6 below shows that its order in nn is nevertheless attained on paths.

Corollary 3.5. EQf(στ)≥EQf(σ0)\mathbb{E}Q_f(\sigma_\tau)\ge\mathbb{E}Q_f(\sigma_0) for every ff, and EQ(στ)≥EQ(σ0)+2FEτ\mathbb{E}Q(\sigma_\tau)\ge\mathbb{E}Q(\sigma_0)+\frac{2}{F}\mathbb{E}\tau.

Proof. The first statement is the submartingale property with optional stopping. The second follows from (4) together with ∑Act⁡oxy≥1\sum_{\operatorname{Act}}o_{xy}\ge1 before absorption. □

In words, the Simpson concentration of every feature can only increase in expectation, and the total overlap gains at least 2/F2/F per unit of time spent before absorption. § 6.1 turns this into a statement about domain sizes on complete graphs.

The order n2n^2 in Corollary 3.3 cannot be improved in general, while the factor F2F^2 can.

Proposition 3.6. (i) On the path PnP_n with vertices 0,…,n−10,\ldots,n-1, let σ0\sigma_0 equal a culture cc on {0,…,j−1}\{0,\ldots,j-1\} and a culture c′c' on {j,…,n−1}\{j,\ldots,n-1\}, where cc and c′c' *differ in exactly

one feature. Then Eτ=j(n−j)F/(F−1)\mathbb{E}\tau= j(n-j)F/(F-1); in particular sup⁡σ0Eτ≥⌊n2/4⌋\sup_{\sigma_0} \mathbb{E}\tau\ge\lfloor n^2/4\rfloor. (ii) On K2K_2 started from overlap o0≥1o_0 \ge1, Eτ=F(HF−1−Ho0−1)\mathbb{E}\tau= F\left(H_{F-1}-H_{o_0-1}\right), where Hk=∑i=1k1/iH_k = \sum_{i=1}^{k}1/i; the largest value is FHF−1FH_{F-1}, of order Flog⁡FF\log F.

Proof. (i) At every time before absorption the configuration consists of two blocks of cultures cc and c′c', and the only active edge is the one joining them, with overlap F−1F-1. It fires at rate (F−1)/F(F-1)/F, and each firing moves the interface one step to the left or to the right with probability 1/21/2. The position of the interface is therefore a simple random walk run at rate (F−1)/F(F-1)/F and absorbed at 00 and nn, and the expected number of steps from jj is j(n−j)j(n-j). (ii) The overlap of the two vertices never decreases; from overlap o∈{1,…,F−1}o \in\{1,\ldots,F-1\} it waits an exponential time with rate o/Fo/F and then increases by one. Summing the expected waiting times gives the formula. □\square

When some feature is initially shared by everybody, the law of the final state is determined exactly.

Proposition 3.7. Let GG be connected, and suppose that some feature f0f_0 is constant in σ0\sigma_0. Then στ\sigma_\tau is a consensus almost surely, and P(στ,f≡s)=ENf,s(σ0)/n\mathbb{P}(\sigma_{\tau,f}\equiv s)=\mathbb{E}N_{f,s}(\sigma_0)/n for every feature ff and value ss.

Proof. A copy reproduces a value already present at the same feature, so f0f_0 stays constant for all times. Every pair of vertices then has overlap at least one, no boundary edge can appear, and an absorbing configuration on a connected graph without boundary edges is a consensus. At consensus Nf,s(στ)=n 1{στ,f≡s}N_{f,s}(\sigma_\tau)=n\,\mathbf{1}_{\{\sigma_{\tau,f}\equiv s\}}, and Proposition 3.1 gives the law. □\square

Without such a shared feature the probability of reaching a particular domain partition is not determined by the martingales alone. On K2K_2, for instance, the final state has two domains if and only if o0=0o_0=0, an event of probability ((q−1)/q)F((q-1)/q)^F under uniform initial cultures.

Triadic structure of absorbing configurations

Throughout this section σ∈A\sigma\in\mathcal{A} is absorbing, so E=I⊔∂E=I\sqcup\partial and A=AI+A∂A=A_I+A_\partial.

Lemma 4.1. Let DD be a domain of σ\sigma. Then σ\sigma is constant on DD, and every edge of GG with both endpoints in DD is interior. Hence GIG_I is the disjoint union of the induced subgraphs G[D]G[D], D∈ΠdomD\in\Pi_{\mathrm{dom}}, and ∂\partial is the set of edges joining distinct domains.

Proof. The culture is constant along interior edges and DD is connected in GIG_I, so σ\sigma is constant on DD. If x,y∈Dx,y\in D and x∼yx\sim y, then oxy=Fo_{xy}=F and the edge is interior. An edge joining two distinct domains cannot be interior, since its endpoints would lie in the same component of GIG_I; being an edge of an absorbing configuration, it is a boundary edge.

The next result is the triadic constraint. In the notation of [3], let t{x,z}=(A2)xzt_{\{x,z\}}=(A^2)_{xz} denote the number of triangles through the edge {x,z}\{x,z\}, and let ∘\circ denote the Hadamard product.

Theorem 4.2. Let σ∈A\sigma\in\mathcal{A}. Then

(AI2)∘A∂=0and(AIA∂)∘AI=0.(5)(A_I^2)\circ A_\partial=0 \qquad\text{and} \qquad(A_I A_\partial)\circ A_I=0. \tag*{(5)}

Equivalently, every triangle of GG contains 00, 22 or 33 boundary edges. Moreover:

(i) the triangles through an interior edge have their two remaining edges both interior or both boundary, and the triangles through a boundary edge contain at least one further boundary edge;

(ii) a triangle with three boundary edges carries three pairwise feature-disjoint cultures, so such triangles exist only if q≥3q \ge3.

Proof. The entry ((AI2)∘A∂)xz\left((A_I^2)\circ A_{\partial}\right)_{xz} counts the vertices yy with {x,y},{y,z}∈I\{x,y\},\{y,z\}\in I and {x,z}∈∂\{x,z\}\in\partial. For such yy the vertices x,y,zx,y,z lie in one domain, and Lemma 4.1 forces {x,z}∈I\{x,z\}\in I, a contradiction. Likewise ((AIA∂)∘AI)xz\left((A_I A_{\partial})\circ A_I\right)_{xz} counts yy with {x,y}∈I\{x,y\}\in I, {y,z}∈∂\{y,z\}\in\partial and {x,z}∈I\{x,z\}\in I; then x,y,zx,y,z lie in one domain and {y,z}∈I\{y,z\}\in I, again a contradiction. Every nonzero contribution to either Hadamard product corresponds to an ordered placement of a path of length two inside a triangle with exactly one boundary edge, and every such triangle, consisting of two interior edges sharing a vertex and a boundary edge closing them, contributes to the first product. This proves the equivalence, and (i) is a restatement. For (ii), the three cultures pairwise disagree in every feature, so feature 1 takes three distinct values on the triangle. □

The constraint is a property of any partition of VV in which II is taken to be the set of edges inside blocks. What is specific to the Axelrod model is that absorbing configurations realise such splits with boundary edges whose endpoints share no feature, which is what § 5 exploits.

Part (i) refines the triangle multiplicity of [3] in the absorbing state: writing te=te(0)+te(1)+te(2)+te(3)t_e=t_e^{(0)}+t_e^{(1)}+t_e^{(2)}+t_e^{(3)} according to the number of boundary edges of the triangle, an interior edge has te(3)=0t_e^{(3)}=0 and a boundary edge has te(0)=0t_e^{(0)}=0. The identities (5) are the absorbing case of a constraint that holds at all times. By (1), for every edge {x,z}\{x,z\} with t{x,z}≥1t_{\{x,z\}}\ge1,

oxz≥1t{x,z}∑y∼x, y∼z(oxy+oyz)−F,(6)o_{xz}\ge\frac{1}{t_{\{x,z\}}}\sum_{y\sim x,\ y\sim z}(o_{xy}+o_{yz})-F, \tag*{(6)}

so an edge whose triangles have, on average, legs with large overlap cannot currently be a boundary edge. In particular an edge closing a wedge with oxy+oyz>Fo_{xy}+o_{yz}>F is never a boundary edge.

A wedge of a graph HH is an unordered pair of edges sharing a vertex, its middle vertex; it is open if the other two endpoints are not adjacent. Recall from [3] that the open-wedge mass ω(H)=∑x(dx2)−3Δ(H)\omega(H)=\sum_x\binom{d_x}{2}-3\Delta(H) of a graph HH with Δ(H)\Delta(H) triangles (here Δ\Delta never denotes the maximum degree) is the number of open wedges of HH, each counted once at its middle vertex, and that ω(H)=0\omega(H)=0 exactly when HH is a disjoint union of cliques.

Corollary 4.3. Let σ∈A\sigma\in\mathcal{A}. Then ω(GI)=∑D∈Πdomω(G[D])\omega(G_I)=\sum_{D\in\Pi_{\mathrm{dom}}}\omega(G[D]) and

ω(G)−ω(GI)=∣{open wedges of G with at least one boundary leg}∣≥0.\omega(G)-\omega(G_I)=\left|\{\text{open wedges of }G\text{ with at least one boundary leg}\}\right|\ge0.

In particular ω(GI)=ω(G)\omega(G_I)=\omega(G) if and only if every open wedge of GG has both legs interior. Likewise Δ(G)=∑DΔ(G[D])+Δ2+Δ3\Delta(G)=\sum_D\Delta(G[D])+\Delta_2+\Delta_3, where Δk\Delta_k is the number of triangles with exactly kk boundary edges.

Proof. The first identity holds because GIG_I is the disjoint union of the induced subgraphs G[D]G[D] (Lemma 4.1). A wedge of GIG_I is a wedge (x,y,z)(x,y,z) of GG with both legs interior; its three vertices lie in one domain, so by Lemma 4.1 the pair {x,z}\{x,z\} is an edge of GIG_I if and only if it is an edge of GG. The wedge is therefore open in $G_I exactly when it is open in GG. Hence the open wedges of GIG_I are the open wedges of GG with two interior legs, and the difference counts those with a boundary leg. The triangle identity follows from Theorem 4.2, since the triangles with no boundary edge are exactly the triangles of the graphs G[D]G[D]. □

Domain quotients and colourability

For a partition Π\Pi of VV into blocks inducing connected subgraphs (a connected partition), let G/ΠG/\Pi denote the simple quotient graph whose vertices are the blocks, two blocks being adjacent when some edge of GG joins them. Write χ(H)\chi(H) for the chromatic number of a graph HH and P(H;q)P(H;q) for its chromatic polynomial, the number of proper colourings of HH with qq colours [2, 7].

Theorem 5.1. A connected partition Π\Pi of VV is the domain partition of some absorbing configuration if and only if χ(G/Π)≤q\chi(G/\Pi) \le q. More precisely, the absorbing configurations with domain partition Π\Pi are in bijection with FF-tuples of proper qq-colourings of G/ΠG/\Pi; there are P(G/Π;q)FP(G/\Pi;q)^F of them.

Proof. Let σ∈A\sigma\in\mathcal{A} with Πdom(σ)=Π\Pi_{\mathrm{dom}}(\sigma)=\Pi. By Lemma 4.1, σ\sigma is constant on blocks, and every edge between distinct blocks is a boundary edge. Hence for each ff the map sending a block to the common value of σf\sigma_f on it is a proper qq-colouring κf\kappa_f of G/ΠG/\Pi, and σ\sigma is recovered from (κ1,…,κF)(\kappa_1,\ldots,\kappa_F). Conversely, let (κ1,…,κF)(\kappa_1,\ldots,\kappa_F) be proper qq-colourings of G/ΠG/\Pi and set σf(x)=κf(P)\sigma_f(x)=\kappa_f(P) for xx in block PP. Edges inside a block have overlap FF. An edge between adjacent blocks P≠P′P\ne P' has overlap 00, because κf(P)≠κf(P′)\kappa_f(P)\ne\kappa_f(P') for every ff. So σ\sigma is absorbing, its interior edges are exactly the edges inside blocks, and, the blocks being connected, its domains are exactly the blocks. The two constructions are mutually inverse. A proper qq-colouring exists if and only if χ(G/Π)≤q\chi(G/\Pi)\le q, and its repetition in all FF features gives existence. □

Remark 5.2. Theorem 5.1 has a compact formulation in terms of graph homomorphisms [12]. Let Kq×FK_q^{\times F} denote the FF-fold categorical (tensor) power of KqK_q: its vertices are the cultures [q]F[q]^F, and two cultures are adjacent when they differ in every feature. A proper qq-colouring of a graph HH is a homomorphism H→KqH\to K_q, so that P(H;q)=hom⁡(H,Kq)P(H;q)=\operatorname{hom}(H,K_q), and a homomorphism into a categorical product is a tuple of homomorphisms into the factors. The theorem therefore says that the absorbing configurations with domain partition Π\Pi are exactly the maps V→[q]FV\to[q]^F that are constant on blocks and induce a homomorphism G/Π→Kq×FG/\Pi\to K_q^{\times F}, and that their number is hom⁡(G/Π,Kq×F)=hom⁡(G/Π,Kq)F\operatorname{hom}(G/\Pi,K_q^{\times F})=\operatorname{hom}(G/\Pi,K_q)^F. For the part of the section, singletons, G/Π=GG/\Pi=G and the absorbing configurations in which every edge is a boundary edge are the homomorphisms G→Kq×FG\to K_q^{\times F}; they exist if and only if χ(G)≤q\chi(G)\le q. With q=2q=2 this recovers the observation of Li [23] that “alternating” absorbing states of binary imitation dynamics exist exactly on bipartite graphs, and, when χ(G)≤q\chi(G)\le q, the count P(G;q)P(G;q) is the number of zero-temperature ground states of the antiferromagnetic qq-state Potts model on GG [28].

Remark 5.3. Nothing in the proof of Theorem 5.1 uses the specific Axelrod rates; it uses only the shape of the absorbing set. Consider any process in which neighbours with opinions in a finite set O\mathcal{O} interact only if their opinions are distinct and compatible, and stop interacting once they agree, as in the voter models with confidence threshold on an opinion graph Γ\Gamma studied in [21, 11], where a,b∈Oa,b\in\mathcal{O} are compatible when 0<dΓ(a,b)≤τ0<d_{\Gamma}(a,b)\le\tau. A configuration is then absorbing if and only if every edge joins equal or incompatible opinions. Let I\mathcal{I} be the incompatibility graph on O\mathcal{O}, in which a≠ba \ne b are adjacent when dΓ(a,b)>τd_{\Gamma}(a,b) > \tau. The proof of Theorem 5.1 then shows, word for word, that the absorbing configurations with domain partition Π\Pi correspond to homomorphisms G/Π→IG/\Pi\to\mathcal{I}, and that there are ∑Πhom⁡(G/Π,I)\sum_{\Pi} \operatorname{hom}(G/\Pi,\mathcal{I}) absorbing configurations in all. For the Axelrod model, Γ\Gamma is the Hamming graph on [q]F[q]^F, τ=F−1\tau= F-1, and I=Kq×F\mathcal{I} = K_q^{\times F}. For opinions in [0,1][0,1] with a confidence threshold ε\varepsilon, the singleton term is the construction behind the bounds of [16] on the number of opinions that can coexist at equilibrium.

Corollary 5.4. The number of absorbing configurations of the Axelrod model on GG is

∣A∣=∑ΠP(G/Π;q)F,|\mathcal{A}| = \sum_{\Pi} P(G/\Pi;q)^F,

the sum running over all connected partitions of VV; the terms with χ(G/Π)>q\chi(G/\Pi) > q vanish.

Example 5.5. For G=K2G = K_2 there are two connected partitions, with quotients K1K_1 and K2K_2, so ∣A∣=qF+(q(q−1))F|\mathcal{A}| = q^F + (q(q-1))^F. These are the pairs of equal cultures and the pairs of cultures differing in every feature.

For two values per feature the sum in Corollary 5.4 collapses to a quantity that does not depend on the graph.

Corollary 5.6. Let GG be connected and q=2q = 2. Then ∣A∣=2n+F−1|\mathcal{A}| = 2^{n+F-1}, and exactly 2n−12^{n-1} connected partitions of VV have a bipartite quotient.

Proof. When q=2q = 2, each culture cc has a unique feature-disjoint partner, its complement cˉ\bar{c}. A configuration is therefore absorbing if and only if every edge joins equal or complementary cultures. Fix a vertex x0x_0. For each culture cc and each set S⊆V∖{x0}S \subseteq V \setminus\{x_0\}, the configuration equal to cˉ\bar{c} on SS and to cc elsewhere is absorbing, and every absorbing configuration arises in this way from exactly one pair (c,S)(c,S), because connectedness forces every culture to lie in {σ(x0),σˉ(x0)}\{\sigma(x_0),\bar{\sigma}(x_0)\}. This gives 2F⋅2n−12^F \cdot2^{n-1} configurations. On the other hand, a connected bipartite graph has exactly two proper 22-colourings, so each connected partition with bipartite quotient contributes 2F2^F to the sum in Corollary 5.4, and the other partitions contribute nothing. Comparing the two counts gives the second statement. □\square

Since A\mathcal{A} factorises over connected components, a graph with cc components has ∣A∣=2n+c(F−1)|\mathcal{A}| = 2^{n+c(F-1)} absorbing configurations when q=2q = 2.

The whole count can also be written as a single homomorphism number, which gives closed forms for trees and cycles. Let Hq,FH_{q,F} be the graph Kq×FK_q^{\times F} of Remark 5.2 with a loop added at every vertex; its adjacency matrix is M=I+(Jq−Iq)⊗FM = I + (J_q-I_q)^{\otimes F}, where JqJ_q is the all-ones q×qq \times q matrix.

Proposition 5.7. For every graph GG, ∣A∣=hom⁡(G,Hq,F)|\mathcal{A}| = \operatorname{hom}(G,H_{q,F}). Consequently, for a tree TT on nn vertices and for the cycle CnC_n,

∣A(T)∣=qF(1+(q−1)F)n−1,|\mathcal{A}(T)| = q^F\left(1+(q-1)^F\right)^{n-1},
∣A(Cn)∣=tr⁡Mn=∑j=0F(Fj)(q−1)j(1+(−1)j(q−1)F−j)n.|\mathcal{A}(C_n)| = \operatorname{tr} M^n = \sum_{j=0}^{F} \binom{F}{j}(q-1)^j\left(1+(-1)^j(q-1)^{F-j}\right)^n.

Proof. A configuration is absorbing exactly when each edge joins equal cultures, which corresponds to a loop of Hq,FH_{q,F}, or feature-disjoint cultures, which corresponds to an edge of Kq×FK_q^{\times F}; this is the first identity, and sorting the homomorphisms according to the set of edges sent to loops recovers Corollary 5.4. For a tree, choose a root culture in qFq^F ways; each further vertex, taken in breadth-first order, either copies its parent’s culture or takes one of the (q−1)F(q-1)^F cultures feature-disjoint from it. For the cycle, hom⁡(Cn,H)=tr⁡Mn\operatorname{hom}(C_n,H)=\operatorname{tr}M^n. The matrix Jq−IqJ_q-I_q has eigenvalues q−1q-1 (once) and −1-1 (q−1q-1 times), and eigenvalues of Kronecker products are products of eigenvalues. Hence MM has eigenvalue 1+(−1)j(q−1)F−j1+(-1)^j(q-1)^{F-j} with multiplicity (Fj)(q−1)j\binom{F}{j}(q-1)^j, for j=0,…,Fj=0,\ldots,F. □

With F=1F=1 the first identity reduces to the classical ∑ΠP(G/Π;q)=qn\sum_{\Pi}P(G/\Pi;q)=q^n, since every configuration of a one-feature model is absorbing. In the opposite direction, the proportion of absorbing configurations tends to one as qq grows. Indeed P(G;q)=qn−mqn−1+O(qn−2)P(G;q)=q^n-mq^{n-1}+O(q^{n-2}), and every other connected partition has at most n−1n-1 blocks and contributes O(q(n−1)F)O(q^{(n-1)F}), so that for F≥2F\ge2

∣A∣qnF=1−Fmq+O(q−2)(q→∞).\frac{|A|}{q^{nF}}=1-\frac{Fm}{q}+O(q^{-2})\qquad(q\to\infty).

This is the finite-graph counterpart of the fragmentation observed for large qq [6, 17]: almost every configuration is already frozen.

Corollary 5.8. Let σ∈A\sigma\in A.

  1. Every clique of GG meets at most qq domains.

  2. If q=2q=2, the quotient G/ΠdomG/\Pi_{\mathrm{dom}} is bipartite. In particular it has no triangles, and every triangle of GG has 0 or 2 boundary edges.

  3. (Here GG need not be connected.) If GG is a disjoint union of cliques, equivalently ω(G)=0\omega(G)=0, each component of GG carries at most qq domains, and their cultures are pairwise feature-disjoint.

Proof. The vertices of a clique lying in kk distinct domains give kk pairwise adjacent blocks of G/ΠdomG/\Pi_{\mathrm{dom}}, so k≤χ(G/Πdom)≤qk\le\chi(G/\Pi_{\mathrm{dom}})\le q by Theorem 5.1; this is (i), and (iii) is (i) applied to each component together with Lemma 4.1. For (ii), a 2-colourable graph is bipartite, and a triangle of GG with three boundary edges would meet three domains forming a triangle of the quotient. □

The chromatic number of the host graph also bounds the number of domains.

Corollary 5.9. Every absorbing configuration has at most n−χ(G)+qn-\chi(G)+q domains and at least χ(G)−q\chi(G)-q interior edges.

Proof. Contracting an edge lowers the chromatic number by at most one, since a colouring of the contracted graph extends to the original graph after one endpoint receives a new colour. The quotient G/ΠdomG/\Pi_{\mathrm{dom}} is obtained from GG by contracting the n−∣Πdom∣n-|\Pi_{\mathrm{dom}}| edges of spanning trees of the domains (and deleting loops and parallel edges), so χ(G)≤χ(G/Πdom)+n−∣Πdom∣≤q+n−∣Πdom∣\chi(G)\le\chi(G/\Pi_{\mathrm{dom}})+n-|\Pi_{\mathrm{dom}}|\le q+n-|\Pi_{\mathrm{dom}}| by Theorem 5.1. Each domain is connected in GIG_I, hence ∣I∣≥n−∣Πdom∣≥χ(G)−q|I|\ge n-|\Pi_{\mathrm{dom}}|\ge\chi(G)-q. □

For G=KnG=K_n the bound reads ∣Πdom∣≤q|\Pi_{\mathrm{dom}}|\le q and is attained; in general it is informative only when χ(G)>q\chi(G)>q.

Remark 5.10. The domain quotient is the natural setting for the contraction inequality of [3 Theorem 10.6]. With BB the directed edge-sum quotient matrix of Πdom\Pi_{\mathrm{dom}} and MM the aggregated two-walk matrix, Baa=2∣E(G[Da])∣B_{aa}=2|E(G[D_a])| counts interior edge-ends, the off-diagonal entries BabB_{ab} count boundary edges, and M≤B2M \le B^2 entrywise, with an explicit overcount. Theorem 5.1 adds that the cultures of BB-adjacent blocks are feature-disjoint. A closer study of MM and B2B^2 in absorbing states, for instance through the wedge-equitability of Πdom\Pi_{\mathrm{dom}}, is left for future work.

Assortativity of absorbing configurations

Let Π\Pi be a partition of VV. Following Newman [26], let ein(Π)e_{\mathrm{in}}(\Pi) be the fraction of edges with both endpoints in the same block, let s(Π)=∑P∈Π(vol⁡P2m)2s(\Pi)=\sum_{P\in\Pi}\left(\frac{\operatorname{vol} P}{2m}\right)^2 with vol⁡P=∑x∈Pdx\operatorname{vol}P=\sum_{x\in P}d_x, and, when s(Π)<1s(\Pi)<1, let

r(Π)=ein(Π)−s(Π)1−s(Π)r(\Pi)=\frac{e_{\mathrm{in}}(\Pi)-s(\Pi)}{1-s(\Pi)}

be the attribute assortativity coefficient of the labelling of vertices by blocks. In the language of [4], eine_{\mathrm{in}} is the interior share of the edge set relative to Π\Pi and 1−ein1-e_{\mathrm{in}} its boundary share; the coefficient compares the interior share with its value under degree-preserving mixing. For an absorbing configuration we abbreviate rdom=r(Πdom)r_{\mathrm{dom}}=r(\Pi_{\mathrm{dom}}), rcult=r(Πcult)r_{\mathrm{cult}}=r(\Pi_{\mathrm{cult}}) and rf=r(Πf)r_f=r(\Pi_f), and we write ι=∣I∣/m\iota=|I|/m for the interior fraction.

Theorem 6.1. Let GG be connected and let σ∈A\sigma\in\mathcal{A} not be a consensus. Then:

(i) ein(Πdom)=ein(Πcult)=ein(Πf)=ι<1e_{\mathrm{in}}(\Pi_{\mathrm{dom}})=e_{\mathrm{in}}(\Pi_{\mathrm{cult}})=e_{\mathrm{in}}(\Pi_f)=\iota<1 for every ff;

(ii) s(Πdom)≤s(Πcult)≤s(Πf)<1s(\Pi_{\mathrm{dom}})\le s(\Pi_{\mathrm{cult}})\le s(\Pi_f)<1 for every ff;

(iii) rf≤rcult≤rdomr_f\le r_{\mathrm{cult}}\le r_{\mathrm{dom}} for every ff. Equality rcult=rdomr_{\mathrm{cult}}=r_{\mathrm{dom}} holds if and only if no two domains carry the same culture, and rf=rcultr_f=r_{\mathrm{cult}} if and only if Πf=Πcult\Pi_f=\Pi_{\mathrm{cult}};

(iv) if Π∈{Πdom,Πcult,Πf}\Pi\in\{\Pi_{\mathrm{dom}},\Pi_{\mathrm{cult}},\Pi_f\} has kk blocks, then r(Π)≤(kι−1)/(k−1)r(\Pi)\le(k\iota-1)/(k-1), with equality if and only if the kk blocks have equal volume; in particular rf≤(qι−1)/(q−1)r_f\le(q\iota-1)/(q-1).

Proof. (i) Since Πdom\Pi_{\mathrm{dom}} refines Πcult\Pi_{\mathrm{cult}} and Πcult\Pi_{\mathrm{cult}} refines Πf\Pi_f, an edge inside a block of a finer partition lies inside a block of each coarser one. By Lemma 4.1 the edges inside blocks of Πdom\Pi_{\mathrm{dom}} are exactly the interior edges. A boundary edge joins two cultures that differ in every feature, so it does not lie inside a block of Πf\Pi_f. Hence all three partitions have the interior edges as their internal edges. Because σ\sigma is not a consensus and GG is connected, GI≠GG_I\ne G, so ∂≠∅\partial\ne\varnothing and ι<1\iota<1.

(ii) Each block has positive volume because GG is connected and n≥2n\ge2. Merging two blocks with volumes a,b>0a,b>0 replaces a2+b2a^2+b^2 by (a+b)2>a2+b2(a+b)^2>a^2+b^2, so ss strictly increases under every proper coarsening. Moreover Πf\Pi_f has at least two blocks, since the

(iii) By (i) the three coefficients have the form ϕ(s)=(ι−s)/(1−s)\phi(s)=(\iota-s)/(1-s) with a common ι<1\iota<1, and ϕ′(s)=(ι−1)/(1−s)2<0\phi'(s)=(\iota-1)/(1-s)^2<0 on [0,1)[0,1). Combining with (ii) gives the chain. Since ϕ\phi is strictly decreasing and ss strictly increases under proper coarsening, equality holds exactly when the two partitions coincide. Now Πcult=Πdom\Pi_{\mathrm{cult}}=\Pi_{\mathrm{dom}} means that distinct domains carry distinct cultures.

(iv) By the Cauchy–Schwarz inequality, s(Π)≥1/ks(\Pi)\ge1/k, and ϕ\phi is decreasing, so r(Π)≤ϕ(1/k)=(kι−1)/(k−1)r(\Pi)\le\phi(1/k)=(k\iota-1)/(k-1). The right side is increasing in kk, its derivative @bibliography being (1−ι)/(k−1)2>0(1-\iota)/(k-1)^2 > 0, and Πf\Pi_f has at most qq blocks. Equality in s(Π)≥1/ks(\Pi) \ge1/k, and hence in the bound for r(Π)r(\Pi), holds exactly when all blocks have volume 2m/k2m/k. □

For an arbitrary pair of nested partitions the finer one never has the larger internal-edge fraction, but it may have a strictly smaller one, and the ordering of the assortativity coefficients can then go either way. In an absorbing state the boundary edges disagree in every feature, so the interior fraction is the same at every level of description. All differences between rfr_f, rcultr_{\mathrm{cult}} and rdomr_{\mathrm{dom}} then come from the degree-weighted concentration ss, that is, from the coexistence of disconnected domains with equal cultures (for rcult<rdomr_{\mathrm{cult}} < r_{\mathrm{dom}}) and from distinct cultures sharing a feature value (for rf<rcultr_f < r_{\mathrm{cult}}).

Complete graphs and unions of cliques

On a clique the structure of absorbing states is rigid, and the submartingales of § 3 translate into a statement about domain sizes.

Proposition 6.2. Let G=KnG = K_n with n≥2n \ge2 vertices, so that m=n(n−1)/2m = n(n-1)/2, and let σ∈A\sigma\in\mathcal{A} have kk domains D1,…,DkD_1,\ldots,D_k.

(i) k≤min⁡(q,n)k \le\min(q,n), the cultures of distinct domains are pairwise feature-disjoint, and Πdom=Πcult=Πf\Pi_{\mathrm{dom}} = \Pi_{\mathrm{cult}} = \Pi_f for every ff. If k≥2k \ge2, then rdom=−1/(n−1)r_{\mathrm{dom}} = -1/(n-1), whatever the domain sizes.

(ii) For the Axelrod process on KnK_n started from σ0\sigma_0,

E∑i∣Di(στ)∣2≥max⁡{max⁡fQf(σ0),Q(σ0)F+2F2Eτ}.\mathbb{E}\sum_i |D_i(\sigma_\tau)|^2 \ge\max\left\{\max_f Q_f(\sigma_0), \frac{Q(\sigma_0)}{F} + \frac{2}{F^2}\mathbb{E}\tau\right\}.

If GG is a disjoint union of cliques, part (i) applies to each component separately, and part (ii) applies to the process restricted to each component, with that component’s own absorption time.

Proof. (i) Every two domains are adjacent in KnK_n, so the quotient is KkK_k and Theorem 5.1 gives k≤qk \le q and pairwise feature-disjoint cultures. Hence the value of each feature determines the domain, and the three partitions coincide. For block sizes n1,…,nkn_1,\ldots,n_k and S=∑ini2/n2S = \sum_i n_i^2/n^2, the volumes are ni(n−1)n_i(n-1) and 2m=n(n−1)2m = n(n-1), so s=Ss = S, and ein=∑ini(ni−1)/(n(n−1))=(nS−1)/(n−1)e_{\mathrm{in}} = \sum_i n_i(n_i-1)/(n(n-1)) = (nS-1)/(n-1). Therefore r=((nS−1)/(n−1)−S)/(1−S)=−1/(n−1)r = ((nS-1)/(n-1)-S)/(1-S) = -1/(n-1).

(ii) By (i), at absorption the classes of every feature are the domains, so Qf(στ)=∑i∣Di∣2Q_f(\sigma_\tau) = \sum_i |D_i|^2 for every ff and Q(στ)=F∑i∣Di∣2Q(\sigma_\tau) = F\sum_i |D_i|^2. The bound follows from Corollary 3.5. For a disjoint union of cliques, the coordinates on different components evolve as independent Axelrod processes, because every transition involves an edge inside one component. The argument therefore applies to each component CC, with its own absorption time τC\tau_C; the absorption time of the whole process is max⁡CτC\max_C \tau_C. □

Part (i) shows that the assortativity coefficient carries no information on a clique: every non-trivial partition of KnK_n has the same value −1/(n−1)-1/(n-1). The orderings of Theorem 6.1 can therefore be strict only on connected graphs that are not complete. Part (ii) is a quantitative form of the tendency towards few large domains. The expected Simpson concentration ∑i∣Di∣2/n2\sum_i |D_i|^2/n^2 of the final domains is at least the largest initial feature concentration, and it exceeds the mean initial overlap by an amount proportional to the expected absorption time.

Exact checks and numerical illustration

Exhaustive enumeration and validation of the simulator

Corollary 5.4 can be checked directly on small graphs. For nine graphs on three to five vertices we enumerated all qFnq^{Fn} configurations, counted those in which every edge has overlap 0 or FF, and compared the count with ∑ΠP(G/Π;q)F\sum_{\Pi} P(G/\Pi;q)^F, computed by listing the connected partitions and counting the proper colourings of each quotient by brute force. The two numbers coincided in all 36 cases of Table 1. The column q=2q=2 shows the value 2n+F−12^{n+F-1} of Corollary 5.6, independent of the graph. A configuration that is absorbing on G+eG+e is absorbing on GG, so the count can only decrease when an edge is added; for q=3q=3 it falls from the two trees through C4C_4 and the paw to the diamond and K4K_4. The values for trees and cycles agree with the closed forms of Proposition 5.7.

Graphnn(F,q)=(2,2)(F,q)=(2,2)(2,3)(2,3)(3,2)(3,2)(3,3)(3,3)
K3K_331615332891
P4P_44321,1256419,683
K1,3K_{1,3}4321,1256419,683
C4C_4432693648,019
paw432765648,019
diamond432549644,131
K4K_4432477642,835
C5C_55643,24912860,507
bull5643,82512872,171

Table 1. Number of absorbing configurations ∣A∣|\mathcal{A}| on small graphs, obtained by exhaustive enumeration of all qFnq^{Fn} configurations; in every case the count equals ∑ΠP(G/Π;q)F\sum_{\Pi}P(G/\Pi;q)^F of Corollary 5.4. The paw is a triangle with a pendant edge, the diamond is K4K_4 minus an edge, and the bull is a triangle with two pendant edges at distinct vertices.

The simulator described below was validated against the generator (2) on K2K_2, P3P_3 and K3K_3 with F=3F=3. From a fixed non-absorbing configuration on each graph we sampled the first transition 2×1052\times10^5 times. The total variation distance between the empirical and exact distributions of the next configuration was 0.0020 at most, of the order of the sampling error, and the mean waiting times (2.994, 0.998, 0.749) matched the exact values 1/∑Act(oxy/F)1/\sum_{\mathrm{Act}}(o_{xy}/F) (3.000, 1.000, 0.750).

Simulations

The simulations below only illustrate the theorems. The process was simulated exactly with the Gillespie algorithm [9] restricted to active edges: an active edge is selected with probability proportional to oxy/Fo_{xy}/F, the total rate ∑Actoxy/F\sum_{\mathrm{Act}}o_{xy}/F sets the exponential waiting time, and the update follows (2). Initial cultures were independent and uniform on [q]F[q]^F. We used nine connected graphs (Table 2) generated or loaded with NetworkX [10]: the Florentine families [27], Zachary’s karate club [34], the Les Misérables co-appearance network [15], an Erdős–Rényi graph G(100,0.06)G(100,0.06), the ring lattice with k=6k=6 [33], a random 6-regular graph, a triangular lattice, a Holme–Kim graph with tunable clustering [13], and a connected caveman graph of ten 10-cliques [32]. For each graph and each (F,q)∈{(2,2),(3,6),(3,12)}(F,q) \in\{(2,2),(3,6),(3,12)\} we ran 40 independent realisations on the same fixed graph, 1080 runs in total; run j=0,…,39j=0,\ldots,39 used the seed 1000+j1000+j for both the initial configuration and the dynamics, and the random graphs were generated once with fixed seeds.

GraphnnmmΔ(G)\Delta(G)ω(G)\omega(G)transitivity
Florentine15203380.191
Karate3478453930.256
Les Misérables7725446714070.499
Erdős–Rényi1003123517610.056
Ring lattice1003003006000.600
Random 6-regular1003002914130.058
Triangular lattice992581606720.417
Holme–Kim10028916021770.181
Caveman10045011202500.931

Table 2. The nine graphs: order nn, size mm, number of triangles Δ(G)\Delta(G), open-wedge mass ω(G)\omega(G) and transitivity 3Δ(G)/∑x(dx2)3\Delta(G)/\sum_x \binom{d_x}{2}.

Table 3 and Table 4 summarise the absorbing configurations. In all 1080 runs no triangle carried exactly one boundary edge (Theorem 4.2), no triangle carried three boundary edges when q=2q=2 (Corollary 5.8), and the ordering rf≤rcult≤rdomr_f \le r_{\mathrm{cult}} \le r_{\mathrm{dom}} held for every feature (Theorem 6.1). In every absorbed configuration, moreover, adjacent blocks of the domain quotient carried different values of each feature ff. This is the constructive content of Theorem 5.1, each feature supplying a proper qq-colouring of the quotient, and it implies in particular that the clique number of the quotient never exceeded qq, as Table 3 confirms. With q=2q=2 the strict inequality rcult<rdomr_{\mathrm{cult}} < r_{\mathrm{dom}} is common, because disconnected domains often repeat a culture; with q=12q=12 cultures are rarely repeated and rcultr_{\mathrm{cult}} and rdomr_{\mathrm{dom}} coincide to two decimals, while rˉfeat\bar{r}_{\mathrm{feat}} is smaller on six of the nine graphs and equal to rcultr_{\mathrm{cult}} to two decimals on the Erdős–Rényi, random regular and Holme–Kim graphs. For q=2q=2, connectedness forces all cultures into a complementary pair {c,cˉ}\{c,\bar{c}\} (proof of Corollary 5.6), so Πf=Πcult\Pi_f=\Pi_{\mathrm{cult}} and rf=rcultr_f=r_{\mathrm{cult}}, as the table shows. On six of the nine graphs the ratio ω(GI)/ω(G)\omega(G_I)/\omega(G) decreases from (F,q)=(2,2)(F,q)=(2,2) to (3,12)(3,12) as the boundary grows; on the Erdős–Rényi, random regular and Holme–Kim graphs it is largest at (3,6)(3,6), where consensus is frequent. On the caveman graph, where 170 of the 250 open wedges use an edge joining two caves, it falls to 0.10 at q=12q=12. The mean absorption times lie below the bound of Corollary 3.3 by factors from about 9 to about 750.

Graph(F,q)(F,q)cons.domains∣∂∣/m|\partial|/mΔ2/Δ(G)\Delta_2/\Delta(G)Δ3/Δ(G)\Delta_3/\Delta(G)∑Δ1\sum\Delta_1ω(GI)ω(G)\frac{\omega(G_I)}{\omega(G)}clmax⁡\mathrm{cl}_{\max}
Florentine(2,2)(2,2)0.332.50.150.220.00000.732
(3,6)(3,6)0.005.80.440.500.10800.363
(3,12)(3,12)0.0010.40.750.530.37500.074
Karate(2,2)(2,2)0.283.40.170.250.00000.722
(3,6)(3,6)0.075.30.270.360.03400.574
(3,12)(3,12)0.0015.10.650.580.24800.135
Les Misérables(2,2)(2,2)0.385.90.140.190.00000.732
(3,6)(3,6)0.009.20.160.210.00600.703
(3,12)(3,12)0.0023.40.460.460.13600.348
Erdős–Rényi(2,2)(2,2)0.352.60.200.300.00000.672
(3,6)(3,6)0.332.10.040.050.00100.943
(3,12)(3,12)0.0010.80.370.420.08200.466
Ring lattice(2,2)(2,2)0.332.90.070.100.00000.872
(3,6)(3,6)0.0012.20.300.390.04200.534
(3,12)(3,12)0.0041.00.700.530.34500.114
Random 6-regular(2,2)(2,2)0.252.30.190.270.00000.692
(3,6)(3,6)0.601.60.020.030.00000.962
(3,12)(3,12)0.007.50.330.390.05800.516
Triangular lattice(2,2)(2,2)0.452.20.080.120.00000.852
(3,6)(3,6)0.056.10.170.230.01400.724
(3,12)(3,12)0.0033.60.610.530.25300.194
Holme–Kim(2,2)(2,2)0.234.80.220.340.00000.632
(3,6)(3,6)0.233.20.050.060.00200.923
(3,12)(3,12)0.0014.80.320.370.06500.525
Caveman(2,2)(2,2)0.284.00.090.130.00000.812
(3,6)(3,6)0.0016.10.370.450.06700.395
(3,12)(3,12)0.0038.00.710.520.35700.107

Table 3. Structure of absorbing configurations, averaged over 40 runs per row: share of runs ending in consensus, mean number of domains, boundary fraction ∣∂∣/m|\partial|/m, shares of triangles with two and with three boundary edges, total number of triangles with exactly one boundary edge over all 40 runs, mean ratio ω(GI)/ω(G)\omega(G_I)/\omega(G), and the largest clique number clmax⁡\mathrm{cl}_{\max} of the domain quotient G/ΠdomG/\Pi_{\mathrm{dom}} over the 40 runs.

Graph(F,q)(F,q)runsrˉfeat\bar r_{\mathrm{feat}}rcultr_{\mathrm{cult}}rdomr_{\mathrm{dom}}Eτ\mathbb{E}\taubound
Florentine(2, 2)270.170.170.2223.5212
(3, 6)400.140.180.1834.4789
(3, 12)400.020.070.0715.9866
Karate(2, 2)290.140.140.2026.21,122
(3, 6)370.160.180.1859.34,201
(3, 12)400.090.120.1241.14,622
Les Misérables(2, 2)250.270.270.3264.95,840
(3, 6)400.350.360.36105.621,948
(3, 12)400.190.210.2194.024,152
Erdős–Rényi(2, 2)260.170.170.1847.99,912
(3, 6)270.110.110.11150.437,123
(3, 12)400.170.170.17161.940,848
Ring lattice(2, 2)270.740.740.80169.49,912
(3, 6)400.480.530.54243.337,123
(3, 12)400.200.260.2678.540,848
Random 6-regular(2, 2)300.210.210.2246.29,912
(3, 6)160.130.130.13151.037,123
(3, 12)400.190.190.19178.840,848
Triangular lattice(2, 2)220.590.590.62106.49,713
(3, 6)380.470.480.48214.136,379
(3, 12)400.240.280.28177.540,030
Holme–Kim(2, 2)310.180.180.2254.49,912
(3, 6)310.150.150.15157.937,123
(3, 12)400.180.180.18172.540,848
Caveman(2, 2)290.670.670.74227.89,912
(3, 6)400.500.570.57150.837,123
(3, 12)400.200.260.2654.840,848

Table 4. Assortativity and absorption time. The coefficients are averaged over the non-consensus runs, whose number is given in the third column; rˉfeat\bar r_{\mathrm{feat}} is the mean of rfr_f over features. The last two columns give the mean absorption time and the mean of the bound F2(Fn2−Q(σ0))\frac{F}{2}(Fn^2-Q(\sigma_0)) of Corollary 3.3.

Figure 1 shows one absorbing configuration on the karate club with F=3F=3 and q=6q=6. It has seven domains but only four cultures: the large domain D1D_1 (24 vertices) shares its culture with the singletons D3D_3 and D4D_4, and D5D_5 shares its culture with D7D_7. Of the 78 edges, 23 are boundary edges. Of the 45 triangles, 24 are interior, 20 have two boundary edges and one, formed by D1D_1, D6D_6 and D7D_7, has three; it appears as the triangle of the quotient and is admissible because q≥3q\ge3. The three feature coefficients are 0.237, 0.237 and 0.246, while rcult=0.246r_{\mathrm{cult}}=0.246 and rdom=0.314r_{\mathrm{dom}}=0.314. The gap between rcultr_{\mathrm{cult}} and rdomr_{\mathrm{dom}} comes entirely from the repeated cultures, as Theorem 6.1(iii) requires. The open-wedge mass drops from ω(G)=393\omega(G)=393 to ω(GI)=223\omega(G_I)=223.

Figure 1. An absorbing configuration of the Axelrod model on the karate club with F=3F = 3, q=6q = 6. (a) Vertices are coloured by culture; solid edges are interior and dashed edges are boundary. (b) The domain quotient; node area is proportional to the number of vertices in the domain, colours are cultures, and edge labels count boundary edges. The weighted attribute assortativity of the quotient (self-loops weighted by interior edges) with respect to culture is 0.246, equal to rcultr_{\mathrm{cult}} for the configuration in (a).

To see how triadicity of the host graph shapes the absorbing states, we rewired ring lattices with n=200n = 200 and k=6k = 6 by the Watts–Strogatz procedure [33], using eight graph realisations (seeds 100, . . . , 107) and ten runs on each for every rewiring probability pp, with F=3F = 3 and q=12q = 12. As pp grows from 0 to 1 the transitivity falls from 0.60 to 0.02. Figure 2 reports the composition of the triangles, the three assortativity coefficients and the boundary and openness fractions. On the highly clustered lattices about seventy per cent of the edges are boundary edges and more than a third of the triangles have three boundary edges. As shortcuts destroy triangles and shorten paths, the boundary fraction falls below ten per cent, close to ninety per cent of the surviving triangles are interior, and ω(GI)/ω(G)\omega(G_I)/\omega(G) rises towards one. No triangle has exactly one boundary edge (Theorem 4.2). The assortativity coefficients rise and then fall, and the chain rf≤rcult≤rdomr_f \le r_{\mathrm{cult}} \le r_{\mathrm{dom}} is preserved throughout. We do not attempt to explain the location of the maximum, which presumably reflects the interplay between the number of domains and the concentration ss.

Figure 2. Absorbing configurations on Watts–Strogatz graphs (n=200n = 200, k=6k = 6, F=3F = 3, q=12q = 12; 80 runs per value of pp). (a) Shares of triangles with 0, 2 and 3 boundary edges; the share with exactly one boundary edge is identically zero. (b) Mean feature, culture and domain assortativity over non-consensus runs. (c) Boundary fraction and the ratio ω(GI)/ω(G)\omega(G_I)/\omega(G). Bands are 95% percentile intervals from a cluster bootstrap over the eight graph realisations (2000 resamples).

Discussion

The main result of the paper is a classification of the absorbing configurations of the Axelrod model on a finite graph. A partition into connected blocks is a domain partition exactly when its quotient is properly qq-colourable, the absorbing configurations with that domain partition are the homomorphisms from the quotient into KqFK_q^F, and their total number is a sum of chromatic polynomials over connected partitions (Theorem 5.1, Corollaries 5.4 and 5.6). The remaining results describe these configurations from the viewpoint of local graph structure. The interior graph is a disjoint union of induced subgraphs (Lemma 4.1), triangles never carry exactly one boundary edge (Theorem 4.2), and the assortativity coefficients at the levels of domains, cultures and features share a common interior fraction and are ordered (Theorem 6.1). On the dynamical side, the feature counts are martingales and the sums of their squares submartingales, with drift equal to 2/F2/F times the total overlap on active edges (Theorem 3.2), which gives an absorption-time bound of order F2n2F^{2}n^{2} and, on cliques, a lower bound on the concentration of final domain sizes.

Several questions remain open. The enumeration of Corollary 5.4 counts absorbing configurations but says nothing about the probability with which the dynamics select them; apart from the degenerate case of Proposition 3.7, describing the law of Πdom(στ)\Pi_{\mathrm{dom}}(\sigma_{\tau}) over the connected partitions, even for small graphs or for trees, is open. A second question concerns the dependence of the boundary fraction on the triadic structure of the host graph. Inequality (6) says that edges sitting in many triangles with high-overlap legs cannot be boundary edges at a given time, and Figure 2 suggests that this local protection alone does not decide the final boundary fraction, since the most clustered lattices freeze with the largest boundaries. A theorem relating E∣∂(στ)∣\mathbb{E}|\partial(\sigma_{\tau})| to the triangle multiplicities tet_e or to the open-wedge mass ω(G)\omega(G), even for restricted families such as circulant graphs, is lacking. A third question concerns the vertex-driven variant of the model, in which each vertex updates at rate one by consulting a uniformly chosen neighbour. There the degree-weighted counts ∑x:σf(x)=adx\sum_{x:\sigma_f(x)=a}d_x are martingales, as for the voter model, and the degree-weighted concentrations s(Πf)s(\Pi_f) in Theorem 6.1 would play the role that Qf/n2Q_f/n^2 plays here. A fourth concerns higher-order interactions: replacing pairwise edges by hyperedges along which cultures are compared would lead to analogues of the operators of [3] for hypergraphs. Finally, none of the present arguments addresses the infinite-volume questions of clustering versus fixation, which for graphs with triangles, such as the triangular lattice, remain open, as far as we know.

Data and code availability

All computations in § 7 use public or synthetic graphs. The code that produces the simulations, the exhaustive enumeration, the tables and the figures, together with the numerical outputs, is available at https://github.com/mboudour/axelrod-absorbing-states.

Declarations

Funding. This work received no specific grant from any funding agency, commercial or not-for-profit sectors.

Competing interests. The author declares no competing interests.

Use of generative AI. During the preparation of this work the author used Chat-GPT (OpenAI) to assist with language editing, the correction of grammatical errors, and with checking bibliographic details. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the content of the published article.

References

School of Professional Studies, Northwestern University, Evanston, IL 60208, USA

Email address: [email protected]

References

  1. [1]Robert Axelrod, The dissemination of culture: A model with local convergence and global polarization, Journal of Conflict Resolution 41 (1997), no. 2, 203–226.
  2. [2]George D. Birkhoff, A determinant formula for the number of ways of coloring a map, Annals of Mathematics 14 (1912), no. 1/4, 42–46.DOI
  3. [3]Moses Boudourides, Two-path operators, triadic decompositions, and majorized quotients for ego-centered network compression, Journal of Complex Networks 14 (2026), no. 3, cnag022.
  4. [4]———, Interior–boundary assortativity profiles on networks and applications to SIS epidemic dynamics, Discrete and Continuous Dynamical Systems – B 43 (2027), 104223, Published online 19 October 2026.DOI
  5. [5]Claudio Castellano, Santo Fortunato, and Vittorio Loreto, Statistical physics of social dynamics, Reviews of Modern Physics 81 (2009), no. 2, 591–646.DOI
  6. [6]Claudio Castellano, Matteo Marsili, and Alessandro Vespignani, Nonequilibrium phase transition in a model for social influence, Physical Review Letters 85 (2000), no. 16, 3536–3539.DOI
  7. [7]Fengming Dong, Khee Meng Koh, and Kee L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific, Singapore, 2005.
  8. [8]Andreas Flache, Michael Mä s, Thomas Feliciani, Edmund Chattoe-Brown, Guillaume Deffuant, Sylvie Huet, and Jan Lorenz, Models of social influence: Towards the next frontiers, Journal of Artificial Societies and Social Simulation 20 (2017), no. 4, 2.DOI
  9. [9]Daniel T. Gillespie, Exact stochastic simulation of coupled chemical reactions, The Journal of Physical Chemistry 81 (1977), no. 25, 2340–2361.DOI
  10. [10]Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart, Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy 2008), 2008, pp. 11–15.
  11. [11]Mela Hardin and Nicolas Lanchier, Probability of consensus in spatial opinion models with confidence threshold, ALEA Latin American Journal of Probability and Mathematical Statistics 19 (2022), 417–437.arxiv.org/abs/1912.06746
  12. [12]Pavol Hell and Jaroslav Nešetřil, Graphs and homomorphisms, Oxford University Press, Oxford, 2004.
  13. [13]Petter Holme and Beom Jun Kim, Growing scale-free networks with tunable clustering, Physical Review E 65 (2002), 026107.pubmed.ncbi.nlm.nih.gov/11863587
  14. [14]Konstantin Klemm, Víctor M. Eguíluz, Raúl Toral, and Maxi San Miguel, Nonequilibrium transitions in complex networks: A model of social interaction, Physical Review E 67 (2003), 026120.pubmed.ncbi.nlm.nih.gov/12636761
  15. [15]Donald E. Knuth, The Stanford GraphBase: A platform for combinatorial computing, Addison-Wesley, Reading, MA, 1993.DOI
  16. [16]Nicolas Lanchier, Opinion dynamics with confidence threshold: An alternative to the Axelrod model, ALEA Latin American Journal of Probability and Mathematical Statistics 7 (2010), 1–18.arxiv.org/abs/1003.0115
  17. [17]———, The Axelrod model for the dissemination of culture revisited, The Annals of Applied Probability 22 (2012), no. 2, 860–880.DOI
  18. [18]Nicolas Lanchier and Hsin-Lun Li, Probability of consensus in the multivariate Deffuant model on finite connected graphs, Electronic Communications in Probability 25 (2020), Paper No. 79, 1–12.arxiv.org/abs/2005.13141
  19. [19]Nicolas Lanchier and Paul-Henri Moisson, Fixation results for the two-feature Axelrod model with a variable number of opinions, Journal of Theoretical Probability 29 (2016), no. 4, 1554–1580.arxiv.org/abs/1407.6289
  20. [20]Nicolas Lanchier and Stylianos Scarlatos, Fixation in the one-dimensional Axelrod model, The Annals of Applied Probability 23 (2013), no. 6, 2538–2559.DOI
  21. [21]______, Limiting behavior for a general class of voter models with confidence threshold, ALEA Latin American Journal of Probability and Mathematical Statistics 14 (2017), 63–92.arxiv.org/abs/1412.4142
  22. [22]Nicolas Lanchier and Jason Schweinsberg, Consensus in the two-state Axelrod model, Stochastic Processes and their Applications 122 (2012), no. 11, 3701–3717.arxiv.org/abs/1107.4413
  23. [23]Hsin-Lun Li, Consensus and stability in opinion-based binary opinion dynamics on social graphs, Physica A: Statistical Mechanics and its Applications 676 (2025), 130868.DOI
  24. [24]Junchi Li, Axelrod’s model in two dimensions, Ph.D. thesis, Duke University, 2014.
  25. [25]Thomas M. Liggett, Interacting particle systems, Springer, New York, 1985.
  26. [26]Mark E. J. Newman, Mixing patterns in networks, Physical Review E 67 (2003), 026126.
  27. [27]John F. Padgett and Christopher K. Ansell, Robust action and the rise of the Medici, 1400–1434, American Journal of Sociology 98 (1993), no. 6, 1259–1319.DOI
  28. [28]Alan D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in Combinatorics 2005 (Bridget S. Webb, ed.), London Mathematical Society Lecture Note Series, vol. 327, Cambridge University Press, Cambridge, 2005, pp. 173–226.DOI
  29. [29]Federico Vázquez, Paul L. Krapivsky, and Sidney Redner, Constrained opinion dynamics: Freezing and slow evolution, Journal of Physics A: Mathematical and General 36 (2003), no. 3, L61–L68.DOI
  30. [30]Federico Vázquez and Sidney Redner, Ultimate fate of constrained voters, Journal of Physics A: Mathematical and General 37 (2004), no. 35, 8479–8494.DOI
  31. [31]Daniele Vilone, Alessandro Vespignani, and Claudio Castellano, Ordering phase transition in the one-dimensional Axelrod model, The European Physical Journal B 30 (2002), 399–406.DOI
  32. [32]Duncan J. Watts, Small worlds: The dynamics of networks between order and randomness, Princeton University Press, Princeton, 1999.
  33. [33]Duncan J. Watts and Steven H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), no. 6684, 440–442.
  34. [34]Wayne W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33 (1977), no. 4, 452–473.DOI

Paper details

vlnc:W_g6xh5f9z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Chat-GPT (OpenAI)

View statement
Looking for related papers…
Contents