A Law of Gravitation for Complex Networks

Inspiring Newton＇s law of universal gravitation and empirical studies, we propose a concept of virtual network mass and network gravitational force in complex networks. Then a network gravitational model for complex networks is presented. In the model, each node in the network is described with its position, edges （links） and virtual network mass. The proposed model is examined by experiments to show its potential applications.     

Macro-Behaviour of Agents＇ Opinion under Influence of an External Field

We propose a model to study the evolution of opinion under the influence of all external field on small world network. The maero-behaviour of agents＇ opinion and the relative change rate as time elapses are studied. The external field is found to play an important role in making the opinion s（t） balance or increase, and without the influence of the external field, the relative change rate γ（t） shows nonlinear increasing behaviour as time runs. What is more, this nonlinear increasing behaviour is independent of the initial condition, the strength of the external field and the time that we cancel the external field. The results may reflect some phenomena in our society, such as the function of the macro-control in China or the mass media in our society.     

Feedback and efficiency in limit order markets

A consistency criterion for price impact functions in limit order markets is proposed that prohibits chain arbitrage exploitation. Both the bid-ask spread and the feedback of sequential market orders of the same kind onto both sides of the order book are essential to ensure consistency at the smallest time scale. All the stocks investigated in Paris Stock Exchange have consistent price impact functions.     

Traffic dynamics based on a traffic awareness routing strategy on scale-free networks

By incorporating local traffic information into the shortest path routing strategy, we numerically investigate the effectiveness of the traffic awareness routing strategy for scale-free networks with different clustering. In order to characterize the efficiency of the packet-delivery process, we introduce an order parameter and an average transmission time that allow us to measure the network capacity by the critical value of phase transition from free flow to congestion. Compared with the shortest path routing protocol, the network capacity is greatly enhanced by the traffic awareness routing strategy. We also find that there exists an optimum value for the tunable parameter in the congestion awareness strategy. Moreover, simulation results show that the more clustered the network, the less efficient the packet-delivery process.     

Cross-impact balances: Applying pair interaction systems and multi-value Kauffman nets to multidisciplinary systems analysis

Cross-impact analysis is the name for a familiar method for multidisciplinary systems analysis in social sciences and management sciences, especially in technology foresight, technology assessment and scenario planning. A recently proposed form of cross-impact analysis, CIB, may be of interest for physicists, sociophysicists and complex network researchers because the CIB concept reveals considerable relations to some concepts of these research fields.This article describes the basics of CIB analysis framework, its applications in the social sciences, and its relations to the equilibrium points of pair interaction systems, random graphs, and generalized Kauffman nets.Therefore CIB can be seen as a merger of concepts originating in utterly different scientific fields. This may prove to be fruitful for both sides: For sociophysicists as an example of the application of complex network concepts in the social sciences and for cross-impact practitioners as a source of theoretical insights in the background of their tool.     

Evolutionary construction of geographical networks with nearly optimal robustness and efficient routing properties

Robust and efficient design of networks on a realistic geographical space is one of the important issues for the realization of dependable communication systems. In this paper, based on a percolation theory and a geometric graph property, we investigate such a design from the following viewpoints: (1) network evolution according to a spatially heterogeneous population, (2) trimodal low degrees for the tolerant connectivity against both failures and attacks, and (3) decentralized routing within short paths. Furthermore, we point out the weakened tolerance by geographical constraints on local cycles, and propose a practical strategy by adding a small fraction of shortcut links between randomly chosen nodes in order to improve the robustness to a similar level to that of the optimal bimodal networks with a larger degree for the network size N. These properties will be useful for constructing future ad hoc networks in wide-area communications.     

Is the topology of the Internet network really fit to sustain its function?

The Internet is one of the most interesting realizations of a “complex” network. As a non-supervised growing object, it allows the study of the selective pressure which drives the network to assume its current structure. The DIMES and the ROUTEVIEWS projects are ongoing projects aimed at evaluating the topological structure of the Internet (at the Autonomous System or AS grain-level) on the basis of different types of measurements. The topological analysis of the networks produced by the two projects has allowed us to infer a growth mechanism which has been used to build up synthetic networks with similar properties. These networks have been used as test-beds for the implementation of a model of traffic dynamics, with the aim of assessing the ability of the Internet’s topology to support the basic actions for data traffic handling. Results have been compared with those obtained by using a random network of similar size. The effects of some structural perturbations (arcs and nodes’ removal, traffic localization) have been also evaluated in terms of the induced variations of the network’s efficiency. The resulting scenario is consistent with the hypothesis that the structure of the Internet is only partially fit to host communication processes and that the intelligence of the TCP/IP protocol is partly needed to overcome some “structural” deficiencies.     

Model of opinion forming and voting

A simple model describing the dynamics of opinion forming in a two-party society is presented. Using a Monte Carlo simulation, we show what is the role played by the mobility of the electorate and the size of the groups within which opinions are exchanged. Each individual is characterized by its opinion and its susceptibility to the influence of others. We show what is the effect for a party to have a small percentage of supporters who will never change their mind. We determine when a party having at the beginning a smaller number of supporters, could nevertheless win democratic elections. The influence of an external random field (media) is also discussed.     

Decorrelation of networked communication flow via load-dependent routing weights

Clever assignments of link weights are able to change communication routes in such a way that loads are distributed almost evenly across a network. This is achieved by weight assignments based on the link load. As demonstrated for scale-free as well as synthetic Internet networks, they decorrelate the loads of the nodes and links from the network structure and increase the transport capacity of the network. For various Internet scans the increase of transport capacity amounts to a factor of around five when compared to shortest-path routing.     

Dynamics of traffic networks: From microscopic and macroscopic perspectives

Considering the microscopic characteristics (vehicle speed, road length etc.) of links and macroscopic behaviors of traffic systems, we derive the critical flow generation rate in scale-free networks. And the dynamics of traffic congestion is studied numerically in this paper. It is shown that the queue length increases with microscopic characteristics of links. Additionally, the critical flow generation rate decreases with increase of the network size N, maximum speed v_max and parameter τ. The significance of this finding is that, in order to improve the traffic environment, both the local information for the single link and behaviors of the whole network must be analyzed simultaneously in a traffic system design.     

Geographical Effects on Complex Networks

We investigate how the geographical structure of a complex network affects its network topology, synchronization and the average spatial length of edges. The geographical structure means that the connecting probability of two nodes is related to the spatial distance of the two nodes. Our simulation results show that the geographical structure changes the network topology. The synchronization tendency is enhanced and the average spatial length of edges is enlarged when the node can randomly connect to the further one. Analytic results support our understanding of the phenomena.     

A Non-Stationary Poisson Model for the Scaling of Urban Traffic Fluctuations

We investigate the traffic flow volume data on the time dependent activity of Beijing＇s urban road network. The couplings between the average flux and the fluctuations on individual links are shown to follow certain scaling laws and yield a wide variety of scaling exponents between 1/2 and 1. To quantitatively explain this interesting phenomenon, a non-stationary Poisson arriving model is proposed. The scaling property is interpreted as the result of the time- variation of the arriving rate of flux over the network, which nicely explicates the effect of aggregation windows, and provides a concise model for the dependence of scaling exponent on the external/internal force ratio.     

Research on Quantum Searching Algorithms Based on Phase Shifts

One iterative in Grover＇s original quantum search algorithm consists of two Hadamard-Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary φ = ψ（0 ≤, ψ≤ 27r）. Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.57π√M/N iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%     

The network of commuters in London

We have studied the directed and weighted network in which the wards of London are vertices and two vertices are connected whenever there is at least one person commuting to work from one ward to another. Remarkably the in-strength and in-degree distribution tail is a power law with exponent around −2, while the out-strength and out-degree distribution tail is exponential. We propose a simple square lattice model to explain the observed empirical behaviour.     

Quantum Partial Searching Algorithm of a Database with Several Target Items

Choi and Korepin [Quantum Information Processing 6（2007）243] presented a quantum partial search algorithm of a database with several target items which can find a target block quickly when each target block contains the same number of target items. Actually, the number of target items in each target block is arbitrary. Aiming at this case, we give a condition to guarantee performance of the partial search algorithm to be performed and the number of queries to oracle of the algorithm to be minimized. In addition, by further numerical computing we come to the conclusion that the more uniform the distribution of target items, the smaller the number of queries.     

Stochastic optimization of spin-glasses on cellular neural/nonlinear network based processors

Nowadays, Cellular Neural/Nonlinear Networks (CNN) are practically implemented in parallel, analog computers, showing a fast developing trend. It is important also for physicists to be aware that such computers are appropriate for implementing in an elegant manner practically important algorithms, which are extremely slow on the classical digital architecture. Here, CNN is used for optimization of spin-glass systems. We prove, that a CNN in which the parameters of all cells can be separately controlled, is the analog correspondent of a two-dimensional Ising type spin-glass system. Using the properties of CNN we show that one single operation on the CNN chip would yield a local minimum of the spin-glass energy function. By using this property a fast optimization method, similar to simulated annealing, can be built. After estimating the simulation time needed for this algorithm on CNN based computers, and comparing it with the time needed on normal digital computers using the classical simulated annealing algorithm, the results look promising: a speed-up of the order 10¹² is expected already at 50×50 lattice sizes. Hardwares realized nowadays are of 128×128 size. Also, there seem to be no technical difficulties adapting CNN chips for such problems and the needed local control of the parameters could be fully developed in the near future.     

Diffusive capture processes for information search

We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2% of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈T〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ=2.4. We also discuss the possible relationship between 〈T〉 and 〈k²〉, the second moment of the degree distribution of the networks.     

Network traffic behaviour near phase transition point

We explore packet traffic dynamics in a data network model near phase transition point from free flow to congestion. The model of data network is an abstraction of the Network Layer of the OSI (Open Systems Interconnect) Reference Model of packet switching networks. The Network Layer is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using the model we investigate spatio-temporal packets traffic dynamics near the phase transition point for various network connection topologies, and static and adaptive routing algorithms. We present selected simulation results and analyze them.     

Detrended Fluctuation Analysis of Traffic Data

Different routing strategies may result in different behaviour of traffic on internet. We analyse the correlation of traffic data for three typical routing strategies by the detrended fluctuation analysis （DFA） and lind that the aregree of correlation of the data can be divided into three regions, i.e. weak, medium, and strong correlation. The DFA scalings are constants in both the regions of weak and strong correlations but monotonically increase in the region of medium correlation. We suggest that it is better to consider the traffic on complex network as three phases, i.e. the free, buffer, and congestion phase, than just as two phases believed before, i.e. the free and congestion phase.     

A class of improved algorithms for detecting communities in complex networks

Detecting communities in complex networks is of considerable importance for understanding both the structure and function of the networks. Here, we propose a class of improved algorithms for community detection, by combining the betweenness algorithm of Girvan and Newman with the edge weight defined by the edge-clustering coefficient. The improved algorithms are tested on some artificial and real-world networks, and the results show that they can detect communities of networks more effectively in both unweighted and weighted cases. In addition, the technique for improving the betweenness algorithm in this paper, thanks to its compatibility, can directly be applied to various detection algorithms.