We consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node, and the leader aims to minimize the number of arcs from a critical set that have positive flow on them, that is, active arcs, in the maximum flow solution obtained by the follower. This problem is motivated by an application in human trafficking disruption. We consider both the optimistic and pessimistic variants of this bilevel optimization problem and develop their respective single-level reformulations. We present a tailored solution method to the pessimistic problem, which solves the problem to optimality for one practically important class of networks. Through computational experiments on randomly generated layered network instances, we show the effectiveness of the proposed methods and demonstrate that the tailored method is orders of magnitude faster than existing approaches in the literature. We also conduct computational experiments on randomly generated test instances inspired by domestic human trafficking networks and draw domain-specific insights. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the National Science Foundation [Grant 2039584]. The computational experiments discussed in this paper were performed on the Palmetto Computing Cluster. The Palmetto Computing Cluster is supported by the National Science Foundation [Grants MRI# 2024205, MRI# 1725573, and CRI# 2010270]. 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.0423 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0423 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

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.

We focus on organizational structures in covert networks, such as criminal or terrorist networks. Their members engage in illegal activities and attempt to hide their association and interactions with these networks. Hence, data about such networks are incomplete. We introduce a novel method of rewiring covert networks parameterized by the edge connectivity standard deviation. The generated networks are statistically similar to themselves and to the original network. The higher-level organizational structures are modeled as a multi-layer network while the lowest level uses the Stochastic Block Model. Such synthetic networks provide alternative structures for data about the original network. Using them, analysts can find structures that are frequent, therefore stable under perturbations. Another application is to anonymize generated networks and use them for testing new software developed in open research facilities. The results indicate that modeling edge structure and the hierarchy together is essential for generating networks that are statistically similar but not identical to each other or the original network. In experiments, we generate many synthetic networks from two covert networks. Only a few structures of synthetics networks repeat, with the most stable ones shared by 18% of all synthetic networks making them strong candidates for the ground truth structure.

Abstract We consider two new problems regarding the impact of edge addition or removal on the modularity of partitions (or community structures) in a network. The first problem seeks to add edges to enforce that a desired partition is one partition that maximizes modularity. The second problem seeks to find the sparsest representation of a network that has the same partition with maximum modularity as the original network. We present integer programming formulations, a row generation algorithm, and heuristic algorithms to solve these problems. Further, we demonstrate a counter‐intuitive behavior of modularity that makes the development of heuristics for general networks difficult. We then present results on a selection of social and illicit networks from the literature.

Abstract Fifty years of research in Networks coincides with 50 years of advances in resilience theory and applications. The purpose of this review is to identify how these two technical communities influenced each other in the past and can bolster each other in the future. Advances in resilience theory show that there are at least four ways networks demonstrate resilience: robustness, rebound, extensibility, and adaptability. Research published in Networks and by the broader network optimization community has focused primarily on technical methods for robustness and rebound. We review this literature to organize seminal problems and papers on the ability of networks to manage increasing stressors and return to normal activities after a stressful event. In contrast, the Networks community has made less progress addressing issues for network extensibility and adaptability. Extensibility refers to the ability to stretch current operations to surprising situations and adaptability refers to the ability to sustain operations into the future. We discuss ways to harness existing network optimization methods to study these forms of resilience and outline their limitations. We conclude by providing a research agenda that ensures the Networks community remains central to future advances in resilience while being pragmatic about the limitations of network optimization for achieving this task.

We study community detection in criminal networks and address the problem caused by intentionally hidden edges which hinder the performance of community detection. We make use of link prediction to demonstrate how the community structure of a network can be better identified by augmenting it with edges. We demonstrate the value of this method by showing this method delivers us better quality communities for real life drug trafficking networks. We discuss also the limitations of the approach, and importance of community detection for investigating of criminal networks.

We consider the class of integrated network design and scheduling (INDS) problems that focus on selecting and scheduling operations that will change the characteristics of a network, while being specifically concerned with the performance of the network over time. Motivating applications of INDS problems include infrastructure restoration after an extreme event and building humanitarian logistics networks. We examine INDS problems under a parallel identical machine scheduling environment where the performance of the network is evaluated by solving classic network optimization problems. We prove that all considered INDS problems are NP ‐hard. We propose a novel heuristic dispatching rule algorithm framework that selects and schedules sets of arcs based on their interactions in the network. These interactions are measured by examining network optimality conditions. Computational testing of these dispatching rules on realistic data sets representing infrastructure networks of lower Manhattan, New York demonstrates that they arrive at near‐optimal solutions in real‐time.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 306–326 2014

Abstract We consider a metric uncapacitated facility location problem where we must assign each customer to a facility and meet the demand of the customer in future time periods through production and inventory decisions at the facility. We show that the problem, in general, is as hard to approximate as the set cover problem. We therefore focus on developing approximation algorithms for special cases of the problem. These special cases come in two forms: (i) specialize the production and inventory cost structure and (ii) specialize the demand pattern of the customers. In the former, we offer reductions to variants of the metric uncapacitated facility location problem that have been previously studied. The latter gives rise to a class of metric uncapacitated facility location problems where the facility cost function is concave in the amount of demand assigned to the facility. We develop a modified greedy algorithm together with the idea of cost‐scaling to provide an algorithm for this class of problems with an approximation guarantee of 1.52. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract We study minimum‐cost network‐flow problems in networks with a countably infinite number of nodes and arcs and integral flow data. This problem class contains many nonstationary planning problems over time where no natural finite planning horizon exists. We use an intuitive natural dual problem and show that weak and strong duality hold. Using recent results regarding the structure of basic solutions to infinite‐dimensional network‐flow problems we extend the well‐known finite‐dimensional network simplex method to the infinite‐dimensional case. In addition, we study a class of infinite network‐flow problems whose flow balance constraints are inequalities and show that the simplex method can be implemented in such a way that each pivot takes only a finite amount of time. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008