OpenRaiser/Intern-Atlas huggingface dataset:
Notes on Elementary Spectral Graph Theory. Applications to Graph Clustering Using Normalized Cuts
Venue: arXiv cs.CV 2013
Year: 2013

These are notes on the method of normalized graph cuts and its applications to graph clustering. I provide a fairly thorough treatment of this deeply original method due to Shi and Malik, including complete proofs. I include the necessary background on graphs and graph Laplacians. I then explain in detail how the eigenvectors of the graph Laplacian can be used to draw a graph. This is an attractive application of graph Laplacians. The main thrust of this paper is the method of normalized cuts. I give a detailed account for K = 2 clusters, and also for K > 2 clusters, based on the work of Yu and Shi. Three points that do not appear to have been clearly articulated before are elaborated: 1. The solutions of the main optimization problem should be viewed as tuples in the K-fold cartesian product of projective space RP^{N-1}. 2. When K > 2, the solutions of the relaxed problem should be viewed as elements of the Grassmannian G(K,N). 3. Two possible Riemannian distances are available to compare the closeness of solutions: (a) The distance on (RP^{N-1})^K. (b) The distance on the Grassmannian. I also clarify what should be the necessary and sufficient conditions for a matrix to represent a partition of the vertices of a graph to be clustered.
Issues about the Adoption of Formal Methods for Dependable Composition of Web Services
Venue: arXiv cs.SE 2013
Year: 2013

Web Services provide interoperable mechanisms for describing, locating and invoking services over the Internet; composition further enables to build complex services out of simpler ones for complex B2B applications. While current studies on these topics are mostly focused - from the technical viewpoint - on standards and protocols, this paper investigates the adoption of formal methods, especially for composition. We logically classify and analyze three different (but interconnected) kinds of important issues towards this goal, namely foundations, verification and extensions. The aim of this work is to individuate the proper questions on the adoption of formal methods for dependable composition of Web Services, not necessarily to find the optimal answers. Nevertheless, we still try to propose some tentative answers based on our proposal for a composition calculus, which we hope can animate a proper discussion.
Over-the-air Signaling in Cellular Networks: An Overview
Venue: arXiv cs.IT 2013
Year: 2013

To improve the capacity and coverage of current cellular networks, many advanced technologies such as massive MIMO, inter-cell coordination, small cells, device-to-device communications, and so on, are under studying. Many proposed techniques have been shown to offer significant performance improvement. Thus, the enabler of those techniques is of great importance. That is the necessary signaling which guarantee the operation of those techniques. The design and transmission of those signaling, especially the over-the-air (OTA) signaling, is challenging. In this article, we provide an overview of the OTA signaling in cellular networks to provide insights on the design of OTA signaling. Specifically, we first give a brief introduction of the OTA signaling in long term evolution (LTE), and then we discuss the challenges and requirements in designing the OTA signaling in cellular networks in detail. To better understand the OTA signaling, we give two important classifications of OTA signaling and address their properties and applications. Finally, we propose a signature-based signaling named (single-tone signaling, STS) which can be used for inter-cell OTA signaling and is especially useful and robust in multi-signal scenario. Simulation results are given to compare the detection performance of different OTA signaling.
MIMO Broadcast Channel with an Unknown Eavesdropper: Secrecy Degrees of Freedom
Venue: arXiv cs.IT 2013
Year: 2013

We study a multi-antenna broadcast channel with two legitimate receivers and an external eavesdropper. We assume that the channel matrix of the eavesdropper is unknown to the legitimate terminals but satisfies a maximum rank constraint. As our main result we characterize the associated secrecy degrees of freedom for the broadcast channel with common and private messages. We show that a direct extension of the single-user wiretap codebook does not achieve the secrecy degrees of freedom. Our proposed optimal scheme involves decomposing the signal space into a common subspace, which can be observed by both receivers, and private subspaces which can be observed by only one of the receivers, and carefully transmitting a subset of messages in each subspace. We also consider the case when each user's private message must additionally remain confidential from the other legitimate receiver and characterize the s.d.o.f.\ region in this case.
Sampling Based Approaches to Handle Imbalances in Network Traffic Dataset for Machine Learning Techniques
Venue: arXiv cs.NI 2013
Year: 2013

Network traffic data is huge, varying and imbalanced because various classes are not equally distributed. Machine learning (ML) algorithms for traffic analysis uses the samples from this data to recommend the actions to be taken by the network administrators as well as training. Due to imbalances in dataset, it is difficult to train machine learning algorithms for traffic analysis and these may give biased or false results leading to serious degradation in performance of these algorithms. Various techniques can be applied during sampling to minimize the effect of imbalanced instances. In this paper various sampling techniques have been analysed in order to compare the decrease in variation in imbalances of network traffic datasets sampled for these algorithms. Various parameters like missing classes in samples, probability of sampling of the different instances have been considered for comparison.
Draft Auctions
Venue: arXiv cs.GT 2013
Year: 2013

We introduce draft auctions, which is a sequential auction format where at each iteration players bid for the right to buy items at a fixed price. We show that draft auctions offer an exponential improvement in social welfare at equilibrium over sequential item auctions where predetermined items are auctioned at each time step. Specifically, we show that for any subadditive valuation the social welfare at equilibrium is an $O(\log^2(m))$-approximation to the optimal social welfare, where $m$ is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Bayes-Nash equilibria and for no-regret learning outcomes, via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class of cardinality valuations, extend with a small degradation, to subadditive valuations, the largest complement-free class of valuations. Variants of draft auctions have been used in practice and have been experimentally shown to outperform other auctions. Our results provide a theoretical justification.
Virtual Modules in Discrete-Event Systems: Achieving Modular Diagnosability
Venue: arXiv cs.SY 2013
Year: 2013

This paper deals with the problem of enforcing modular diagnosability for discrete-event systems that don't satisfy this property by their natural modularity. We introduce an approach to achieve this property combining existing modules into new virtual modules. An underlining mathematical problem is to find a partition of a set, such that the partition satisfies the required property. The time complexity of such problem is very high. To overcome it, the paper introduces a structural analysis of the system's modules. In the analysis we focus on the case when the modules participate in diagnosis with their observations, rather then the case when indistinguishable observations are blocked due to concurrency.
An Experience based Evaluation Process for ERP bids
Venue: arXiv cs.SE 2013
Year: 2013

Enterprise Resource Planning ERP systems integrate information across an entire organization that automate core activities such as finance accounting, human resources, manufacturing, production and supply chain management etc. to facilitate an integrated centralized system and rapid decision making resulting in cost reduction, greater planning, and increased control. Many organizations are updating their current management information systems with ERP systems. This is not a trivial task. They have to identify the organizations objectives and satisfy a myriad of stakeholders. They have to understand what business processes they have, how they can be improved, and what particular systems would best suit their needs. They have to understand how an ERP system is built, it involves the modification of an existing system with its own set of business rules. Deciding what to ask for and how to select the best option is a very complex operation and there is limited experience with this type of contracting in organizations. In this paper we discuss a particular experience with contracting out an ERP system, provide some lessons learned, and offer suggestions in how the RFP and bid selection processes could have been improved.
Authorship Attribution Using Word Network Features
Venue: arXiv cs.CL 2013
Year: 2013

In this paper, we explore a set of novel features for authorship attribution of documents. These features are derived from a word network representation of natural language text. As has been noted in previous studies, natural language tends to show complex network structure at word level, with low degrees of separation and scale-free (power law) degree distribution. There has also been work on authorship attribution that incorporates ideas from complex networks. The goal of our paper is to explore properties of these complex networks that are suitable as features for machine-learning-based authorship attribution of documents. We performed experiments on three different datasets, and obtained promising results.
Incrementally Introducing Process Model Rationale Support in an Organization
Venue: arXiv cs.SE 2013
Year: 2013

Popular process models such as the Rational Unified Process or the V-Modell XT are by nature large and complex. Each time that a new release is published software development organizations are confronted with the big challenge of understanding the rationale behind the new release and the extent to which it affects them. Usually, there is no information about what has changed or most importantly why. This is because of the lack of a flexible approach that supports organizations responsible for evolving such large process models in documenting their decisions and that reflects the extent of the capabilities to which they can provide this information. This paper describes an approach to incrementally deploying rationale support as needed to match an organisation's needs, the capabilities and interests of the organisation's process engineering teams, and the organisation's willingness to support the effort required for the collection and application of the rationale information.
Endogenous games with goals: side-payments among goal-directed artificial agents
Venue: arXiv cs.GT 2013
Year: 2013

Artificial agents are typically oriented to the realization of an externally assigned task and try to optimize over secondary aspects of plan execution such time lapse or power consumption, technically displaying a quasi-dichotomous preference relation. Boolean games have been developed as a paradigm for modelling societies of agents with this type of preference. In boolean games agents exercise control over propositional variables and strive to achieve a goal formula whose realization might require the opponents' cooperation. Recently, a theory of incentive engineering for such games has been devised, where an external authority steers the outcome of the game towards certain desirable properties consistent with players' goals, by imposing a taxation mechanism on the players that makes the outcomes that do not comply with those properties less appealing to them. The present contribution stems from a complementary perspective and studies, instead, how games with quasi-dichotomous preferences can be transformed from inside, rather than from outside, by endowing players with the possibility of sacrificing a part of their payoff received at a certain outcome in order to convince other players to play a certain strategy. Concretely we explore the properties of endogenous games with goals, obtained coupling strategic games with goals, a generalization of boolean games, with the machinery of endogenous games coming from game theory. We analyze equilibria in those structures, showing the preconditions needed for desirable outcomes to be achieved without external intervention. What our results show is that endogenous games with goals display specific irreducible features - with respect to what already known for endogenous games - which makes them worth studying in their own sake.
Architecture of an Ontology-Based Domain-Specific Natural Language Question Answering System
Venue: arXiv cs.CL 2013
Year: 2013

Question answering (QA) system aims at retrieving precise information from a large collection of documents against a query. This paper describes the architecture of a Natural Language Question Answering (NLQA) system for a specific domain based on the ontological information, a step towards semantic web question answering. The proposed architecture defines four basic modules suitable for enhancing current QA capabilities with the ability of processing complex questions. The first module was the question processing, which analyses and classifies the question and also reformulates the user query. The second module allows the process of retrieving the relevant documents. The next module processes the retrieved documents, and the last module performs the extraction and generation of a response. Natural language processing techniques are used for processing the question and documents and also for answer extraction. Ontology and domain knowledge are used for reformulating queries and identifying the relations. The aim of the system is to generate short and specific answer to the question that is asked in the natural language in a specific domain. We have achieved 94 % accuracy of natural language question answering in our implementation.
A Study of Actor and Action Semantic Retention in Video Supervoxel Segmentation
Venue: arXiv cs.CV 2013
Year: 2013

Existing methods in the semantic computer vision community seem unable to deal with the explosion and richness of modern, open-source and social video content. Although sophisticated methods such as object detection or bag-of-words models have been well studied, they typically operate on low level features and ultimately suffer from either scalability issues or a lack of semantic meaning. On the other hand, video supervoxel segmentation has recently been established and applied to large scale data processing, which potentially serves as an intermediate representation to high level video semantic extraction. The supervoxels are rich decompositions of the video content: they capture object shape and motion well. However, it is not yet known if the supervoxel segmentation retains the semantics of the underlying video content. In this paper, we conduct a systematic study of how well the actor and action semantics are retained in video supervoxel segmentation. Our study has human observers watching supervoxel segmentation videos and trying to discriminate both actor (human or animal) and action (one of eight everyday actions). We gather and analyze a large set of 640 human perceptions over 96 videos in 3 different supervoxel scales. Furthermore, we conduct machine recognition experiments on a feature defined on supervoxel segmentation, called supervoxel shape context, which is inspired by the higher order processes in human perception. Our ultimate findings suggest that a significant amount of semantics have been well retained in the video supervoxel segmentation and can be used for further video analysis.
Low-complexity End-to-End Performance Optimization in MIMO Full-Duplex Relay Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we deal with the deployment of full-duplex relaying in amplify-and-forward (AF) cooperative networks with multiple-antenna terminals. In contrast to previous studies, which focus on the spatial mitigation of the loopback interference (LI) at the relay node, a joint precoding/decoding design that maximizes the end-to-end (e2e) performance is investigated. The proposed precoding incorporates rank-1 zero-forcing (ZF) LI suppression at the relay node and is derived in closed-form by solving appropriate optimization problems. In order to further reduce system complexity, the antenna selection (AS) problem for full-duplex AF cooperative systems is discussed. We investigate different AS schemes to select a single transmit antenna at both the source and the relay, as well as a single receive antenna at both the relay and the destination. To facilitate comparison, exact outage probability expressions and asymptotic approximations of the proposed AS schemes are provided. In order to overcome zero-diversity effects associated with the AS operation, a simple power allocation scheme at the relay node is also investigated and its optimal value is analytically derived. Numerical and simulation results show that the joint ZF-based precoding significantly improves e2e performance, while AS schemes are efficient solutions for scenarios with strict computational constraints.
A New Algorithm for Distributed Nonparametric Sequential Detection
Venue: arXiv cs.IT 2013
Year: 2013

We consider nonparametric sequential hypothesis testing problem when the distribution under the null hypothesis is fully known but the alternate hypothesis corresponds to some other unknown distribution with some loose constraints. We propose a simple algorithm to address the problem. These problems are primarily motivated from wireless sensor networks and spectrum sensing in Cognitive Radios. A decentralized version utilizing spatial diversity is also proposed. Its performance is analysed and asymptotic properties are proved. The simulated and analysed performance of the algorithm is compared with an earlier algorithm addressing the same problem with similar assumptions. We also modify the algorithm for optimizing performance when information about the prior probabilities of occurrence of the two hypotheses are known.
Model predictive control of voltage profiles in MV networks with distributed generation
Venue: arXiv cs.SY 2013
Year: 2013

The Model Predictive Control (MPC) approach is used in this paper to control the voltage profiles in MV networks with distributed generation. The proposed algorithm lies at the intermediate level of a three-layer hierarchical structure. At the upper level a static Optimal Power Flow (OPF) manager computes the required voltage profiles to be transmitted to the MPC level, while at the lower level local Automatic Voltage Regulators (AVR), one for each Distributed Generator (DG), track the reactive power reference values computed by MPC. The control algorithm is based on an impulse response model of the system, easily obtained by means of a detailed simulator of the network, and allows to cope with constraints on the voltage profiles and/or on the reactive power flows along the network. If these constraints cannot be satisfied by acting on the available DGs, the algorithm acts on the On-Load Tap Changing (OLTC) transformer. A radial rural network with two feeders, eight DGs, and thirty-one loads is used as case study. The model of the network is implemented in DIgSILENT PowerFactory, while the control algorithm runs in Matlab. A number of simulation results is reported to witness the main characteristics and limitations of the proposed approach.
Improving The Scalability By Contact Information Compression In Routing
Venue: arXiv cs.IT 2013
Year: 2013

The existence of reduced scalability and delivery leads to the development of scalable routing by contact information compression. The previous work dealt with the result of consistent analysis in the performance of DTN hierarchical routing (DHR). It increases as the source to destination distance increases with decreases in the routing performance. This paper focuses on improving the scalability and delivery through contact information compression algorithm and also addresses the problem of power awareness routing to increase the lifetime of the overall network. Thus implementing the contact information compression (CIC) algorithm the estimated shortest path (ESP) is detected dynamically. The scalability and release are more improved during multipath multicasting, which delivers the information to a collection of target concurrently in a single transmission from the source
Analyses and performance of techniques PAPR reduction for STBC MIMO-OFDM system in (4G) wireless communication
Venue: arXiv cs.NI 2013
Year: 2013

An OFDM system is combined with multiple-input multiple-output (MIMO) in order to increase the diversity gain and system capacity over the time variant frequency-selective channels. However, a major drawback of MIMO-OFDM system is that the transmitted signals on different antennas might exhibit high peak-to-average power ratio (PAPR).In this paper, we present a PAPR analysis reduction of space-timeblock-coded (STBC) MIMO-OFDM system for 4G wirelessnetworks. Several techniques have been used to reduce the PAPR of the (STBC) MIMOOFDM system: clipping and filtering, partial transmit sequence (PTS) and selected mapping (SLM). Simulation results show that clipping and filtering provides a better PAPR reduction than the others methods and only SLM technique conserve the PAPR reduction in reception part of signal.
Chapter 10: Algebraic Algorithms
Venue: arXiv cs.DS 2013
Year: 2013

Our Chapter in the upcoming Volume I: Computer Science and Software Engineering of Computing Handbook (Third edition), Allen Tucker, Teo Gonzales and Jorge L. Diaz-Herrera, editors, covers Algebraic Algorithms, both symbolic and numerical, for matrix computations and root-finding for polynomials and systems of polynomials equations. We cover part of these large subjects and include basic bibliography for further study. To meet space limitation we cite books, surveys, and comprehensive articles with pointers to further references, rather than including all the original technical papers.
Exploiting Direct and Indirect Information for Friend Suggestion in ZingMe
Venue: arXiv cs.SI 2013
Year: 2013

Friend suggestion is a fundamental problem in social networks with the goal of assisting users in creating more relationships, and thereby enhances interest of users to the social networks. This problem is often considered to be the link prediction problem in the network. ZingMe is one of the largest social networks in Vietnam. In this paper, we analyze the current approach for the friend suggestion problem in ZingMe, showing its limitations and disadvantages. We propose a new efficient approach for friend suggestion that uses information from the network structure, attributes and interactions of users to create resources for the evaluation of friend connection amongst users. Friend connection is evaluated exploiting both direct communication between the users and information from other ones in the network. The proposed approach has been implemented in a new system version of ZingMe. We conducted experiments, exploiting a dataset derived from the users' real use of ZingMe, to compare the newly proposed approach to the current approach and some well-known ones for the accuracy of friend suggestion. The experimental results show that the newly proposed approach outperforms the current one, i.e., by an increase of 7% to 98% on average in the friend suggestion accuracy. The proposed approach also outperforms other ones for users who have a small number of friends with improvements from 20% to 85% on average. In this paper, we also discuss a number of open issues and possible improvements for the proposed approach.