Critical events detection and management in complex networks

• Main Author: Yu, Yi
• Other Authors: Xiao Gaoxi
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Science::Mathematics::Topology; DRNTU::Science::Mathematics::Analysis
• Online Access: http://hdl.handle.net/10356/66311
• Institution: Nanyang Technological University

The world is evolving quickly and becoming increasingly interconnected than ever. Such drastically increased interconnections and complexity lead to totally different scenarios of critical events from what we knew before. Infectious diseases, rumors, and innovative ideas may spread out at frightening/exciting speed, social systems may emerge, crash and re-emerge suddenly. A “trivial” event may cause catastrophic consequences in seemingly irrelevant regions and areas. It is of great importance to develop knowledge for understanding, detecting and, if such is possible, controlling such critical events in a complex world. This thesis contributes to studying critical events detection and management in complex networks. We study the monitor placement algorithms and their effectiveness in complex networks; the influence of community structures on infection propagation, detection and control; the formation of opinion groups and community structures in adaptive networks; and the cascading decline of online social networks. Specifically, our work includes: (i) Early detection of strong infection in complex networks. We study the problem of finding the best locations of a given number of monitors in the network to minimize the worst-case infection size of a strong infection. Our main contributions are two-fold: i) we formulate the problem, prove its NP-hardness and design an efficient heuristic algorithm to find a suboptimal solution; ii) extensive simulations on various synthetic and real-world networks demonstrate that a moderate number of monitors is able to restrict the worst-case infection size to a low level in most cases. If monitors are not reliable, however, the infection size may be significantly increased even at a low chance of failure of detection. (ii) Infection spreading, detection and control in community networks. As a natural extension of the first piece of work, in this part, we seek to understand the dynamics of infection spreading and control in networks with community structures. Using extensive simulations, we evaluate how different community structures and link rewiring strategies influence the propagation, detection and control of the infection spreading in complex networks. The results demonstrate that the existence of community structures tends to slow down the infection spreading and whether they help reduce the overall infection size when no control method is adopted however depends on the network topology. Besides, the existence of strong community structures indeed makes infection detection and control relatively easier. (iii) Opinion diversity and community formation in adaptive networks. To better understand and detect critical events in social opinion formation and “abrupt” opinion changes, we believe that better modelling methods are needed. In this work, we aim to propose an effective modelling approach for describing the co-evolution between network structures and multiple competing infections spreading. Specifically, we propose a new adaptive system model by integrating consensus formation, link rewiring and opinion change in a simple form. It is shown that the proposed model allows complex system dynamics to emerge and “sustain” rather than always converging into an over-simple steady state which we could seldom, if not never, observe in real life. In our model, similar opinion holders may form into communities yet without strict community consensus; and rather than being separated into disconnected communities, different communities remain to be interconnected by non-trivial proportion of inter-community links, allowing complex dynamics to emerge when there are changes of opinions in a certain portion of population. We construct a framework for theoretically analyzing the co-evolution process. Theoretical analysis and extensive simulation results reveal some useful insights into the complex co-evolution process, including the formation of dynamic equilibrium, and the dynamics between opinion distribution and network communities/modularity, etc. (iv) Cascading declines of online social networks (OSN) under competition. Sudden crash of social networks is another critical event which, as we shall demonstrate in detail, can also be viewed as spreading of decision making: an individual’s decision of leaving a social network may be affected by the decisions of his/her neighbors. We propose a simple model where an individual may decide to leave an OSN either when s/he has too few connections left, or has lost a large enough proportion of connections which shall encourage him/her to leave the current OSN and join its competitor. The simulation results based on this model match well with real-life cases, e.g., the crash of Friendster. Further, an interesting observation is that, following an initial decay, a network may sometimes keep a long-term stable state before it suddenly crashes. We believe that the above studies would provide useful insights into the propagation of infection/decision/information in complex social systems and the co-evolution between individuals’ behaviors/decisions and system dynamics. Such understanding shall help better understand and handle various critical events in complex systems.