| Abstract 摘要 | In the modeling, monitoring, and control of complex networks, a fundamental problem concerns the comprehensive determination of the state of the system from limited measurements. Using power grids as example networks, in this talk I will first show that this problem leads to a new type of percolation (depth-1 percolation) transition, termed observability transition, which we can solve analytically for the configuration model of network. Next, I will consider the depth-1 percolation problem on networks with arbitrary topology. I will show that by introducing a system of coupled nonlinear equations, valid under the locally tree-like ansatz, we can describe the size of the largest observable cluster as a function of the fraction of directly observable nodes present in the network. I will also demonstrate the equivalence between the optimal depth-1 percolation problem and the minimum dominating set problem. To tackle this problem, I will introduce a community-based algorithm in which the network is judiciously partitioned into smaller, largely independent components that can be solved exactly. This approach allows us to address, for the first time, the optimal depth-1 percolation problem on the Eastern North American power gird—a network of nearly 60,000 nodes. Potential applications of these work include the development of efficient and scalable algorithms for real-time surveillance of social networks, monitoring of technological networks, and control of biological networks. |
