Behavior Model Inference techniques aim at mining behavior models from execution traces. While most of approaches usually ground on local similarities in traces, recent work, referred to as behavior mining with tempor...
详细信息
ISBN:
(纸本)9781479954827
Behavior Model Inference techniques aim at mining behavior models from execution traces. While most of approaches usually ground on local similarities in traces, recent work, referred to as behavior mining with temporal steering, propose to include long term dependencies in the mining process. Such dependencies correspond to temporal implications between events in execution traces, whose consideration allows to ensure a better consistency of the extracted model. Nevertheless, the existing approaches are usually limited by their high computational complexity and the approximations to reduce the cost of temporal rules checking. This paper revisits behavior mining with temporal steering by defining an efficient algorithm that performs an exact consideration of the observed dependencies: in our experiments, greatly reduced processing times (from exponential to quasi-linear) for exact mining with temporal steering have been observed. Furthermore, beyond highlighting the great benefits of considering temporal dependencies, this paper also proposes new key extensions to the existing work that allow to include more complex dependencies in the mining process. Intensive evaluation finally demonstrates the great performances of the proposed approach.
We propose a general framework of risk-averse reinforcement learning for algorithmic trading. Our approach is tested in an experiment based on 1.5 years of millisecond time-scale limit order data from NASDAQ, which co...
详细信息
ISBN:
(纸本)9781479923809
We propose a general framework of risk-averse reinforcement learning for algorithmic trading. Our approach is tested in an experiment based on 1.5 years of millisecond time-scale limit order data from NASDAQ, which contain the data around the 2010 flash crash. The results show that our algorithm outperforms the risk-neutral reinforcement learning algorithm by 1) keeping the trading cost at a substantially low level at the spot when the flash crash happened, and 2) significantly reducing the risk over the whole test period.
Many complex systems, from World Wide Web and online social networks to mobile networks, exhibit community structure in which nodes can be grouped into densely interconnected communities. This special structure has be...
详细信息
ISBN:
(纸本)9781479958771
Many complex systems, from World Wide Web and online social networks to mobile networks, exhibit community structure in which nodes can be grouped into densely interconnected communities. This special structure has been exploited extensively to design better solutions for many operations and applications such as routing in wireless networks, worm containment and interest prediction in social networks. The outcome of these solutions are sensitive to the network structures, which raises an important question: can communities be broken easily in a network? To answer this question, we introduce a density-based problem formulation for analyzing the vulnerability of communities. Our approach includes the NP-completeness and a O(log k) approximation algorithm for solving the problem where k is the number of communities to be broken. Additionally, we analyze the vulnerability of communities in the context of arbitrary community detection algorithms. The empirical results show that communities are vulnerable to edge removal and in some cases the removal of a small fraction of edges can break the community structure.
One of the widely studied structural properties of social and information networks is their community structure, and a vast variety of community detection algorithms have been proposed in the literature. Expansion of ...
详细信息
ISBN:
(纸本)9781479958771
One of the widely studied structural properties of social and information networks is their community structure, and a vast variety of community detection algorithms have been proposed in the literature. Expansion of a seed node into a community is one of the most successful methods for local community detection, especially when the global structure of the network is not accessible. An algorithm for local community detection only requires a partial knowledge of the network and the computations can be done in parallel starting from seed nodes. The parallel nature of local algorithms allow for fast and scalable solutions, however, the coverage of the communities heavily depends on the seed selection. The communities identified by a local algorithm might cover only a subset of the nodes in a network if the seeds are not selected carefully. In this paper, we propose a novel seeding algorithm which is parameter free, utilizes merely the local structure of the network, and identifies good seeds which span over the whole network. In order to find such seeds, our algorithm first computes similarity indices from local link prediction techniques to assign a similarity score to each node, and then a biased graph coloring algorithm is used to enhance the seed selection. Our experiments using large-scale real-world networks show that our algorithm is able to select good seeds which are then expanded into high quality overlapping communities covering the vast majority of the nodes in the network using a personalized PageRank-based community detection algorithm. We also show that using our local seeding algorithm can dramatically reduce the execution time of community detection.
作者：
Orlin, JBSharma, DMIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA Univ Michigan
Dept Ind & Operat Engn Ann Arbor MI 48105 USA
We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a Neighborhood for combinatorial optimization problem X. We say that N' is LO-equivalent ( locally optimal) to N if...
详细信息
We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a Neighborhood for combinatorial optimization problem X. We say that N' is LO-equivalent ( locally optimal) to N if for any instance of X, the set of locally optimal solutions with respect to N and N' are the same. The union of two LO-equivalent neighborhoods is itself LO-equivalent to the neighborhoods. The largest neighborhood that is LO-equivalent to N is called the extended neighborhood of N, and denoted as N*. We analyze some basic properties of the extended neighborhood. We provide a geometric characterization of the extended neighborhood N* when the instances have linear costs defined over a cone. For the TSP, we consider 2-opt*, the extended neighborhood for the 2-opt (i.e., 2-exchange) neighborhood structure. We show that number of neighbors of each tour T in 2-opt* is at least (n/2 - 2)!. We show that finding the best tour in the 2-opt* neighborhood is NP-hard. We also show that the extended neighborhood for the graph partition problem is the same as the original neighborhood, regardless of the neighborhood defined. This result extends to the quadratic assignment problem as well. This result on extended neighborhoods relies on a proof that the convex hull of solutions for the graph partition problem has a diameter of 1, that is, every two corner points of this polytope are adjacent.
暂无评论