In this work, we propose computationally tractable techniques for extracting valuable information from diverse data sources collected by multiple sensors in a variety of formats (visual, sonar, quantitative, qualitative, social information, etc.). More specifically, we develop an integrated approach consisting of two algorithms for extracting information and achieving a consensus-based, robust solution. The first algorithm extracts solutions from sensors within each data source, whereas the second algorithm reaches a compromise among the generated solutions from the previous algorithm across all data sources. To accomplish these goals, we initially transform the multisensor multitarget tracking problem (MSMTT) problem into a multidimensional assignment problem. Subsequently, we introduce a decomposition-based multisensor recursive approach referred to as a revised multisensor recursive algorithm, which can efficiently deliver a robust solution for each single data source MSMTT problem. In the second algorithm, we extend our methodology to the multisource MSMTT problem by introducing a connection-based symmetric nonnegative matrix factorization technique, which is shown to be computationally feasible and efficient in obtaining high-quality solutions. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by the Army Research Laboratory [Grant G00006831]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0016 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0016 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract Centrality metrics have become a popular concept in network science and optimization. Over the years, centrality has been used to assign importance and identify influential elements in various settings, including transportation, infrastructure, biological, and social networks, among others. That said, most of the literature has focused on nodal versions of centrality. Recently, group counterparts of centrality have started attracting scientific and practitioner interest. The identification of sets of nodes that are influential within a network is becoming increasingly more important. This is even more pronounced when these sets of nodes are required to induce a certain motif or structure. In this study, we review group centrality metrics from an operations research and optimization perspective for the first time. This is particularly interesting due to the rapid evolution and development of this area in the operations research community over the last decade. We first present a historical overview of how we have reached this point in the study of group centrality. We then discuss the different structures and motifs that appear prominently in the literature, alongside the techniques and methodologies that are popular. We finally present possible avenues and directions for future work, mainly in three areas: (i) probabilistic metrics to account for randomness along with stochastic optimization techniques; (ii) structures and relaxations that have not been yet studied; and (iii) new emerging applications that can take advantage of group centrality. Our survey offers a concise review of group centrality and its intersection with network analysis and optimization.

Abstract Providing first aid and other supplies (e.g., epi‐pens, medical supplies, dry food, water) during and after a disaster is always challenging. The complexity of these operations increases when the transportation, power, and communications networks fail, leaving people stranded and unable to communicate their locations and needs. The advent of emerging technologies like uncrewed autonomous vehicles can help humanitarian logistics providers reach otherwise stranded populations after transportation network failures. However, due to the failures in telecommunication infrastructure, demand for emergency aid can become uncertain. To address the challenges of delivering emergency aid to trapped populations with failing infrastructure networks, we propose a novel robust computational framework for a two‐echelon vehicle routing problem that uses uncrewed autonomous vehicles (UAVs), or drones, for the deliveries. We formulate the problem as a two‐stage robust optimization model to handle demand uncertainty. Then, we propose a column‐and‐constraint generation approach for worst‐case demand scenario generation for a given set of truck and UAV routes. Moreover, we develop a decomposition scheme inspired by the column generation approach to generate UAV routes for a set of demand scenarios heuristically. Finally, we combine the decomposition scheme within the column‐and‐constraint generation approach to determine robust routes for both trucks (first echelon vehicles) and UAVs (second echelon vehicles), the time that affected communities are served, and the quantities of aid materials delivered. To validate our proposed algorithms, we use a simulated dataset that aims to recreate emergency aid requests in different areas of Puerto Rico after Hurricane Maria in 2017.

We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, is shown to be [Formula: see text]-complete. In this work, we first propose a new integer programming (IP) formulation, which has a smaller number of constraints and nonzero coefficients in them than the existing formulation in the literature. We present classes of networks in which the problem is solvable in polynomial time and offer a new proof of [Formula: see text]-completeness that shows the problem remains [Formula: see text]-complete for both bipartite and split graphs. In addition, we propose a decomposition framework that is suitable for both the existing and our formulations. We implement several acceleration techniques in this framework, motivated by techniques used in Benders decomposition. We test our approaches on networks generated based on the Barabási–Albert, Erdös–Rényi, and Watts–Strogatz models. Our decomposition approach outperforms solving the IP formulations in most of the instances in terms of both solution time and quality; this is especially true for larger and denser graphs. We then test the decomposition algorithm on large-scale protein–protein interaction networks, for which SDC is shown to be an important centrality metric. Summary of Contribution: In this study, we first introduce a new integer programming (NIP) formulation for the star degree centrality (SDC) problem in which the goal is to identify the induced star with the largest open neighborhood. We then show that, although the SDC can be efficiently solved in tree graphs, it remains [Formula: see text]-complete in both split and bipartite graphs via a reduction performed from the set cover problem. In addition, we implement a decomposition algorithm motivated by Benders decomposition together with several acceleration techniques to both the NIP formulation and the existing formulation in the literature. Our experimental results indicate that the decomposition implementation on the NIP is the best solution method in terms of both solution time and quality.

Abstract In this work, we introduce centrality metrics based on group structures, and we show their performance in estimating importance in protein‐protein interaction networks (PPINs). The centrality metrics introduced are extensions of well‐known nodal metrics. However, instead of focusing on a single node, we focus on that node and the set of nodes around it. Furthermore, we require the set of nodes to induce a specific pattern or structure. The structures investigated range from the “stricter“ induced stars and cliques, to a “looser” definition of a representative structure. We derive the computational complexity of all metrics and provide mixed integer programming formulations; due to the problem complexity and the size of PPINs, using commercial solvers is not always viable. Hence, we propose a combinatorial branch‐and‐bound solution approach. We conclude by showing the effectiveness of the proposed metrics in identifying essential proteins inHelicobacter pyloriand comparing them to nodal metrics.

Advances in modern genomics have allowed researchers to apply phylogenetic analyses on a genome-wide scale. While large volumes of genomic data can be generated cheaply and quickly, data missingness is a non-trivial and somewhat expected problem. Since the available information is often incomplete for a given set of genetic loci and individual organisms, a large proportion of trees that depict the evolutionary history of a single genetic locus, called gene trees, fail to contain all individuals. Data incompleteness causes difficulties in data collection, information extraction, and gene tree inference. Furthermore, identifying outlying gene trees, which can represent horizontal gene transfers, gene duplications, or hybridizations, is difficult when data is missing from the gene trees. The typical approach is to remove all individuals with missing data from the gene trees, and focus the analysis on individuals whose information is fully available - a huge loss of information. In this work, we propose and design an optimization-based imputation approach to infer the missing distances between leaves in a set of gene trees via a mixed integer non-linear programming model. We also present a new research pipeline, imPhy, that can (i) simulate a set of gene trees with leaves randomly missing in each tree, (ii) impute the missing pairwise distances in each gene tree, (iii) reconstruct the gene trees using the Neighbor Joining (NJ) and Unweighted Pair Group Method with Arithmetic Mean (UPGMA) methods, and (iv) analyze and report the efficiency of the reconstruction. To impute the missing leaves, we employ our newly proposed non-linear programming framework, and demonstrate its capability in reconstructing gene trees with incomplete information in both simulated and empirical datasets. In the empirical datasets apicomplexa and lungfish, our imputation has very small normalized mean square errors, even in the extreme case where 50 percent of the individuals in each gene tree are missing. Data, software, and user manuals can be found at https://github.com/yasuiniko/imPhy.

Disruptions in airline operations are not uncommon and can interrupt smooth and efficient passenger transportation, especially during extreme weather conditions and hurricanes. Airline operations can be severely affected and/or halted for the duration of these phenomena. In order to develop tools to implement proper recovery actions for different stakeholders during a disruption present in an air transportation system, prior hurricane data analysis is crucial. This work focuses on analyzing a large set of airline data during Hurricane Matthew in 2016 to obtain meaningful insights regarding the affected airports and airlines. Our analysis also predicts the number of affected airline passengers during the hurricane. The results of our study show that Orlando International Airport (MCO) and Southwest Airlines were the most affected airport and airline, respectively. Our findings further reveal that certain airline passengers were affected before and after the day of the hurricane.

In this work, we propose a novel centrality metric, referred to as star centrality, which incorporates information from the closed neighborhood of a node, rather than solely from the node itself, when calculating its topological importance. More specifically, we focus on degree centrality and show that in the complex protein–protein interaction networks, it is a naive metric that can lead to misclassifying protein importance. For our extension of degree centrality when considering stars, we derive its computational complexity, provide a mathematical formulation, and propose two approximation algorithms that are shown to be efficient in practice. We portray the success of this new metric in protein–protein interaction networks when predicting protein essentiality in several organisms, including the well-studied Saccharomyces cerevisiae, Helicobacter pylori, and Caenorhabditis elegans, where star centrality is shown to significantly outperform other nodal centrality metrics at detecting essential proteins. We also analyze the average and worst-case performance of the two approximation algorithms in practice and show that they are viable options for computing star centrality in very large-scale protein–protein interaction networks, such as the human proteome, where exact methodologies are bound to be time and memory intensive.

The graph bipartitioning problem consists of dividing a graph into two disjoint subgraphs, such that each node is highly similar to others in the same subgraph, but also different from members of the other subgraph, according to some homogeneity criterion. This problem has received significant attention over the last few years because of its applicability in areas as diverse as data classification, image segmentation, and social network analysis. In this article we study a variation of the graph bipartitioning problem in which, in addition to considering homogeneity criteria for generating the partition, we also ensure that one of the subgraphs satisfies a set of predefined structural properties—that is, such a subgraph is required to induce a given motif. We focus our attention on imposing structural constraints that force one of the subgraphs to induce stars, cliques, and clique relaxations (quasi‐cliques) and discuss some specific applications for such particular cases. We tackle this problem by modeling it as a general fractional programming optimization problem and study several solution approaches. Moreover, we discuss additional algorithmic enhancements to tackle some of the aforementioned cases, and provide two greedy algorithms for the specific cases of induced cliques and stars, showing the approximation ratio for induced stars. Finally, we test the quality of our approach by solving a collection of several real‐life and randomly generated instances with various configurations, analyzing the benefits of the proposed models, as well as possible further extensions. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 432–450 2018