Rounding of first-order phase transitions and optimal cooperation in scale-free
networks
M. Karsai,1,2 J-Ch. Anglès d’Auriac,2 and F. Iglói3, 1
Institute of Theoretical Physics, Szeged University, H-6720 Szeged, Hungary
Centre de Recherches sur les Trés Basses Températures, B. P. 166, F-38042 Grenoble, France
Research Institute for Solid State Physics and Optics, H-1525 Budapest, P.O.Box 49, Hungary
(Dated: November 20, 2018)
We consider the ferromagnetic large-q state Potts model in complex evolving networks, which is
equivalent to an optimal cooperation problem, in which the agents try to optimize the total sum
of pair cooperation benefits and the supports of independent projects. The agents are found to be
typically of two kinds: a fraction of m (being the magnetization of the Potts model) belongs to a
large cooperating cluster, whereas the others are isolated one man’s projects. It is shown rigorously
that the homogeneous model has a strongly first-order phase transition, which turns to second-order
for random interactions (benefits), the properties of which are studied numerically on the Barabási-
Albert network. The distribution of finite-size transition points is characterized by a shift exponent,
1/ν̃′ = .26(1), and by a different width exponent, 1/ν′ = .18(1), whereas the magnetization at the
transition point scales with the size of the network, N , as: m ∼ N−x, with x = .66(1).
I. INTRODUCTION
Complex networks have been used to describe the
structure and topology of a large class of systems in dif-
ferent fields of science, technics, transport, social and
political life, etc, see Refs.1,2,3,4 for recent reviews. A
complex network is represented by a graph5, in which the
nodes stand for the agents and the edges denote the possi-
ble interactions. Realistic networks generally have three
basic properties. The average distance between the nodes
is small, which is called the small-world effect6. There is a
tendency of clustering and the degree-distribution of the
edges, P (k), has a power-law tail, PD(k) ≃ Ak
−γ , k ≫ 1.
Thus the edge distribution is scale free7, which is usually
attributed to growth and preferential attachment during
the evaluation of the network.
In reality there is some sort of interaction between the
agents of a network which leads to some kind of coop-
erative behavior in macroscopic scales. One throughly
studied question in this field is the spread of infections
and epidemics in networks8,9,10, which problem is closely
related to another non-equilibrium processes, such as
percolation11, diffusion12, the contact process13 or the
zero-range process14, etc. In another investigations one
considers simple magnetic models15,16,17,18,19, in which
the agents are represented by classical (Ising or Potts)
spin variables, the interactions are described by ferro-
magnetic couplings, whereas the temperature plays the
rôle of a disordering field.
In theoretical investigations of the cooperative behav-
ior one usually resort on some kind of approximations.
For example the sites of the networks are often consid-
ered uncorrelated, which is generally not true for evolv-
ing networks, such as the Barabási-Albert (BA) network.
However this effect is expected to be irrelevant, as far as
the singularities in the system are considered. Also the
simple mean-field approach could lead to exact results
due to long-range interactions in the networks, which has
been checked by numerical simulations15 and by another,
more accurate theoretical methods19 (Bethe-lattice ap-
proach, replica method, etc.). In these calculations the
critical behavior of the network is found to depend on the
value of the degree exponent, γ. For sufficiently weakly
connected networks with γ > γu (γu = 5 for the Ising
model) there are conventional mean-field singularities. In
the intermediate or unconventional mean-field regime, for
γu > γ > γc, the critical exponents are γ dependent. Fi-
nally, for γ ≤ γc, when the average of k
2, defined by
〈k2〉 =
PD(k)k
2dk, as well as the strength of the aver-
age interaction becomes divergent the scale-free network
remains in the ordered state at any finite temperature.
Since γc = 3, in realistic networks with homogeneous
interactions always this type of phenomena is expected
to occur. In weighted networks, however, in which the
strengths of the interaction is appropriately rescaled with
the degrees of the connected vertices, γc is shifted to
larger values and therefore the complete phase-transition
scenario can be tested13,19. We note that the properties
of the phase transitions are generally different for undi-
rected (as we consider here) and directed networks20.
In several models the phase transition in regular lat-
tices is of first order, such as for the q-state Potts model
for sufficiently large value of q. Putting these models on a
complex network the inhomogeneities of the lattice play
the rôle of some kind of disorder and it is expected that
the value of the latent heat is reduced or even the tran-
sition is smoothened to a continuous one. This type of
scenario is indeed found in a mean-field treatment17, in
which the transition is of first-order for γ > γ(q) and be-
comes continuous for γc < γ < γ(q), where 3 < γ(q) < 4.
On the other hand in an effective medium Bethe lattice
approach one has obtained γ(q) = 3, thus the unconven-
tional mean-field regime is absent in this treatment18.
The interactions considered so far were homogeneous,
however, in realistic situations the disorder is inevitable,
which has a strong influence on the properties of the
http://arxiv.org/abs/0704.1538v1
phase transition. In regular lattices and for a second-
order transition Harris-type relevance-irrelevance crite-
rion can be used to decide about the stability of the pure
system’s fixed point in the presence of weak disorder. On
the contrary for a first-order transition such type of cri-
terion does not exist. In this case rigorous results asserts
that in two dimensions (2d) for any type of continuous
disorder the originally first order transition softens into a
second order one21. In three dimensions there are numer-
ical investigations which have shown22,23,24,25,26 that this
kind of softening takes place only for sufficiently strong
disorder.
In this paper we consider interacting models with ran-
dom interactions on complex networks and in this way we
study the combined effect of network topology and bond
disorder. The particular model we consider is the ran-
dom bond ferromagnetic Potts model (RBPM) for large
value of q. This model besides its relevance in ordering-
disordering phenomena and phase transitions has an
exact relation with an optimal cooperation problem27.
This mapping is based on the observation that in the
large-q limit the thermodynamic properties of the sys-
tem are dominated by one single diagram28 of the high-
temperature expansion29 and its calculation is equiva-
lent to the solution of an optimization problem. This
optimization problem can be interpreted in terms of co-
operating agents which try to maximize the total sum of
benefits received for pair cooperations plus a unit sup-
port which is paid for each independent projects. For a
given realization of the interactions the optimal state is
calculated exactly by a combinatorial optimization algo-
rithm which works in strongly polynomial time27. The
optimal graph of this problem consists of connected com-
ponents (representing sets of cooperating agents) and
isolated sites and its temperature (support) dependent
topology contains information about the collective be-
havior of the agents. In the thermodynamic limit one
expects to have a sharp phase transition in the system,
which separates the ordered (cooperating) phase with a
giant clusters from a disordered (non-cooperating) phase,
having only clusters of finite extent.
The structure of the paper is the following. The model
and the optimization method used in the study for large
q is presented in Sec. II. The solution for homogeneous
non-random evolving networks can be found in Sec. III,
whereas numerical study of the random model on the
Barabási-Albert network is presented in Sec. IV. Our
results are discussed in Sec. V.
II. THE MODEL AND ITS RELATION WITH
OPTIMAL COOPERATION
The q-state Potts model30 is defined by the Hamilto-
nian:
H = −
〈i,j〉
Jijδ(σi, σj) (1)
in terms of the Potts-spin variables, σi = 0, 1, · · · , q − 1.
Here i and j are sites of a lattice, which is represented by
a complex network in our case and the summation runs
over nearest neighbors, i.e. pairs of connected sites.
The couplings, Jij > 0, are ferromagnetic and they
are either identical, Jij = J , which is the case of homo-
geneous networks, or they are identically and indepen-
dently distributed random variables. In this paper we
use a quasi-continuous distribution:
P (Jij) =
1 + ∆
2i− l − 1
− Jij
which consists of large number of l equally spaced discrete
values within the range J(1 ± ∆/2) and 0 ≤ ∆ ≤ 2
measures the strength of disorder.
For a given set of couplings the partition function of
the system is convenient to write in the random cluster
representation29 as:
qc(G)
qβJij − 1
where the sum runs over all subset of bonds, G and c(G)
stands for the number of connected components of G. In
Eq. (3) we use the reduced temperature, T → T ln q and
its inverse β → β/ ln q, which are of O(1) even in the
large-q limit31. In this limit we have qβJij ≫ 1 and the
partition function can be written as
qφ(G), φ(G) = c(G) + β
Jij (4)
which is dominated by the largest term, φ∗ = maxG φ(G).
Note that this graph, which is called the optimal set,
generally depends on the temperature. The free-energy
per site is proportional to φ∗ and given by −βf = φ∗/N
where N stands for the number of sites of the lattice.
As already mentioned in the introduction the optimiza-
tion in Eq. (4) can be interpreted as an optimal coopera-
tion problem27 in which the agents, which cooperate with
each other in some projects, form connected components.
Each cooperating pair receives a benefit represented by
the weight of the connecting edge (which is proportional
to the inverse temperature) and also there is a unit sup-
port to each component, i.e. for each projects. Thus by
uniting two projects the support will be reduced but at
the same time the edge benefits will be enhanced. Finally
one is interested in the optimal form of cooperation when
the total value of the project grants is maximal.
In a mathematical point of view the cost-function in
Eq. (4), −φ(G), is sub-modular32 and there is an effi-
cient combinatorial optimization algorithm which calcu-
lates the optimal set (i.e. set of bonds which minimizes
the cost-function) exactly at any temperature in strongly
polynomial time27. In the algorithm the optimal set is
calculated iteratively and at each step one new vertex of
the lattice is taken into account. Having the optimal set
at a given step, say with n vertices, its connected compo-
nents have the property to contain all the edges between
their sites. Due to the submodularity of −φ(G) each con-
nected component is contracted into a new vertex with
effective weights being the sum of individual weights in
the original representation. Now adding a new vertex one
should solve the optimization problem in terms of the ef-
fective vertices, which needs the application of a standard
maximum flow algorithm, since any contractions should
include the new vertex. After making the possible new
contractions one repeats the previous steps until all the
vertices are taken into account and the optimal set of the
problem is found.
This method has already been applied for 2d31,33 and
3d25,26 regular lattices with short range random inter-
actions. As a general result the optimal graph at low
temperatures is compact and the largest connected sub-
graph contains a finite fraction of the sites, m(T ), which
is identified by the orderparameter of the system. In the
other limit, for high temperature, most of the sites in the
optimal set are isolated and the connected clusters have
a finite extent, the typical size of which is used to define
the correlation length, ξ. Between the two phases there is
a sharp phase transition in the thermodynamic limit, the
order of which depends on the dimension of the lattice
and the strength of disorder, ∆.
In the following the optimization problem is solved ex-
actly for homogeneous evolving networks in Sec.III and
studied numerically in random Barabási-Albert networks
in Sec.IV.
III. EXACT SOLUTION FOR HOMOGENEOUS
EVOLVING NETWORKS
In regular d-dimensional lattices the solution of the
optimization problem in Eq. (4) is simple, since there are
only two distinct optimal sets, which correspond to the
T = 0 and T → ∞ solutions, respectively. For T <
Tc(0) it is the fully connected diagram, E, with a free-
energy: −βNf = 1 + NβJd and for T > Tc(0) it is the
empty diagram, Ø, with −βNf = N . In the proof we
make use of the fact, that any edge of a regular lattice,
e1, can be transformed to any another edge, e2, through
operations of the automorphy group of the lattice. Thus
if e1 belongs to some optimal set, then e2 belongs to
an optimal set, too. Furthermore, due to submodularity
the union of optimal sets is also an optimal set, from
which follows that at any temperature the optimal set
is either Ø or E. By equating the free energies in the
two phases we obtain for the position of the transition
point: Tc(0) = Jd/(1 − 1/N) whereas the latent heat is
maximal: ∆e/Tc(0) = 1− 1/N .
In the following we consider the optimization problem
in homogeneous evolving networks which are generated
by the following rules:
• we start with a complete graph with 2µ vertices
• at each timestep we add a new vertex
• which is connected to µ existing vertices.
In definition of these networks there is no restric-
tion in which way the µ existing vertices are selected.
These could be chosen randomly, as in the Erdős-Rényi
model34, or one can follow some defined rule, like the
preferential attachment in the BA network7. In the
following we show that for such networks the phase-
transition point is located at Tc(0) = Jµ and for T <
Tc(0) (T > Tc(0)) the optimal set is the fully connected
diagram (empty diagram), as for the regular lattices.
Furthermore, the latent heat is maximal: ∆e/Tc(0) = 1.
In the proof we follow the optimal cooperation
algorithm27 outlined in Sec.II, and in application of the
algorithm we add the vertices one by one in the same or-
der as in the construction of the network. First we note,
that the statement is true for the initial graph, which is a
complete graph, thus the optimal set can be either fully
connected, having a free-energy: −β2µf = 1 + µ(2µ −
1)βJd, or empty, having a free-energy: −β2µf = 2µ,
thus the transition point is indeed at T = Tc(0). We
suppose then that the property is satisfied after n steps
and add a new vertex, v0. Here we investigate the two
cases, T ≤ Tc(0) and T ≥ Tc(0) separately.
• If T ≤ Tc(0), then according to our statement all
vertices of the original graph are contracted into
a single vertex, s, which has an effective weight,
µ × J/T > µJ/Tc(0) = 1, to the new vertex v0.
Consequently in the optimal set s and v0 are con-
nected, in accordance with our statement.
• If T ≥ Tc(0), then all vertices of the original graph
are disconnected, which means that for any subset,
S, having ns ≤ n vertices and es edges one has:
ns ≥ esJT + 1. Let us denote by µs ≤ µ the
number of edges between v0 and the vertices of S.
One has µsJ/T ≤ µJ/T ≤ µJ/Tc(0) = 1, so that
for the composite S+ v0 we have: ns+1 ≥ esJT +
1+µsJ/T , which proves that the vertex v0 will not
be connected to any subset S and thus will not be
contracted to any vertex.
This result, i.e. a maximally first-order transition of
the large-q state Potts model holds for a wide class of
evolving networks, which satisfy the construction rules
presented above. This is true, among others, for ran-
domly selected sites, for the BA evolving network which
has a degree exponent γ = 3 and for several generaliza-
tions of the BA network1 including nonlinear preferential
attachment, initial attractiveness, etc. In these latter
network models the degree exponent can vary in a range
of 2 < γ < ∞. It is interesting to note that for uncorre-
lated random networks with a given degree distribution
the q-state Potts model is in the ordered phase17,18 for
any γ ≤ 3. This is in contrast to evolving networks in
which correlations in the network sites results in the ex-
istence of a disordered phase for T > Tc(0), at least for
large q.
3.12.92.72.5
Tc(∞)
N=256
N=512
N=1024
N=2048
N=4096
 0  0.5  1  1.5  2  2.5  3
∆=0.2
∆=0.8
∆=1.4
∆=2.0
FIG. 1: (Color online) Temperature dependence of the av-
erage magnetization in a BA network of N = 1024 sites for
different strength of the disorder, ∆. At T = Tc(0) = 2 the
magnetization is independent of ∆ > 0 and its value is in-
dicated by an arrow. Inset: The average magnetization for
uniform disorder, ∆ = 2, close to the transition point for dif-
ferent finite sizes. The arrow indicates the critical point of
the infinite system.
IV. NUMERICAL STUDY OF RANDOM
BARABÁSI-ALBERT NETWORKS
In this section we study the large-q state Potts model
in the BA network with a given value of the connectiv-
ity, µ = 2, and the size of the network varies between
N = 26 to N = 212. The interactions are independent
random variables taken from the quasi-continuous distri-
bution in Eq.(2) having l = 1024 discrete peaks and we fix
J = 1. The advantage of using quasi-continuous distri-
butions is that in this way we avoid extra, non-physical
singularities, which could appear for discrete (e.q. bi-
modal) distributions31. For a given size we have gener-
ated 100 independent networks and for each we have 100
independent realizations of the disordered couplings.
A. Magnetization and structure of the optimal set
In Fig.1 the temperature dependence of the average
magnetization is shown for various strength of disorder,
∆, for a BA network ofN = 1024 sites. It is seen that the
sharp first-order phase transition of the pure system with
∆ = 0 is rounded and the magnetization has considerable
variation within a temperature range of ∼ ∆. The phase
transition seems to be continuous even for weak disorder.
Close to the transition point the magnetization curves
for uniform disorder (∆ = 2) are presented in the inset
of Fig.1, which are calculated for different finite systems.
Some features of the magnetization curves and the
properties of the phase transition can be understood
by analysing the structure of the optimal set. For low
enough temperature this optimal set is fully connected,
i.e. the magnetization is m = 1, which happens for
T < Tc(0)−∆. Indeed, the first sites with k = µ = 2 (i.e.
those which have only outgoing edges) are removed from
the fully connected diagram, if the sum of the connected
bonds is
i=1 Ji < T , which happens within the tem-
perature range indicated above. From a similar analysis
follows that the optimal set is empty for any finite system
for T > Tc(0) + ∆. The magnetization can be estimated
for t = T − (Tc(0)−∆) ≪ 1, and the correction is given
by: 1−m ∼ tµ. For the numerically studied model with
µ = 2 and ∆ = 2, we have m(T ) ≈ 1 − T 2/8, which is
indeed a good approximation for T < 1. In the tempera-
ture range Tc(0)−∆ < T < Tc(0)+∆ typically the sites
are either isolated or belong to the largest cluster. There
are also some clusters with an intermediate size, which
are dominantly two-site clusters for T < Tc(0) and their
fraction is less then 1%, as shown in Fig.2. The fraction
of two-site clusters for ∆ = 2 and T < Tc(0) = 2 can
be estimated as follows. First, we note that since they
are not part of the biggest cluster they can be taken out
of a fraction of p1 = 1 − m(T ) sites. Before being dis-
connected a two-site cluster has typically three bonds to
the biggest cluster, denoted by J1, J2 and J3. When it
becomes disconnected we have J1 + J2 + J3 < T , which
happens with a probability p2 = T
3/48. At the same
time the coupling within the two-site cluster should be
J4 > T , which happens with probability p3 = (2− T )/2.
Thus the fraction of two-site clusters is approximately:
n2 ≈ p1 × p2 × p3 ≈ T
5(2− T )/768, which describes well
the general behavior of the distribution in Fig.2.
In the temperature range T > Tc(0) the intermedi-
ate clusters have at least three sites and their fraction is
negligible, which is seen in Fig.2. Consequently the in-
termediate size clusters do not influence the properties of
the phase transition in the system. In the ordered phase,
T < Tc, the largest connected cluster contains a finite
fraction of m(T ) < 1 of the sites. We have analyzed the
degree distribution of this connected giant cluster in Fig.
3, which has scale-free behavior and for any tempera-
ture T < Tc there is the same degree exponent, γ = 3,
as for the original BA network. We note an interesting
feature of the magnetization curves in Fig.1 that cross
each other at the transition point of the pure system, at
Tc(0) = 2, having a value of m(Tc(0)) = 0.58, for any
strength of disorder. This property follows from the fact
that for a given realization of the disorder the optimal
set at T = Tc(0) only depends on the sign of the sum
of fluctuations of given couplings (c.f. some set of sites
is connected (disconnected) to the giant cluster only for
positive (negative) accumulated fluctuations) and does
not depend on the actual value of ∆ > 0.
We can thus conclude the following picture about the
evaluation of the optimal set. This is basically one large
connected cluster with N sites, immersed in the see of
isolated vertices. With increasing temperature more and
more loosely connected sites are dissolved from the clus-
ter, but for T < Tc we have N/N = m(T ) > 0 and the
N=128
N=256
N=512
N=1024
FIG. 2: (Color online) Fraction of intermediate size clusters
as a function of the temperature.
 0  1  2  3  4  5  6
ln(k)
T=1.957
T=2.464
T=2.738
T=2.816
T=2.894
T=2.972
T=3.030
T=3.089
T=3.128
FIG. 3: (Color online) Degree distribution of the largest
cluster at different temperatures in a finite network with
N = 2048. The dashed straight line indicates the range of
the critical temperature.
cluster has the same type of scale-free character as the
underlaying network. On the contrary above the phase-
transition point, Tc(0) + ∆ > T > Tc, the large clus-
ter has only a finite extent, N < ∞. The order of the
transition depends on the way how N behaves close to
Tc. A first-order transition, i.e. phase-cooexistence at
Tc does not fit to the above scenario. Indeed, as long
as N ∼ N the same type of continuous erosion of the
large cluster should take place, i.e. the transition is of
second order for any strength, ∆ > 0 of the disorder.
Approaching the critical point one expects the following
singularities: m(T ) ∼ (Tc − T )
β and N ∼ (T − Tc)
−ν′ .
Finally, at T = Tc the large cluster has N ∼ N
1−x sites,
with x = β/ν′.
B. Distribution of the finite-size transition
temperatures
The first step in the study of the critical singularities
is to locate the position of the phase-transition point.
In this respect it is not convenient to use the magne-
tization, which approaches zero very smoothly, see the
inset of Fig.1, so that there is a relatively large error by
calculating Tc in this way. One might have, however, a
better estimate by defining for each given sample, say
α, a finite-size transition temperature Tc(α,N), as has
been made for regular lattices25,26,31. For a network we
use a condition for the size of the connected component:
N (T ) ≃ AN1−x , in which x is the magnetization critical
exponent and A = O(1) is a free parameter, from which
the scaling form of the distribution is expected to be in-
dependent. The calculation is made self-consistently: for
a fixed A and a starting value of xs = x1 we have deter-
mined the distribution of the finite-size transition tem-
peratures and at their average value we have obtained
an estimate for the exponent, x = x2. Then the whole
procedure is repeated with xs = x2, etc. until a good
convergence is obtained. Fortunatelly the distribution
function, p(Tc, N), has only a weak x-dependence thus it
was enough to make only two iterations. We have started
with a logarithmic initial condition, N (T ) ≃ A lnN ,
which means formally x1 = 1 and we have obtained
x2 = .69. Then in the next step the critical exponents
are converged within the error of the calculation and they
are found to be independent of the value of A, which has
been set to be A = 1, 2 and 3.
The distribution of the finite-size critical temperatures
calculated with x2 = 0.69 and A = 3. are shown in Fig.4
for different sizes of the network. One can observe a
shift of the position of the maxima as well as a shrinking
of the width of the distribution with increasing size of
the network. The shift of the average value, T avc (N), is
asymptotically given by:
T avc (N)− Tc(∞) ∼ N
−1/ν̃′ , (5)
whereas the width, characterized by the mean standard
deviation, ∆Tc(N), scales with another exponent, ν
′, as:
∆Tc(N) ∼ N
−1/ν′ . (6)
Using Eq.(5) from a three-point fit we have obtained
ν̃′ = 3.8(2) and Tc(∞) = 3.03(2). We have determined
the position of the transition point in the infinite sys-
tem, Tc(∞), in another way by plotting the difference
T avc (N) − Tc(∞) vs. N in a log-log scale for different
values of Tc(∞), see Fig.5. At the true transition point
according to Eq.(5) there is an asymptotic linear depen-
dence, which is indeed the case around Tc(∞) = 3.03(2)
and the slope of the line is compatible with 1/ν̃′ = .27(1).
For the width exponent, ν′, we obtained from Eq.(6)
with two-point fit the estimate: ν′ = 5.6(2). With
these parameters the data in Fig.4 can be collapsed to
a master curve as shown in the inset of Fig.4. This
 1.8  2  2.2  2.4  2.6  2.8  3  3.2
N=128
N=256
N=512
N=1024
N=2048
N=4096
-3 -2 -1  0  1  2  3  4  5
FIG. 4: (Color online) Distribution of the finite-size transi-
tion temperatures for different sizes of the BA network. In-
set: scaling collapse of the data in terms of t = (Tc(N) −
(N))/∆Tc(N), using the scaling form in Eqs.(5) and (6)
with ν′ = 3.8(2), and ν̃′ = 5.6(2).
 4  4.5  5  5.5  6  6.5  7  7.5  8  8.5
ln(N)
Tc=3.17
Tc=3.14
Tc=3.11
Tc=3.08
Tc=3.05
Tc=3.03
Tc=3.01
Tc=2.98
Tc=2.96
FIG. 5: (Color online) Shift of the average finite-size transi-
tion temperatures, T av
(N) − Tc(∞), vs. N in a log-log scale
plotted for different values of Tc(∞). The lines connecting
the points at the same Tc(∞) are guide for the eye. At the
true transition point the asymptotic behavior is linear which
is indicated by a dotted straight line.
master curve looks not symmetric, at least for the fi-
nite sizes used in the present calculation, and can be
well fitted by a modified Gumbel distribution, Gω(−y) =
ωω/Γ(ω)(exp(−y−e−y))ω , with a parameter ω = 4.2. We
note that the same type of fitting curve has already been
used in Ref.35. For another values of the initial parame-
ter, A = 1 and 2 the estimates of the critical exponents
as well as the position of the transition point are found
to be stable and stand in the range indicated by the error
bars.
The equations in Eqs.(5) and (6) are generalizations
of the relations obtained in regular d-dimensional lat-
tices36,37,38,39,40 in which N is replaced by Ld, L being
the linear size of the system and therefore instead of ν′
and ν̃′ we have ν = ν′/d and ν̃ = ν̃′/d, respectively. Gen-
erally at a random fixed point the two characteristic ex-
ponents are equal and satisfy the relation41 ν′ = ν̃′ ≥ 2.
This has indeed been observed for the 2d31 and 3d25,26
random bond Potts models for large q at disorder induced
critical points. On the other hand if the transition stays
first-order there are two distinct exponents35,42 ν̃′ = 1
and ν′ = 2.
Interestingly our results on the distribution of the
finite-size transition temperatures in networks are differ-
ent of those found in regular lattices. Here the transition
is of second order but still there are two distinct critical
exponents, which are completely different of that at a
disordered first-order transition. For our system ν′ > ν̃′,
which means that disorder fluctuations in the critical
point are dominant over deterministic shift of the tran-
sition point. Similar trend is observed about the finite-
size transition parameters in the random transverse-field
Ising model43, the critical behavior of which is controlled
by an infinite disorder fixed point. In this respect the
RBPM in scale-free networks can be considered as a new
realization of an infinite disorder fixed point.
C. Size of the critical cluster
Having the distribution of the finite-size transition
temperatures we have calculated the size of the largest
cluster at T avc (N), which is expected to scale as
N [N, T avc (N)] ∼ N
1−x. Then from two-point fit we
have obtained an estimate for the magnetization expo-
nent: x = .66(1). We have also plotted N [N, T avc (N)] vs.
N1−x in Fig.6 for different initial parameters, A. Here
we have obtained an asymptotic linear dependence with
an exponent, x = .65(1), which agrees with the previous
value within the error of the calculation.
V. DISCUSSION IN TERMS OF OPTIMAL
COOPERATION
In this paper we have studied the properties of the
Potts model for large value of q on scale-free evolving
complex networks, such as the BA network, both for ho-
mogeneous and random ferromagnetic couplings. This
problem is equivalent to an optimal cooperation prob-
lem in which the agents try to optimize the total sum of
the benefits coming from pair cooperations (represented
by the Potts couplings) and the total sum of the support
which is the same for each cooperating projects (given by
the temperature of the Potts model). The homogeneous
problem is shown exactly to have two distinct states: ei-
ther all the agents cooperate with each other or there is
no cooperation between any agents. There is a strongly
first-order phase transition: by increasing the support
the agents stop cooperating at a critical value.
 0  10  20  30  40  50
[0 , 0]
 0  10  20  30  40  50
[0 , 0]
FIG. 6: (Color online) Size dependence of the critical cluster
at the average finite-size critical temperature as a function
of N1−x with x = .65. The date points for different initial
parameters, A, are well described by straight lines, which are
guides to the eye.
In the random problem, in which the benefits are ran-
dom and depend on the pairs of the cooprerating agents,
the structure of the optimal set depends on the value of
the support. Typically the agents are of two kinds: a frac-
tion of m belongs to a large cooperating cluster whereas
the others are isolated, representing one man’s projects.
With increasing support more and more agents are split
off the cluster, thus its size, as well as m is decreasing,
but the cluster keeps its scale-free topology. For a critical
value of the support m goes to zero continuously and the
corresponding singularity is characterized by non-trivial
critical exponents. This transition, as shown by the nu-
merically calculated critical exponents for the BA net-
work, belongs to a new universality class. One interesting
feature of it is that the distribution of the finite-size tran-
sition points is characterized by two distinct exponents
and the width of the distribution is dominated over the
shift of the average transition point, which is character-
istic at an infinite disorder fixed point43.
We thank for useful discussions with C. Monthus and
for previous cooperation on the subject with M.-T. Mer-
caldo. This work has been supported by the National
Office of Research and Technology under Grant No.
ASEP1111, by the Hungarian National Research Fund
under grant No OTKA TO48721, K62588, MO45596 and
M36803. M.K. thanks the Ministère Français des Affaires
Étrangères for a research grant.
1 R. Albert and A.L. Barabási, Rev. Mod. Phys. 74, 47
(2002).
2 S.N. Dorogovtsev and J.F.F. Mendes, Adv. Phys. 51, 1079
(2002).
3 S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Net-
works: From Biological Nets to the Internet and WWW
(Oxford University Press, Oxford, 2003)
4 M.E.J. Newman, SIAM Review 45, 167-256 (2003).
5 B. Bollobás, Random Graphs (Academic Press, London,
1985).
6 D.J. Watts and S.H. Strogatz, Nature (London) 393, 440
(1998).
7 A.L. Barabási and R. Albert, Science 286, 509 (1999).
8 R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett.
86, 3200 (2001); Phys. Rev. E 63, 066117 (2001).
9 M.E.J. Newman, Phys. Rev. E 66, 016128 (2002).
10 Z. Dezső, A.-L. Barabási, Phys. Rev. E 65, 055103 (2002).
11 D.S. Callaway, M.E.J. Newman, S.H. Strogatz, and D.J.
Watts, Phys. Rev. Lett. 85, 5468 (2000); R. Cohen, D.
ben-Avraham, and S. Havlin, Phys. Rev. E 66, 036113
(2002).
12 J.-D. Noh, and H. Rieger, Phys. Rev. Lett. 92, 118701
(2004).
13 M. Karsai, R. Juhász, and F. Iglói, Phys. Rev. E73, 036116
(2006).
14 J.-D. Noh, Phys. Rev. E72, 056123 (2005).
15 A. Aleksiejuk, J.A. Holyst, and D. Stauffer, Physica A 310,
260 (2002).
16 M. Leone, A. Vazquez, A. Vespignani, and R. Zecchina,
Eur. Phys. J. B 28, 191 (2002); S.N. Dorogovtsev, A.V.
Goltsev, and J.F.F. Mendes, Phys. Rev. E 66, 016104
(2002); G. Bianconi, Phys. Lett. A 303, 166 (2002).
17 F. Iglói and L. Turban, Phys. Rev. E66, 036140 (2002).
18 S. N. Dorogovtsev, A. V Goltsev, and J.F.F. Mendes, Eur.
Phys. J. B 38, 177 (2004).
19 C.V. Giuraniuc, J.P.L. Hatchett, J.O. Indekeu, M. Leone,
I. Perez Castillo, B. Van Schaeybroeck, and C. Van-
derzande, Phys. Rev. Lett. 95, 098701 (2005); Phys. Rev.
E 74, 036108 (2006).
20 M.A. Sumour, A.H. El-Astal, F.W.S. Lima, M.M. Shabat,
H.M. Khalil, e-print cond-mat/0612189.
21 M. Aizenman and J. Wehr, Phys. Rev. Lett. 62, 2503
(1989); errata 64, 1311 (1990).
22 K. Uzelac, A. Hasmy, and R. Jullien, Phys. Rev. Lett. 74,
422 (1995).
23 H.G. Ballesteros, L.A. Fernández, V. Mart̀ın-Mayor, A.
Muñoz Sudupe, G. Parisi, and J.J. Ruiz-Lorenzo, Phys.
Rev. B 61, 3215 (2000).
24 C. Chatelain, B. Berche, W. Janke, and P.-E. Berche,
Phys. Rev. E64, 036120 (2001); W. Janke, P.-E. Berche,
C. Chatelain, and B. Berche, Nuclear Physics B 719 275
(2005).
25 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Eu-
rophys. Lett. 70, 733 (2005).
26 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Phys.
Rev. E73, 026126 (2006).
27 J.-Ch. Anglès d’Auriac et al., J. Phys. A35, 6973 (2002);
J.-Ch. Anglès d’Auriac, in New Optimization Algorithms
in Physics, edt. A. K. Hartmann and H. Rieger (Wiley-
VCH, Berlin 2004).
28 R. Juhász, H. Rieger, and F. Iglói, Phys. Rev. E64, 056122
(2001).
29 P.W. Kasteleyn and C.M. Fortuin, J. Phys. Soc. Jpn. 46
(suppl.), 11 (1969).
http://arxiv.org/abs/cond-mat/0612189
30 F.Y. Wu, Rev. Mod. Phys. 54, 235 (1982).
31 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Phys.
Rev. E 69, 056112 (2004).
32 M. Grötschel, L. Lovász, A. Schrijver, Combinatorica 1
169-197 (1981).
33 J.-Ch. Anglès d’Auriac and F. Iglói, Phys. Rev. Lett. 90,
190601 (2003).
34 P. Erdős and A. Rényi, Publ. Math. Debrecen 6, 290
(1959); Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
35 C. Monthus, and T. Garel, Eur. Phys. J. B 48, 393 (2005).
36 S. Wiseman and E. Domany, Phys Rev E 52, 3469 (1995).
37 A. Aharony, A.B. Harris, Phys Rev Lett 77, 3700 (1996).
38 F. Pázmándi, R.T. Scalettar and G.T. Zimányi, Phys. Rev.
Lett. 79, 5130 (1997).
39 S. Wiseman and E. Domany, Phys. Rev. Lett. 81, 22 (1998)
; Phys Rev E 58, 2938 (1998).
40 A. Aharony, A.B. Harris and S. Wiseman, Phys. Rev. Lett.
81, 252 (1998).
41 J. T. Chayes et al., Phys. Rev. Lett. 57, 299 (1986).
42 D.S. Fisher, Phys. Rev. B 51, 6411 (1995).
43 F. Iglói, Y.-C. Lin, H. Rieger, and C. Monthus, (unpub-
lished).

  We consider the ferromagnetic large-$q$ state Potts model in complex evolving
networks, which is equivalent to an optimal cooperation problem, in which the
agents try to optimize the total sum of pair cooperation benefits and the
supports of independent projects. The agents are found to be typically of two
kinds: a fraction of $m$ (being the magnetization of the Potts model) belongs
to a large cooperating cluster, whereas the others are isolated one man's
projects. It is shown rigorously that the homogeneous model has a strongly
first-order phase transition, which turns to second-order for random
interactions (benefits), the properties of which are studied numerically on the
Barab\'asi-Albert network. The distribution of finite-size transition points is
characterized by a shift exponent, $1/\tilde{\nu}'=.26(1)$, and by a different
width exponent, $1/\nu'=.18(1)$, whereas the magnetization at the transition
point scales with the size of the network, $N$, as: $m\sim N^{-x}$, with
$x=.66(1)$.

Rounding of first-order phase transitions and optimal cooperation in scale-free
networks
M. Karsai,1,2 J-Ch. Anglès d’Auriac,2 and F. Iglói3, 1
Institute of Theoretical Physics, Szeged University, H-6720 Szeged, Hungary
Centre de Recherches sur les Trés Basses Températures, B. P. 166, F-38042 Grenoble, France
Research Institute for Solid State Physics and Optics, H-1525 Budapest, P.O.Box 49, Hungary
(Dated: November 20, 2018)
We consider the ferromagnetic large-q state Potts model in complex evolving networks, which is
equivalent to an optimal cooperation problem, in which the agents try to optimize the total sum
of pair cooperation benefits and the supports of independent projects. The agents are found to be
typically of two kinds: a fraction of m (being the magnetization of the Potts model) belongs to a
large cooperating cluster, whereas the others are isolated one man’s projects. It is shown rigorously
that the homogeneous model has a strongly first-order phase transition, which turns to second-order
for random interactions (benefits), the properties of which are studied numerically on the Barabási-
Albert network. The distribution of finite-size transition points is characterized by a shift exponent,
1/ν̃′ = .26(1), and by a different width exponent, 1/ν′ = .18(1), whereas the magnetization at the
transition point scales with the size of the network, N , as: m ∼ N−x, with x = .66(1).
I. INTRODUCTION
Complex networks have been used to describe the
structure and topology of a large class of systems in dif-
ferent fields of science, technics, transport, social and
political life, etc, see Refs.1,2,3,4 for recent reviews. A
complex network is represented by a graph5, in which the
nodes stand for the agents and the edges denote the possi-
ble interactions. Realistic networks generally have three
basic properties. The average distance between the nodes
is small, which is called the small-world effect6. There is a
tendency of clustering and the degree-distribution of the
edges, P (k), has a power-law tail, PD(k) ≃ Ak
−γ , k ≫ 1.
Thus the edge distribution is scale free7, which is usually
attributed to growth and preferential attachment during
the evaluation of the network.
In reality there is some sort of interaction between the
agents of a network which leads to some kind of coop-
erative behavior in macroscopic scales. One throughly
studied question in this field is the spread of infections
and epidemics in networks8,9,10, which problem is closely
related to another non-equilibrium processes, such as
percolation11, diffusion12, the contact process13 or the
zero-range process14, etc. In another investigations one
considers simple magnetic models15,16,17,18,19, in which
the agents are represented by classical (Ising or Potts)
spin variables, the interactions are described by ferro-
magnetic couplings, whereas the temperature plays the
rôle of a disordering field.
In theoretical investigations of the cooperative behav-
ior one usually resort on some kind of approximations.
For example the sites of the networks are often consid-
ered uncorrelated, which is generally not true for evolv-
ing networks, such as the Barabási-Albert (BA) network.
However this effect is expected to be irrelevant, as far as
the singularities in the system are considered. Also the
simple mean-field approach could lead to exact results
due to long-range interactions in the networks, which has
been checked by numerical simulations15 and by another,
more accurate theoretical methods19 (Bethe-lattice ap-
proach, replica method, etc.). In these calculations the
critical behavior of the network is found to depend on the
value of the degree exponent, γ. For sufficiently weakly
connected networks with γ > γu (γu = 5 for the Ising
model) there are conventional mean-field singularities. In
the intermediate or unconventional mean-field regime, for
γu > γ > γc, the critical exponents are γ dependent. Fi-
nally, for γ ≤ γc, when the average of k
2, defined by
〈k2〉 =
PD(k)k
2dk, as well as the strength of the aver-
age interaction becomes divergent the scale-free network
remains in the ordered state at any finite temperature.
Since γc = 3, in realistic networks with homogeneous
interactions always this type of phenomena is expected
to occur. In weighted networks, however, in which the
strengths of the interaction is appropriately rescaled with
the degrees of the connected vertices, γc is shifted to
larger values and therefore the complete phase-transition
scenario can be tested13,19. We note that the properties
of the phase transitions are generally different for undi-
rected (as we consider here) and directed networks20.
In several models the phase transition in regular lat-
tices is of first order, such as for the q-state Potts model
for sufficiently large value of q. Putting these models on a
complex network the inhomogeneities of the lattice play
the rôle of some kind of disorder and it is expected that
the value of the latent heat is reduced or even the tran-
sition is smoothened to a continuous one. This type of
scenario is indeed found in a mean-field treatment17, in
which the transition is of first-order for γ > γ(q) and be-
comes continuous for γc < γ < γ(q), where 3 < γ(q) < 4.
On the other hand in an effective medium Bethe lattice
approach one has obtained γ(q) = 3, thus the unconven-
tional mean-field regime is absent in this treatment18.
The interactions considered so far were homogeneous,
however, in realistic situations the disorder is inevitable,
which has a strong influence on the properties of the
http://arxiv.org/abs/0704.1538v1
phase transition. In regular lattices and for a second-
order transition Harris-type relevance-irrelevance crite-
rion can be used to decide about the stability of the pure
system’s fixed point in the presence of weak disorder. On
the contrary for a first-order transition such type of cri-
terion does not exist. In this case rigorous results asserts
that in two dimensions (2d) for any type of continuous
disorder the originally first order transition softens into a
second order one21. In three dimensions there are numer-
ical investigations which have shown22,23,24,25,26 that this
kind of softening takes place only for sufficiently strong
disorder.
In this paper we consider interacting models with ran-
dom interactions on complex networks and in this way we
study the combined effect of network topology and bond
disorder. The particular model we consider is the ran-
dom bond ferromagnetic Potts model (RBPM) for large
value of q. This model besides its relevance in ordering-
disordering phenomena and phase transitions has an
exact relation with an optimal cooperation problem27.
This mapping is based on the observation that in the
large-q limit the thermodynamic properties of the sys-
tem are dominated by one single diagram28 of the high-
temperature expansion29 and its calculation is equiva-
lent to the solution of an optimization problem. This
optimization problem can be interpreted in terms of co-
operating agents which try to maximize the total sum of
benefits received for pair cooperations plus a unit sup-
port which is paid for each independent projects. For a
given realization of the interactions the optimal state is
calculated exactly by a combinatorial optimization algo-
rithm which works in strongly polynomial time27. The
optimal graph of this problem consists of connected com-
ponents (representing sets of cooperating agents) and
isolated sites and its temperature (support) dependent
topology contains information about the collective be-
havior of the agents. In the thermodynamic limit one
expects to have a sharp phase transition in the system,
which separates the ordered (cooperating) phase with a
giant clusters from a disordered (non-cooperating) phase,
having only clusters of finite extent.
The structure of the paper is the following. The model
and the optimization method used in the study for large
q is presented in Sec. II. The solution for homogeneous
non-random evolving networks can be found in Sec. III,
whereas numerical study of the random model on the
Barabási-Albert network is presented in Sec. IV. Our
results are discussed in Sec. V.
II. THE MODEL AND ITS RELATION WITH
OPTIMAL COOPERATION
The q-state Potts model30 is defined by the Hamilto-
nian:
H = −
〈i,j〉
Jijδ(σi, σj) (1)
in terms of the Potts-spin variables, σi = 0, 1, · · · , q − 1.
Here i and j are sites of a lattice, which is represented by
a complex network in our case and the summation runs
over nearest neighbors, i.e. pairs of connected sites.
The couplings, Jij > 0, are ferromagnetic and they
are either identical, Jij = J , which is the case of homo-
geneous networks, or they are identically and indepen-
dently distributed random variables. In this paper we
use a quasi-continuous distribution:
P (Jij) =
1 + ∆
2i− l − 1
− Jij
which consists of large number of l equally spaced discrete
values within the range J(1 ± ∆/2) and 0 ≤ ∆ ≤ 2
measures the strength of disorder.
For a given set of couplings the partition function of
the system is convenient to write in the random cluster
representation29 as:
qc(G)
qβJij − 1
where the sum runs over all subset of bonds, G and c(G)
stands for the number of connected components of G. In
Eq. (3) we use the reduced temperature, T → T ln q and
its inverse β → β/ ln q, which are of O(1) even in the
large-q limit31. In this limit we have qβJij ≫ 1 and the
partition function can be written as
qφ(G), φ(G) = c(G) + β
Jij (4)
which is dominated by the largest term, φ∗ = maxG φ(G).
Note that this graph, which is called the optimal set,
generally depends on the temperature. The free-energy
per site is proportional to φ∗ and given by −βf = φ∗/N
where N stands for the number of sites of the lattice.
As already mentioned in the introduction the optimiza-
tion in Eq. (4) can be interpreted as an optimal coopera-
tion problem27 in which the agents, which cooperate with
each other in some projects, form connected components.
Each cooperating pair receives a benefit represented by
the weight of the connecting edge (which is proportional
to the inverse temperature) and also there is a unit sup-
port to each component, i.e. for each projects. Thus by
uniting two projects the support will be reduced but at
the same time the edge benefits will be enhanced. Finally
one is interested in the optimal form of cooperation when
the total value of the project grants is maximal.
In a mathematical point of view the cost-function in
Eq. (4), −φ(G), is sub-modular32 and there is an effi-
cient combinatorial optimization algorithm which calcu-
lates the optimal set (i.e. set of bonds which minimizes
the cost-function) exactly at any temperature in strongly
polynomial time27. In the algorithm the optimal set is
calculated iteratively and at each step one new vertex of
the lattice is taken into account. Having the optimal set
at a given step, say with n vertices, its connected compo-
nents have the property to contain all the edges between
their sites. Due to the submodularity of −φ(G) each con-
nected component is contracted into a new vertex with
effective weights being the sum of individual weights in
the original representation. Now adding a new vertex one
should solve the optimization problem in terms of the ef-
fective vertices, which needs the application of a standard
maximum flow algorithm, since any contractions should
include the new vertex. After making the possible new
contractions one repeats the previous steps until all the
vertices are taken into account and the optimal set of the
problem is found.
This method has already been applied for 2d31,33 and
3d25,26 regular lattices with short range random inter-
actions. As a general result the optimal graph at low
temperatures is compact and the largest connected sub-
graph contains a finite fraction of the sites, m(T ), which
is identified by the orderparameter of the system. In the
other limit, for high temperature, most of the sites in the
optimal set are isolated and the connected clusters have
a finite extent, the typical size of which is used to define
the correlation length, ξ. Between the two phases there is
a sharp phase transition in the thermodynamic limit, the
order of which depends on the dimension of the lattice
and the strength of disorder, ∆.
In the following the optimization problem is solved ex-
actly for homogeneous evolving networks in Sec.III and
studied numerically in random Barabási-Albert networks
in Sec.IV.
III. EXACT SOLUTION FOR HOMOGENEOUS
EVOLVING NETWORKS
In regular d-dimensional lattices the solution of the
optimization problem in Eq. (4) is simple, since there are
only two distinct optimal sets, which correspond to the
T = 0 and T → ∞ solutions, respectively. For T <
Tc(0) it is the fully connected diagram, E, with a free-
energy: −βNf = 1 + NβJd and for T > Tc(0) it is the
empty diagram, Ø, with −βNf = N . In the proof we
make use of the fact, that any edge of a regular lattice,
e1, can be transformed to any another edge, e2, through
operations of the automorphy group of the lattice. Thus
if e1 belongs to some optimal set, then e2 belongs to
an optimal set, too. Furthermore, due to submodularity
the union of optimal sets is also an optimal set, from
which follows that at any temperature the optimal set
is either Ø or E. By equating the free energies in the
two phases we obtain for the position of the transition
point: Tc(0) = Jd/(1 − 1/N) whereas the latent heat is
maximal: ∆e/Tc(0) = 1− 1/N .
In the following we consider the optimization problem
in homogeneous evolving networks which are generated
by the following rules:
• we start with a complete graph with 2µ vertices
• at each timestep we add a new vertex
• which is connected to µ existing vertices.
In definition of these networks there is no restric-
tion in which way the µ existing vertices are selected.
These could be chosen randomly, as in the Erdős-Rényi
model34, or one can follow some defined rule, like the
preferential attachment in the BA network7. In the
following we show that for such networks the phase-
transition point is located at Tc(0) = Jµ and for T <
Tc(0) (T > Tc(0)) the optimal set is the fully connected
diagram (empty diagram), as for the regular lattices.
Furthermore, the latent heat is maximal: ∆e/Tc(0) = 1.
In the proof we follow the optimal cooperation
algorithm27 outlined in Sec.II, and in application of the
algorithm we add the vertices one by one in the same or-
der as in the construction of the network. First we note,
that the statement is true for the initial graph, which is a
complete graph, thus the optimal set can be either fully
connected, having a free-energy: −β2µf = 1 + µ(2µ −
1)βJd, or empty, having a free-energy: −β2µf = 2µ,
thus the transition point is indeed at T = Tc(0). We
suppose then that the property is satisfied after n steps
and add a new vertex, v0. Here we investigate the two
cases, T ≤ Tc(0) and T ≥ Tc(0) separately.
• If T ≤ Tc(0), then according to our statement all
vertices of the original graph are contracted into
a single vertex, s, which has an effective weight,
µ × J/T > µJ/Tc(0) = 1, to the new vertex v0.
Consequently in the optimal set s and v0 are con-
nected, in accordance with our statement.
• If T ≥ Tc(0), then all vertices of the original graph
are disconnected, which means that for any subset,
S, having ns ≤ n vertices and es edges one has:
ns ≥ esJT + 1. Let us denote by µs ≤ µ the
number of edges between v0 and the vertices of S.
One has µsJ/T ≤ µJ/T ≤ µJ/Tc(0) = 1, so that
for the composite S+ v0 we have: ns+1 ≥ esJT +
1+µsJ/T , which proves that the vertex v0 will not
be connected to any subset S and thus will not be
contracted to any vertex.
This result, i.e. a maximally first-order transition of
the large-q state Potts model holds for a wide class of
evolving networks, which satisfy the construction rules
presented above. This is true, among others, for ran-
domly selected sites, for the BA evolving network which
has a degree exponent γ = 3 and for several generaliza-
tions of the BA network1 including nonlinear preferential
attachment, initial attractiveness, etc. In these latter
network models the degree exponent can vary in a range
of 2 < γ < ∞. It is interesting to note that for uncorre-
lated random networks with a given degree distribution
the q-state Potts model is in the ordered phase17,18 for
any γ ≤ 3. This is in contrast to evolving networks in
which correlations in the network sites results in the ex-
istence of a disordered phase for T > Tc(0), at least for
large q.
3.12.92.72.5
Tc(∞)
N=256
N=512
N=1024
N=2048
N=4096
 0  0.5  1  1.5  2  2.5  3
∆=0.2
∆=0.8
∆=1.4
∆=2.0
FIG. 1: (Color online) Temperature dependence of the av-
erage magnetization in a BA network of N = 1024 sites for
different strength of the disorder, ∆. At T = Tc(0) = 2 the
magnetization is independent of ∆ > 0 and its value is in-
dicated by an arrow. Inset: The average magnetization for
uniform disorder, ∆ = 2, close to the transition point for dif-
ferent finite sizes. The arrow indicates the critical point of
the infinite system.
IV. NUMERICAL STUDY OF RANDOM
BARABÁSI-ALBERT NETWORKS
In this section we study the large-q state Potts model
in the BA network with a given value of the connectiv-
ity, µ = 2, and the size of the network varies between
N = 26 to N = 212. The interactions are independent
random variables taken from the quasi-continuous distri-
bution in Eq.(2) having l = 1024 discrete peaks and we fix
J = 1. The advantage of using quasi-continuous distri-
butions is that in this way we avoid extra, non-physical
singularities, which could appear for discrete (e.q. bi-
modal) distributions31. For a given size we have gener-
ated 100 independent networks and for each we have 100
independent realizations of the disordered couplings.
A. Magnetization and structure of the optimal set
In Fig.1 the temperature dependence of the average
magnetization is shown for various strength of disorder,
∆, for a BA network ofN = 1024 sites. It is seen that the
sharp first-order phase transition of the pure system with
∆ = 0 is rounded and the magnetization has considerable
variation within a temperature range of ∼ ∆. The phase
transition seems to be continuous even for weak disorder.
Close to the transition point the magnetization curves
for uniform disorder (∆ = 2) are presented in the inset
of Fig.1, which are calculated for different finite systems.
Some features of the magnetization curves and the
properties of the phase transition can be understood
by analysing the structure of the optimal set. For low
enough temperature this optimal set is fully connected,
i.e. the magnetization is m = 1, which happens for
T < Tc(0)−∆. Indeed, the first sites with k = µ = 2 (i.e.
those which have only outgoing edges) are removed from
the fully connected diagram, if the sum of the connected
bonds is
i=1 Ji < T , which happens within the tem-
perature range indicated above. From a similar analysis
follows that the optimal set is empty for any finite system
for T > Tc(0) + ∆. The magnetization can be estimated
for t = T − (Tc(0)−∆) ≪ 1, and the correction is given
by: 1−m ∼ tµ. For the numerically studied model with
µ = 2 and ∆ = 2, we have m(T ) ≈ 1 − T 2/8, which is
indeed a good approximation for T < 1. In the tempera-
ture range Tc(0)−∆ < T < Tc(0)+∆ typically the sites
are either isolated or belong to the largest cluster. There
are also some clusters with an intermediate size, which
are dominantly two-site clusters for T < Tc(0) and their
fraction is less then 1%, as shown in Fig.2. The fraction
of two-site clusters for ∆ = 2 and T < Tc(0) = 2 can
be estimated as follows. First, we note that since they
are not part of the biggest cluster they can be taken out
of a fraction of p1 = 1 − m(T ) sites. Before being dis-
connected a two-site cluster has typically three bonds to
the biggest cluster, denoted by J1, J2 and J3. When it
becomes disconnected we have J1 + J2 + J3 < T , which
happens with a probability p2 = T
3/48. At the same
time the coupling within the two-site cluster should be
J4 > T , which happens with probability p3 = (2− T )/2.
Thus the fraction of two-site clusters is approximately:
n2 ≈ p1 × p2 × p3 ≈ T
5(2− T )/768, which describes well
the general behavior of the distribution in Fig.2.
In the temperature range T > Tc(0) the intermedi-
ate clusters have at least three sites and their fraction is
negligible, which is seen in Fig.2. Consequently the in-
termediate size clusters do not influence the properties of
the phase transition in the system. In the ordered phase,
T < Tc, the largest connected cluster contains a finite
fraction of m(T ) < 1 of the sites. We have analyzed the
degree distribution of this connected giant cluster in Fig.
3, which has scale-free behavior and for any tempera-
ture T < Tc there is the same degree exponent, γ = 3,
as for the original BA network. We note an interesting
feature of the magnetization curves in Fig.1 that cross
each other at the transition point of the pure system, at
Tc(0) = 2, having a value of m(Tc(0)) = 0.58, for any
strength of disorder. This property follows from the fact
that for a given realization of the disorder the optimal
set at T = Tc(0) only depends on the sign of the sum
of fluctuations of given couplings (c.f. some set of sites
is connected (disconnected) to the giant cluster only for
positive (negative) accumulated fluctuations) and does
not depend on the actual value of ∆ > 0.
We can thus conclude the following picture about the
evaluation of the optimal set. This is basically one large
connected cluster with N sites, immersed in the see of
isolated vertices. With increasing temperature more and
more loosely connected sites are dissolved from the clus-
ter, but for T < Tc we have N/N = m(T ) > 0 and the
N=128
N=256
N=512
N=1024
FIG. 2: (Color online) Fraction of intermediate size clusters
as a function of the temperature.
 0  1  2  3  4  5  6
ln(k)
T=1.957
T=2.464
T=2.738
T=2.816
T=2.894
T=2.972
T=3.030
T=3.089
T=3.128
FIG. 3: (Color online) Degree distribution of the largest
cluster at different temperatures in a finite network with
N = 2048. The dashed straight line indicates the range of
the critical temperature.
cluster has the same type of scale-free character as the
underlaying network. On the contrary above the phase-
transition point, Tc(0) + ∆ > T > Tc, the large clus-
ter has only a finite extent, N < ∞. The order of the
transition depends on the way how N behaves close to
Tc. A first-order transition, i.e. phase-cooexistence at
Tc does not fit to the above scenario. Indeed, as long
as N ∼ N the same type of continuous erosion of the
large cluster should take place, i.e. the transition is of
second order for any strength, ∆ > 0 of the disorder.
Approaching the critical point one expects the following
singularities: m(T ) ∼ (Tc − T )
β and N ∼ (T − Tc)
−ν′ .
Finally, at T = Tc the large cluster has N ∼ N
1−x sites,
with x = β/ν′.
B. Distribution of the finite-size transition
temperatures
The first step in the study of the critical singularities
is to locate the position of the phase-transition point.
In this respect it is not convenient to use the magne-
tization, which approaches zero very smoothly, see the
inset of Fig.1, so that there is a relatively large error by
calculating Tc in this way. One might have, however, a
better estimate by defining for each given sample, say
α, a finite-size transition temperature Tc(α,N), as has
been made for regular lattices25,26,31. For a network we
use a condition for the size of the connected component:
N (T ) ≃ AN1−x , in which x is the magnetization critical
exponent and A = O(1) is a free parameter, from which
the scaling form of the distribution is expected to be in-
dependent. The calculation is made self-consistently: for
a fixed A and a starting value of xs = x1 we have deter-
mined the distribution of the finite-size transition tem-
peratures and at their average value we have obtained
an estimate for the exponent, x = x2. Then the whole
procedure is repeated with xs = x2, etc. until a good
convergence is obtained. Fortunatelly the distribution
function, p(Tc, N), has only a weak x-dependence thus it
was enough to make only two iterations. We have started
with a logarithmic initial condition, N (T ) ≃ A lnN ,
which means formally x1 = 1 and we have obtained
x2 = .69. Then in the next step the critical exponents
are converged within the error of the calculation and they
are found to be independent of the value of A, which has
been set to be A = 1, 2 and 3.
The distribution of the finite-size critical temperatures
calculated with x2 = 0.69 and A = 3. are shown in Fig.4
for different sizes of the network. One can observe a
shift of the position of the maxima as well as a shrinking
of the width of the distribution with increasing size of
the network. The shift of the average value, T avc (N), is
asymptotically given by:
T avc (N)− Tc(∞) ∼ N
−1/ν̃′ , (5)
whereas the width, characterized by the mean standard
deviation, ∆Tc(N), scales with another exponent, ν
′, as:
∆Tc(N) ∼ N
−1/ν′ . (6)
Using Eq.(5) from a three-point fit we have obtained
ν̃′ = 3.8(2) and Tc(∞) = 3.03(2). We have determined
the position of the transition point in the infinite sys-
tem, Tc(∞), in another way by plotting the difference
T avc (N) − Tc(∞) vs. N in a log-log scale for different
values of Tc(∞), see Fig.5. At the true transition point
according to Eq.(5) there is an asymptotic linear depen-
dence, which is indeed the case around Tc(∞) = 3.03(2)
and the slope of the line is compatible with 1/ν̃′ = .27(1).
For the width exponent, ν′, we obtained from Eq.(6)
with two-point fit the estimate: ν′ = 5.6(2). With
these parameters the data in Fig.4 can be collapsed to
a master curve as shown in the inset of Fig.4. This
 1.8  2  2.2  2.4  2.6  2.8  3  3.2
N=128
N=256
N=512
N=1024
N=2048
N=4096
-3 -2 -1  0  1  2  3  4  5
FIG. 4: (Color online) Distribution of the finite-size transi-
tion temperatures for different sizes of the BA network. In-
set: scaling collapse of the data in terms of t = (Tc(N) −
(N))/∆Tc(N), using the scaling form in Eqs.(5) and (6)
with ν′ = 3.8(2), and ν̃′ = 5.6(2).
 4  4.5  5  5.5  6  6.5  7  7.5  8  8.5
ln(N)
Tc=3.17
Tc=3.14
Tc=3.11
Tc=3.08
Tc=3.05
Tc=3.03
Tc=3.01
Tc=2.98
Tc=2.96
FIG. 5: (Color online) Shift of the average finite-size transi-
tion temperatures, T av
(N) − Tc(∞), vs. N in a log-log scale
plotted for different values of Tc(∞). The lines connecting
the points at the same Tc(∞) are guide for the eye. At the
true transition point the asymptotic behavior is linear which
is indicated by a dotted straight line.
master curve looks not symmetric, at least for the fi-
nite sizes used in the present calculation, and can be
well fitted by a modified Gumbel distribution, Gω(−y) =
ωω/Γ(ω)(exp(−y−e−y))ω , with a parameter ω = 4.2. We
note that the same type of fitting curve has already been
used in Ref.35. For another values of the initial parame-
ter, A = 1 and 2 the estimates of the critical exponents
as well as the position of the transition point are found
to be stable and stand in the range indicated by the error
bars.
The equations in Eqs.(5) and (6) are generalizations
of the relations obtained in regular d-dimensional lat-
tices36,37,38,39,40 in which N is replaced by Ld, L being
the linear size of the system and therefore instead of ν′
and ν̃′ we have ν = ν′/d and ν̃ = ν̃′/d, respectively. Gen-
erally at a random fixed point the two characteristic ex-
ponents are equal and satisfy the relation41 ν′ = ν̃′ ≥ 2.
This has indeed been observed for the 2d31 and 3d25,26
random bond Potts models for large q at disorder induced
critical points. On the other hand if the transition stays
first-order there are two distinct exponents35,42 ν̃′ = 1
and ν′ = 2.
Interestingly our results on the distribution of the
finite-size transition temperatures in networks are differ-
ent of those found in regular lattices. Here the transition
is of second order but still there are two distinct critical
exponents, which are completely different of that at a
disordered first-order transition. For our system ν′ > ν̃′,
which means that disorder fluctuations in the critical
point are dominant over deterministic shift of the tran-
sition point. Similar trend is observed about the finite-
size transition parameters in the random transverse-field
Ising model43, the critical behavior of which is controlled
by an infinite disorder fixed point. In this respect the
RBPM in scale-free networks can be considered as a new
realization of an infinite disorder fixed point.
C. Size of the critical cluster
Having the distribution of the finite-size transition
temperatures we have calculated the size of the largest
cluster at T avc (N), which is expected to scale as
N [N, T avc (N)] ∼ N
1−x. Then from two-point fit we
have obtained an estimate for the magnetization expo-
nent: x = .66(1). We have also plotted N [N, T avc (N)] vs.
N1−x in Fig.6 for different initial parameters, A. Here
we have obtained an asymptotic linear dependence with
an exponent, x = .65(1), which agrees with the previous
value within the error of the calculation.
V. DISCUSSION IN TERMS OF OPTIMAL
COOPERATION
In this paper we have studied the properties of the
Potts model for large value of q on scale-free evolving
complex networks, such as the BA network, both for ho-
mogeneous and random ferromagnetic couplings. This
problem is equivalent to an optimal cooperation prob-
lem in which the agents try to optimize the total sum of
the benefits coming from pair cooperations (represented
by the Potts couplings) and the total sum of the support
which is the same for each cooperating projects (given by
the temperature of the Potts model). The homogeneous
problem is shown exactly to have two distinct states: ei-
ther all the agents cooperate with each other or there is
no cooperation between any agents. There is a strongly
first-order phase transition: by increasing the support
the agents stop cooperating at a critical value.
 0  10  20  30  40  50
[0 , 0]
 0  10  20  30  40  50
[0 , 0]
FIG. 6: (Color online) Size dependence of the critical cluster
at the average finite-size critical temperature as a function
of N1−x with x = .65. The date points for different initial
parameters, A, are well described by straight lines, which are
guides to the eye.
In the random problem, in which the benefits are ran-
dom and depend on the pairs of the cooprerating agents,
the structure of the optimal set depends on the value of
the support. Typically the agents are of two kinds: a frac-
tion of m belongs to a large cooperating cluster whereas
the others are isolated, representing one man’s projects.
With increasing support more and more agents are split
off the cluster, thus its size, as well as m is decreasing,
but the cluster keeps its scale-free topology. For a critical
value of the support m goes to zero continuously and the
corresponding singularity is characterized by non-trivial
critical exponents. This transition, as shown by the nu-
merically calculated critical exponents for the BA net-
work, belongs to a new universality class. One interesting
feature of it is that the distribution of the finite-size tran-
sition points is characterized by two distinct exponents
and the width of the distribution is dominated over the
shift of the average transition point, which is character-
istic at an infinite disorder fixed point43.
We thank for useful discussions with C. Monthus and
for previous cooperation on the subject with M.-T. Mer-
caldo. This work has been supported by the National
Office of Research and Technology under Grant No.
ASEP1111, by the Hungarian National Research Fund
under grant No OTKA TO48721, K62588, MO45596 and
M36803. M.K. thanks the Ministère Français des Affaires
Étrangères for a research grant.
1 R. Albert and A.L. Barabási, Rev. Mod. Phys. 74, 47
(2002).
2 S.N. Dorogovtsev and J.F.F. Mendes, Adv. Phys. 51, 1079
(2002).
3 S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Net-
works: From Biological Nets to the Internet and WWW
(Oxford University Press, Oxford, 2003)
4 M.E.J. Newman, SIAM Review 45, 167-256 (2003).
5 B. Bollobás, Random Graphs (Academic Press, London,
1985).
6 D.J. Watts and S.H. Strogatz, Nature (London) 393, 440
(1998).
7 A.L. Barabási and R. Albert, Science 286, 509 (1999).
8 R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett.
86, 3200 (2001); Phys. Rev. E 63, 066117 (2001).
9 M.E.J. Newman, Phys. Rev. E 66, 016128 (2002).
10 Z. Dezső, A.-L. Barabási, Phys. Rev. E 65, 055103 (2002).
11 D.S. Callaway, M.E.J. Newman, S.H. Strogatz, and D.J.
Watts, Phys. Rev. Lett. 85, 5468 (2000); R. Cohen, D.
ben-Avraham, and S. Havlin, Phys. Rev. E 66, 036113
(2002).
12 J.-D. Noh, and H. Rieger, Phys. Rev. Lett. 92, 118701
(2004).
13 M. Karsai, R. Juhász, and F. Iglói, Phys. Rev. E73, 036116
(2006).
14 J.-D. Noh, Phys. Rev. E72, 056123 (2005).
15 A. Aleksiejuk, J.A. Holyst, and D. Stauffer, Physica A 310,
260 (2002).
16 M. Leone, A. Vazquez, A. Vespignani, and R. Zecchina,
Eur. Phys. J. B 28, 191 (2002); S.N. Dorogovtsev, A.V.
Goltsev, and J.F.F. Mendes, Phys. Rev. E 66, 016104
(2002); G. Bianconi, Phys. Lett. A 303, 166 (2002).
17 F. Iglói and L. Turban, Phys. Rev. E66, 036140 (2002).
18 S. N. Dorogovtsev, A. V Goltsev, and J.F.F. Mendes, Eur.
Phys. J. B 38, 177 (2004).
19 C.V. Giuraniuc, J.P.L. Hatchett, J.O. Indekeu, M. Leone,
I. Perez Castillo, B. Van Schaeybroeck, and C. Van-
derzande, Phys. Rev. Lett. 95, 098701 (2005); Phys. Rev.
E 74, 036108 (2006).
20 M.A. Sumour, A.H. El-Astal, F.W.S. Lima, M.M. Shabat,
H.M. Khalil, e-print cond-mat/0612189.
21 M. Aizenman and J. Wehr, Phys. Rev. Lett. 62, 2503
(1989); errata 64, 1311 (1990).
22 K. Uzelac, A. Hasmy, and R. Jullien, Phys. Rev. Lett. 74,
422 (1995).
23 H.G. Ballesteros, L.A. Fernández, V. Mart̀ın-Mayor, A.
Muñoz Sudupe, G. Parisi, and J.J. Ruiz-Lorenzo, Phys.
Rev. B 61, 3215 (2000).
24 C. Chatelain, B. Berche, W. Janke, and P.-E. Berche,
Phys. Rev. E64, 036120 (2001); W. Janke, P.-E. Berche,
C. Chatelain, and B. Berche, Nuclear Physics B 719 275
(2005).
25 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Eu-
rophys. Lett. 70, 733 (2005).
26 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Phys.
Rev. E73, 026126 (2006).
27 J.-Ch. Anglès d’Auriac et al., J. Phys. A35, 6973 (2002);
J.-Ch. Anglès d’Auriac, in New Optimization Algorithms
in Physics, edt. A. K. Hartmann and H. Rieger (Wiley-
VCH, Berlin 2004).
28 R. Juhász, H. Rieger, and F. Iglói, Phys. Rev. E64, 056122
(2001).
29 P.W. Kasteleyn and C.M. Fortuin, J. Phys. Soc. Jpn. 46
(suppl.), 11 (1969).
http://arxiv.org/abs/cond-mat/0612189
30 F.Y. Wu, Rev. Mod. Phys. 54, 235 (1982).
31 M.-T. Mercaldo, J-Ch. Anglés d’Auriac, and F. Iglói, Phys.
Rev. E 69, 056112 (2004).
32 M. Grötschel, L. Lovász, A. Schrijver, Combinatorica 1
169-197 (1981).
33 J.-Ch. Anglès d’Auriac and F. Iglói, Phys. Rev. Lett. 90,
190601 (2003).
34 P. Erdős and A. Rényi, Publ. Math. Debrecen 6, 290
(1959); Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
35 C. Monthus, and T. Garel, Eur. Phys. J. B 48, 393 (2005).
36 S. Wiseman and E. Domany, Phys Rev E 52, 3469 (1995).
37 A. Aharony, A.B. Harris, Phys Rev Lett 77, 3700 (1996).
38 F. Pázmándi, R.T. Scalettar and G.T. Zimányi, Phys. Rev.
Lett. 79, 5130 (1997).
39 S. Wiseman and E. Domany, Phys. Rev. Lett. 81, 22 (1998)
; Phys Rev E 58, 2938 (1998).
40 A. Aharony, A.B. Harris and S. Wiseman, Phys. Rev. Lett.
81, 252 (1998).
41 J. T. Chayes et al., Phys. Rev. Lett. 57, 299 (1986).
42 D.S. Fisher, Phys. Rev. B 51, 6411 (1995).
43 F. Iglói, Y.-C. Lin, H. Rieger, and C. Monthus, (unpub-
lished).
