Physical Review Letters 67 (13) 1803 , Sept. 23, 1991 ENTROPIC PREDICTIONS FOR CELLULAR NETWORKS Michael A. Peshkin Northwestern University, Evanston IL, 60208 Katherine J. Strandburg Argonne National Laboratory, Argonne IL, 60439 Nicolas Rivier Blackett Laboratory, Imperial College, London SW7 2BZ, Great Britain ABSTRACT Diverse cellular systems evolve to remarkably similar stationary states. We therefore have studied and simulated a purely topological model. We use a maximum entropy argument to predict that the average number of l-sided cells adjacent to an n-sided cell, Ml(n), will be linear in n. One consequence is the empirically observed linearity of the total number of edges of cells adjacent to an n-sided cell, known as the Aboav-Weaire law. The prevailing justification of that law is shown to be incorrect, and thus the apparently universal experimental slope of ~5 remains unexplained. TEXT Soap bubbles, polycrystalline grain mosaics and biological tissues are natural examples of random, space-filling cellular networks. Despite length scales spanning geology1, metallurgy2, and biology3, cellular networks have similar structure and evolve to a steady state, characterized by a scaling (stationary) distribution of cell sizes, shapes, and correlations. The similarity of the scaling state across systems molded by different physical forces has led many workers to seek an explanation independent of the driving forces4, 5, 6, 7, 8. Our purpose in this paper is to explore maximum entropy as an explanation for the similarity of many physical cellular networks once they have attained the scaling state. Among the properties of the scaling state, the probability Pn of cells with n sides is the most frequently measured in experimental systems. However the best-obeyed empirical regularity pertains to two-cell correlations. The Aboav-Weaire law2, 9, 10 states that on average the sum of the number of sides of the cells immediately adjacent to an n-sided cell11 (nm(n)) is linear in n: n m(n) = (6 a) n + (6a + m2), with a ~ 1 (Aboav-Weaire) (1) where m2 = Sn (n 6)2 Pn is the second moment of the Pn distribution. (The first moment for networks of trivalent vertices must be 6.) We look upon the Aboav- Weaire law as consisting of three assertions: n m(n) is linear in n. The slope of n m(n) is approximately 5, i.e. a ~ 1, empirically. Whatever the slope, we have 6 m(6) = 36 + m2. (This assertion is a direct result9 of the linearity of n m(n).) In this paper we focus on the two-cell correlation Ml(n), the average number of l- sided neighbors of an n-sided cell. Using a maximum entropy argument we predict that Ml(n) should be of the linear form Ml(n)=Al + nBl. We discuss the experimental status of this prediction. One consequence of linear Ml(n) is the empirically observed linearity of the Aboav- Weaire law. The Aboav-Weaire slope is not fixed by our maximum entropy analysis. Both by results of simulation and by statistical reasoning we show that a previous ("microreversibility") argument for linearity and slope 5 is incorrect. While our maximum entropy approach re-establishes a theoretical basis for linearity, the value of the slope in experimental studies is now unexplained. The maximum entropy argument The topology of cellular networks imposes constraints on the possible configurations of the cells, and in particular on the possible distributions Pn and Ml(n): Sn Pn = 1, the trivial constraint on probabilities. (2) Sn nPn=6, Euler's topological constraint for trivalent vertices. (3) Sl Ml(n) = n, as an n-sided cell always has n neighbors in total. (4) Sn Ml(n)Pn = l Pl, a consequence of counting the edges of l-sided cells (5) both from adjacent cells (LHS) and from within l--sided cells (RHS). Pl Mn(l) = Pn Ml(n), as the number of edges between n-sided cells and (6) l-sided cells is the same as that between l-sided cells and n-sided cells. We observe that if and only if Ml(n) has the linear form Ml(n) = Al + Bl n (7) then for every l the constraint (5) may be written Al Sn Pn + Bl Sn n Pn = l Pl, (8) which is a linear combination of the constraints (2) and (3). Duplication of the constraints avoids the reduction of configuration space which would result from imposition of any new constraints, and is therefore the prediction of maximum entropy. The argument that duplication of constraints is equivalent to maximum entropy was originally used by Rivier and Lissowski12 to prove a relation between size and shape of cells, discovered empirically by Lewis in biological tissues3, 13. A demonstration that reduction of the number of independent constraints does indeed increase the entropy is given by Rivier14, 15. The empirically observed linearity of nm(n) follows from the linearity of Ml(n). Noting the definition of nm(n) in terms of Ml(n) and using (7) we have nm(n) Sl Ml(n) l = (Sl Al l ) + n (Sl Bl l ). (9) Thus the linearity of the Aboav-Weaire law follows from maximum entropy. The widely observed slope ~5 is not explained by the current argument. Topological simulation To test our prediction of linear Ml(n) we performed a simulation of a cellular network, much like the simulations of Fradkov et. al. 6, 7 and Telley et. al. 16, 17. A cellular network of six-sided cells, with periodic boundary conditions, was constructed. The simulation proceeded by randomly choosing an edge from among all the cell edges in the network, and applying one of two elementary topological transformations (ETTs, figure 1) to the chosen edge. The spacefilling nature of the network is preserved by either ETT. Figure 1: Elementary topological transformations (ETTs) acting on cell edges. (a) disappearance of a 3-sided cell. (b) neighbor-switching process. The number of sides of the cells before and after each ETT is indicated. Note that our cellular network is purely topological, consisting of a connectivity graph of cell edges and three-fold vertices. Only the graph is retained during the simulation; there are no geometric or physical attributes, e.g. no vertex positions, edge curvatures, cell areas or internal pressures. The ratio of disappearances to switches is controlled by a parameter D. D=3 indicates that when the edge chosen is that of a 3-sided cell a disappearance is performed, and otherwise a switch is performed. For D=30, 90% of the switchs are rejected, thus preferring disappearances by a factor of 10. For D=0.3, 90% of the disappearances are rejected. For D=0, only switchs are performed. Our prediction of linear Ml(n) is well obeyed in D=0, D=0.3, and D=3 simulations. Shown in figure 2 is Ml(n), the number of l-sided neighbors of an n-sided cell, (scaled by 1/Pl), from our D=3 simulation. If there were no adjacency correlations, Ml(n) would be proportional to n: Ml(n) = nlPl/6. The curves in figure 2 do not intersect the origin for l 6, indicating that strong adjacency correlations are present, and yet linearity remains. Two direct consequences of the linearity of Ml(n), A6=0 and the linearity (in l) of Bl/Pl, are also observed in our simulation. Figure 2: The number of l-sided neighbors adjacent to an n-sided cell, as measured in a simulation with equal weighting for the two ETTs shown in figure 1 (i.e. D=3). Ml(n) for D=0 and D=0.3 simulations are much more linear than the D=3 results shown, while for D=30 substantial curvature at small n becomes visible, especially for large l. We find that curvature (for all D) decreases with increasing length of the simulation run. The limited experimental and Potts model data available6, 7, 18 for Ml(n) also show significant deviations from linearity, qualitatively much like the D=30 simulation19 . This observation suggests that the experimental systems and Potts model (and our D=30 simulation) may not yet have reached the scaling regime for neighbor correlations. In our simulations, as the disappearance rate, D, increases, our simulation times are increasingly limited since we simply run out of cells at earlier simulation times. Currently we can only report a trend toward increasing linearity as coarsening proceeds. For large D, longer simulations will be required to thoroughly test the prediction of our maximum entropy argument that Ml(n) will eventually attain a linear form. A determination of the time dependence of Ml(n) for a physically- driven simulation (e.g. the Potts model) or for an experimental system would also be of great interest to check the extent to which the maximum entropy predictions apply in real systems. Disproof of the microreversibility argument A previous argument20, 21, based on microreversibility of the ETTs illustrated in figure 1, appeared to explain both the linearity of the Aboav-Weaire law and the universal observation of slope ~5. Here we briefly rehearse that argument and show that it is incorrect. The microreversibility argument assumes stationarity of nm(n), and posits that any ETT should leave the values of nm(n) unchanged. Consider first a cell-disappearance as shown in figure 1(a). Before the disappearance, the sum of the sides of the neighbors of the n-sided cell nm(n)=a+b+3+..., where ... indicates the sides of the other neighbors of the n-sided cell which are not affected by the disappearance. After the disappearance, we have (n1)m(n1)= (a1) + (b1) + .... Subtraction yields nm(n) (n1)m(n1) = 5. Therefore, since n could have been any value, the only possible stationary function nm(n) is linear with slope 5. Next consider an neighbor-switching, shown in figure 1(b). Before the switch, we have nm(n) = a + c + ...; after the switch we have (n+1)m(n+1)= (a1) + (b+1) + (c 1)+ .... Subtraction yields (n+1)m(n+1) nm(n) = b1. Assuming that second neighbors are uncorrelated, it was argued that b is a "typical" cell with =6. Thus the slope 5 required for the function nm(n) to be stationary with respect to neighbor- switchings is the same as that required for it to be stationary with respect to disappearances. Measurements of nm(n) for a simulation involving random neighbor-switchings alone (D=0) are shown in the upper curve of figure 3. The slope is not 5, but 7.33! The explanation lies in the fact that when we choose an edge to participate in a switch, the cell b to which it is attached is more likely to be a cell with a large number of vertices, since larger cells have more edges attached to them. More precisely, the number of edges of cells selected in this way is the sidedness- weighted average = Sn n2 Pn / Sn n Pn = 6 + m2/6 (10) Therefore the slope required for stationarity with respect to neighbor-switchings is not 5, but 5 + m2/6. In our simulation the measured second moment of Pn is m2 = 12.69, and the resulting prediction for the slope of nm(n) is 7.12, close to the observed slope of 7.33. Thus for D=0 the corrected microreversibility argument predicts the observed slope of nm(n), with the small discrepency attributable to weak second neighbor correlations. Note that for D 0 it is central to the microreversibility argument that the two ETTs result in the same slope, 5. If the ratio of switchs to disappearances affecting an n-sided cell were independent of n a linear Aboav-Weaire law would still result from microreversibility, with a slope intermediate between 7.12 and 5. However there is no reason a priori to expect the ratio to be independent, since 3-sided cells are (by the Aboav-Weaire law itself) preferentially adjacent to cells with large n. Larger cells would be expected to experience proportionately more disappearances, and the gradient of nm(n) would be closer to 5 for larger cells, violating linearity. Figure 3: Aboav's law: nm(n) is the average total number of sides of all cells adjacent to an n-sided cell. From the top, the four curves are results of simulations with increasing rates of cell disappearances. Lines are linear fits, with slopes 7.33, 6.96, 6.03, and 5.51 respectively. Discussion Now that we can no longer use microreversibility of the ETTs to explain the widely observed slope ~5 of the Aboav-Weaire law in experimental systems, we are left with a puzzle. It seems likely that such a coincidence does not depend on the detailed physical interactions driving a coarsening froth, but rather reflects an underlying mathematical cause such as topology, entropy, or geometry. Our simulations capture both topology and entropy however, and do not display slope ~5. Simulations of the Potts model have the character of a well-controlled experiment (i.e. they include a particular physical driving mechanism), and do obtain slope 5, but without illuminating the cause18. One possible explanation is that real froths may coarsen exclusively or predominantly by cell-disappearances, for which the expected slope is 5. We have found that disappearances alone cannot continue indefinitely, however, because 3- sided cells become extinct. The ratio of switchs to disappearances never falls much below unity. It is also possible that unmodeled processes such as the direct disappearance of 4- and 5-sided cells may play a significant role6, 7. Further experimental measurement of Ml(n) in real froths could better explore the role of maximum entropy in the evolution of those froths. The time-dependence of our simulations suggests that existing experiments and Potts model simulations may not have fully reached a scaling state with respect to two-cell correlations. Studies of the time dependence of both experiments and simulations might help resolve this issue. The fact that the early stage deviations from linearity present in the experimental systems and Potts model simulations are captured by our random, purely topological model suggests that topological considerations alone may be sufficient to understand the scaling state, at least at the level of two-cell correlations. A detailed description of our simulations, settling times, and comparison with experiment, will be presented elsewhere. We would like to thank J. Eastman, R. Englman, D. Fain, A. Gervois, J. Glazier, G. Grest, V. Fradkov, K. Hampel, B. O'Keefe, Murray Peshkin, R. Siegel, H. Telley, D. Udler, and D. Weaire for helpful discussions. Computer time provided by the Center for Manufacturing Engineering of Northwestern University is gratefully acknowledged. This work was supported by U. S. Dept. of Energy, BES-Materials Sciences, under contract W-31-109-ENG-38, NSF contract RII-9003018 (KJS), and NSF contract DMC-8857854 (MP). 1. Foley, S., Trans. Royal Soc. 18, 170 (1694). 2. Aboav, D. A., Metallography 3, 382 (1970). 3. Lewis, F. T., Anat. Record 50, 235 (1931). 4. Weaire, D. and N. Rivier, Contemp. Phys. 25, 59 (1984). (a useful survey) 5. Glazier, J. A., Dynamics of Cellular Patterns, thesis, University of Chicago (1989). (contains a useful survey) 6. Fradkov, V. E., L. S. Shvindlerman and D. G. Udler, Phil. Mag. B 55(6), 289 (1987). 7. Fradkov, V. E., L. S. Schvindlerman and D. G. Udler, Computer simulation of normal grain growth in two dimensions comprising spontaneous switchings, (1986). (unpublished report) 8. Lemaitre, J., J. P. Troadec, A. Gervois, D. Bideau, L. Oger, M. Ammi and N. Rivier, J. de Phys , (1991). (submitted) 9. Lambert, C. J. and D. Weaire, Phil. Mag. B 47(4), 445 (1983). 10. Weaire, D., Metallography 7, 157 (1974). 11. For historical reasons this is written as n times the average number of sides per neighbor m(n)., 12. Rivier, N. and A. Lissowski, J. Phys. A 15, L143 (1982). 13. Lewis, F. T., Anat. Record 38, 341 (1928). 14. Rivier, N., Maximum Entropy and Bayesian Methods, Fougre, P. F. ed., Kluwer Acad. Publ, (1990). (p.297) 15. Rivier, N., Amorphous Materials: Modeling of Structure and Properties, Vitek, V. ed., The Metallogical Society of AIME, Warrendale (1983). (p.81) 16. Telley, H., A. Mocellin and T. M. Liebling, Acta Stereol. 8(2), 453 (1989). 17. Telley, H., Modlisation et Simulation Bidimensionnelle de la Croissance des Polycristaux,, thesis, Ecole Polytechnique Federale, Lausanne (1989). 18. Glazier, J. A., M. P. Anderson and G. S. Grest, Phil. Mag. B 62(6), 615 (1990). 19. In our simulations, the probability of 3-sided cells P3 in the D=30 simulation is closest to P3 in the Potts model and experimental systems, suggesting that D=30 is the most appropriate for comparison., 20. Blanc, M. and A. Mocellin, Acta Met. 27, 1231 (1979). 21. Rivier, N., Phil. Mag. B 52(3), 795 (1985). Figure captions Figure 1: Elementary topological transformations (ETTs) acting on cell edges. (a) disappearance of a 3-sided cell. (b) neighbor-switching process. The number of sides of the cells before and after each ETT is indicated. Figure 2: The number of l-sided neighbors adjacent to an n-sided cell, as measured in a simulation with equal weighting for the two ETTs shown in figure 1 (i.e. D=3). Figure 3: Aboav's law: nm(n) is the average total number of sides of all cells adjacent to an n-sided cell. From the top, the four curves are results of simulations with increasing rates of cell disappearances. Lines are linear fits, with slopes 7.33, 6.96, 6.03, and 5.51 respectively.