OpenRaiser/Intern-Atlas huggingface dataset:
Seed Selection for Spread of Influence in Social Networks: Temporal vs. Static Approach
Venue: arXiv cs.SI 2014
Year: 2014

The problem of finding optimal set of users for influencing others in the social network has been widely studied. Because it is NP-hard, some heuristics were proposed to find sub-optimal solutions. Still, one of the commonly used assumption is the one that seeds are chosen on the static network, not the dynamic one. This static approach is in fact far from the real-world networks, where new nodes may appear and old ones dynamically disappear in course of time. The main purpose of this paper is to analyse how the results of one of the typical models for spread of influence - linear threshold - differ depending on the strategy of building the social network used later for choosing seeds. To show the impact of network creation strategy on the final number of influenced nodes - outcome of spread of influence, the results for three approaches were studied: one static and two temporal with different granularities, i.e. various number of time windows. Social networks for each time window encapsulated dynamic changes in the network structure. Calculation of various node structural measures like degree or betweenness respected these changes by means of forgetting mechanism - more recent data had greater influence on node measure values. These measures were, in turn, used for node ranking and their selection for seeding. All concepts were applied to experimental verification on five real datasets. The results revealed that temporal approach is always better than static and the higher granularity in the temporal social network while seeding, the more finally influenced nodes. Additionally, outdegree measure with exponential forgetting typically outperformed other time-dependent structural measures, if used for seed candidate ranking.
Simultaneous Finite Automata: An Efficient Data-Parallel Model for Regular Expression Matching
Venue: arXiv cs.FL 2014
Year: 2014

Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automaton so that it involves the simulation of transitions. Since an SFA itself has a good property of parallelism, we can develop easily a parallel implementation without overheads. We have implemented a regular expression matcher based on SFA, and it has achieved over 10-times speedups on an environment with dual hexa-core CPUs in a typical case.
Automated Attribution and Intertextual Analysis
Venue: arXiv cs.CL 2014
Year: 2014

In this work, we employ quantitative methods from the realm of statistics and machine learning to develop novel methodologies for author attribution and textual analysis. In particular, we develop techniques and software suitable for applications to Classical study, and we illustrate the efficacy of our approach in several interesting open questions in the field. We apply our numerical analysis techniques to questions of authorship attribution in the case of the Greek tragedian Euripides, to instances of intertextuality and influence in the poetry of the Roman statesman Seneca the Younger, and to cases of "interpolated" text with respect to the histories of Livy.
x-index: a fantastic new indicator for quantifying a scientist's scientific impact
Venue: arXiv cs.DL 2014
Year: 2014

h-index has become the most popular indicator for quantifying a scientist's scientific impact in various scientific fields. h-index is defined as the largest number of papers with citation number larger than or equal to h and it treats each citation equally. However, different citations usually come from different papers with different influence and quality, and a citation from a highly influential paper is a greater recognition of the target paper than a citation from an ordinary paper. Based on this assumption, we proposed a new indicator named x-index to quantify a scientist's scientific impact by considering only the citations coming from influential papers. x-index is defined as the largest number of papers with influential citation number larger than or equal to x, where each influential citation comes from a paper for which the average ACNPP (Average Citation Number Per Paper) of its authors larger than or equal to x . Through analysis on the APS dataset, we find that the proposed x-index has much better ability to discriminate between Physics Prize Winners and ordinary physicists.
"Translation can't change a name": Using Multilingual Data for Named Entity Recognition
Venue: arXiv cs.CL 2014
Year: 2014

Named Entities (NEs) are often written with no orthographic changes across different languages that share a common alphabet. We show that this can be leveraged so as to improve named entity recognition (NER) by using unsupervised word clusters from secondary languages as features in state-of-the-art discriminative NER systems. We observe significant increases in performance, finding that person and location identification is particularly improved, and that phylogenetically close languages provide more valuable features than more distant languages.
A Brief History of Web Crawlers
Venue: arXiv cs.IR 2014
Year: 2014

Web crawlers visit internet applications, collect data, and learn about new web pages from visited pages. Web crawlers have a long and interesting history. Early web crawlers collected statistics about the web. In addition to collecting statistics about the web and indexing the applications for search engines, modern crawlers can be used to perform accessibility and vulnerability checks on the application. Quick expansion of the web, and the complexity added to web applications have made the process of crawling a very challenging one. Throughout the history of web crawling many researchers and industrial groups addressed different issues and challenges that web crawlers face. Different solutions have been proposed to reduce the time and cost of crawling. Performing an exhaustive crawl is a challenging question. Additionally capturing the model of a modern web application and extracting data from it automatically is another open question. What follows is a brief history of different technique and algorithms used from the early days of crawling up to the recent days. We introduce criteria to evaluate the relative performance of web crawlers. Based on these criteria we plot the evolution of web crawlers and compare their performance
A note on the ring loading problem
Venue: arXiv cs.DM 2014
Year: 2014

The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than +(19/14)D, where D is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of +(3/2)D. We also present an improved lower bound of +1.1 D (previously +1.01 D) on the best possible bound and disprove a famous long-standing conjecture of Schrijver et al. in this context.
Ready for the design of voting rules?
Venue: arXiv cs.GT 2014
Year: 2014

The design of fair voting rules has been addressed quite often in the literature. Still, the so-called inverse problem is not entirely resolved. We summarize some achievements in this direction and formulate explicit open questions and conjectures.
Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of minimizing the regret in stochastic multi-armed bandit, when the measure of goodness of an arm is not the mean return, but some general function of the mean and the variance.We characterize the conditions under which learning is possible and present examples for which no natural algorithm can achieve sublinear regret.
CEGAR for Qualitative Analysis of Probabilistic Systems
Venue: arXiv cs.LO 2014
Year: 2014

We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
Robust Subspace Outlier Detection in High Dimensional Space
Venue: arXiv cs.AI 2014
Year: 2014

Rare data in a large-scale database are called outliers that reveal significant information in the real world. The subspace-based outlier detection is regarded as a feasible approach in very high dimensional space. However, the outliers found in subspaces are only part of the true outliers in high dimensional space, indeed. The outliers hidden in normal-clustered points are sometimes neglected in the projected dimensional subspace. In this paper, we propose a robust subspace method for detecting such inner outliers in a given dataset, which uses two dimensional-projections: detecting outliers in subspaces with local density ratio in the first projected dimensions; finding outliers by comparing neighbor's positions in the second projected dimensions. Each point's weight is calculated by summing up all related values got in the two steps projected dimensions, and then the points scoring the largest weight values are taken as outliers. By taking a series of experiments with the number of dimensions from 10 to 10000, the results show that our proposed method achieves high precision in the case of extremely high dimensional space, and works well in low dimensional space.
Bottleneck Partial-Matching Voronoi Diagrams and Applications
Venue: arXiv cs.CG 2014
Year: 2014

Given two point sets in the plane, we study the minimization of the bottleneck distance between a point set B and an equally-sized subset of a point set A under translations. We relate this problem to a Voronoi-type diagram and derive polynomial bounds for its complexity that are optimal in the size of A. We devise efficient algorithms for the construction of such a diagram and its lexicographic variant, which generalize to higher dimensions. We use the diagram to find an optimal bottleneck matching under translations, to compute a connecting path of minimum bottleneck cost between two positions of B, and to determine the maximum bottleneck cost in a convex polygon.
Design Of Fuzzy Logic Traffic Controller For Isolated Intersections With Emergency Vehicle Priority System Using MATLAB Simulation
Venue: arXiv cs.AI 2014
Year: 2014

Traffic is the chief puzzle problem which every country faces because of the enhancement in number of vehicles throughout the world, especially in large urban towns. Hence the need arises for simulating and optimizing traffic control algorithms to better accommodate this increasing demand. Fuzzy optimization deals with finding the values of input parameters of a complex simulated system which result in desired output. This paper presents a MATLAB simulation of fuzzy logic traffic controller for controlling flow of traffic in isolated intersections. This controller is based on the waiting time and queue length of vehicles at present green phase and vehicles queue lengths at the other phases. The controller controls the traffic light timings and phase difference to ascertain sebaceous flow of traffic with least waiting time and queue length. In this paper, the isolated intersection model used consists of two alleyways in each approach. Every outlook has different value of queue length and waiting time, systematically, at the intersection. The maximum value of waiting time and vehicle queue length has to be selected by using proximity sensors as inputs to controller for the ameliorate control traffic flow at the intersection. An intelligent traffic model and fuzzy logic traffic controller are developed to evaluate the performance of traffic controller under different pre-defined conditions for oleaginous flow of traffic. Additionally, this fuzzy logic traffic controller has emergency vehicle siren sensors which detect emergency vehicle movement like ambulance, fire brigade, Police Van etc. and gives maximum priority to him and pass preferred signal to it.
Do we need Asimov's Laws?
Venue: arXiv cs.AI 2014
Year: 2014

In this essay the stance on robots is discussed. The attitude against robots in history, starting in Ancient Greek culture until the industrial revolution is described. The uncanny valley and some possible explanations are given. Some differences in Western and Asian understanding of robots are listed and finally we answer the question raised with the title.
Many-Broadcast Channels: Definition and Capacity in the Degraded Case
Venue: arXiv cs.IT 2014
Year: 2014

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. Motivated by emerging systems with a massive number of users, this paper studies the new {\em many-user paradigm}, where the number of users is allowed to grow with the blocklength. The focus of this paper is the degraded many-broadcast channel model, whose number of users may grow as fast as linearly with the blocklength. A notion of capacity in terms of message length is defined and an example of Gaussian degraded many-broadcast channel is studied. In addition, a numerical example for the Gaussian degraded many-broadcast channel with fixed transmit power constraint is solved, where every user achieves strictly positive message length asymptotically.
KR$^3$: An Architecture for Knowledge Representation and Reasoning in Robotics
Venue: arXiv cs.AI 2014
Year: 2014

This paper describes an architecture that combines the complementary strengths of declarative programming and probabilistic graphical models to enable robots to represent, reason with, and learn from, qualitative and quantitative descriptions of uncertainty and knowledge. An action language is used for the low-level (LL) and high-level (HL) system descriptions in the architecture, and the definition of recorded histories in the HL is expanded to allow prioritized defaults. For any given goal, tentative plans created in the HL using default knowledge and commonsense reasoning are implemented in the LL using probabilistic algorithms, with the corresponding observations used to update the HL history. Tight coupling between the two levels enables automatic selection of relevant variables and generation of suitable action policies in the LL for each HL action, and supports reasoning with violation of defaults, noisy observations and unreliable actions in large and complex domains. The architecture is evaluated in simulation and on physical robots transporting objects in indoor domains; the benefit on robots is a reduction in task execution time of 39% compared with a purely probabilistic, but still hierarchical, approach.
Study on performance improvement of oil paint image filter algorithm using parallel pattern library
Venue: arXiv cs.CV 2014
Year: 2014

This paper gives a detailed study on the performance of oil paint image filter algorithm with various parameters applied on an image of RGB model. Oil Paint image processing, being very performance hungry, current research tries to find improvement using parallel pattern library. With increasing kernel-size, the processing time of oil paint image filter algorithm increases exponentially.
Data-flow Analysis of Programs with Associative Arrays
Venue: arXiv cs.SE 2014
Year: 2014

Dynamic programming languages, such as PHP, JavaScript, and Python, provide built-in data structures including associative arrays and objects with similar semantics-object properties can be created at run-time and accessed via arbitrary expressions. While a high level of security and safety of applications written in these languages can be of a particular importance (consider a web application storing sensitive data and providing its functionality worldwide), dynamic data structures pose significant challenges for data-flow analysis making traditional static verification methods both unsound and imprecise. In this paper, we propose a sound and precise approach for value and points-to analysis of programs with associative arrays-like data structures, upon which data-flow analyses can be built. We implemented our approach in a web-application domain-in an analyzer of PHP code.
Interactive Sensing and Decision Making in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

The proliferation of social media such as real time microblogging and online reputation systems facilitate real time sensing of social patterns and behavior. In the last decade, sensing and decision making in social networks have witnessed significant progress in the electrical engineering, computer science, economics, finance, and sociology research communities. Research in this area involves the interaction of dynamic random graphs, socio-economic analysis, and statistical inference algorithms. This monograph provides a survey, tutorial development, and discussion of four highly stylized examples: social learning for interactive sensing; tracking the degree distribution of social networks; sensing and information diffusion; and coordination of decision making via game-theoretic learning. Each of the four examples is motivated by practical examples, and comprises of a literature survey together with careful problem formulation and mathematical analysis. Despite being highly stylized, these examples provide a rich variety of models, algorithms and analysis tools that are readily accessible to a signal processing, control/systems theory, and applied mathematics audience.
What's the Gist? Privacy-Preserving Aggregation of User Profiles
Venue: arXiv cs.CR 2014
Year: 2014

Over the past few years, online service providers have started gathering increasing amounts of personal information to build user profiles and monetize them with advertisers and data brokers. Users have little control of what information is processed and are often left with an all-or-nothing decision between receiving free services or refusing to be profiled. This paper explores an alternative approach where users only disclose an aggregate model -- the "gist" -- of their data. We aim to preserve data utility and simultaneously provide user privacy. We show that this approach can be efficiently supported by letting users contribute encrypted and differentially-private data to an aggregator. The aggregator combines encrypted contributions and can only extract an aggregate model of the underlying data. We evaluate our framework on a dataset of 100,000 U.S. users obtained from the U.S. Census Bureau and show that (i) it provides accurate aggregates with as little as 100 users, (ii) it generates revenue for both users and data brokers, and (iii) its overhead is appreciably low.
Spectral Efficiency of Dynamic Coordinated Beamforming: A Stochastic Geometry Approach
Venue: arXiv cs.IT 2014
Year: 2014

This paper characterizes the performance of coordinated beamforming with dynamic clustering. A downlink model based on stochastic geometry is put forth to analyze the performance of such base station (BS) coordination strategy. Analytical expressions for the complementary cumulative distribution function (CCDF) of the instantaneous signal-to-interference ratio (SIR) are derived in terms of relevant system parameters, chiefly the number of BSs forming the coordination clusters, the number of antennas per BS, and the pathloss exponent. Utilizing this CCDF, with pilot overheads further incorporated into the analysis, we formulate the optimization of the BS coordination clusters for a given fading coherence. Our results indicate that (i) coordinated beamforming is most beneficial to users that are in the outer part of their cells yet in the inner part of their coordination cluster, and that (ii) the optimal cluster cardinality for the typical user is small and it scales with the fading coherence. Simulation results verify the exactness of the SIR distributions derived for stochastic geometries, which are further compared with the corresponding distributions for deterministic grid networks.
Consensus with an Abstract MAC Layer
Venue: arXiv cs.DC 2014
Year: 2014

In this paper, we study distributed consensus in the radio network setting. We produce new upper and lower bounds for this problem in an abstract MAC layer model that captures the key guarantees provided by most wireless MAC layers. In more detail, we first generalize the well-known impossibility of deterministic consensus with a single crash failure [FLP 1895] from the asynchronous message passing model to our wireless setting. Proceeding under the assumption of no faults, we then investigate the amount of network knowledge required to solve consensus in our model---an important question given that these networks are often deployed in an ad hoc manner. We prove consensus is impossible without unique ids or without knowledge of network size (in multihop topologies). We also prove a lower bound on optimal time complexity. We then match these lower bounds with a pair of new deterministic consensus algorithms---one for single hop topologies and one for multihop topologies---providing a comprehensive characterization of the consensus problem in the wireless setting. From a theoretical perspective, our results shed new insight into the role of network information and the power of MAC layer abstractions in solving distributed consensus. From a practical perspective, given the level of abstraction used by our model, our upper bounds can be easily implemented in real wireless devices on existing MAC layers while preserving their correctness guarantees---facilitating the development of wireless distributed systems.