Vladimir Boginski

Vladimir Boginski
Department of Industrial and Systems Engineering
The University of Florida

 

Analyzing Cohesive Clusters in Complex Networks

Abstract. Networks are ubiquitous in the modern world. Many natural and man-made complex systems and processes can be modeled as networks, where nodes (vertices) are elements of a system, and links (edges) represent interactions between these elements. Notable examples of such systems include the Internet, wireless communications, power grids, natural ecosystems, biological interactions, and social networks, among other applications. One important issue of interest to many such applications is finding large clusters, or ‘‘tightly knit’’ (“cohesive”) subsets of vertices. The ideal description of a cluster of similar elements is given by the concept of a clique (complete subgraph), defined as a subset of vertices any two of which are connected by an edge. Moreover, in the context of physical networks, cliques are very resilient to node/link failures (the property sometimes referred to as “attack tolerance”). However, cliques are often overly restrictive in practical settings, because they may be too expensive or infeasible to construct, and they do not provide much modeling flexibility (i.e., a clique with a few missing edges would for many practical purposes still be a sufficiently “tight” cluster, but the classical clique model does not capture this adjustment). Therefore, more flexible models of cohesive network clusters, referred to as clique relaxations, have been introduced. These models “relax” certain characteristics of a clique, such as edge density (quasi-clique), minimum node degree (k-plex), diameter (k-club), etc. In this presentation, we will discuss combinatorial optimization problems dealing with: 1) identifying the largest cohesive/robust cluster (clique relaxation) in a given network; 2) optimal design/augmentation of a network so that it would form a robust cluster. Recent developments in both theoretical and computational aspects of these areas will be presented.