Optimization and information retrieval techniques for complex networks.

摘要

This study develops novel approaches to modeling real-world datasets arising in diverse application areas as networks and information retrieval from these datasets using network optimization techniques. Network-based models allow one to extract information from datasets using various concepts from graph theory. In many cases, one can investigate specific properties of a dataset by detecting special formations in the corresponding graph (for instance, connected components, spanning trees, cliques, and independent sets). This process often involves solving computationally challenging combinatorial optimization problems on graphs (maximum independent set, maximum clique, minimum clique partition, etc.). These problems are especially difficult to solve for large graphs. However, in certain cases, the exact solution of a hard optimization problem can be found using a special structure of the considered graph.; A significant part of the dissertation focuses on developing network-based models of real-world complex systems, including the stock market and the human brain, which have always been of special interest to scientists. These systems generate huge amounts of data and are especially hard to analyze. This dissertation demonstrates that network-based models can be successfully applied to information retrieval from datasets, providing new insight into the structural properties and patterns underlying the corresponding complex systems.; The developed network representations of the considered datasets are in many cases non-trivial and include certain statistical preprocessing techniques. In particular, the U.S. stock market is represented as a network based on cross-correlations of price fluctuations of the financial instruments, which are calculated over a certain number of trading days. This model (market graph) allows one to analyze the structure and dynamics of the stock market from an alternative perspective and obtain useful information about the global structure of the market, classes of similar stocks, and diversified portfolios.; Similarly, a macroscopic network model of the human brain is constructed based on the statistical measures of entrainment between electroencephalographic (EEG) signals recorded from different functional units of the brain. Studying the evolution of the properties of these networks revealed some interesting facts about brain disorders, such as epilepsy.