Identifying Critical Components and Key Communities in Complex Networks

This dissertation studies three newly introduced network optimization problems in separate chapters. The first one, that is cost vertex blocker clique problem, deals with identifying a subset of critical vertices in a network whose removal bounds the weight of all cliques in the remaining network. The point of identifying such vertices is to fortify them in advance to preserve the network’s functionality. This problem has practical applications in pandemic control, vulnerability analysis, and drug discovery. The second chapter is focused on two variants of the clique closeness centrality problem that count the accessibility of a clique to other vertices in the network. These central cliques represent the key communities in information diffusion processes appealing to viral marketing, portfolio optimization, and disease treatment. And, the final chapter addresses a distance-based clique relaxation community called k-club. A k-club is a subset of vertices in a network whose induced subgraph has a diameter of at most k. For a relatively small k, large k-clubs effectively model cohesive communities within the network. That being so, identifying the largest k-clubs has potential applications in text mining, recommender systems, and cybersecurity. We walk through the theoretical properties of these three problems and develop state-of-the-art algorithms to find these critical vertices and key communities effectively in complex networks. That motivated us to file our methods for patents