TITLE: Detecting Critical Subsets (nodes, edges, shortest paths, or cliques) in Large Networks
SPEAKER: Panos M. Pardalos (Center for Applied Optimization (CAO), Department of Industrial and Systems Engineering, University of Florida, USA; Laboratory of Algorithms and Technologies for Networks Analysis (LATNA), National Research University, Higher School of Economics, Moscow 101000, Russia)

ABSTRACT:

In network analysis, the problem of detecting subsets of elements important to the connectivity of a network (i.e., critical elements) has become a fundamental task over the last few years. Identifying the nodes, arcs, paths, clusters, cliques, etc., that are responsible for network cohesion can be crucial for studying many fundamental properties of a network. Depending on the context, finding these elements can help to analyze structural characteristics such as, attack tolerance, robustness, and vulnerability. Furthermore we can classify critical elements based on their centrality, prestige, reputation and can determine dominant clusters and partitions.

From the point of view of robustness and vulnerability analysis, evaluating how well a network will perform under certain disruptive events plays a vital role in the design and operation of such a network. To detect vulnerability issues, it is of particular importance to analyze how well connected a network will remain after a disruptive event takes place, destroying or impairing a set of its elements. The main goal is to identify the set of critical elements that must be protected or reinforced in order to mitigate the negative impact that the absence of such elements may produce in the network. Applications  are typically found in homeland security, energy grid, evacuation planning, immunization strategies, financial networks, biological networks, and transportation. 

From the member-classification perspective, identifying members with a high reputation and influential power within a social network could be of great importance when designing a marketing strategy. Positioning a product, spreading a rumor, or developing a campaign against drugs and alcohol abuse may have a great impact over society if the strategy is properly targeted among the most influential and recognized members of a community. The recent emergence of social networks such as Facebook, Twitter, LinkedIn, etc. provide countless applications for problems of critical-element detection.

In addition, determining dominant cliques or clusters over different industries and markets via critical clique detection may be crucial in the analysis of market share concentrations and debt concentrations, spotting possible collusive actions or even helping to prevent future economic crises.

This presentation surveys some of the recent advances for solving these kinds of problems including heuristics, mathematical programing, dynamic programing, approximation algorithms, and simulation approaches. We also summarize some applications that can be found in the literature and present further motivation for the use of these methodologies for network analysis in a broader context.


This is joint work with Steffen Rebennack, Ashwin Arulselvan, Clayton Commander, Vladimir Boginski, Chrysafis Vogiatzis, Jose L. Walteros, Neng Fan, Donatella Granata (CAO), and Olga Khvostova (LATNA).