Detecting Critical Elements in Large Networks

Professor Panos M. Pardalos
Center for Applied Optimization (CAO)
Department of Industrial and Systems Engineering,
University of Florida, Gainesville, FL, USA.
and
Laboratory of Algorithms and Technologies for Networks Analysis (LATNA)
National Research University, Higher School of Economics
Moscow, Russia
E-mail: [email protected]
 

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 programming, dynamic programming, 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.

Short biography: Panos M. Pardalos serves as Distinguished Professor of Industrial and Systems Engineering at the University of Florida. He is also an affiliated faculty member of the Computer and Information Science Department, the Hellenic Studies Center, and the Biomedical Engineering Program. He is also the Director of the Center for Applied Optimization. Dr. Pardalos is a world leading expert in global and combinatorial optimization. His recent research interests include network design problems, optimization in telecommunications, e-commerce, data mining, biomedical applications, and massive computing.
Full CV: http://www.ise.ufl.edu/pardalos/files/2011/08/CV_Dec13.pdf
Recent Achievments: http://www.eng.ufl.edu/news/first-engineering-chair-appointed-under-ufs-preeminence-initiative-goes-to-big-data-expert/
Profile in Scholar Google: scholar.google.com/scholar?q=P+Pardalos&btnG=&hl=en&as_sdt=0,5