The constantly evolving digital transformation imposes new requirements on our society. Aspects relating to reliance on the networking domain and the difficulty of achieving security by design pose a ...challenge today. As a result, data-centric and machine-learning approaches arose as feasible solutions for securing large networks. Although, in the network security domain, ML-based solutions face a challenge regarding the capability to generalize between different contexts. In other words, solutions based on specific network data usually do not perform satisfactorily on other networks. This paper describes the stacked-unsupervised federated learning (FL) approach to generalize on a cross-silo configuration for a flow-based network intrusion detection system (NIDS). The proposed approach we have examined comprises a deep autoencoder in conjunction with an energy flow classifier in an ensemble learning task. Our approach performs better than traditional local learning and naive cross-evaluation (training in one context and testing on another network data). Remarkably, the proposed approach demonstrates a sound performance in the case of non-IID data silos. In conjunction with an informative feature in an ensemble architecture for unsupervised learning, we advise that the proposed FL-based NIDS results in a feasible approach for generalization between heterogeneous networks.
We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a
k
-way partition. The framework ...generalizes the flow-based improvement algorithm of the Karlsruhe Fast Flow Partitioner (KaFFPa) from graphs to hypergraphs and is integrated into the hypergraph partitioner Karlsruhe Hypergraph Partitioning (KaHyPar). By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas for
both
the connectivity and the cut-net metric while still having a running time comparable to that of hMetis. In the case of graph partitioning, our algorithm compares favorably with KaFFPa, even after enhancing the latter with our improved flow network, and at the same time is more than a factor of two faster. Finally, we show that our algorithm improves the performance of the memetic multilevel hypergraph partitioner KaHyPar-E.
Max flows in O(nm) time, or better Orlin, James B.
Proceedings of the forty-fifth annual ACM symposium on Theory of Computing,
06/2013
Conference Proceeding
Recenzirano
Odprti dostop
In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m31/16 ...log2 n) time. In the case that m = O(n1.06), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm logm/(n log n)n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n2/ log n).
We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to (1 + 1 / poly(n)) accuracy in almost-linear time. These problems include ℓp-norm minimizing ...flow for p large (p ∈ ω(1), o(log2/3 n) ), and their duals, ℓp-norm semi-supervised learning for p close to 1.
As p tends to infinity, p-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives.
Our framework is inspired by the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC ’04, SIMAX ’14), and is based on several new tools we develop, including adaptive non-linear preconditioning, tree-routings, and (ultra-)sparsification for mixed ℓ2 and ℓp norm objectives.
Motivated by the prevalence of ride-sharing platforms, in “Spatial Pricing in Ride-Sharing Networks,” Bimpikis, Candogan, and Saban explore the impact of the demand pattern for rides across a ...network’s locations on a platform’s optimal pricing and compensation policy, profits, and consumer surplus. They explicitly account for the pricing problem’s spatial dimension and the fact that the drivers endogenously determine whether and where to provide service. Their first contribution is to develop a tractable model to study a platform operating on a network of locations that may differ in both the size of their potential demand and the destination preferences of riders. Second, they provide a characterization of the platform’s optimal policy and identify “balancedness” of the demand pattern as a property that captures the profit potential of a given network. Finally, they discuss the benefits and limitations of a number of alternative pricing and compensation schemes.
We explore spatial price discrimination in the context of a ride-sharing platform that serves a network of locations. Riders are heterogeneous in terms of their destination preferences and their willingness to pay for receiving service. Drivers decide whether and where to provide service so as to maximize their expected earnings given the platform’s pricing and compensation policy. Our findings highlight the impact of the demand pattern on the platform’s prices, profits, and the induced consumer surplus. In particular, we establish that profits and consumer surplus at the equilibrium corresponding to the platform’s optimal pricing and compensation policy are maximized when the demand pattern is “balanced” across the network’s locations. In addition, we show that they both increase monotonically with the balancedness of the demand pattern (as formalized by its structural properties). Furthermore, if the demand pattern is not balanced, the platform can benefit substantially from pricing rides differently depending on the location from which they originate. Finally, we consider a number of alternative pricing and compensation schemes that are commonly used in practice and explore their performance for the platform.
The e-companion is available at
https://doi.org/10.1287/opre.2018.1800
.
In this paper, we show that tracking different kinds of interacting objects can be formulated as a network-flow mixed integer program. This is made possible by tracking all objects simultaneously ...using intertwined flow variables and expressing the fact that one object can appear or disappear at locations where another is in terms of linear flow constraints. Our proposed method is able to track invisible objects whose only evidence is the presence of other objects that contain them. Furthermore, our tracklet-based implementation yields real-time tracking performance. We demonstrate the power of our approach on scenes involving cars and pedestrians, bags being carried and dropped by people, and balls being passed from one player to the next in team sports. In particular, we show that by estimating jointly and globally the trajectories of different types of objects, the presence of the ones which were not initially detected based solely on image evidence can be inferred from the detections of the others.
Flow-based intrusion detection is an innovative way of detecting intrusions in high-speed networks. Flow-based intrusion detection only inspects the packet header and does not analyze the packet ...payload. This paper provides a comprehensive survey of current state of the art in flow-based intrusion detection. It also describes the available flow-based datasets used for evaluation of flow-based intrusion detection systems. The paper proposes a taxonomy for flow-based intrusion detection systems on the basis of the technique used for detection of maliciousness in flow records. We review the architecture and evaluation results of available flow-based intrusion detection systems. We also identify important research challenges for future research in the area of flow-based intrusion detection.
We deal here with a general 2-commodity flow model over a time expanded network designed for the management of a shared mobility systems. The model involves an integral flow vector that represents ...carriers together with an integral flow vector that represents the items transported by those carriers. It simultaneously copes with temporal and resource issues, and is difficult to handle in the practice. So we propose here a Project and Lift approach to handle it. We start by projecting the time expanded network model on the original transit network to obtain a simpler two-commodity flow projected model. In order to make this projected model consistent with the original problem, we introduce some complex constraints, prove that these constraints can be separated in polynomial time and discuss the experimental behavior of the related Branch-and-Cut algorithm. Next, we introduce the Lift issue about the way one may turn an optimal solution of our projected model into a solution of the original problem. Finally, we thoroughly study a somewhat restrictive Strong Lift setting of this Lift issue, design and test an exact mixed integer programming Strong Lift model, and discuss some flexible alternative approaches.
This paper defines and studies the multi-terminal maximum-flow network-interdiction problem (MTNIP) in which a
network user attempts to maximize flow in a network among
K
⩾
3 pre-specified
node ...groups while an
interdictor uses limited resources to interdict network arcs to minimize this maximum flow. The paper proposes an exact (MTNIP-E) and an approximating model (MPNIM) to solve this NP-hard problem and presents computational results to compare the models. MTNIP-E is obtained by first formulating MTNIP as bi-level min–max program and then converting it into a mixed integer program where the flow is explicitly minimized. MPNIM is binary-integer program that does not minimize the flow directly. It partitions the node set into disjoint subsets such that each node group is in a different subset and minimizes the sum of the arc capacities crossing between different subsets. Computational results show that MPNIM can solve all instances in a few seconds while MTNIP-E cannot solve about one third of the problems in 24
hour. The optimal objective function values of both models are equal to each other for some problems while they differ from each other as much as 46.2% in the worst case. However, when the post-interdiction flow capacity incurred by the solution of MPNIM is computed and compared to the objective value of MTNIP-E, the largest difference is only 7.90% implying that MPNIM may be a very good approximation to MTNIP-E.
PDF
