document: kauffman networks are disordered dynamical systems proposed by kauffman in 1969 as a model for genetic regulatory systems @xcite . 
   they attracted the interest of physicists in the 80 s @xcite , due to their analogy with the disordered systems studied in statistical mechanics , such as the mean field spin glass @xcite . 
   a dynamical phase transition was found and studied in the framework of mean field theory . in this and in the next paper 
   @xcite we deal with some structural properties of the networks that determine their attractors . in the present paper 
   we introduce the relevant elements , a notion that was suggested by flyvbjerg @xcite and flyvbjerg and kjaer @xcite , and we study their probability distribution . in the next one 
   we describe how the relevant elements are subdivided into asymptotically non communicating , independent modules . 
   the modular organization of random boolean networks was already suggested by kauffman @xcite , and it was used by flyvbjerg and kjaer to study analytically the attractors in @xmath4 networks . 
   we shall show that it is possible to describe the phase transition in random boolean networks in terms of the scaling of the number of relevant elements with system size , or in terms of a percolation transition in the set of the relevant elements . 
   the interest of this approach is that some consequences about the statistical properties of the attractors can be directly drawn .    in @xcite 
   we computed the properties of the attractors in the framework of the annealed approximation , introduced by derrida and pomeau @xcite , but we observed that the results of this approximation are reliable only when the system is chaotic enough , becoming exact for a random map . 
   the study of the relevant elements is complementary to this approach , and we sketch the lines of a new approximation scheme that works better in the frozen phase and on the critical line . 
   this region in parameter space is the most interesting one , since , according to kauffman , it reproduces some features of real cells , and is also the less understood , since neither approximate computations nor simulations @xcite give a precise picture of the properties of the attractors for systems of large size .    in next section 
   we define the model , discussing some old results together with open problems . in section 3 
   we define the relevant elements and in section 4 we give an approximate argument predicting the scaling of their number with system size in the different phases of the model . in the following section we present our numerical results , starting from the magnetization and the stable elements ( section 5.1 ) and then discussing the distribution of the relevant elements and its connection with the properties of the attractors , respectively in the chaotic phase ( section 5.2 ) and on the critical line ( section 5.3 ) . 
   the discussion of the results is postponed to our following paper @xcite , concerning the modular organization of the relevant elements on the critical line . 
   kauffman model is defined as follows . 
   we consider a set of @xmath1 elements @xmath5 and we associate to each of them a binary variable , @xmath6 . in the biological interpretation proposed by kauffman each element of the network 
   represents one gene and the binary variable @xmath7 represents its state of activation . 
   each element is under the control of @xmath8 elements , in the sense that its state at time @xmath9 is determined by the states at time @xmath10 of the @xmath8 control genes , @xmath11 and by a response function of @xmath8 binary variables , @xmath12 , that specifies how the element @xmath13 responds to the signals coming from its control variables . 
   the control elements are chosen in @xmath14 with uniform probability . 
   the response functions are also extracted at random , and it s believed that the properties of the model do not depend on the details of their distribution @xcite . 
   the rule most generally used in teh literature is the following : for each of the possible inputs @xmath15 we extract independently the value of @xmath16 , and we call @xmath17 the probability that @xmath16 is equal to 0 .    the dynamics of the system obey the equation    _ 
   i(t+1)=f_i(_j_1(i),_j_k(i ) ) . 
   this evolution law is deterministic , but the system is disordered because the control rules ( elements and functions ) are chosen at random from the beginning and kept fixed : thus we deal with a statistical ensemble of deterministic dynamical systems , and we are interested in the statistical properties of systems of large size . for finite @xmath1 , 
   every trajectory becomes periodic after a long enough transient time , and the configuration space is partitioned into the attraction basins of the different periodic orbits . 
   we are interested in the probability distributions of the number , the length and the size of the attraction basin of the periodic orbits , as well as in that of transient times . in the biological metaphor , 
   given a set of rules ( a genome ) an attractor represents a possible cellular type , its length represents the duration of the cellular cycle , and the number of attractors represents the number of cells that can be formed with a given genome . 
   it was observed already in the first simulations that two dynamical regimes are present , and that the line separating them has properties reminiscent of those of real cells @xcite . in the so - called chaotic phase ( large connectivity , @xmath17 close to @xmath18 ) the average length of the cycles increases exponentially with system size . 
   the limit case of the chaotic phase , @xmath19 , was already known as random map in the mathematical literature , and was studied in detail by derrida and flyvbjerg @xcite , who pointed out interesting analogies between this system and the mean field spin glass @xcite concerning the distribution of the weights of the attraction basins . in the frozen phase , 
   on the other hand , the typical length of the cycles does not increase with @xmath1 . 
   the limit case of this phase , @xmath4 , was analytically studied to some extent by flyvbjerg and kjaer @xcite , who introduced in that context the concept of relevant elements ( though without using this name ) .    the first description of this dynamical phase transition in terms of an order parameter was given by derrida and pomeau @xcite . 
   they studied the evolution of the hamming distance between configurations in the kauffman networks approximating it with a markovian stochastic process . 
   such approximation ( the so - called annealed approximation ) was then shown to be exact in the infinite size limit , concerning the average value of the distance @xcite . below a critical line in parameter space 
   the average distance goes to zero in the infinite size limit ( _ frozen phase _ ) and above it the distance goes to a finite value ( _ chaotic phase _ ) . 
   the position of the phase transition depends only on the parameter @xmath20 , representing the probability that the responses to two different signals are different one has @xmath21 , so its value is comprised between zero and 1/2 , but for @xmath4 @xmath20 can be taken as an independent parameter in [ 0,1 ] ] , and is given by the equation @xmath22 .    the properties of the attractors can be easily computed from the knowledge of the whole stationary distribution of the distance , and this can also be obtained within the annealed approximation @xcite , but the validity of this approximation in this more general case is not guaranteed . 
   comparison with simulations shows that the agreement is satisfactory in the chaotic phase , while the approximation fails on the critical line . 
   in the chaotic phase it is possible to compute the value of the exponent of the typical length of a cycle , @xmath23 , in good agreement with numerical results , but the distribution of cycle lengths is much broader than it is expected . 
   the annealed approximation predicts also that the distribution of the weights of the attraction basins is universal in the whole chaotic phase , and equal to the one obtained by derrida and flyvbjerg in the case of the random map @xcite . 
   the corrections to this prediction appear small , if any , even for @xmath24 . 
   finally , the number of different cycles in a network is expected to be linear in @xmath1 , but it is very hard to test numerically this prediction . 
   the annealed approximation makes also predictions about the critical line of the model @xcite . 
   it predicts that the properties of the attractors are universal on the critical line @xmath25 ( with the exceptions of the points @xmath26 and @xmath27 , which are not transition points ) . 
   in particular , the typical length of the cycles should increase as @xmath0 all along the critical line . 
   numerical results are not clear under this respect @xcite : it seems that the rescaled cycle length @xmath28 has a limit distribution if @xmath29 is small ( roughly , smaller than 2 ) but for larger values the distribution becomes broader and broader as @xmath1 increases @xcite , so that it is possible to define an effective length scale increasing much faster with system size ( as a stretched exponential ) . 
   the distribution of the number of cycles has exactly the same characteristics . 
   these results cast doubts on the validity of the biological analogy proposed by kauffman , that relies very much on the fact that in critical networks the typical number of cycles scales as @xmath0 , reminiscent of the fact that the number of cell types of multicellular organisms very far apart in the filogenetic tree scales as the square root of the number of the genes , and that in critical networks the typical length of the cycles increases as a power law of system size , also consistently with the behavior of cell cycles time . 
   thus it is interesting to understand how these distributions look like in the limit of very large systems . 
   another reason of interest of the present approach is that it allows to understand the limits of the annealed approximation . in our interpretation 
   the annealed approximation is valid as far as the system loses memory of the details of its evolution . 
   this , of course , does not happen if in a realization of a random network some structural properties that are able to influence its asymptotic dynamics emerge . 
   thus the approach presented here is complementary to the one used in @xcite . 
   let us start recalling the definition of the stable elements @xcite . 
   these are elements that evolve to a constant state , independent of the initial configuration . flyvbjerg defined them and computed their fraction @xmath30 using the annealed approximation , which becomes exact in the infinite size limit . 
   we now recall briefly , for future convenience , the main steps of this calculation . 
   let us suppose that an element is controlled by @xmath31 stable elements and @xmath13 stable ones 
   . then it will be stable if the control function does not depend on the unstable arguments when the stable arguments assume their fixed values . 
   otherwise it will be unstable . 
   when all the @xmath13 unstable elements are different ( this can always be taken to be the case if @xmath8 is finite and @xmath1 grows ) , the probability @xmath32 to choose a constant control function of @xmath13 binary variables is given by @xmath33 , with @xmath34 . in the framework of the annealed approximation , 
   extracting at random connections and response functions at each time step , we get the following equation for the fraction of variables that are stable at time @xmath10 : [ stable ] s(t+1)=(s(t))= _ i=0^k ki s(t)^k - i(1-s(t))^i p_i . 
   this equation can be shown to be exact in the infinite size limit . 
   the fixed point of this map ( which can be interpreted as a self - consistency equation for the fraction of stable variables ) has only the trivial solution @xmath35 in the frozen phase , in other words all the elements are stable except eventually a number increasing less than linearly with @xmath1 . in the chaotic phase 
   this solution becomes unstable and another solution less than 1 appears . 
   this happens when @xmath36 . 
   since @xmath37 ( it is just the probability that the response to two different signals are different ) this condition is equivalent to the condition obtained from the study of the hamming distance . 
   the existence of the stable variables is due to the finite connectivity of the network ( @xmath38 goes to zero very fast when @xmath8 increases ) . 
   these variables do not take part in the asymptotic dynamics . among the remaining unstable variables , 
   some are irrelevant for the dynamics , either because they do not send signals to any other variable , or because they send signals , but the response functions are independent of this signal when the stable variables have attained their fixed values . 
   the remaining variables , that are unstable and control some unstable variable , are what we call the relevant variables . 
   they are the only ones that can influence the long time behavior of the system .    to be more clear we now describe the algorithm that we used to identify the relevant variables . as a first step , we have to identify the stable variables . 
   these are the variables that assume the same constant state in every limit cycle , and identifying them is computationally very hard , but very simple in principle . 
   we then eliminate from the system the stable variables , reducing the response functions to functions of the unstable variables alone . some of the connections left are still irrelevant , and we have to eliminate them ( a connection between the elements @xmath13 and @xmath39 is irrelevant if the reduced response function @xmath40 does not depend on the argument @xmath41 for all the configurations of the remaining @xmath42 control variables ) . at this point 
   we iterate a procedure to eliminate the irrelevant variables . at each iteration 
   we eliminate the variables that do not send any signal to anyone of the variables that are left , until we remain with a set that can not be further reduced . 
   this is the set of the relevant variables . 
   measuring the number of relevant variables is computationally a very hard task . in order to identify the stable variables , in fact 
   , we should find all the cycles in the network , and , to be rigorous , we should simulate a number of trajectories of the same order of the number of configurations in the system . 
   of course this is not feasible and we run only 200 ( in some case 300 ) randomly chosen trajectories in every network . 
   thus we overestimate the number of stable elements . 
   nevertheless , the number of stable elements changes very little when we simulate more initial conditions and we think that the error that we make is not very large . 
   however , for every network we simulate some hundreds of trajectories and every trajectories has to be followed until the closing time . 
   this grows exponentially with system size in the chaotic phase . on the critical line 
   the typical closing time increase roughly as a power law of system size , but the distribution becomes broader and broader and the average closing time is more and more dominated by rare events . 
   the average depends thus on the number of samples generated and on the cutoff of the closing time , _ 
   i.e. _ the maximum time that we are disposed to wait to look for a cycle . to reduce the bias determined by the cutoff 
   , we had to run simulations lasting a time which increases roughly as a stretched exponential of system size on the critical line . 
   thus it is not possible to simulate systems of more than about one hundred elements in the chaotic phase and one thousands of elements on the critical line . 
   the mean field analysis @xcite shows that the fraction of relevant variables vanishes in the frozen phase and on the critical line , but does not tell how the number of relevant variables scales with @xmath1 as @xmath1 grows . 
   in order to clarify this point , we have to go beyond the mean field picture .    in the special case of @xmath4 , belonging to the frozen phase for every @xmath43 
   , there are detailed analytical results about the distribution of the relevant variables @xcite . 
   we propose here a rough argument that generalizes those results to the whole frozen phase and predicts that the typical number of relevant elements scales as @xmath0 on the critical line . though this argument is based on some approximations which we can not control , its results coincide for @xmath4 with the exact results by flyvbjerg and kjaer .    let us suppose that we add a new element to a system with @xmath1 elements , @xmath44 of which are relevant , while @xmath45 are stable and @xmath46 are indifferent , _ i.e. _ neither stable nor relevant . 
   the probability that the new element is relevant can be computed as a function of @xmath44 and @xmath45 , within some approximations that we are going to discuss in a while . 
   this probability is equal to the fraction of relevant elements in the system with @xmath47 elements , given that the relevant elements are @xmath44 and the stable ones are @xmath45 in the system with @xmath1 elements . 
   we can then average over @xmath44 and @xmath45 in order to get an equation connecting @xmath48 to the moments of the distribution of @xmath44 in the system with @xmath1 elements . since in the frozen phase and on the critical line 
   @xmath49 vanishes , it will be enough to consider the first two moments of the distribution , and the resulting equation can be solved asymptotically in @xmath1 . 
   the weakness of this approach lies on the assumptions that allow us to express the probability that the new element is relevant as a function of @xmath44 and @xmath45 , as it will become soon clear . 
   we compute now this probability . to this aim 
   , we need two steps :    1 .   as a first step 
   , we have to extract the @xmath8 control elements and the response function of the new element . as a consequence , 
   the new element can be stable , unstable or , if it receives an input from itself and this input is relevant in the sense discussed above , relevant . 
   the evaluation of the stability is perfectly equivalent to the mean field argument , but this stability is only temporary because it can be altered by the second step described below . 
   thus we call a new element that is stable ( unstable ) after the first step a _ temporarily _ stable ( unstable ) element . 
   then we have to send to the old system the signal of the new element . for each of the @xmath50 old control connections we have a probability @xmath51 that the connection is broken and the old control element is substituted by the new element . 
   this step perturbs the elements that control the new element and modifies its temporary stability . 
   we have no chance to take this into account , unless we use some drastic approximations .    in the second step 
   , three situations can occur .    1 . 
   if the new element was relevant in the first step , the new step can not modify this condition . 
   2 .   if the new element was unstable , it can not become stable through the feedback of its signal . 
   so it will be relevant or indifferent , depending on whether it sends an input to at least one relevant element or not . 
   3 .   if the new element was stable , its signal can destabilize some of the elements that control it and thus it can become relevant through a feedback mechanism , very hard to investigate analytically .    to compute the probability of case 3 , we should know the organization of the network in the very detail and not only the number of relevant and stable elements . 
   we propose to bypass this difficulty considering a different event : we will consider the new element relevant if it receives a signal from a previously relevant element or from itself . 
   this is the simplest way to get a closed equation for the average number of relevant elements . in this way we make two errors of opposite sign 
   : on one hand we overestimate the probability that a temporarily unstable element becomes relevant , on the other one we underestimate the probability that the new element is temporarily unstable and we neglect the probability that a temporarily stable element becomes relevant through a feedback loop .    we think that this method captures at least the qualitative behavior of the number of relevant elements . 
   we have then to compare the estimate given by this approximation to the simulations , because the approximation is not under control . 
   we present this argument because its results agree with both the numerical results and with the analytical calculations for @xmath4 and because we believe that it is possible to improve this method and to keep the approximation under control . 
   since we are interested in the frozen phase , where the fraction of unstable elements vanishes in the infinite size limit , we can neglect the eventuality that the new element is controlled by more than two elements that were relevant in the old system . 
   the results are consistent with this assumption . with these approximations 
   we obtain the following equation for the probability that the new element is relevant :    r_n+1=_n=0^n \{r_n = n } [k(n+1n+1 ) (1-n+1n+1)^k-1.[rilev ] + + ._2k2(n+1n+1)^2 (1-n+1n+1)^k-2 ] , where @xmath52 represents the probability that a boolean function of two arguments is not constant and in terms of @xmath20 is given by _ 2=1-p^4-(1-p)^4=(2 - 2 ) .    in the frozen phase it is sufficient to consider that the new element receives only one signal from the previously relevant elements . 
   so , posing @xmath53 , the equation for the new fraction of relevant elements , @xmath54 , is r_n+1cr_n+cn . 
   the first term represents a new element that receives a relevant signal from one of the previously relevant elements , the second term represents a new element that receives its own relevant signal . 
   thus the average number of relevant elements is independent on @xmath1 and its asymptotic value is r_n = c1-c.[froz ]    this number diverges on the critical line @xmath55 . in this case 
   , we have to consider also the eventuality that the new element receives a signal from two of the previously relevant elements . 
   expanding to the second order in @xmath56 , and using the fact that @xmath57 , we get the equation r_n+1r_n - (k-14k ) r^2_n+1n , whence , in the asymptotic regime where the variations of @xmath58 are of order @xmath59 , we finally get r^2_n(k-14k)1n . 
   this means that the scale of the number of relevant elements grows , on the chaotic phase , as @xmath0 . 
   we stress here that these computations are valid because of the finite connectivity of the system . 
   if we perform the limit @xmath19 on the above result , we get that the scale of the number of relevant elements grow as @xmath60 . 
   if , instead , we apply the limit @xmath19 prior to the limit @xmath61 we get the trivial critical point @xmath62 , where all the elements are stable after one time step , while for every other @xmath20 value all the elements are relevant . 
   thus , the two limits do not commute . 
   in fact , the equation ( [ stable ] ) for the fraction of stable variables and all the computations performed in this section are valid only if we can neglect that the same element is chosen more than once to control a given element , _ 
   i.e. _ for @xmath63 .    the result ( [ froz ] ) coincides for @xmath4 with the analytical computation by flyvbjerg and kjaer @xcite , thus suggesting that the distribution of relevant elements is independent on @xmath1 in the whole frozen phase , and depends on the two parameters @xmath8 and @xmath20 only through their product . 
   this picture agrees with the results of the annealed approximation , which predicts that the distribution of the number of different elements in two asymptotic configurations is independent on @xmath1 and depends only on the product of the parameters @xmath8 and @xmath20 in the frozen phase @xcite . 
   our simulations confirm that on the critical line the number of relevant elements scales as @xmath0 ( see figure [ fig_ril4 ] ) . 
   also the annealed approximation is consistent with this result , since it predicts that the number of elements whose state is different in two asymptotic configurations has to be rescaled with @xmath0 on the critical line @xcite . on the other hand 
   the number of unstable elements grows much faster with @xmath1 ( numerically it is found that it goes as @xmath64 , see below ) but this discrepancy is only apparent , since the asymptotic hamming distance is related more to the number of relevant elements than to this quantity . 
   for later convenience ( see our next paper ) it is also interesting to compute the effective connectivity , defined as the average value of the relevant connections between relevant elements . 
   let us compute it by imposing the condition that the network has @xmath44 relevant elements . 
   the effective connectivity is equal to the average number of connections between the new element and the other relevant elements of the older system , with the condition that the new element is relevant . from equation ( [ rilev ] ) we have , at the leading order in @xmath65 :    [ ceff ] k_eff(r)= & & c(1-)^k-1 + 2_2k2()^2(1-)^k-2c(1-)^k-1+_2k2()^2(1-)^k-2 + & & 1+a(k , ) . 
   this equation shows that the effective connectivity minus 1 goes to zero as @xmath65 in the frozen phase ( where @xmath66 ) and on the critical line ( where @xmath67 ) . for a fixed system size , 
   the effective connectivity increases linearly with the number of relevant elements . 
   the distribution of this variable , shown in figure [ fig_magneti ] for @xmath24 and @xmath70 , has many peaks , corresponding to simple rational values . 
   this perhaps reflects the fact that the relevant elements are divided into asymptotically independent modules , so that a cycle can be decomposed into several independent shorter cycles . 
   this subject will be further discussed in our second paper . 
   our results have to be compared to the analytical work by derrida and flyvbjerg @xcite . 
   they defined the magnetization of element @xmath13 at time @xmath10 on a given network as the activity of the element at time @xmath10 averaged over many initial configurations and could compute analytically its stationary distribution , in the limit @xmath61 , using the annealed approximation , that can be shown to be exact for this purpose . 
   the picture they got is different from ours , in particular we see peaks much higher than theirs . 
   for instance the peak at @xmath71 , which gives information on the size of the stable core of the network , is about 10 times larger then expected , and the first moments of the magnetization , that can be computed analytically , are larger than the predicted values . 
   thus we performed other simulations that strongly suggest that these discrepancies are finite size effects , and we present an argument that explains their origin .    in order to investigate larger systems we had to change the definition of the magnetization . 
   the definition ( [ mag ] ) is numerically cumbersome , since the measure takes place only after that a cycle has been found , and this means , for chaotic systems , that we have to wait a time exponentially increasing with @xmath1 . 
   thus we neglected this condition and we measured the magnetization of the variable @xmath13 at time @xmath10 as the average activity of the variable with respect to different initial conditions ( this definition coincides with the one used by derrida and flyvbjerg ) . 
   for very large @xmath10 , when all trajectories have reached a limit cycle , this quantity tends to the asymptotic value    m_i=_w_m_i^,[magna]where @xmath72 is the weight of the basin of cycle @xmath69 and @xmath68 is defined in ( [ mag ] ) . 
   we observed that @xmath73 reaches a stationary value ( within some precision ) much earlier than the typical time at which the trajectories reach their limit cycles . at first sight 
   surprisingly , the time after which @xmath73 reaches its stationary distribution does decrease with system size instead of increasing ( see figure [ fig_score ] ) . 
   we measured the second and fourth moment of the magnetization in a system with @xmath24 and @xmath74 , and we found a large positive correction to the infinite size values computed by derrida and flyvbjerg @xcite . 
   the values found coincide within the statistical error with those obtained from equation ( [ mag ] ) for a system of small size for which we did an explicit comparison . 
   these values can be fitted to the sum of the infinite size value , that we got from @xcite , plus an exponentially decreasing term . 
   the exponent of the best fit turned out to be the same for both the moments that we measured : we found @xmath75 , and @xmath76 . 
   the measure of the magnetization allows to identify the stable elements as the elements with @xmath77 equal either to 0 or to 1 . 
   the two definitions of the magnetization gave roughly the same number of stable elements in the cases where we could compare the results , but with the second method we could consider much larger systems ( we recall that the difference between the two methods is that in the first case a cycle has been reached while in the second one the system is still in some transient configuration ) . 
   the second method was used only to study finite size effects , since it does not allow to identify the relevant elements ( see below ) . 
   both the methods overestimate the number of stable elements , since it could happen that an element appearing stable in our sample of trajectories ( some hundreds ) oscillates in a cycle that is not reached by any of them . 
   we checked that the results do not change qualitatively if we consider a larger number of trajectories . 
   the fraction of stable nodes measured in simulations with @xmath24 and @xmath1 ranging from 50 to 200 have been compared to the prediction of the mean field theory by flyvbjerg . 
   the networks with @xmath78 have a stable core about 10 times larger than the mean field value ( in this case we measured the magnetization using both the above definitions , while for larger systems only equation ( [ magna ] ) was used ) . 
   the corrections to the mean field value , that is exact in the infinite size limit , appear to decay exponentially with a rate identical , within statistical errors , to the decay rate of the corrections to the moments of the magnetization : we found @xmath79 . 
   for every size of the systems which we simulated the stable core is then much larger than it would be in an infinite system . on this ground 
   , we may expect very important finite size effects concerning the dynamical properties of the system . 
   summarizing , the distribution of the magnetization for finite systems has the following characteristic : 1 ) the asymptotic value is reached after a time that _ decreases _ with system size ; 2 ) the corrections to the infinite size values are very large ; and 3 ) these corrections decrease exponentially with system size . 
   these apparently strange finite size effects have a simple interpretation : they arise as a consequence of the periodic dynamic of the random networks . 
   the mean field values of the magnetization and of the stable core are computed within the annealed approximation without taking into account the fact that the asymptotic dynamic is periodic . as we proposed in @xcite , the existence of limit cycles 
   must be taken into account in the framework of the annealed approximation in this way : if at time @xmath10 all the configurations generated are different ( _ i.e. _ the trajectory is still open ) we treat the quantities of interest ( distance , magnetization or stable core ) as a markovian stochastic process ; if one configuration has been found twice ( the trajectory is closed ) we impose the condition that all quantities are periodic . 
   thus the master equation for the distribution for the number of stable variables is , in the framework of the annealed approximation :    & & \ { s(t+1)=s,o(t+1)s(t)=s , o(t)}= n s((s))^s(1-(s))^n - s(1-_n(s , t ) ) + & & \ { s(t+1)=s,s(t)=s , o(t)}= ns((s))^s(1-(s))^n - s_n(s , t ) + & & \ { s(t+1)=s,s(t)=s , } = _ ss , [ stable2 ] where @xmath80 is the number of stable elements , @xmath30 , @xmath81 stands for the condition that the trajectory is open at time @xmath10 ( no configuration has been visited twice ) , @xmath82 stands for the condition complementary to @xmath81 ( the trajectory has closed on a previously visited configuration ) and @xmath83 is the probability that a trajectory open at time @xmath10 and with @xmath45 stable elements at time @xmath9 closes at that time . 
   finally , @xmath84 is given by equation ( [ stable ] ) . 
   we do nt know how to compute @xmath83 , but it is clear that this is an increasing function of @xmath45 for fixed @xmath10 : the more elements are stable , the more it is likely that the trajectory closes . 
   the infinite size value of the stable core is given by equation ( [ stable ] ) , that represents the evolution of the most probable number of stable variables . 
   it is clear that the corrections to this value are positive , and that they go to zero as soon as the closing time becomes much larger than the time necessary for the stable core to reach its stationary value in an infinite system ( where all trajectories are still open ) . 
   thus we expect that these corrections vanish as a power law of the typical length of the cycles : in the chaotic phase this means that the finite size corrections due to this effect vanish exponentially with system size , as we observed simulating systems with @xmath24 and @xmath74 . 
   lastly , this argument implies that the time after which the distribution of the stable elements becomes stationary is shorter in an infinite system than in a small system , where the evolution of @xmath80 is coupled to the closure of the periodic orbits . 
   thus the correction of the annealed approximation to take into account the existence of periodic attractors can account for all the features of the finite size effects that we observed .      after having identified the stable elements we detect the relevant elements using the algorithm described in the second section and we study how this quantity influences the dynamical properties of the network . 
   the main results are that the average cycle length grows almost exponentially with the number of relevant variables in some range of this variable and the average weight of the attraction basins has apparently a non monotonic behavior versus the number of relevant variables . 
   this qualitative features are the same both in the chaotic phase and on the critical line , but the ranges of @xmath44 in which these things happen are quite different in the two cases . 
   we start discussing the situation in the chaotic phase . 
   the simulations were done generating at random @xmath85 sample networks and running 200 trajectories on each of them . 
   the parameters considered in this section are @xmath24 , @xmath74 and system size @xmath1 ranging from 30 to 60 elements . 
   figure [ fig_ril ] shows the density of the distribution of the fraction @xmath49 of relevant variables , @xmath86 . the density relative to the most probable value increases with system size , and it appears that @xmath49 tends to be delta - distributed in the infinite size limit , as it is expected on the ground of the annealed master equation ( [ stable2 ] ) . 
   we observe an excess of networks with very few relevant elements ( _ i.e. _ very many stable elements ) , consistently with the finite size effects discussed in last section . 
   this excess seems to disappear in the infinite size limit . 
   then we show the average length of the cycles in networks with @xmath44 relevant elements ( figure [ perril ] ) . 
   this quantity increases almost exponentially with @xmath44 when @xmath56 is large , while its behavior is different for small @xmath54 . 
   the crossover takes place at about @xmath87 . 
   thus the number of relevant elements turns out to have a very important influence on the typical length of the cycles    we have also measured the conditional distribution of the length of the cycles in networks with @xmath44 relevant elements . 
   when @xmath44 is close to @xmath1 the distribution decays as a stretched exponential with an exponent smaller than one , very close to the one found in the unconditioned distribution . 
   thus the deviation of the unconditioned distribution from the prediction of the annealed approximation , that predicts a much narrower distribution , is not a consequence of the existence of the relevant elements . 
   y_2=_w_^2 , where @xmath72 is the attraction basin of cycle @xmath89 . 
   we used the method proposed by derrida and flyvbjerg @xcite , that is based on the fact that @xmath88 is equal to the probability that two trajectories chosen at random end up on the same attractor .    from our data 
   ( not shown ) it appears that @xmath88 has a non monotonic behavior as a function of @xmath54 : for very small @xmath54 it decreases from the value 1 , corresponding to @xmath90 , reaches a minimum and rapidly increases . at large @xmath54 , @xmath88 does not seem to be correlated with @xmath54 ( at least within the statistical error , that is rather large ) . 
   we will see in the next paper that the decreasing behavior at small @xmath54 can be interpreted as an effect of the modular organization of kauffman networks . 
   we simulated systems with @xmath91 and the critical value @xmath92 . 
   systems size ranges from 120 to 1600 . concerning the statistical properties of the attractors , these networks have a behavior very similar to that of the more studied @xmath93 , @xmath74 networks @xcite .    in these networks 
   , the number of relevant elements appears to scale as @xmath0 , in agreement with the argument presented in section 4 . 
   the number of unstable elements , on the other hand , appears to scale as @xmath64 . 
   this implies that the probability to extract at random an element which is relevant , scaling as @xmath94 , is approximately proportional to the square of the probability to extract at random an element which is relevant ( @xmath95 ) . 
   these scaling laws can be observed both looking at the average quantities and looking at the whole distribution . 
   the average number of unstable variables is found to follow the power law @xmath96 , with @xmath97 . 
   we then define the rescaled variable @xmath98 , and we compare its probability density for various system sizes . as it can be seen in figure [ fig_unst ] the different curves superimpose within the statistical errors . 
   this suggests that @xmath99 has a well defined probability density in the infinite size limit , although our data are rather noisy to state this point without doubts . 
   we can distinguish in the distribution three different ranges with different characteristics : at vanishingly small values of @xmath99 ( ranging from @xmath100 up to @xmath101 ) the density decreases very fast . at intermediate values , roughly up to @xmath102 , it looks to decrease approximately as a power law with a small exponent ( the best fit exponents that we found range from 0.25 to 0.40 , showing some tendency to increase with system size ) . 
   asymptotically , for large @xmath99 , the best fit is a stretched exponential , @xmath103 , with an exponent compatible with @xmath104 for all the systems that with studied with @xmath1 larger than 240 . 
   the number of relevant variables was studied in a similar way . 
   its average value increases as a power law of @xmath1 , @xmath105 , with @xmath106 . 
   the rescaled variable @xmath107 looks to have a well defined distribution in the infinite size limit , as it is shown in figure [ fig_ril4 ] , where the probability density of @xmath108 is plotted for system sizes ranging from 120 to 1600 . for large @xmath109 the density of the distribution 
   is well fitted by a stretched exponential , @xmath110 , with the exponent @xmath111 compatible with the value @xmath112 for system size larger than 240 . 
   the average length of the cycles increases exponentially as a function of the number of relevant elements , for @xmath54 large , and more slowly for @xmath54 small , just as it happens in the chaotic phase . 
   figure [ fig_perril4 ] shows on a logarithmic scale the behavior of the average length of the cycles as a function of the rescaled number of relevant elements , @xmath107 , for different system sizes at the critical point @xmath91 , @xmath92 . 
   the average weight of the attraction basins , @xmath88 , has a non monotonic behavior as a function of the number of relevant elements , as it happens in the chaotic phase . 
   the value of @xmath113 is one for @xmath114 , then decreases to a minimum value and increases very slowly , as it is shown in figure [ fig_yril4 ] , where @xmath115 is plotted against @xmath107 , for @xmath91 , @xmath92 and different system sizes . 
   nevertheless , there are two important differences with respect to the chaotic phase : first , the range where @xmath113 is a decreasing function is much wider on the critical line than in the chaotic phase ; then , on the critical line the curves corresponding to a smaller @xmath1 value are lower , while in the chaotic phase the contrary holds . as a consequence , 
   if we average @xmath113 over @xmath44 on the critical line , we get a quantity vanishing in the infinite size limit @xcite , while the average weight of the attraction basins is finite and very close to the random map value in the chaotic phase @xcite . 
   this difference and the non monotonic @xmath44 behavior of @xmath113 have a clear interpretation in the framework of the modular organization of kauffman networks @xcite . 
   we thus postpone to that paper the discussion of our results . 
   kauffman ( 1969 ) , metabolic stability and epigenesis in random constructed genetic nets , _ j. theor . 
   _ * 22 * , 437 - 467 . 
   kauffman ( 1993 ) , _ origins of order : self - organization and selection in evolution _ , oxford university press derrida b. and y. pomeau ( 1986 ) , random networks of automata : a simple annealed approximation , _ biophys . lett . _ * 1*(*2 * ) , 45 - 49 b. derrida and g. weisbuch ( 1986 ) , _ j. physique _ * 47 * 1297 . 
   hilorst and m. nijmajer ( 1987 ) , _ j. phys . 
   paris , * 48 * _ , 185 . 
   b. derrida and h. flyvbjerg ( 1986 ) , multivalley structure in kauffman s model : analogy with spin glasses , _ j.phys.a : math.gen._ * 19 * , l1003-l1008 h. flyvbjerg ( 1988 ) , an order parameter for networks of automata , _ 
   a : math.gen . _ * 21 * l955-l960 h. flyvbjerg , n.j . kjaer ( 1988 ) , exact solution of kauffman model with connectivity one , _ j.phys . a : math.gen . _ * 21*(*7 * ) , 1695 - 1718 m. mezard , g. parisi , m.a . 
   virasoro ( 1987 ) , _ spin glass theory and beyond _ , singapore : world scientific u. bastolla and g. parisi ( 1997 ) , the modular structure of kauffman networks , _ physica d _ u. bastolla and g. parisi ( 1996 ) , closing probabilities in the kauffman model : an annealed computation , _ physica d _ 98 , 1 . 
   u. bastolla and g. parisi ( 1996 ) , the critical line of kauffman networks , _ journal of theoretical biology _ , in press . 
   b. derrida , h. flyvbjerg ( 1986 ) , the random map model : a disordered model with deterministic dynamics , _ journal de physique _ * 48 * , 971 - 978 a. bhattacharijya and s. liang ( 1996 ) , power - law distribution in the kauffman net , _ physica d _ b. derrida and h. flyvbjerg ( 1987 ) , distribution of local magnetizations in random networks of automata , _ j.phys.a : math.gen._ * 20 * , l1107-l1112 .
summary: this is the first of two papers about the structure of kauffman networks . in this paper 
   we define the relevant elements of random networks of automata , following previous work by flyvbjerg @xcite and flyvbjerg and kjaer @xcite , and we study numerically their probability distribution in the chaotic phase and on the critical line of the model . 
   a simple approximate argument predicts that their number scales as @xmath0 on the critical line , while it is linear with @xmath1 in the chaotic phase and independent on system size in the frozen phase . 
   this argument is confirmed by numerical results . 
   the study of the relevant elements gives useful information about the properties of the attractors in critical networks , where the pictures coming from either approximate computation methods or from simulations are not very clear . 
   48 pt -1.5 truecm -1.2 truecm 16.5 cm 23 cm        @xmath2dipartimento di fisica , universit `` la sapienza '' , p.le aldo moro 2 , i-00185 roma italy    @xmath3hlrz , forschungszentrum jlich , d-52425 jlich germany    keywords : disordered systems , genetic regulatory networks ,    random boolean networks , cellular automata