Invited Speakers

Computation of PageRank is usually made iteratively with a large use of computational time. In this paper we show that the PageRank can be expressed in terms of a wave function obeying a Schroedinger-like equation. In particular the topological disorder given by the unbalance of outgoing and ingoing links between pages, induces wave function and potential structuring. This allows to directly localize the pages with the largest score. Based on this analysis we also propose a model of growth of the WWW based on PageRank evaluation.

Statistical physics approaches are developed and applied successfully in recent years to understand the topology, robustness and function of complex networks. We will show how ideas and tools from percolation theory lead to novel results on the robustness, immunization strategies, optimal paths and minimum spanning trees. These results are relevant to many real world systems ranging from the Internet to social systems and climate. A novel percolation process which is characterized by fragmenting the network by removing a minimal number of nodes will be also discussed. This result is useful for efficient immunization strategies. We will also discuss how one can synthesize novel materials in which light can be localized by modifying the network topology.

In the talk, I first introduce molecular models of the origin of life and biological evolution with connected mutation-selection scheme proposed by Eigen [1] and the solution of a paradox about the origin of life with lethal mutants and truncated selection [2]. I then introduce Crow-Kimura model with parallel mutation-selection scheme [3]. Baake et al. mapped equations of the parallel model into a quantum spin model in a transverse magnetic field [4]. Recently, David B. Saakian and I did the similar mapping for the Eigen model [5]. Using Suzuki-Trottere formalism, we have studied statics and dynamics of the Eigen model and the Crow-Kimura model with the single-peak fitness function and found that the relaxation in the parallel model is faster than that in the connected model [5]. We have also studied both models with rather general fitness functions [5] and obtained error thresholds for various cases. For the Eigen model with nonzero degradation rate, we find a new phase which can represent virus quasi-species under attack by the immune system [6]. We also study the Eigen model with multiple peaks which can represent virus or cancer cells attached by drug or the immune systems [7]. Finally, we calculate the phase diagrams of a diploid biological evolution model and find new phases in which the final steady states depend on initial sequence distributions [8].

References

[1] M. Eigen, Naturwissenschaften 58, 465 (1971);
     M. Eigen, J. McCaskill, and P. Schuster, Adv. Chem. Phys. 75, 149 (1989).
[2] D. B. Saakian and C.-K. Hu, preprint. [3] J. F. Crow and M. Kimura, An Introduction to Population Genetics Theory (Harper Row, New York, 1970).
[4] E. Baake, M. Baake, and M. Wagner, Phys. Rev. Lett. 78, 559 (1997).
[5] D. B. Saakian and C.-K. Hu, Phys. Rev. E 69, 021319 (2004); ibid. 69, 046121 (2004);
     D. B. Saakian, C.-K. Hu and H. Khachatryan, ibid. 70, 041908 (2004).
[6] D. B. Saakian and C.-K. Hu, Proc. Natl. Acad. Sci. USA 103, 4935 (2006).
[7] D. B. Saakian, E. Muñoz, M. Yang, C.-K. Hu and M. W. Deem, Phys. Rev. E., 73, 041913 (2006).
[8] D. B. Saakian and C.-K. Hu, Phys. Rev. E 77, 061907 (2008).

During the past 10 years since the publication of pioneering papers on small-world and scale-free networks, explosive number of papers have been published in multidisciplinary fields. In my talks, I present how researches on complex networks have evolved during the past 10 years through the introduction of a growing co-authorship network in network science. Fractality is found to be distinct feature of the co-authorship network in the early stage of the evolution, which is hidden in the later stage. However, we find that it is still underneath the network structure as a skeleton when we remove inactive links. Dynamics on fractal scale-free networks is introduced, which proceeds slowly compared with the one on non-fractal scale-free networks.

Recent development in information and communication technology has enabled to study networks of social interactions of unprecedented size. Such systems include email or phone networks and e-communities. In contrast to the traditional, questionnaire-based investigations, in these cases a natural quatitative measure of the strength of the interactions is present (like the frequency or duration of calls) leading to weighted network representations. One important observation is that this strength of the interactions varies over many orders of magnitude. A natural conclusion is that the weights play important roles both in the evolution of the network topology and in the dynamics of the processes on the networks. Based on simple rules borrowed from sociology we construct a model [1], where the emergence of the community structure is a consequence of the interplay between topology and weights. We show that the model reflects well the observations made on a huge call network [2,3].

[1] J.M. Kumpula, J.-P. Onnela, J. Saramaki, K. Kaski, J. Kertesz: Emergence of communities in weighted networks, Phys. Rev. L ett. 99, 228701 (2007).
[2] J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.-L. Barabasi:Structure and tie strengths in mobile communication networks, PNAS 104, (2007).
[3] J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, M. Argollo de Menezes, K. Kaski, A.-L. Barabasi, J. Kertesz: Analysis of a large-scale weighted network of one-to-one human communication, New J. Phys. 9, 179 (2007).

We study how to detect, in complex networks, groups or components each of which consists of nodes sharing a similar connection pattern. Based on the mixture models and exploratory analysis set up by Newman and Leicht, we develop an algorithm that is applicable to a network with any degree distribution. The partitioning of a network suggested by this algorithm also applies to its complementary network. In general, groups of similar components are not necessarily identical with the communities in a community network: thus partitioning a network into groups of similar components provides additional information of the network structure. The proposed algorithm can also be used for community detection when the groups and communities overlap. By introducing a tunable parameter that controls the involved effects of heterogeneity, we can also investigate conveniently how the group structure can be coupled with the heterogeneity characteristics. In particular, an interesting example shows that a group partition can evolve into a community partition in some situations where the involved heterogeneity effects are tuned. The extension of this algorithm to weighted networks is discussed as well.

Cellular networks describe the relations between genes, proteins, metabolites and so on. The relations are physical, chemical or functional interactions. Comparison of cellular networks is one of the essential topics in systems biology, for example, one can gain deep insights into evolution by comparing networks of different species, or find cure solutions to diseases by comparing the diseased networks to healthy ones.

Structures and functions of cellular networks are bridged by dynamical processes occurring from micro- to macro- scales. To reach a reliable comparison we should compare simultaneously the patterns at different scales in a quantitative way. What is more, because we can not explore completely a cellular network, the resulting data are just some samples of the entire network. This incomplete exploration may also introduce noise to the resulting network, namely, artificial edges and losing edges and nodes.

Structures of networks determine the dynamical processes. The structures of complex networks can induce nontrivial properties to the physical processes occurring on them. The physical processes in turn can be used as probes to capture the structure properties. Well studied dynamical processes, such as the random walks and the Boolean dynamics, can be good candidates as probes.

In this talk we review briefly some of our recent works on this topic. The localization properties of electrons walking on networks are used to detect the structural characteristics of cellular networks. Totally eight protein-protein interaction networks are considered. It is found that the real world networks share some characteristics significantly different from some modeling networks.

It is becoming common practice to partition glass-forming liquids into two classes, based on the behavior of an Arrhenius plot, log(η) vs 1/T where η is the shear viscosity. Strong liquids correspond to linear behavior while fragile liquids to have up word-curvature. Here we analyze the existing experimental data of the transport parameters (the shear viscosity, the self-diffusion coefficients and the density-density time relaxations) of 76 glass forming liquids. We show the data are consistent with the onset of an Arrhenius behavior for T below a crossover temperature Tcross, where η ~ 10^3 Poise, well above the glass transition temperature TG where η is of the order of 10^13 Poise for all liquids we study. We also show that below Tcross the Stokes-Einstein relation (SE) D/T ~ η-1 is replaced by a fractional SE D/T ~ η^(-0.65). We also note that ηcross ~ 10^3 Poise is far below the glass transition ηcross ~ 10^13 Poise. An important goal of our study is that the fractional SE (the variation with respect to temperature of the transport properties of all these glass forming liquids) gives clear evidence of a remarkable degree of universality.

During the past decade or so, a considerable amount of research has been devoted to power law behaviors, particularly with regard to complex networks. However, when real data is analyzed, in most of the cases the power law trend holds only for an intermediate range of values; there is a power law breakdown in the distribution tails. Both the breakdown point and the tail functional form are of interest. Several explanations leading to various power law correction schemes have been provided for this phenomenon, such as finite size effects, network dilution, network growth constraints and different underlying dynamical regimes. Here we uncover a universal behavior of the way in which elements of a system are distributed according to their importance with respect to a given property, valid for the full range of values, regardless of whether or not a power law has previously been suggested [1]. The two parameter function we propose for these rank-ordered distributions is a generalization of the beta distribution and gives excellent fits to an impressive amount of very diverse phenomena, coming from the arts, social and natural sciences. The parameters have the potential of providing a criterion for rough classifications.

Based on our phenomenological observations we have studied several models that generate data following our distribution. In some cases, under appropriate limiting conditions, we obtain the generalized beta functional form as a stationary solution. From the modeling and data analysis we have identified relevant features such as conflicting dynamics and convergence of multiple heterogeneous processes. The ubiquity of this functional universality suggests that there must be a general underlying explanation, most probably of a statistical nature. Some progress has been attained in this respect.

[1] G. Martinez-Mekler, R. Alvarez Martinez, M. Beltran del Rio, R. Mansilla, P. Miramontes and G. Cocho, "Universality of Rank-Ordering Distributions in the Arts and Sciences", accepted in PLOSone (2009).

Social Harmony Equation (SHE) leads the social system to the evolution direction of social entropy increase by accumulation of "social combustion substances", i.e., the accumulation of microcosmic "basic particles" (individual) in social system from assimilate "basic social energy" to dissimilated one; meanwhile, the catalysis of "social combustion promoter" (social excitation energy) has enhanced the "social temperature" of disordering process of social system and completed the energy accumulation of social entropy increase that can generate the transition. Finally, ignited by the "social trigger threshold", the social system has completed the abrupt change from orderliness to disorderliness. The continuous variation of the above-mentioned three basic nonlinear processes has jointly composed the whole contents of social combustion theory. Under the restriction of such conditions of different time (t), different space (α) and different scale (β), it is finally explained as a comprehensive dynamics of social system deterioration.

The deviation from a Random Walk behavior in financial time series have been identified as Stylized Facts (SF) and are common to all markets. The main ones are that the fluctuations are much lager than those predicted from the standard economic theory (gaussian fluctuations), the clustering of volatility and a substantial nonstationarity of all properties. Many Agent Based Models have been proposed to explain these phenomena and many are indeed able to reproduce some of them. However the situation is still rather problematic becaus these models are typically rather complicated and with various ad hoc assumptions. This has prevented a systhematic study of these effects. We have tried therefore to define a workable Agent based Model (1), which would contain the essential elements, but in a mathematically simple and well defined framework. In addition we have considered some new important elements like the nonstationarity of the process with respect to the number of agents and the question of the self-organization. Namely why all markets evolve spontaneously towards the situation corresponding to the SF, considering that in all models this is restricted to a narrow range of parameters.

The SF are shown to correspond to finite size effects (with respect to time and to the number of agents N) which, however, can be active at different time scales. This implies that universality cannot be expected in describing these properties in terms of effecive critical exponents. The introduction of a threshold in the agents' action (small price movements lead to no action) triggers the self-organization towards the intermittent state corresponding to the SF. From these studies the herding phenomenon seems to be a crucial one beyond the standard theory as a triggering element of bubbles and crashs which develop spontaneously without a cause-effect relation. The model can also be used backwards to derive the strategies of the agents from the price time series. Other applications are under consideration like the problem of finite liquidity and the possibility that the reference fundamental price is subject to large fluctuations if one cnsiders that all markets are linked into a large network (2).

1. V.Alfi, L.Pietronero e A.Zaccaria, Minimal Agent Based Model for the Origin and Self-organization of Financial Markets, preprint 2008 (arXiv:0807.1888).
2. D.Delli Gatti, M.Gallegati, B.Greenwald, A.Russo, e J.E.Stiglitz, Financially Constrained Fluctuations in an Evolving Network Economy, NBER working paper, n.14112, June 2008.

The term 'systemic risk' commonly denotes the risk that a whole system consisting of many interacting agents fails. It is a macroscopic property which emerges from the nonlinear interactions of agents. In fact, 'systemic risk' already implies that the failure of the system cannot be fully explained by the failure of a single agent. Instead, one has to understand how such singular failures are able to spread through the whole system, affecting other agents. Here, in addition to network topology, dynamic mechanisms such as contagion (similar to epidemic processes or herding behavior), reinforcement (of prevailing trends), and redistribution (e.g. of load, stress, or debt) play a considerable role. The talk aims at categorizing some of the existing models in a common framework, first, and discussing a specific model of financial networks, afterwards, to elucidate the critical conditions for the breakdown of a system.

Exploring the topology of large complex networks is a considerable research challenge. The main difficulty of mapping these networks is related to their dynamically changing structure and self-organized growth. The physical structure of the Internet is one of the best examples demonstrating the complexity of this problem. In the absence of accurate Internet maps, the complex systems and networking research communities started new efforts (see for example www.netdimes.org) to map the topology in a distributed fashion. These use methods based on local views of the network from several points and merge these views in order to get an accurate global map. Local views are obtained by evaluating a certain number of paths to different destinations by using specific tools such as traceroute. In a typical traceroute study, a set of active sources deployed in the network run traceroute probes to a set of destination nodes. Each probe collects information on all the nodes and edges traversed along the path connecting the source to the destination, allowing the discovery of the network. To a first approximation the route obtained by traceroute-like probes is the shortest path between the two nodes.

In this talk we present new results for the link and node discovery probability and for the number of links and nodes discovered by traceroute-like shortest path based methods in complex networks. Our most important finding is that the link discovery probability in real networks is several order of magnitude lower than it is predicted by the mean-field approximation. As a consequence, the number of discovered nodes grows much slower than expected. We demonstrate this in simulated growing complex networks, real Internet data provided by DIMES and in traceroute measurements done in the PlanetLab infrastructure. The result can also be applied for Peer-to-Peer overlay networks where the average number of Internet routers affected by the P2P can be estimated.

First we formulate the link discovery probability for randomly placed source and destination pairs in generic complex networks. In this case we recover exactly the mean-field approximation introduced by Dall'Asta, Alvarez-Hamelin, Barrat, V'azquez, and Vespignani. In the mean-field approximation the discovery probability $\pi_i=1-\exp(-\varrho_T\varrho_Sb_i)$ depends on the product of density of traceroute sources $ \varrho_S$ and targets $\varrho_T$ and the betweenness $b_i$ of the link. We show that the number of discovered links $N_d$ scales with the product of numbers of source $N_S$ and target $N_T$ nodes $N_d\sim N_TN_S$.

Then we consider various types of growing complex networks. In case of {\em tree networks} we give an exact closed expression for the link discovery probability and for the number of discovered links. We show that neither the discovery probability nor the number of discovered links follows the predictions of the mean-field approximation. Instead, the discovery probabilty depends on the sum of densities of sources and targets $ \varrho_S+\varrho_T$ and the number of discovered nodes is proportional with the sum of target and source nodes $N_d\sim N_T+N_S$. In case the number of probes is small compared to the number of nodes in the network $N_S,N_T\ll N$ the relations are linear with logarithmic corrections.

In case of a broad range of non-tree like growing complex networks we carry out large scale numerical simulations. Both the real number of discovered nodes and the mean-field estimates are calculated and averaged for many realizations. A linear scaling in the number of discovered nodes is observed similar to the tree case. Some deviations are observed and explained for low number of probes.

A similar study is carried out for the DIMES router data available at www.netdimes.org. The results are very similar to those observed in growing networks with similar degree distribution and mean degree.

Finally traceroute data measured in PlanetLab is analyzed. Both classical and Paris traceroute studies are carried out among about 300 PlanetLab sites. The number of discovered IP addresses and number of discovered links is averaged for randomly selected subsets of the nodes. The results confirm again the new type of scaling. This study can be considered as a prototype model of P2P networks where the number of discovered links and nodes can be interpreted as links and routers involved in forming the overlay network.

The vertex-cover problem is a well-known nondeterministic polynomial complete (NP-complete) combinatorial optimization problem in theoretical computer science. Given a graph of vertices and edges, a vertex-cover consists of a subset U of vertices of the graph such that for each edge of the graph, at least one of its end vertices is in this subset U. The optimization version of the vertex-cover problem aims at constructing a vertex-cover of minimal size (one of the ground states). In this work, the vertex-cover problem on a completely random graph of mean vertex degree c is studied using the cavity method of statistical physics [1, 2, 3, 4]. We demonstrate that when the mean vertex degree c is larger than a critical value 2.718283, long-range correlations among the vertices of the random graph build up and they make a simple warning-propagation algorithm fail to converge [2]. In the parameter range of c>2.718283, the ground-state energy and entropy densities of the random vertex-cover problem are estimated by the zero-temperature first-step replica-symmetry-breaking (1RSB) cavity method [1,3,4]. An efficient survey-propagation algorithm is also implemented to construct optimal or near-optimal vertex-covers for single random graphs [3].

Many other NP-complete combinatorial optimization problems can also be studied by the same cavity method. This work also presents a physical interpretation on why the random vertex-cover problem becomes computationally difficult when c>2.718283.

[1] H. Zhou, Vertex cover problem studied by cavity method: Analytics and population dynamics, European Physical Journal B 32 (2003) 265-270.
[2] H. Zhou, Long range frustration in a spin-glass model of the random vertex-cover problem, Physical Review Letters 94 (2005) 217203.
[3] M. Weigt and H. Zhou, Message passing for vertex covers, Physical Review E 74 (2006) 046110.
[4] J. Zhou and H. Zhou, Ground-state entropy of the random vertex-cover problem, Physical Review E (2008, Rapid Communication, in press).