Simple models of small-world networks with directed links

Eigenvalue-based entropy and spectrum of bipartite digraph

Graph entropy is an important measure of the evolution and complexity of networks. Bipartite graph is a special network and an important mathematical model for system resource allocation and management. In reality, a network system usually has obvious directionality. The direction of the network, or the movement trend of the network, can be described with spectrum index. However, little research has been done on the eigenvalue-based entropy of directed bipartite network. In this study, based on the adjacency matrix, the in-degree Laplacian matrix and the in-degree signless Laplacian matrix of directed bipartite graph, we defined the eigenvalue-based entropy for the directed bipartite network. Using the eigenvalue-based entropy, we described the evolution law of the directed bipartite network structure. Aiming at the direction and bipartite feature of the directed bipartite network, we improved the generation algorithm of the undirected network. We then constructed the directed bipartite nearest-neighbor coupling network, directed bipartite small-world network, directed bipartite scale-free network, and directed bipartite random network. In the proposed model, spectrum of those directed bipartite network is used to describe the directionality and bipartite property. Moreover, eigenvalue-based entropy is empirically studied on a real-world directed movie recommendation network, in which the law of eigenvalue-base entropy is observed. That is, if eigenvalue-based entropy value of the recommendation system is large, the evolution of movie recommendation network becomes orderless. While if eigenvalue-based entropy value is small, the structural evolution of the movie recommendation network tends to be regular. The simulation experiment shows that eigenvalue-based entropy value in the real directed bipartite network is between the values of a directed bipartite small world and a scale-free network. It shows that the real directed bipartite network has the structural property of the two typical directed bipartite networks. The coexistence of the small-world phenomena and the scale-free phenomena in the real network is consistent with the evolution law of typical network models. The experimental results show that the validity and rationality of the definition of eigenvalue-based entropy, which serves as a tool in the analysis of directed bipartite networks.

Eigenvalue-based entropy in directed complex networks

Entropy is an important index for describing the structure, function, and evolution of network. The existing research on entropy is primarily applied to undirected networks. Compared with an undirected network, a directed network involves a special asymmetric transfer. The research on the entropy of directed networks is very significant to effectively quantify the structural information of the whole network. Typical complex network models include nearest-neighbour coupling network, small-world network, scale-free network, and random network. These network models are abstracted as undirected graphs without considering the direction of node connection. For complex networks, modeling through the direction of network nodes is extremely challenging. In this paper, based on these typical models of complex network, a directed network model considering node connection in-direction is proposed, and the eigenvalue entropies of three matrices in the directed network is defined and studied, where the three matrices are adjacency matrix, in-degree Laplacian matrix and in-degree signless Laplacian matrix. The eigenvalue-based entropies of three matrices are calculated in directed nearest-neighbor coupling, directed small world, directed scale-free and directed random networks. Through the simulation experiment on the real directed network, the result shows that the eigenvalue entropy of the real directed network is between the eigenvalue entropy of directed scale-free network and directed small-world network.

Scaling of directed dynamical small-world networks with random responses

A dynamical model of small-world networks, with directed links which describe various correlations in social and natural phenomena, is presented. Random responses of sites to the input message are introduced to simulate real systems. The interplay of these ingredients results in the collective dynamical evolution of a spinlike variable S(t) of the whole network. The global average spreading length <L>(s) and average spreading time <T>(s) are found to scale as p(-alpha)ln(N with different exponents. Meanwhile, S(t) behaves in a duple scaling form for N>>N(*): S approximately f(p(-beta)q(gamma)t), where p and q are rewiring and external parameters, alpha, beta, and gamma are scaling exponents, and f(t) is a universal function. Possible applications of the model are discussed.

Simple model for directed networks

We study a model for directed networks based on the Watts-Stogatz model for small-world phenomena. We focus on some topological aspects of directed networks inspired in food web theory, namely, the fraction of basal and top nodes in the network and node level distributions. We argue that in directed networks basal nodes play an important role, collecting information or resources from the environment. We give analytical expressions for the fraction of basal and top nodes for the model, and study the node level distributions with numerical simulations.