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 -colourable. The configurations with a given domain partition correspond to homomorphisms from the quotient into the -fold categorical power of , so their total number is a sum of chromatic polynomials over connected partitions; this gives closed forms for trees and cycles and the value for 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 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 features, each taking one of 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 is closely related to the constrained voter model [29, 30].
Rigorous results are fewer. Lanchier [17] proved that the one-dimensional system with clusters and that it fixates in a fragmented configuration when is sufficiently large relative to ; Lanchier and Schweinsberg [22] extended clustering to and arbitrary ; Lanchier and Scarlato [20] proved fixation for with and for , ; 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 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 -colouring, and the absorbing configurations with a given domain partition are in bijection with graph homomorphisms from the quotient into the -fold categorical power of the complete graph . Counting them gives the number of absorbing configurations as a sum of chromatic polynomials raised to the power (Corollary 5.4). The term of this sum for the partition into singletons is the number of proper -colourings of , that is, of zero-temperature ground states of the antiferromagnetic -state Potts model on [28], raised to the power ; 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 . 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 . 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 , 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 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 is times the total overlap on active edges. The second fact yields the explicit bound on the absorption time, where is the total pairwise overlap; this gives a quantitative version of almost sure absorption, whose order in 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 , and a bound on the number of domains in terms of . § 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 be a finite simple graph with vertices and edges. Unless stated otherwise is connected, so every vertex has positive degree . Write for the adjacency matrix and when . Fix integers and , and let . A configuration is a map ; we write for the -th feature of the culture . The overlap of two vertices is
and is the Hamming distance between and . Since the Hamming distance is a metric on ,
We use the continuous-time formulation of [17]. Each edge is activated at rate one; one of its endpoints, say , is chosen with probability ; with probability the vertex then copies the value of a feature chosen uniformly among the features on which and disagree, and nothing happens otherwise. Let denote the configuration obtained from by setting . The process is the continuous-time Markov chain on with generator
where for $0\le o<F$; when the inner sum is empty. The rate is symmetric in and $y, and this symmetry is behind the conservation laws of § 3.
An edge is interior if , boundary if , and active otherwise. We write , and for the three classes, so that , and , for the adjacency matrices of the spanning subgraphs and . The total transition rate out of equals , because an active edge with overlap produces a change with probability per activation. Hence is absorbing if and only if , that is, if and only if every edge is interior or boundary. Let denote the set of absorbing configurations and the absorption time.
The cultural domains of are the connected components of ; this is the notion used in [17]. They form a partition of . We also use the partition of into classes of vertices with the same culture, and, for each feature , the partition into classes of vertices with the same value of feature . Since is constant along interior edges, refines , and refines every . Finally, for a configuration let be the number of vertices holding value in feature .
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 and every function , the process is a martingale. In particular each is a martingale and .
Proof. Let . A transition with leaves unchanged. For an edge with , the two transitions and in feature occur at the same rate and change by and respectively. Their contributions to (2) cancel, so . On a finite state space this makes a martingale. The process is bounded and almost surely (Corollary 3.3 below, or [17 Lemma 6]), so optional stopping gives the last identity.
Next consider, for each feature , the quantity
where the sums run over ordered pairs, diagonal included. Thus is the total pairwise overlap of the population, taken over all pairs and not only over edges, and is the Simpson concentration of feature . We call 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 ,
Consequently each and is a bounded submartingale, and
Proof. Suppose and copies feature from . Then decreases by one and increases by one, so changes by . The reverse transition, in which copies from , changes by . Both occur at rate , so the edge contributes to . Summing over edges that disagree in gives the first formula; the terms with vanish. Summing over , an active edge disagrees in exactly features, so it contributes to , while boundary and interior edges contribute nothing. For the identity, Dynkin’s formula for the bounded stopping time gives . As , the left side converges by bounded convergence, since almost surely by Corollary 3.3, whose proof uses only this display for finite , and the right side converges by monotone convergence. □
Corollary 3.3. For every initial configuration ,
In particular the process is absorbed almost surely.
Proof. If , at least one edge is active and its overlap is at least one, so by (3). Dynkin’s formula for therefore gives , because . Letting and using monotone convergence yields the first inequality. The second follows from , 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 , uniform over all graphs on vertices. The argument is the familiar quadratic-Lyapunov argument for voter-type models, with the homophily factor 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 is nevertheless attained on paths.
Corollary 3.5. for every , and .
Proof. The first statement is the submartingale property with optional stopping. The second follows from (4) together with before absorption. □
In words, the Simpson concentration of every feature can only increase in expectation, and the total overlap gains at least per unit of time spent before absorption. § 6.1 turns this into a statement about domain sizes on complete graphs.
The order in Corollary 3.3 cannot be improved in general, while the factor can.
Proposition 3.6. (i) On the path with vertices , let equal a culture on and a culture on , where and *differ in exactly
one feature. Then ; in particular . (ii) On started from overlap , , where ; the largest value is , of order .
Proof. (i) At every time before absorption the configuration consists of two blocks of cultures and , and the only active edge is the one joining them, with overlap . It fires at rate , and each firing moves the interface one step to the left or to the right with probability . The position of the interface is therefore a simple random walk run at rate and absorbed at and , and the expected number of steps from is . (ii) The overlap of the two vertices never decreases; from overlap it waits an exponential time with rate and then increases by one. Summing the expected waiting times gives the formula.
When some feature is initially shared by everybody, the law of the final state is determined exactly.
Proposition 3.7. Let be connected, and suppose that some feature is constant in . Then is a consensus almost surely, and for every feature and value .
Proof. A copy reproduces a value already present at the same feature, so 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 , and Proposition 3.1 gives the law.
Without such a shared feature the probability of reaching a particular domain partition is not determined by the martingales alone. On , for instance, the final state has two domains if and only if , an event of probability under uniform initial cultures.
Triadic structure of absorbing configurations
Throughout this section is absorbing, so and .
Lemma 4.1. Let be a domain of . Then is constant on , and every edge of with both endpoints in is interior. Hence is the disjoint union of the induced subgraphs , , and is the set of edges joining distinct domains.
Proof. The culture is constant along interior edges and is connected in , so is constant on . If and , then and the edge is interior. An edge joining two distinct domains cannot be interior, since its endpoints would lie in the same component of ; 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 denote the number of triangles through the edge , and let denote the Hadamard product.
Theorem 4.2. Let . Then
Equivalently, every triangle of contains , or 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 .
Proof. The entry counts the vertices with and . For such the vertices lie in one domain, and Lemma 4.1 forces , a contradiction. Likewise counts with , and ; then lie in one domain and , 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 in which 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 according to the number of boundary edges of the triangle, an interior edge has and a boundary edge has . The identities (5) are the absorbing case of a constraint that holds at all times. By (1), for every edge with ,
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 is never a boundary edge.
A wedge of a graph 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 of a graph with triangles (here never denotes the maximum degree) is the number of open wedges of , each counted once at its middle vertex, and that exactly when is a disjoint union of cliques.
Corollary 4.3. Let . Then and
In particular if and only if every open wedge of has both legs interior. Likewise , where is the number of triangles with exactly boundary edges.
Proof. The first identity holds because is the disjoint union of the induced subgraphs (Lemma 4.1). A wedge of is a wedge of with both legs interior; its three vertices lie in one domain, so by Lemma 4.1 the pair is an edge of if and only if it is an edge of . The wedge is therefore open in $G_I exactly when it is open in . Hence the open wedges of are the open wedges of 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 . □
Domain quotients and colourability
For a partition of into blocks inducing connected subgraphs (a connected partition), let denote the simple quotient graph whose vertices are the blocks, two blocks being adjacent when some edge of joins them. Write for the chromatic number of a graph and for its chromatic polynomial, the number of proper colourings of with colours [2, 7].
Theorem 5.1. A connected partition of is the domain partition of some absorbing configuration if and only if . More precisely, the absorbing configurations with domain partition are in bijection with -tuples of proper -colourings of ; there are of them.
Proof. Let with . By Lemma 4.1, is constant on blocks, and every edge between distinct blocks is a boundary edge. Hence for each the map sending a block to the common value of on it is a proper -colouring of , and is recovered from . Conversely, let be proper -colourings of and set for in block . Edges inside a block have overlap . An edge between adjacent blocks has overlap , because for every . So 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 -colouring exists if and only if , and its repetition in all features gives existence. □
Remark 5.2. Theorem 5.1 has a compact formulation in terms of graph homomorphisms [12]. Let denote the -fold categorical (tensor) power of : its vertices are the cultures , and two cultures are adjacent when they differ in every feature. A proper -colouring of a graph is a homomorphism , so that , 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 are exactly the maps that are constant on blocks and induce a homomorphism , and that their number is . For the part of the section, singletons, and the absorbing configurations in which every edge is a boundary edge are the homomorphisms ; they exist if and only if . With this recovers the observation of Li [23] that “alternating” absorbing states of binary imitation dynamics exist exactly on bipartite graphs, and, when , the count is the number of zero-temperature ground states of the antiferromagnetic -state Potts model on [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 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 studied in [21, 11], where are compatible when . A configuration is then absorbing if and only if every edge joins equal or incompatible opinions. Let be the incompatibility graph on , in which are adjacent when . The proof of Theorem 5.1 then shows, word for word, that the absorbing configurations with domain partition correspond to homomorphisms , and that there are absorbing configurations in all. For the Axelrod model, is the Hamming graph on , , and . For opinions in with a confidence threshold , 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 is
the sum running over all connected partitions of ; the terms with vanish.
Example 5.5. For there are two connected partitions, with quotients and , so . 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 be connected and . Then , and exactly connected partitions of have a bipartite quotient.
Proof. When , each culture has a unique feature-disjoint partner, its complement . A configuration is therefore absorbing if and only if every edge joins equal or complementary cultures. Fix a vertex . For each culture and each set , the configuration equal to on and to elsewhere is absorbing, and every absorbing configuration arises in this way from exactly one pair , because connectedness forces every culture to lie in . This gives configurations. On the other hand, a connected bipartite graph has exactly two proper -colourings, so each connected partition with bipartite quotient contributes to the sum in Corollary 5.4, and the other partitions contribute nothing. Comparing the two counts gives the second statement.
Since factorises over connected components, a graph with components has absorbing configurations when .
The whole count can also be written as a single homomorphism number, which gives closed forms for trees and cycles. Let be the graph of Remark 5.2 with a loop added at every vertex; its adjacency matrix is , where is the all-ones matrix.
Proposition 5.7. For every graph , . Consequently, for a tree on vertices and for the cycle ,
Proof. A configuration is absorbing exactly when each edge joins equal cultures, which corresponds to a loop of , or feature-disjoint cultures, which corresponds to an edge of ; 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 ways; each further vertex, taken in breadth-first order, either copies its parent’s culture or takes one of the cultures feature-disjoint from it. For the cycle, . The matrix has eigenvalues (once) and ( times), and eigenvalues of Kronecker products are products of eigenvalues. Hence has eigenvalue with multiplicity , for . □
With the first identity reduces to the classical , since every configuration of a one-feature model is absorbing. In the opposite direction, the proportion of absorbing configurations tends to one as grows. Indeed , and every other connected partition has at most blocks and contributes , so that for
This is the finite-graph counterpart of the fragmentation observed for large [6, 17]: almost every configuration is already frozen.
Corollary 5.8. Let .
Every clique of meets at most domains.
If , the quotient is bipartite. In particular it has no triangles, and every triangle of has 0 or 2 boundary edges.
(Here need not be connected.) If is a disjoint union of cliques, equivalently , each component of carries at most domains, and their cultures are pairwise feature-disjoint.
Proof. The vertices of a clique lying in distinct domains give pairwise adjacent blocks of , so 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 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 domains and at least 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 is obtained from by contracting the edges of spanning trees of the domains (and deleting loops and parallel edges), so by Theorem 5.1. Each domain is connected in , hence . □
For the bound reads and is attained; in general it is informative only when .
Remark 5.10. The domain quotient is the natural setting for the contraction inequality of [3 Theorem 10.6]. With the directed edge-sum quotient matrix of and the aggregated two-walk matrix, counts interior edge-ends, the off-diagonal entries count boundary edges, and entrywise, with an explicit overcount. Theorem 5.1 adds that the cultures of -adjacent blocks are feature-disjoint. A closer study of and in absorbing states, for instance through the wedge-equitability of , is left for future work.
Assortativity of absorbing configurations
Let be a partition of . Following Newman [26], let be the fraction of edges with both endpoints in the same block, let with , and, when , let
be the attribute assortativity coefficient of the labelling of vertices by blocks. In the language of [4], is the interior share of the edge set relative to and its boundary share; the coefficient compares the interior share with its value under degree-preserving mixing. For an absorbing configuration we abbreviate , and , and we write for the interior fraction.
Theorem 6.1. Let be connected and let not be a consensus. Then:
(i) for every ;
(ii) for every ;
(iii) for every . Equality holds if and only if no two domains carry the same culture, and if and only if ;
(iv) if has blocks, then , with equality if and only if the blocks have equal volume; in particular .
Proof. (i) Since refines and refines , 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 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 . Hence all three partitions have the interior edges as their internal edges. Because is not a consensus and is connected, , so and .
(ii) Each block has positive volume because is connected and . Merging two blocks with volumes replaces by , so strictly increases under every proper coarsening. Moreover has at least two blocks, since the
(iii) By (i) the three coefficients have the form with a common , and on . Combining with (ii) gives the chain. Since is strictly decreasing and strictly increases under proper coarsening, equality holds exactly when the two partitions coincide. Now means that distinct domains carry distinct cultures.
(iv) By the Cauchy–Schwarz inequality, , and is decreasing, so . The right side is increasing in , its derivative @bibliography being , and has at most blocks. Equality in , and hence in the bound for , holds exactly when all blocks have volume . □
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 , and then come from the degree-weighted concentration , that is, from the coexistence of disconnected domains with equal cultures (for ) and from distinct cultures sharing a feature value (for ).
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 with vertices, so that , and let have domains .
(i) , the cultures of distinct domains are pairwise feature-disjoint, and for every . If , then , whatever the domain sizes.
(ii) For the Axelrod process on started from ,
If 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 , so the quotient is and Theorem 5.1 gives and pairwise feature-disjoint cultures. Hence the value of each feature determines the domain, and the three partitions coincide. For block sizes and , the volumes are and , so , and . Therefore .
(ii) By (i), at absorption the classes of every feature are the domains, so for every and . 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 , with its own absorption time ; the absorption time of the whole process is . □
Part (i) shows that the assortativity coefficient carries no information on a clique: every non-trivial partition of has the same value . 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 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 configurations, counted those in which every edge has overlap 0 or , and compared the count with , 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 shows the value of Corollary 5.6, independent of the graph. A configuration that is absorbing on is absorbing on , so the count can only decrease when an edge is added; for it falls from the two trees through and the paw to the diamond and . The values for trees and cycles agree with the closed forms of Proposition 5.7.
| Graph | |||||
| 3 | 16 | 153 | 32 | 891 | |
| 4 | 32 | 1,125 | 64 | 19,683 | |
| 4 | 32 | 1,125 | 64 | 19,683 | |
| 4 | 32 | 693 | 64 | 8,019 | |
| paw | 4 | 32 | 765 | 64 | 8,019 |
| diamond | 4 | 32 | 549 | 64 | 4,131 |
| 4 | 32 | 477 | 64 | 2,835 | |
| 5 | 64 | 3,249 | 128 | 60,507 | |
| bull | 5 | 64 | 3,825 | 128 | 72,171 |
Table 1. Number of absorbing configurations on small graphs, obtained by exhaustive enumeration of all configurations; in every case the count equals of Corollary 5.4. The paw is a triangle with a pendant edge, the diamond is 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 , and with . From a fixed non-absorbing configuration on each graph we sampled the first transition 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 (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 , the total rate sets the exponential waiting time, and the update follows (2). Initial cultures were independent and uniform on . 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 , the ring lattice with [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 we ran 40 independent realisations on the same fixed graph, 1080 runs in total; run used the seed for both the initial configuration and the dynamics, and the random graphs were generated once with fixed seeds.
| Graph | transitivity | ||||
| Florentine | 15 | 20 | 3 | 38 | 0.191 |
| Karate | 34 | 78 | 45 | 393 | 0.256 |
| Les Misérables | 77 | 254 | 467 | 1407 | 0.499 |
| Erdős–Rényi | 100 | 312 | 35 | 1761 | 0.056 |
| Ring lattice | 100 | 300 | 300 | 600 | 0.600 |
| Random 6-regular | 100 | 300 | 29 | 1413 | 0.058 |
| Triangular lattice | 99 | 258 | 160 | 672 | 0.417 |
| Holme–Kim | 100 | 289 | 160 | 2177 | 0.181 |
| Caveman | 100 | 450 | 1120 | 250 | 0.931 |
Table 2. The nine graphs: order , size , number of triangles , open-wedge mass and transitivity .
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 (Corollary 5.8), and the ordering held for every feature (Theorem 6.1). In every absorbed configuration, moreover, adjacent blocks of the domain quotient carried different values of each feature . This is the constructive content of Theorem 5.1, each feature supplying a proper -colouring of the quotient, and it implies in particular that the clique number of the quotient never exceeded , as Table 3 confirms. With the strict inequality is common, because disconnected domains often repeat a culture; with cultures are rarely repeated and and coincide to two decimals, while is smaller on six of the nine graphs and equal to to two decimals on the Erdős–Rényi, random regular and Holme–Kim graphs. For , connectedness forces all cultures into a complementary pair (proof of Corollary 5.6), so and , as the table shows. On six of the nine graphs the ratio decreases from to as the boundary grows; on the Erdős–Rényi, random regular and Holme–Kim graphs it is largest at , 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 . The mean absorption times lie below the bound of Corollary 3.3 by factors from about 9 to about 750.
| Graph | cons. | domains | |||||||
| Florentine | 0.33 | 2.5 | 0.15 | 0.22 | 0.000 | 0 | 0.73 | 2 | |
| 0.00 | 5.8 | 0.44 | 0.50 | 0.108 | 0 | 0.36 | 3 | ||
| 0.00 | 10.4 | 0.75 | 0.53 | 0.375 | 0 | 0.07 | 4 | ||
| Karate | 0.28 | 3.4 | 0.17 | 0.25 | 0.000 | 0 | 0.72 | 2 | |
| 0.07 | 5.3 | 0.27 | 0.36 | 0.034 | 0 | 0.57 | 4 | ||
| 0.00 | 15.1 | 0.65 | 0.58 | 0.248 | 0 | 0.13 | 5 | ||
| Les Misérables | 0.38 | 5.9 | 0.14 | 0.19 | 0.000 | 0 | 0.73 | 2 | |
| 0.00 | 9.2 | 0.16 | 0.21 | 0.006 | 0 | 0.70 | 3 | ||
| 0.00 | 23.4 | 0.46 | 0.46 | 0.136 | 0 | 0.34 | 8 | ||
| Erdős–Rényi | 0.35 | 2.6 | 0.20 | 0.30 | 0.000 | 0 | 0.67 | 2 | |
| 0.33 | 2.1 | 0.04 | 0.05 | 0.001 | 0 | 0.94 | 3 | ||
| 0.00 | 10.8 | 0.37 | 0.42 | 0.082 | 0 | 0.46 | 6 | ||
| Ring lattice | 0.33 | 2.9 | 0.07 | 0.10 | 0.000 | 0 | 0.87 | 2 | |
| 0.00 | 12.2 | 0.30 | 0.39 | 0.042 | 0 | 0.53 | 4 | ||
| 0.00 | 41.0 | 0.70 | 0.53 | 0.345 | 0 | 0.11 | 4 | ||
| Random 6-regular | 0.25 | 2.3 | 0.19 | 0.27 | 0.000 | 0 | 0.69 | 2 | |
| 0.60 | 1.6 | 0.02 | 0.03 | 0.000 | 0 | 0.96 | 2 | ||
| 0.00 | 7.5 | 0.33 | 0.39 | 0.058 | 0 | 0.51 | 6 | ||
| Triangular lattice | 0.45 | 2.2 | 0.08 | 0.12 | 0.000 | 0 | 0.85 | 2 | |
| 0.05 | 6.1 | 0.17 | 0.23 | 0.014 | 0 | 0.72 | 4 | ||
| 0.00 | 33.6 | 0.61 | 0.53 | 0.253 | 0 | 0.19 | 4 | ||
| Holme–Kim | 0.23 | 4.8 | 0.22 | 0.34 | 0.000 | 0 | 0.63 | 2 | |
| 0.23 | 3.2 | 0.05 | 0.06 | 0.002 | 0 | 0.92 | 3 | ||
| 0.00 | 14.8 | 0.32 | 0.37 | 0.065 | 0 | 0.52 | 5 | ||
| Caveman | 0.28 | 4.0 | 0.09 | 0.13 | 0.000 | 0 | 0.81 | 2 | |
| 0.00 | 16.1 | 0.37 | 0.45 | 0.067 | 0 | 0.39 | 5 | ||
| 0.00 | 38.0 | 0.71 | 0.52 | 0.357 | 0 | 0.10 | 7 |
Table 3. Structure of absorbing configurations, averaged over 40 runs per row: share of runs ending in consensus, mean number of domains, boundary fraction , 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 , and the largest clique number of the domain quotient over the 40 runs.
| Graph | runs | bound | |||||
| Florentine | (2, 2) | 27 | 0.17 | 0.17 | 0.22 | 23.5 | 212 |
| (3, 6) | 40 | 0.14 | 0.18 | 0.18 | 34.4 | 789 | |
| (3, 12) | 40 | 0.02 | 0.07 | 0.07 | 15.9 | 866 | |
| Karate | (2, 2) | 29 | 0.14 | 0.14 | 0.20 | 26.2 | 1,122 |
| (3, 6) | 37 | 0.16 | 0.18 | 0.18 | 59.3 | 4,201 | |
| (3, 12) | 40 | 0.09 | 0.12 | 0.12 | 41.1 | 4,622 | |
| Les Misérables | (2, 2) | 25 | 0.27 | 0.27 | 0.32 | 64.9 | 5,840 |
| (3, 6) | 40 | 0.35 | 0.36 | 0.36 | 105.6 | 21,948 | |
| (3, 12) | 40 | 0.19 | 0.21 | 0.21 | 94.0 | 24,152 | |
| Erdős–Rényi | (2, 2) | 26 | 0.17 | 0.17 | 0.18 | 47.9 | 9,912 |
| (3, 6) | 27 | 0.11 | 0.11 | 0.11 | 150.4 | 37,123 | |
| (3, 12) | 40 | 0.17 | 0.17 | 0.17 | 161.9 | 40,848 | |
| Ring lattice | (2, 2) | 27 | 0.74 | 0.74 | 0.80 | 169.4 | 9,912 |
| (3, 6) | 40 | 0.48 | 0.53 | 0.54 | 243.3 | 37,123 | |
| (3, 12) | 40 | 0.20 | 0.26 | 0.26 | 78.5 | 40,848 | |
| Random 6-regular | (2, 2) | 30 | 0.21 | 0.21 | 0.22 | 46.2 | 9,912 |
| (3, 6) | 16 | 0.13 | 0.13 | 0.13 | 151.0 | 37,123 | |
| (3, 12) | 40 | 0.19 | 0.19 | 0.19 | 178.8 | 40,848 | |
| Triangular lattice | (2, 2) | 22 | 0.59 | 0.59 | 0.62 | 106.4 | 9,713 |
| (3, 6) | 38 | 0.47 | 0.48 | 0.48 | 214.1 | 36,379 | |
| (3, 12) | 40 | 0.24 | 0.28 | 0.28 | 177.5 | 40,030 | |
| Holme–Kim | (2, 2) | 31 | 0.18 | 0.18 | 0.22 | 54.4 | 9,912 |
| (3, 6) | 31 | 0.15 | 0.15 | 0.15 | 157.9 | 37,123 | |
| (3, 12) | 40 | 0.18 | 0.18 | 0.18 | 172.5 | 40,848 | |
| Caveman | (2, 2) | 29 | 0.67 | 0.67 | 0.74 | 227.8 | 9,912 |
| (3, 6) | 40 | 0.50 | 0.57 | 0.57 | 150.8 | 37,123 | |
| (3, 12) | 40 | 0.20 | 0.26 | 0.26 | 54.8 | 40,848 |
Table 4. Assortativity and absorption time. The coefficients are averaged over the non-consensus runs, whose number is given in the third column; is the mean of over features. The last two columns give the mean absorption time and the mean of the bound of Corollary 3.3.
Figure 1 shows one absorbing configuration on the karate club with and . It has seven domains but only four cultures: the large domain (24 vertices) shares its culture with the singletons and , and shares its culture with . Of the 78 edges, 23 are boundary edges. Of the 45 triangles, 24 are interior, 20 have two boundary edges and one, formed by , and , has three; it appears as the triangle of the quotient and is admissible because . The three feature coefficients are 0.237, 0.237 and 0.246, while and . The gap between and comes entirely from the repeated cultures, as Theorem 6.1(iii) requires. The open-wedge mass drops from to .
Figure 1. An absorbing configuration of the Axelrod model on the karate club with , . (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 for the configuration in (a).
To see how triadicity of the host graph shapes the absorbing states, we rewired ring lattices with and by the Watts–Strogatz procedure [33], using eight graph realisations (seeds 100, . . . , 107) and ten runs on each for every rewiring probability , with and . As 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 rises towards one. No triangle has exactly one boundary edge (Theorem 4.2). The assortativity coefficients rise and then fall, and the chain 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 .
Figure 2. Absorbing configurations on Watts–Strogatz graphs (, , , ; 80 runs per value of ). (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 . 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 -colourable, the absorbing configurations with that domain partition are the homomorphisms from the quotient into , 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 times the total overlap on active edges (Theorem 3.2), which gives an absorption-time bound of order 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 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 to the triangle multiplicities or to the open-wedge mass , 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 are martingales, as for the voter model, and the degree-weighted concentrations in Theorem 6.1 would play the role that 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]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]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]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]———, 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]Claudio Castellano, Santo Fortunato, and Vittorio Loreto, Statistical physics of social dynamics, Reviews of Modern Physics 81 (2009), no. 2, 591–646.DOI
- [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]Fengming Dong, Khee Meng Koh, and Kee L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific, Singapore, 2005.
- [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]Daniel T. Gillespie, Exact stochastic simulation of coupled chemical reactions, The Journal of Physical Chemistry 81 (1977), no. 25, 2340–2361.DOI
- [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]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]Pavol Hell and Jaroslav Nešetřil, Graphs and homomorphisms, Oxford University Press, Oxford, 2004.
- [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]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]Donald E. Knuth, The Stanford GraphBase: A platform for combinatorial computing, Addison-Wesley, Reading, MA, 1993.DOI
- [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]———, The Axelrod model for the dissemination of culture revisited, The Annals of Applied Probability 22 (2012), no. 2, 860–880.DOI
- [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]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]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]______, 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]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]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]Junchi Li, Axelrod’s model in two dimensions, Ph.D. thesis, Duke University, 2014.
- [25]Thomas M. Liggett, Interacting particle systems, Springer, New York, 1985.
- [26]Mark E. J. Newman, Mixing patterns in networks, Physical Review E 67 (2003), 026126.
- [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]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]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]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]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]Duncan J. Watts, Small worlds: The dynamics of networks between order and randomness, Princeton University Press, Princeton, 1999.
- [33]Duncan J. Watts and Steven H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), no. 6684, 440–442.
- [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

