Abstract:
Least box number coverage problem for calculating dimension of fractal networks is a NP-hard problem. Meanwhile, the time complexity of random ball coverage for calculating dimension is very low. In this paper we strictly present the upper bound of relative error for random ball coverage algorithm. We also propose twice-random ball coverage algorithm for calculating network dimension. For many real-world fractal networks, when the network diameter is sufficient large, the relative error upper bound of this method will tend to 0. In this point of view, given a proper acceptable error range, the dimension calculation is not a NP-hard problem, but P problem instead.

Abstract:
It has been proved that the spanning tree from a given network has the optimal synchronizability, which means the index $R=\lambda_{N}/\lambda_{2}$ reaches the minimum 1. Although the optimal synchronizability is corresponding to the minimal critical overall coupling strength to reach synchronization, it does not guarantee a shorter converging time from disorder initial configuration to synchronized state. In this letter, we find that it is the depth of the tree that affects the converging time. In addition, we present a simple and universal way to get such an effective oriented tree in a given network to reduce the converging time significantly by minimizing the depth of the tree. The shortest spanning tree has both the maximal synchronizability and efficiency.

Abstract:
Authors of Phys. Rev. Lett. 103, 228702 (2009) claim that "The residual degree gradient (RDG) method can enhance thesynchronizability of networks by simply changing the direction of the links". In this paper, we argue that in some case the RDG method will lead to the failure of synchronization ($R=\lambda^{r}_{2}/\lambda^{r}_{N}=0$). Additionally, we also propose a so-called residual betweenness gradient (RBG) method to solve this problem.

Abstract:
The loop structure plays an important role in many aspects of complex networks and attracts much attention. Among the previous works, Bianconi et al find that real networks often have fewer short loops as compared to random models. In this paper, we focus on the uneven location of loops which makes some parts of the network rich while some other parts sparse in loops. We propose a node removing process to analyze the unevenness and find rich loop cores can exist in many real networks such as neural networks and food web networks. Finally, an index is presented to quantify the unevenness of loop location in complex networks.

Abstract:
For any system, whether physical or non-physical, knowledge of the form and strength of inter-individual interactions is a key-information. In an approach based on statistical physics one needs to know the interaction Hamiltonian. For non-physical systems, based on qualitative arguments similar to those used in physical chemistry, interaction strength gives useful clues about the macroscopic properties of the system. Even though our ultimate objective is the understanding of social phenomena, we found that systems composed of insects (or other living organisms) are of great convenience for investigating group effects. In this paper we show how to design experiments that enable us to estimate the strength of interaction in groups of insects. By repeating the same experiments with increasing numbers of insects, ranging from less than 10 to several hundreds, one is able to explore key-properties of the interaction. The data turn out to be consistent with a global correlation that is independent of distance (at least within a range of a few centimetres). Estimates of this average cross-correlation will be given for ants, beetles and fruit flies. The experimental results clearly exclude an Ising-like interaction, that is to say one that would be restricted to nearest neighbours. In the case of fruit flies the average cross-correlation appears to be negative which means that instead of an inter-individual attraction there is a (weak) repulsive effect. In our conclusion we insist on the fact that such "physics-like experiments" on insect populations provide a valuable alternative to computer simulations. When testable group effects are predicted by a model, the required experiments can be set up, thus permitting to confirm or disprove the model.

Abstract:
Background Many complex systems can be represented as networks, and how a network breaks up into subnetworks or communities is of wide interest. However, the development of a method to detect nodes important to communities that is both fast and accurate is a very challenging and open problem. Methodology/Principal Findings In this manuscript, we introduce a new approach to characterize the node importance to communities. First, a centrality metric is proposed to measure the importance of network nodes to community structure using the spectrum of the adjacency matrix. We define the node importance to communities as the relative change in the eigenvalues of the network adjacency matrix upon their removal. Second, we also propose an index to distinguish two kinds of important nodes in communities, i.e., “community core” and “bridge”. Conclusions/Significance Our indices are only relied on the spectrum of the graph matrix. They are applied in many artificial networks as well as many real-world networks. This new methodology gives us a basic approach to solve this challenging problem and provides a realistic result.

Abstract:
Stanley Milgram's small world experiment presents "six degrees of separation" of our world. One phenomenon of the experiment still puzzling us is that how individuals operating with the social network information with their characteristics can be very adept at finding the short chains. The previous works on this issue focus whether on the methods of navigation in a given network structure, or on the effects of additional information to the searching process. In this paper, we emphasize that the growth and shape of network architecture is tightly related to the individuals' attributes. We introduce a method to reconstruct nodes' intimacy degree based on local interaction. Then we provide an intimacy based approach for orientation in networks. We find that the basic reason of efficient search in social networks is that the degree of "intimacy" of each pair of nodes decays with the length of their shortest path exponentially. Meanwhile, the model can explain the hubs limitation which was observed in real-world experiment.

Abstract:
A bipartite producer-consumer network is constructed to describe the industrial structure. The edges from consumer to producer represent the choices of the consumer for the final products and the degree of producer can represent its market share. So the size distribution of firms can be characterized by producer's degree distribution. The probability for a producer receiving a new consumption is determined by its competency described by initial attractiveness and the self-reinforcing mechanism in the competition described by preferential attachment. The cases with constant total consumption and with growing market are studied. The following results are obtained: 1, Without market growth and a uniform initial attractiveness $a$, the final distribution of firm sizes is Gamma distribution for $a>1$ and is exponential for $a=1$. If $a<1$, the distribution is power in small size and exponential in upper tail; 2, For a growing market, the size distribution of firms obeys the power law. The exponent is affected by the market growth and the initial attractiveness of the firms.

Abstract:
Modularity Q is an important function for identifying community structure in complex networks. In this paper, we prove that the modularity maximization problem is equivalent to a nonconvex quadratic programming problem. This result provide us a simple way to improve the efficiency of heuristic algorithms for maximizing modularity Q. Many numerical results demonstrate that it is very effective.

Abstract:
Social network structure is very important for understanding human information diffusing, cooperating and competing patterns. It can bring us with some deep insights about how people affect each other. As a part of complex networks, social networks have been studied extensively. Many important universal properties with which we are quite familiar have been recovered, such as scale free degree distribution, small world, community structure, self-similarity and navigability. According to some empirical investigations, we conclude that our social network also possesses another important universal property. The spatial structure of social network is scale invariable. The distribution of geographic distance between friendship is about $Pr(d)\propto d^{-1}$ which is harmonious with navigability. More importantly, from the perspective of searching information, this kind of property can benefit individuals most.