Controlling complex networks is of paramount importance in science and engineering. Despite the recent development of structural-controllability theory, we continue to lack a framework to control undirected complex networks, especially given link wei
ghts. Here we introduce an exact-controllability paradigm based on the maximum multiplicity to identify the minimum set of driver nodes required to achieve full control of networks with arbitrary structures and link-weight distributions. The framework reproduces the structural controllability of directed networks characterized by structural matrices. We explore the controllability of a large number of real and model networks, finding that dense networks with identical weights are difficult to be controlled. An efficient and accurate tool is offered to assess the controllability of large sparse and dense networks. The exact-controllability framework enables a comprehensive understanding of the impact of network properties on controllability, a fundamental problem towards our ultimate control of complex systems.
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 h
ave 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.
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 simpl
e way to improve the efficiency of heuristic algorithms for maximizing modularity Q. Many numerical results demonstrate that it is very effective.
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 r
elative 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.
