Random Graphs And Consensus Problems In Multi-agent Systems

With the development of science and technology, complex network emerging as a new interdisciplinary research field has made great progress. Except for the substantial-evidence analysis, the topological properties and dynamical systems on complex networks are two upmost research topics. They offer an effective approach to the analysis of complex systems, and have essential meanings for the analysis, modeling, control and decision of science, industry and business. In the framework of complex networks, we study random intersection graphs, random geometric graphs, wireless networks and consensus problems of multi-agent systems etc. Our main contribution is as follows:We obtain the joint probability generating function for the degrees of active and passive random intersection graphs by sieve method. This is the first step towards the study of interrelationship of active and passive intersection graphs. We propose a new generalization of random intersection graph, whose degree distribution relies on the weights on both vertex sets. We get the "double expo-nential" result for the probability of connectivity in random intersection graphs through the Stein-Chen method, which is reminiscent of classical random graphs.Through the techniques of Palm theory and marked point process, we inves-tigate the random sector graphs extensively. We get the central limit theorems for in/out-degrees, focusing results on the maximal in/out-degrees and strong laws of large numbers of fixed subgraphs. We obtain the limit theorems for the ratio of chromatic number and distant chromatic number in the super-connectivity, connectivity and sub-connectivity regimes, respectively, for random geometric graphs. We propose the concept of accessible connectivity and deduce the ana-lytical connectivity probability for random interval graphs, which is applicable to internet and access networks. We also get the 2-connectivity probability for in-terval graphs in closed form. We propose an exponential random geometric graph process model for mobile wireless networks. Via the autoregressive process the-ory and the Laplacian transforms, we tackle its evolving properties (connectivity evolution, component evolution, etc.) as well as statical properties (connectivity component, degree distribution, the largest nearest neighbor distance, etc.).For a system with increasing protocol under fixed topology, we prove it achieves a consensus if and only if the underlying network contains a spanning tree. We obtain general finite time consensus criteria for continuous-time multi-agent systems under fixed topologies. By the delayed stochastic differential equa-tion theory, we deduce the synchronization conditions for the networks of coupled harmonic oscillators with random perturbation and time delays. We generalize the random moving neighborhood network model and prove the almost sure con-sensus conditions by the theory of ergodic Markov chains and stochastic stability. We analyze the leader-following consensus problems with a time-varying leader under measurement noises. We prove the mean square consensus conditions un-der fixed and switching topologies, respectively, by algebraic graph theory and stopping time truncation method.