OpenRaiser/Intern-Atlas huggingface dataset:
Apples and Oranges: Detecting Least-Privilege Violators with Peer Group Analysis
Venue: arXiv cs.CR 2015
Year: 2015

Clustering software into peer groups based on its apparent functionality allows for simple, intuitive categorization of software that can, in particular, help identify which software uses comparatively more privilege than is necessary to implement its functionality. Such relative comparison can improve the security of a software ecosystem in a number of ways. For example, it can allow market operators to incentivize software developers to adhere to the principle of least privilege, e.g., by encouraging users to use alternative, less-privileged applications for any desired functionality. This paper introduces software peer group analysis, a novel technique to identify least privilege violation and rank software based on the severity of the violation. We show that peer group analysis is an effective tool for detecting and estimating the severity of least privilege violation. It provides intuitive, meaningful results, even across different definitions of peer groups and security-relevant privileges. Our evaluation is based on empirically applying our analysis to over a million software items, in two different online software markets, and on a validation of our assumptions in a medium-scale user study.
Impact of Imbalance Usage of Social Networking Sites on Families
Venue: arXiv cs.HC 2015
Year: 2015

With the proliferation of social networking sites (SNSs) such as Facebook and Google+, investigating the impact of SNSs on our lives has become an important research area in recent years. Though SNS usage plays a key role in connecting people with friends and families from distant places, SNSs also bring concern for families. We focus on imbalance SNS usage, i.e., an individual remains busy in using SNSs when her family member is expecting to spend time with her. More specifically, we investigate the cause and pattern of imbalance SNS usage and how the emotion of family members may become affected, if they use SNSs in an imbalanced way in a regular manner. This paper is the first attempt to identify the relationship between an individual's imbalance SNS usage and the emotion of her family member in the context of a developing country.
Pan-Tilt Camera and PIR Sensor Fusion Based Moving Object Detection for Mobile Security Robots
Venue: arXiv cs.RO 2015
Year: 2015

One of fundamental issues for security robots is to detect and track people in the surroundings. The main problems of this task are real-time constraints, a changing background, varying illumination conditions and a non-rigid shape of the person to be tracked. In this paper, we propose a solution for tracking with a pan-tilt camera and a passive infrared range (PIR) sensor to detect the moving object based on consecutive frame difference. The proposed method is excellent in real-time performance because it requires only a little memory and computation. Experiment results show that this method can detect the moving object such as human efficiently and accurately in non-stationary and complex indoor environment.
The Impossibility of Extending Random Dictatorship to Weak Preferences
Venue: arXiv cs.MA 2015
Year: 2015

Random dictatorship has been characterized as the only social decision scheme that satisfies efficiency and strategyproofness when individual preferences are strict. We show that no extension of random dictatorship to weak preferences satisfies these properties, even when significantly weakening the required degree of strategyproofness.
A Markov Random Field and Active Contour Image Segmentation Model for Animal Spots Patterns
Venue: arXiv cs.CV 2015
Year: 2015

Non-intrusive biometrics of animals using images allows to analyze phenotypic populations and individuals with patterns like stripes and spots without affecting the studied subjects. However, non-intrusive biometrics demand a well trained subject or the development of computer vision algorithms that ease the identification task. In this work, an analysis of classic segmentation approaches that require a supervised tuning of their parameters such as threshold, adaptive threshold, histogram equalization, and saturation correction is presented. In contrast, a general unsupervised algorithm using Markov Random Fields (MRF) for segmentation of spots patterns is proposed. Active contours are used to boost results using MRF output as seeds. As study subject the Diploglossus millepunctatus lizard is used. The proposed method achieved a maximum efficiency of $91.11\%$.
Partial Key Grouping: Load-Balanced Partitioning of Distributed Streams
Venue: arXiv cs.DC 2015
Year: 2015

We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce Partial Key Grouping (PKG), a new stream partitioning scheme that adapts the classical "power of two choices" to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 175% in throughput and up to 45% in latency when deployed on a real Storm cluster. PKG has been integrated in Apache Storm v0.10.
Computational models: Bottom-up and top-down aspects
Venue: arXiv cs.CV 2015
Year: 2015

Computational models of visual attention have become popular over the past decade, we believe primarily for two reasons: First, models make testable predictions that can be explored by experimentalists as well as theoreticians, second, models have practical and technological applications of interest to the applied science and engineering communities. In this chapter, we take a critical look at recent attention modeling efforts. We focus on {\em computational models of attention} as defined by Tsotsos \& Rothenstein \shortcite{Tsotsos_Rothenstein11}: Models which can process any visual stimulus (typically, an image or video clip), which can possibly also be given some task definition, and which make predictions that can be compared to human or animal behavioral or physiological responses elicited by the same stimulus and task. Thus, we here place less emphasis on abstract models, phenomenological models, purely data-driven fitting or extrapolation models, or models specifically designed for a single task or for a restricted class of stimuli. For theoretical models, we refer the reader to a number of previous reviews that address attention theories and models more generally \cite{Itti_Koch01nrn,Paletta_etal05,Frintrop_etal10,Rothenstein_Tsotsos08,Gottlieb_Balan10,Toet11,Borji_Itti12pami}.
Cells in the Internet of Things
Venue: arXiv cs.NI 2015
Year: 2015

The Internet of Things combines various earlier areas of research. As a result, research on the subject is still organized around these pre-existing areas: distributed computing with services and objects, networks (usually combining 6lowpan with Zigbee etc. for the last-hop), artificial intelligence and semantic web, and human-computer interaction. We are yet to create a unified model that covers all these perspectives - domain, device, service, agent, etc. In this paper, we propose the concept of cells as units of structure and context in the Internet of things. This allows us to have a unified vocabulary to refer to single entities (whether dumb motes, intelligent spimes, or virtual services), intranets of things, and finally the complete Internet of things. The question that naturally follows, is what criteria we choose to demarcate boundaries; we suggest various possible answers to this question. We also mention how this concept ties into the existing visions and protocols, and suggest how it may be used as the foundation of a formal model.
Interplay Between Delayed CSIT and Network Topology for Secure MISO BC
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of secure transmission over a Gaussian two-user multi-input single-output (MISO) broadcast channel under the assumption that links connecting the transmitter to the two receivers may have unequal strength statistically. In addition to this, the state of the channel to each receiver is conveyed in a strictly causal manner to the transmitter. We focus on a two state topological setting of strong v.s. weak links. Under these assumptions, we first consider the MISO wiretap channel and establish bounds on generalized secure degrees of freedom (GSDoF). Next, we extend this model to the two-user MISO broadcast channel and establish inner and outer bounds on GSDoF region with different topology states. The encoding scheme sheds light on the usage of both resources, i.e., topology of the model and strictly causal channel state information at the transmitter (CSIT); and, allows digitization and multi-casting of overheard side information, while transmitting confidential message over the stronger link. Furthermore, for a special class of channels, we show that the established bounds agree and so we characterize the sum GSDoF.
Approximating Betweenness Centrality in Fully-dynamic Networks
Venue: arXiv cs.DS 2015
Year: 2015

Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of betweenness in networks that change over time. In this paper we propose the first betweenness centrality approximation algorithms with a provable guarantee on the maximum approximation error for dynamic networks. Several new intermediate algorithmic results contribute to the respective approximation algorithms: (i) new upper bounds on the vertex diameter, (ii) the first fully-dynamic algorithm for updating an approximation of the vertex diameter in undirected graphs, and (iii) an algorithm with lower time complexity for updating single-source shortest paths in unweighted graphs after a batch of edge actions. Using approximation, our algorithms are the first to make in-memory computation of betweenness in dynamic networks with millions of edges feasible. Our experiments show that our algorithms can achieve substantial speedups compared to recomputation, up to several orders of magnitude. Moreover, the approximation accuracy is usually significantly better than the theoretical guarantee in terms of absolute error. More importantly, for reasonably small approximation error thresholds, the rank of nodes is well preserved, in particular for nodes with high betweenness.
A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
Venue: arXiv cs.DS 2015
Year: 2015

A graph $G$ is called a \emph{block graph} if each maximal $2$-connected component of $G$ is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective of fixed parameter tractable (FPT) and kernelization algorithm. In particular, an input to Block Graph Vertex Deletion consists of a graph $G$ and a positive integer $k$ and the objective to check whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that the graph induced on $V(G)\setminus S$ is a block graph. In this paper we give an FPT algorithm with running time $4^kn^{O(1)}$ and a polynomial kernel of size $O(k^4)$ for Block Graph Vertex Deletion. The running time of our FPT algorithm improves over the previous best algorithm for the problem that ran in time $10^kn^{O(1)}$ and the size of our kernel reduces over the previously known kernel of size $O(k^9)$. Our results are based on a novel connection between Block Graph Vertex Deletion and the classical {\sc Feedback Vertex Set} problem in graphs without induced $C_4$ and $K_4-e$. To achieve our results we also obtain an algorithm for {\sc Weighted Feedback Vertex Set} running in time $3.618^kn^{O(1)}$ and improving over the running time of previously known algorithm with running time $5^kn^{O(1)}$.
A Hybrid Optimization Approach to Demand Response Management for the Smart Grid
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a hybrid approach to optimal day-ahead pricing for demand response management. At the customer-side, compared with the existing work, a detailed, comprehensive and complete energy management system, which includes all possible types of appliances, all possible applications, and an effective waiting time cost model is proposed to manage the energy usages in households (lower level problem). At the retailer-side, the best retail prices are determined to maximize the retailer's profit (upper level problem). The interactions between the electricity retailer and its customers can be cast as a bilevel optimization problem. To overcome the weakness and infeasibility of conventional Karush--Kuhn--Tucker (KKT) approach for this particular type of bilevel problem, a hybrid pricing optimization approach, which adopts the multi-population genetic algorithms for the upper level problem and distributed individual optimization algorithms for the lower level problem, is proposed. Numerical results show the applicability and effectiveness of the proposed approach and its benefit to the retailer and its customers by improving the retailer's profit and reducing the customers' bills.
Structurally Cyclic Petri Nets
Venue: arXiv cs.LO 2015
Year: 2015

A Petri net is structurally cyclic if every configuration is reachable from itself in one or more steps. We show that structural cyclicity is decidable in deterministic polynomial time. For this, we adapt the Kosaraju's approach for the general reachability problem for Petri nets.
Inactivation Decoding Analysis for LT Codes
Venue: arXiv cs.IT 2015
Year: 2015

We provide two analytical tools to model the inactivation decoding process of LT codes. First, a model is presented which derives the expected number of inactivations occurring in the decoding process of an LT code. This analysis is then extended allowing the derivation of the distribution of the number of inactivations. The accuracy of the method is verified by Monte Carlo simulations. The proposed analysis opens the door to the design of LT codes optimized for inactivation decoding.
Emoticons vs. Emojis on Twitter: A Causal Inference Approach
Venue: arXiv cs.CL 2015
Year: 2015

Online writing lacks the non-verbal cues present in face-to-face communication, which provide additional contextual information about the utterance, such as the speaker's intention or affective state. To fill this void, a number of orthographic features, such as emoticons, expressive lengthening, and non-standard punctuation, have become popular in social media services including Twitter and Instagram. Recently, emojis have been introduced to social media, and are increasingly popular. This raises the question of whether these predefined pictographic characters will come to replace earlier orthographic methods of paralinguistic communication. In this abstract, we attempt to shed light on this question, using a matching approach from causal inference to test whether the adoption of emojis causes individual users to employ fewer emoticons in their text on Twitter.
Ghost Cities Analysis Based on Positioning Data in China
Venue: arXiv cs.SI 2015
Year: 2015

Real estate projects are developed excessively in China in this decade. Many new housing districts are built, but they far exceed the actual demand in some cities. These cities with a high housing vacancy rate are called ghost cities. The real situation of vacant housing areas in China has not been studied in previous research. This study, using Baidu positioning data, presents the spatial distribution of the vacant housing areas in China and classifies cities with a large vacant housing area as cities or tourism sites. To the best of our knowledge, it is the first time that we detected and analyzed the ghost cities in China at such fine scale. To understand the human dynamic in ghost cities, we select one city and one tourism sites as cases to analyze the features of human dynamics. This study illustrates the capability of big data in sensing our cities objectively and comprehensively.
Regular Symmetry Patterns (Technical Report)
Venue: arXiv cs.LO 2015
Year: 2015

Symmetry reduction is a well-known approach for alleviating the state explosion problem in model checking. Automatically identifying symmetries in concurrent systems, however, is computationally expensive. We propose a symbolic framework for capturing symmetry patterns in parameterised systems (i.e. an infinite family of finite-state systems): two regular word transducers to represent, respectively, parameterised systems and symmetry patterns. The framework subsumes various types of symmetry relations ranging from weaker notions (e.g. simulation preorders) to the strongest notion (i.e. isomorphisms). Our framework enjoys two algorithmic properties: (1) symmetry verification: given a transducer, we can automatically check whether it is a symmetry pattern of a given system, and (2) symmetry synthesis: we can automatically generate a symmetry pattern for a given system in the form of a transducer. Furthermore, our symbolic language allows additional constraints that the symmetry patterns need to satisfy to be easily incorporated in the verification/synthesis. We show how these properties can help identify symmetry patterns in examples like dining philosopher protocols, self-stabilising protocols, and prioritised resource-allocator protocol. In some cases (e.g. Gries's coffee can problem), our technique automatically synthesises a safety-preserving finite approximant, which can then be verified for safety solely using a finite-state model checker.
On Differentially Private Online Collaborative Recommendation Systems
Venue: arXiv cs.CR 2015
Year: 2015

In collaborative recommendation systems, privacy may be compromised, as users' opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation system, and we measure users' privacy in terms of the standard differential privacy. We give the first quantitative analysis of the trade-offs between recommendation quality and users' privacy in such a system by showing a lower bound on the best achievable privacy for any non-trivial algorithm, and proposing a near-optimal algorithm. From our results, we find that there is actually little trade-off between recommendation quality and privacy for any non-trivial algorithm. Our results also identify the key parameters that determine the best achievable privacy.
Attention with Intention for a Neural Network Conversation Model
Venue: arXiv cs.NE 2015
Year: 2015

In a conversation or a dialogue process, attention and intention play intrinsic roles. This paper proposes a neural network based approach that models the attention and intention processes. It essentially consists of three recurrent networks. The encoder network is a word-level model representing source side sentences. The intention network is a recurrent network that models the dynamics of the intention process. The decoder network is a recurrent network produces responses to the input from the source side. It is a language model that is dependent on the intention and has an attention mechanism to attend to particular source side words, when predicting a symbol in the response. The model is trained end-to-end without labeling data. Experiments show that this model generates natural responses to user inputs.
Channel Estimation Techniques for Diffusion-Based Molecular Communications
Venue: arXiv cs.IT 2015
Year: 2015

In molecular communication (MC) systems, the expected number of molecules observed at the receiver over time after the instantaneous release of molecules by the transmitter is referred to as the channel impulse response (CIR). Knowledge of the CIR is needed for the design of detection and equalization schemes. In this paper, we present a training-based CIR estimation framework for MC systems which aims at estimating the CIR based on the observed number of molecules at the receiver due to emission of a sequence of known numbers of molecules by the transmitter. In particular, we derive maximum likelihood (ML) and least sum of square errors (LSSE) estimators. We also study the Cramer Rao (CR) lower bound and training sequence design for the considered system. Simulation results confirm the analysis and compare the performance of the proposed estimation techniques with the CR lower bound.
The "Most informative boolean function" conjecture holds for high noise
Venue: arXiv cs.IT 2015
Year: 2015

We prove the "Most informative boolean function" conjecture of Courtade and Kumar for high noise $ε\ge 1/2 - δ$, for some absolute constant $δ> 0$. Namely, if $X$ is uniformly distributed in $\{0,1\}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $ε$, then, provided $ε\ge 1/2 - δ$, for any boolean function $f$ holds $I(f(X);Y) \le 1 - H(ε)$. This conjecture was previously known to hold only for balanced functions.
Close Communities in Social Networks: Boroughs and 2-Clubs
Venue: arXiv cs.SI 2015
Year: 2015

The structure of close communication, contacts and association in social networks is studied in the form of maximal subgraphs of diameter 2 (2-clubs), corresponding to three types of close communities: hamlets, social circles and coteries. The concept of borough of a graph is defined and introduced. Each borough is a chained union of 2-clubs of the network and any 2-club of the network belongs to one borough. Thus the set of boroughs of a network, together with the 2-clubs held by them, are shown to contain the structure of close communication in a network. Applications are given with examples from real world network data.
Noisy Index Coding with Quadrature Amplitude Modulation (QAM)
Venue: arXiv cs.IT 2015
Year: 2015

This paper discusses noisy index coding problem over Gaussian broadcast channel. We propose a technique for mapping the index coded bits to M-QAM symbols such that the receivers whose side information satisfies certain conditions get coding gain, which we call the QAM side information coding gain. We compare this with the PSK side information coding gain, which was discussed in "Index Coded PSK Modulation," arXiv:1356200, [cs.IT] 19 September 2015.
National research impact indicators from Mendeley readers
Venue: arXiv cs.DL 2015
Year: 2015

National research impact indicators derived from citation counts are used by governments to help assess their national research performance and to identify the effect of funding or policy changes. Citation counts lag research by several years, however, and so their information is somewhat out of date. Some of this lag can be avoided by using readership counts from the social reference sharing site Mendeley because these accumulate more quickly than citations. This article introduces a method to calculate national research impact indicators from Mendeley, using citation counts from older time periods to partially compensate for international biases in Mendeley readership. A refinement to accommodate recent national changes in Mendeley uptake makes little difference, despite being theoretically more accurate. The Mendeley patterns using the methods broadly reflect the results from similar calculations with citations and seem to reflect impact trends about a year earlier. Nevertheless, the reasons for the differences between the indicators from the two data sources are unclear.