OpenRaiser/Intern-Atlas huggingface dataset:
PAC Quasi-automatizability of Resolution over Restricted Distributions
Venue: arXiv cs.DS 2013
Year: 2013

We consider principled alternatives to unsupervised learning in data mining by situating the learning task in the context of the subsequent analysis task. Specifically, we consider a query-answering (hypothesis-testing) task: In the combined task, we decide whether an input query formula is satisfied over a background distribution by using input examples directly, rather than invoking a two-stage process in which (i) rules over the distribution are learned by an unsupervised learning algorithm and (ii) a reasoning algorithm decides whether or not the query formula follows from the learned rules. In a previous work (2013), we observed that the learning task could satisfy numerous desirable criteria in this combined context -- effectively matching what could be achieved by agnostic learning of CNFs from partial information -- that are not known to be achievable directly. In this work, we show that likewise, there are reasoning tasks that are achievable in such a combined context that are not known to be achievable directly (and indeed, have been seriously conjectured to be impossible, cf. (Alekhnovich and Razborov, 2008)). Namely, we test for a resolution proof of the query formula of a given size in quasipolynomial time (that is, "quasi-automatizing" resolution). The learning setting we consider is a partial-information, restricted-distribution setting that generalizes learning parities over the uniform distribution from partial information, another task that is known not to be achievable directly in various models (cf. (Ben-David and Dichterman, 1998) and (Michael, 2010)).
DELTACON: A Principled Massive-Graph Similarity Function
Venue: arXiv cs.SI 2013
Year: 2013

How much did a network change since yesterday? How different is the wiring between Bob's brain (a left-handed male) and Alice's brain (a right-handed female)? Graph similarity with known node correspondence, i.e. the detection of changes in the connectivity of graphs, arises in numerous settings. In this work, we formally state the axioms and desired properties of the graph similarity functions, and evaluate when state-of-the-art methods fail to detect crucial connectivity changes in graphs. We propose DeltaCon, a principled, intuitive, and scalable algorithm that assesses the similarity between two graphs on the same nodes (e.g. employees of a company, customers of a mobile carrier). Experiments on various synthetic and real graphs showcase the advantages of our method over existing similarity measures. Finally, we employ DeltaCon to real applications: (a) we classify people to groups of high and low creativity based on their brain connectivity graphs, and (b) do temporal anomaly detection in the who-emails-whom Enron graph.
A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
Venue: arXiv cs.SI 2013
Year: 2013

The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called "communities". One popular approach to find communities is to maximize a quality function known as {\em modularity} to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an $\ell_2$ balance term. By employing numerical techniques from image processing and $\ell_1$ compressive sensing -- such as convex splitting and the Merriman-Bence-Osher (MBO) scheme -- we develop a variational algorithm for the minimization problem. We present our computational results using both synthetic benchmark networks and real data.
What are Chinese Talking about in Hot Weibos?
Venue: arXiv cs.SI 2013
Year: 2013

SinaWeibo is a Twitter-like social network service emerging in China in recent years. People can post weibos (microblogs) and communicate with others on it. Based on a dataset of 650 million weibos from August 2009 to January 2012 crawled from APIs of SinaWeibo, we study the hot ones that have been reposted for at least 1000 times. We find that hot weibos can be roughly classified into eight categories, i.e. Entertainment & Fashion, Hot Social Events, Leisure & Mood, Life & Health, Seeking for Help, Sales Promotion, Fengshui & Fortune and Deleted Weibos. In particular, Leisure & Mood and Hot Social Events account for almost 65% of all the hot weibos. This reflects very well the fundamental dual-structure of the current society of China: On the one hand, economy has made a great progress and quite a part of people are now living a relatively prosperous and fairly easy life. On the other hand, there still exist quite a lot of serious social problems, such as government corruptions and environmental pollutions. It is also shown that users' posting and reposting behaviors are greatly affected by their identity factors (gender, verification status, and regional location). For instance, (1) Two thirds of the hot weibos are created by male users. (2) Although verified users account for only 0.1% in SinaWeibo, 46.5% of the hot weibos are contributed by them. Very interestingly, 39.2% are written by SPA users. A more or less pathetic fact is that only 14.4% of the hot weibos are created by grassroots (individual users that are neither SPA nor verified). (3) Users from different areas of China have distinct posting and reposting behaviors which usually reflect very their local cultures. Homophily is also examined for people's reposting behaviors.
Efficient Calculation of Determinants of Symbolic Matrices with Many Variables
Venue: arXiv cs.SC 2013
Year: 2013

Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.
Modulation Coding for Flash Memories
Venue: arXiv cs.IT 2013
Year: 2013

The aggressive scaling down of flash memories has threatened data reliability since the scaling down of cell sizes gives rise to more serious degradation mechanisms such as cell-to-cell interference and lateral charge spreading. The effect of these mechanisms has pattern dependency and some data patterns are more vulnerable than other ones. In this paper, we will categorize data patterns taking into account degradation mechanisms and pattern dependency. In addition, we propose several modulation coding schemes to improve the data reliability by transforming original vulnerable data patterns into more robust ones.
Forensic Analysis of Instant Messenger Applications on Android Devices
Venue: arXiv cs.CY 2013
Year: 2013

This paper focuses on conducting forensic data analysis of 2 widely used IMs applications on Android phones WhatsApp and Viber. The tests and analysis were performed with the aim of determining what data and information can be found on the devices internal memory for instant messengers eg chat messaging logs and history send & received image or video files etc. The experiments and results show that heavy amount of potential evidences and valuable data can be found on Android phones by forensic investigators.
Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem
Venue: arXiv cs.CC 2013
Year: 2013

In analogy with epsilon-biased sets over Z_2^n, we construct explicit epsilon-biased sets over nonabelian finite groups G. That is, we find sets S subset G such that | Exp_{x in S} rho(x)| <= epsilon for any nontrivial irreducible representation rho. Equivalently, such sets make G's Cayley graph an expander with eigenvalue |lambda| <= epsilon. The Alon-Roichman theorem shows that random sets of size O(log |G| / epsilon^2) suffice. For groups of the form G = G_1 x ... x G_n, our construction has size poly(max_i |G_i|, n, epsilon^{-1}), and we show that a set S \subset G^n considered by Meka and Zuckerman that fools read-once branching programs over G is also epsilon-biased in this sense. For solvable groups whose abelian quotients have constant exponent, we obtain epsilon-biased sets of size (log |G|)^{1+o(1)} poly(epsilon^{-1}). Our techniques include derandomized squaring (in both the matrix product and tensor product senses) and a Chernoff-like bound on the expected norm of the product of independently random operators that may be of independent interest.
Towards an Infrastructure-less SOA for Mobile Web Service Composition
Venue: arXiv cs.DC 2013
Year: 2013

Service composition enables customizable services to be provided to the service consumers. Since the capabilities and the performances of mobile devices (e.g., smart phone, PDA, handheld media player) have improved, a mobile device can be utilized to interact with external mobile service providers towards providing composite Web service to remote clients. Existing approaches on mobile-hosted service composition are usually platform dependent, and rely on centralized infrastructure. Such approaches are not feasible in an open, mobile infrastructure-less environment, in which networked services are implemented using different technologies, devices are capable of dynamically joining or leaving the network, and a centralized management entity is nonexistent. This paper proposes a solution to enable mobile Web service composition in an open, infrastructure-less environment based on loosely coupled SOA techniques.
Joint On-the-Fly Network Coding/Video Quality Adaptation for Real-Time Delivery
Venue: arXiv cs.MM 2013
Year: 2013

This paper introduces a redundancy adaptation algorithm for an on-the-fly erasure network coding scheme called Tetrys in the context of real-time video transmission. The algorithm exploits the relationship between the redundancy ratio used by Tetrys and the gain or loss in encoding bit rate from changing a video quality parameter called the Quantization Parameter (QP). Our evaluations show that with equal or less bandwidth occupation, the video protected by Tetrys with redundancy adaptation algorithm obtains a PSNR gain up to or more 4 dB compared to the video without Tetrys protection. We demonstrate that the Tetrys redundancy adaptation algorithm performs well with the variations of both loss pattern and delay induced by the networks. We also show that Tetrys with the redundancy adaptation algorithm outperforms FEC with and without redundancy adaptation.
The Tap code - a code similar to Morse code for communication by tapping
Venue: arXiv cs.IT 2013
Year: 2013

A code is presented for fast, easy and efficient communication over channels that allow only two signal types: a single sound (e.g. a knock), or no sound (i.e. silence). This is a true binary code while Morse code is a ternary code and does not work in such situations. Thus the presented code is more universal than Morse and can be used in much more situations. Additionally it is very tolerant to variations in signal strength or duration. The paper contains various ways in which the code can be derived, that all lead to the same code. It also contains a comparison to other, similar codes, including the Morse code, in regards to efficiency and other attributes. The replacement of Morse code with Tap code is not proposed.
Impact maturity times and citation time windows: The 2-year maximum journal impact factor
Venue: arXiv cs.DL 2013
Year: 2013

Journal metrics are employed for the assessment of scientific scholar journals from a general bibliometric perspective. In this context, the Thomson Reuters journal impact factors (JIF) are the citation-based indicators most used. The 2-year journal impact factor (2-JIF) counts citations to one and two year old articles, while the 5-year journal impact factor (5-JIF) counts citations from one to five year old articles. Nevertheless, these indicators are not comparable among fields of science for two reasons: (i) each field has a different impact maturity time, and (ii) because of systematic differences in publication and citation behaviour across disciplines. In fact, the 5-JIF firstly appeared in the Journal Citation Reports (JCR) in 2007 with the purpose of making more comparable impacts in fields in which impact matures slowly. However, there is not an optimal fixed impact maturity time valid for all the fields. In some of them two years provides a good performance whereas in others three or more years are necessary. Therefore, there is a problem when comparing a journal from a field in which impact matures slowly with a journal from a field in which impact matures rapidly. In this work, we propose the 2-year maximum journal impact factor (2M-JIF), a new impact indicator that considers the 2-year rolling citation time window of maximum impact instead of the previous 2-year time window. Finally, an empirical application comparing 2-JIF, 5-JIF, and 2M-JIF shows that the maximum rolling target window reduces the between-group variance with respect to the within-group variance in a random sample of about six hundred journals from eight different fields.
Comparative Study of Simulation for Vehicular Ad-hoc Network
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we have discussed about the number of automobiles that has been increased on the road in the past few years. Due to high density of vehicles, the potential threats and road accident is increasing. Wireless technology is aiming to equip technology in vehicles to reduce these factors by sending messages to each other. The vehicular safety application should be thoroughly tested before it is deployed in a real world to use. Simulator tool has been preferred over out door experiment because it simple, easy and cheap. VANET requires that a traffic and network simulator should be used together to perform this test. Many tools exist for this purpose but most of them have the problem with the proper interaction. Simulating vehicular networks with external stimulus to analyze its effect on wireless communication but to do this job a good simulator is also needed.
Temporal Description Logic for Ontology-Based Data Access (Extended Version)
Venue: arXiv cs.LO 2013
Year: 2013

Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a temporal description logic, TQL, that extends the standard ontology language OWL 2 QL, provides basic means for temporal conceptual modelling and ensures first-order rewritability of conjunctive queries for suitably defined data instances with validity time.
Mobility Models for Vehicular Ad-hoc Network Simulation
Venue: arXiv cs.NI 2013
Year: 2013

One of the emerging applications that belong to ambient systems is to transparently and directly interconnect vehicles on roads, making an ad hoc network that enables a variety of applications through distributed software without the need of any fixed and dedicated infrastructure. The network as well as the embedded computers and sensors in the vehicle will be invisible to the driver, who will get the required services during his journey. New type of ad hoc network is the Vehicular Ad hoc Network, in which vehicles constitute the mobile nodes in the network. Due to the prohibitive cost of deploying and implementing such as system in a real world, most research work in VANET relies on simulations for evaluation purpose. The key concept for VANET simulations is a real world vehicular mobility model which will ensures conclusions drawn from simulation experiments will carry through to real world deployments. In this paper we present a tool SUMO, MOVE that allows users to easily generate real world mobility models for VANET simulations. MOVE tool is built on top of SUMO which is open source micro traffic simulator. Output of MOVE is a real world mobility model and can used by NS-2 and Qual-net simulator. In this paper we evaluate and compare ad hoc routing performance for vehicular nodes using MOVE, which is using random way point model. The simulation results are obtained when nodes are moving according to a real world mobility model which is significantly different from that of the generally used random way point model.
Carbon Dating The Web: Estimating the Age of Web Resources
Venue: arXiv cs.IR 2013
Year: 2013

In the course of web research it is often necessary to estimate the creation datetime for web resources (in the general case, this value can only be estimated). While it is feasible to manually establish likely datetime values for small numbers of resources, this becomes infeasible if the collection is large. We present "carbon date", a simple web application that estimates the creation date for a URI by polling a number of sources of evidence and returning a machine-readable structure with their respective values. To establish a likely datetime, we poll bitly for the first time someone shortened the URI, topsy for the first time someone tweeted the URI, a Memento aggregator for the first time it appeared in a public web archive, Google's time of last crawl, and the Last-Modified HTTP response header of the resource itself. We also examine the backlinks of the URI as reported by Google and apply the same techniques for the resources that link to the URI. We evaluated our tool on a gold-standard data set of 1200 URIs in which the creation date was manually verified. We were able to estimate a creation date for 75.90% of the resources, with 32.78% having the correct value. Given the different nature of the URIs, the union of the various methods produces the best results. While the Google last crawl date and topsy account for nearly 66% of the closest answers, eliminating the web archives or Last-Modified from the results produces the largest overall negative impact on the results. The carbon date application is available for download or use via a webAPI.
An optimal lower bound for monotonicity testing over hypergrids
Venue: arXiv cs.DS 2013
Year: 2013

For positive integers $n, d$, consider the hypergrid $[n]^d$ with the coordinate-wise product partial ordering denoted by $\prec$. A function $f: [n]^d \mapsto \mathbb{N}$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$. A function $f$ is $\eps$-far from monotone if at least an $\eps$-fraction of values must be changed to make $f$ monotone. Given a parameter $\eps$, a \emph{monotonicity tester} must distinguish with high probability a monotone function from one that is $\eps$-far. We prove that any (adaptive, two-sided) monotonicity tester for functions $f:[n]^d \mapsto \mathbb{N}$ must make $Ω(\eps^{-1}d\log n - \eps^{-1}\log \eps^{-1})$ queries. Recent upper bounds show the existence of $O(\eps^{-1}d \log n)$ query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of $Ω(d \log n)$.
Exclusion and Guard Zones in DC-CDMA Ad Hoc Networks
Venue: arXiv cs.IT 2013
Year: 2013

The central issue in direct-sequence code-division multiple-access (DS-CDMA) ad hoc networks is the prevention of a near-far problem. This paper considers two types of guard zones that may be used to control the near-far problem: a fundamental exclusion zone and an additional CSMA guard zone that may be established by the carrier-sense multiple-access (CSMA) protocol. In the exclusion zone, no mobiles are physically present, modeling the minimum physical separation among mobiles that is always present in actual networks. Potentially interfering mobiles beyond a transmitting mobile's exclusion zone, but within its CSMA guard zone, are deactivated by the protocol. This paper provides an analysis of DS-CSMA networks with either or both types of guard zones. A network of finite extent with a finite number of mobiles and uniform clustering as the spatial distribution is modeled. The analysis applies a closed-form expression for the outage probability in the presence of Nakagami fading, conditioned on the network geometry. The tradeoffs between exclusion zones and CSMA guard zones are explored for DS-CDMA and unspread networks. The spreading factor and the guard-zone radius provide design flexibility in achieving specified levels of average outage probability and transmission capacity. The advantage of an exclusion zone over a CSMA guard zone is that since the network is not thinned, the number of active mobiles remains constant, and higher transmission capacities can be achieved.
K model for designing Data Driven Test Automation Frameworks and its Design Architecture Snow Leopard
Venue: arXiv cs.SE 2013
Year: 2013

Automated testing improves the efficiency of testing practice at various levels of projects in the organization. Unfortunately, we do not have a common architecture or common standards for designing frameworks across different test levels, projects and test tools which can assist developers, testers and business analysts. To address the above problem, in this paper, I have first proposed a unique reference model and then a design architecture using the proposed model for designing any Data Driven Automation Frameworks. The reference model is K model which can be used for modeling any data-driven automation framework. The unique Design architecture, based on above model is Snow Leopard.
Fair Sets of Some Class of Graphs
Venue: arXiv cs.DM 2013
Year: 2013

Given a non empty set $S$ of vertices of a graph, the partiality of a vertex with respect to $S$ is the difference between maximum and minimum of the distances of the vertex to the vertices of $S$. The vertices with minimum partiality constitute the fair center of the set. Any vertex set which is the fair center of some set of vertices is called a fair set. In this paper we prove that the induced subgraph of any fair set is connected in the case of trees and characterise block graphs as the class of chordal graphs for which the induced subgraph of all fair sets are connected. The fair sets of $K_{n}$, $K_{m,n}$, $K_{n}-e$, wheel graphs, odd cycles and symmetric even graphs are identified. The fair sets of the Cartesian product graphs are also discussed.
Patterns to analyze requirements of a Decisional Information System
Venue: arXiv cs.OH 2013
Year: 2013

The domain of analysis and conception of Decisional Information System (DIS) is, highly, applying new techniques and methods to succeed the process of the decision and minimizing the time of conception. Our objective in this paper is to define a group of patterns to ensure a systematic reuse of our approach to analyse a DIS s business requirements. We seek, through this work, to guide the discovery of an organizations business requirements, expressed as goals by introducing the notion of context, to promote good processes design for a DIS, to capitalize the process and models proposed in our approach and systematize reuse steps of this approach to analyze similar projects or adapt them as needed. The patterns are at the same time the process s patterns and product s patterns as they capitalize models and their associated processes. These patterns are represented according to the PSIGMA formalism.
Making Math Searchable in Wikipedia
Venue: arXiv cs.DL 2013
Year: 2013

Wikipedia, the world largest encyclopedia contains a lot of knowledge that is expressed as formulae exclusively. Unfortunately, this knowledge is currently not fully accessible by intelligent information retrieval systems. This immense body of knowledge is hidden form value-added services, such as search. In this paper, we present our MathSearch implementation for Wikipedia that enables users to perform a combined text and fully unlock the potential benefits.