OpenRaiser/Intern-Atlas huggingface dataset:
Exploring the relationship between the Engineering and Physical Sciences and the Health and Life Sciences by advanced bibliometric methods
Venue: arXiv cs.DL 2014
Year: 2014

We investigate the extent to which advances in the health and life sciences (HLS) are dependent on research in the engineering and physical sciences (EPS), particularly physics, chemistry, mathematics, and engineering. The analysis combines two different bibliometric approaches. The first approach to analyze the 'EPS-HLS interface' is based on term map visualizations of HLS research fields. We consider 16 clinical fields and five life science fields. On the basis of expert judgment, EPS research in these fields is studied by identifying EPS-related terms in the term maps. In the second approach, a large-scale citation-based network analysis is applied to publications from all fields of science. We work with about 22,000 clusters of publications, each representing a topic in the scientific literature. Citation relations are used to identify topics at the EPS-HLS interface. The two approaches complement each other. The advantages of working with textual data compensate for the limitations of working with citation relations and the other way around. An important advantage of working with textual data is in the in-depth qualitative insights it provides. Working with citation relations, on the other hand, yields many relevant quantitative statistics. We find that EPS research contributes to HLS developments mainly in the following five ways: new materials and their properties; chemical methods for analysis and molecular synthesis; imaging of parts of the body as well as of biomaterial surfaces; medical engineering mainly related to imaging, radiation therapy, signal processing technology, and other medical instrumentation; mathematical and statistical methods for data analysis. In our analysis, about 10% of all EPS and HLS publications are classified as being at the EPS-HLS interface. This percentage has remained more or less constant during the past decade.
Imaging with Kantorovich-Rubinstein discrepancy
Venue: arXiv cs.CV 2014
Year: 2014

We propose the use of the Kantorovich-Rubinstein norm from optimal transport in imaging problems. In particular, we discuss a variational regularisation model endowed with a Kantorovich-Rubinstein discrepancy term and total variation regularization in the context of image denoising and cartoon-texture decomposition. We point out connections of this approach to several other recently proposed methods such as total generalized variation and norms capturing oscillating patterns. We also show that the respective optimization problem can be turned into a convex-concave saddle point problem with simple constraints and hence, can be solved by standard tools. Numerical examples exhibit interesting features and favourable performance for denoising and cartoon-texture decomposition.
A Multi Level Data Fusion Approach for Speaker Identification on Telephone Speech
Venue: arXiv cs.SD 2014
Year: 2014

Several speaker identification systems are giving good performance with clean speech but are affected by the degradations introduced by noisy audio conditions. To deal with this problem, we investigate the use of complementary information at different levels for computing a combined match score for the unknown speaker. In this work, we observe the effect of two supervised machine learning approaches including support vectors machines (SVM) and naïve bayes (NB). We define two feature vector sets based on mel frequency cepstral coefficients (MFCC) and relative spectral perceptual linear predictive coefficients (RASTA-PLP). Each feature is modeled using the Gaussian Mixture Model (GMM). Several ways of combining these information sources give significant improvements in a text-independent speaker identification task using a very large telephone degraded NTIMIT database.
Concurrent Kleene Algebra of Partial Strings
Venue: arXiv cs.LO 2014
Year: 2014

Concurrent Kleene Algebra (CKA) is a recently proposed algebraic structure by Hoare and collaborators that unifies the laws of concurrent programming. The unifying power of CKA rests largely on the so-called exchange law that describes how concurrent and sequential composition operators can be interchanged. Based on extensive theoretical work on true concurrency in the past, this paper extends Gischer's pomset model with least fixed point operators and formalizes the program refinement relation by Ésik's monotonic bijective morphisms to construct a partial order model of CKA. The existence of such a model is relevant when we want to prove and disprove properties about concurrent programs with loops. In particular, it gives a foundation for the analysis of programs that concurrently access relaxed memory as shown in subsequent work.
Technical Report: Dealing with Undependable Workers in Decentralized Network Supercomputing
Venue: arXiv cs.DC 2014
Year: 2014

Internet supercomputing is an approach to solving partitionable, computation-intensive problems by harnessing the power of a vast number of interconnected computers. This paper presents a new algorithm for the problem of using network supercomputing to perform a large collection of independent tasks, while dealing with undependable processors. The adversary may cause the processors to return bogus results for tasks with certain probabilities, and may cause a subset $F$ of the initial set of processors $P$ to crash. The adversary is constrained in two ways. First, for the set of non-crashed processors $P-F$, the \emph{average} probability of a processor returning a bogus result is inferior to $\frac{1}{2}$. Second, the adversary may crash a subset of processors $F$, provided the size of $P-F$ is bounded from below. We consider two models: the first bounds the size of $P-F$ by a fractional polynomial, the second bounds this size by a poly-logarithm. Both models yield adversaries that are much stronger than previously studied. Our randomized synchronous algorithm is formulated for $n$ processors and $t$ tasks, with $n\le t$, where depending on the number of crashes each live processor is able to terminate dynamically with the knowledge that the problem is solved with high probability. For the adversary constrained by a fractional polynomial, the round complexity of the algorithm is $O(\frac{t}{n^\varepsilon}\log{n}\log{\log{n}})$, its work is $O(t\log{n} \log{\log{n}})$ and message complexity is $O(n\log{n}\log{\log{n}})$. For the poly-log constrained adversary, the round complexity is $O(t)$, work is $O(t n^{\varepsilon})$, %$O(t \, poly \log{n})$, and message complexity is $O(n^{1+\varepsilon})$ %$O(n \, poly \log{n})$. All bounds are shown to hold with high probability.
Classification-based Approximate Policy Iteration: Experiments and Extended Discussions
Venue: arXiv cs.LG 2014
Year: 2014

Tackling large approximate dynamic programming or reinforcement learning problems requires methods that can exploit regularities, or intrinsic structure, of the problem in hand. Most current methods are geared towards exploiting the regularities of either the value function or the policy. We introduce a general classification-based approximate policy iteration (CAPI) framework, which encompasses a large class of algorithms that can exploit regularities of both the value function and the policy space, depending on what is advantageous. This framework has two main components: a generic value function estimator and a classifier that learns a policy based on the estimated value function. We establish theoretical guarantees for the sample complexity of CAPI-style algorithms, which allow the policy evaluation step to be performed by a wide variety of algorithms (including temporal-difference-style methods), and can handle nonparametric representations of policies. Our bounds on the estimation error of the performance loss are tighter than existing results. We also illustrate this approach empirically on several problems, including a large HIV control task.
How did the Suicide Act and Speak Differently Online? Behavioral and Linguistic Features of China's Suicide Microblog Users
Venue: arXiv cs.SI 2014
Year: 2014

Background: Suicide issue is of great concern in China. Social media provides an active approach to understanding suicide individuals in terms of their behavior and language use. Aims: This study investigates how suicide Microblog users in China act and speak differently on social media from others. Methods: Hypothesis testing in behavioral and linguistic features was performed between a target group of 33 Chinese Microblog users who have committed suicide and a control group of 30 active users without suicidal ideation. Results: Suicide group significantly outnumbered control group in the extent of openly published posts and self-reference, and the intensity of using 7 word categories: negative words/social process words/cognitive process words/emotion process words/negative emotion words/exclusive words/physiological process words. Limitations: Information collection and confirmation of suicide users remain difficult. Conclusions: It is revealed that suicide people vary from others in certain behavioral and linguistic features in social media. This study fills the niche of suicide studies by noting specified indicators of suicide ideation for Chinese individuals online, providing insights of constructing an online alarm system for early detection and intervention of suicidal individuals.
Lockdown: Dynamic Control-Flow Integrity
Venue: arXiv cs.CR 2014
Year: 2014

Applications written in low-level languages without type or memory safety are especially prone to memory corruption. Attackers gain code execution capabilities through such applications despite all currently deployed defenses by exploiting memory corruption vulnerabilities. Control-Flow Integrity (CFI) is a promising defense mechanism that restricts open control-flow transfers to a static set of well-known locations. We present Lockdown, an approach to dynamic CFI that protects legacy, binary-only executables and libraries. Lockdown adaptively learns the control-flow graph of a running process using information from a trusted dynamic loader. The sandbox component of Lockdown restricts interactions between different shared objects to imported and exported functions by enforcing fine-grained CFI checks. Our prototype implementation shows that dynamic CFI results in low performance overhead.
Co-Following on Twitter
Venue: arXiv cs.SI 2014
Year: 2014

We present an in-depth study of co-following on Twitter based on the observation that two Twitter users whose followers have similar friends are also similar, even though they might not share any direct links or a single mutual follower. We show how this observation contributes to (i) a better understanding of language-agnostic user classification on Twitter, (ii) eliciting opportunities for Computational Social Science, and (iii) improving online marketing by identifying cross-selling opportunities. We start with a machine learning problem of predicting a user's preference among two alternative choices of Twitter friends. We show that co-following information provides strong signals for diverse classification tasks and that these signals persist even when (i) the most discriminative features are removed and (ii) only relatively "sparse" users with fewer than 152 but more than 43 Twitter friends are considered. Going beyond mere classification performance optimization, we present applications of our methodology to Computational Social Science. Here we confirm stereotypes such as that the country singer Kenny Chesney (@kennychesney) is more popular among @GOP followers, whereas Lady Gaga (@ladygaga) enjoys more support from @TheDemocrats followers. In the domain of marketing we give evidence that celebrity endorsement is reflected in co-following and we demonstrate how our methodology can be used to reveal the audience similarities between Apple and Puma and, less obviously, between Nike and Coca-Cola. Concerning a user's popularity we find a statistically significant connection between having a more "average" followership and having more followers than direct rivals. Interestingly, a \emph{larger} audience also seems to be linked to a \emph{less diverse} audience in terms of their co-following.
Enhanced Trellis Coded Multiple Access (ETCMA)
Venue: arXiv cs.IT 2014
Year: 2014

We propose an enhanced version of trellis coded multiple access (TCMA), an overloaded multiple access scheme that outperforms the original TCMA in terms of achieved spectral efficiency. Enhanced TCMA (ETCMA) performs simultaneous transmission of multiple data streams intended for users experiencing similar signal-to-noise ratios and can be employed both in the uplink and in the downlink of wireless systems, thus overcoming one of the main limitations of TCMA. Thanks to a new receiver algorithm, ETCMA is capable of delivering a significantly higher spectral efficiency. We show that ETCMA approaches the capacity of the Additive White Gaussian Noise channel for a wide range of signal-to-noise ratios.
Predicting Lifetime of Dynamical Networks Experiencing Persistent Random Attacks
Venue: arXiv cs.SI 2014
Year: 2014

Empirical estimation of critical points at which complex systems abruptly flip from one state to another is among the remaining challenges in network science. However, due to the stochastic nature of critical transitions it is widely believed that critical points are difficult to estimate, and it is even more difficult, if not impossible, to predict the time such transitions occur [1-4]. We analyze a class of decaying dynamical networks experiencing persistent attacks in which the magnitude of the attack is quantified by the probability of an internal failure, and there is some chance that an internal failure will be permanent. When the fraction of active neighbors declines to a critical threshold, cascading failures trigger a network breakdown. For this class of network we find both numerically and analytically that the time to the network breakdown, equivalent to the network lifetime, is inversely dependent upon the magnitude of the attack and logarithmically dependent on the threshold. We analyze how permanent attacks affect dynamical network robustness and use the network lifetime as a measure of dynamical network robustness offering new methodological insight into system dynamics.
Extraction of Multi-layered Social Networks from Activity Data
Venue: arXiv cs.SI 2014
Year: 2014

The data gathered in all kind of web-based systems, which enable users to interact with each other, provides an opportunity to extract social networks that consist of people and relationships between them. The emerging structures are very complex due to the number and type of discovered connections. In webbased systems, the characteristic element of each interaction between users is that there is always an object that serves as a communication medium. This can be e.g. an email sent from one user to another or post at the forum authored by one user and commented by others. Based on these objects and activities that users perform towards them, different kinds of relationships can be identified and extracted. Additional challenge arises from the fact that hierarchies can exist between objects, e.g. a forum consists of one or more groups of topics, and each of them contains topics that finally include posts. In this paper, we propose a new method for creation of multi-layered social network based on the data about users activities towards different types of objects between which the hierarchy exists. Due to the flattening, preprocessing procedure new layers and new relationships in the multi-layered social network can be identified and analysed.
CBM-Of-TRaCE: An Ontology-Driven Framework for the Improvement of Business Service Traceability, Consistency Management and Reusability
Venue: arXiv cs.SE 2014
Year: 2014

In this paper, we represent CBM-Of-TRaCE which is an ontological framework that integrates two aspects of business components: conceptual and methodology. In the development of our framework we have taken IBM Actionable Business Approach (ABA) in to consideration. We evaluate our framework through some aspects such as support and facilitation for a business from five different aspects: service-orientation, business process, management integration, reusability improvement, consistency rules, and traceability. As well, we demonstrate the compatibility of our CBM-Of-TRaCE with ABA four phases.
Why do simple algorithms for triangle enumeration work in the real world?
Venue: arXiv cs.SI 2014
Year: 2014

Listing all triangles is a fundamental graph operation. Triangles can have important interpretations in real-world graphs, especially social and other interaction networks. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? We study one of the most prevalent algorithms used by practitioners. A trivial algorithm enumerates all paths of length $2$, and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length $2$ where the middle vertex has the lowest degree. It is easily implemented and is empirically known to give remarkable speedups over the trivial algorithm. We study the behavior of this algorithm over graphs with heavy-tailed degree distributions, a defining feature of real-world graphs. The erased configuration model (ECM) efficiently generates a graph with asymptotically (almost) any desired degree sequence. We show that the expected running time of this algorithm over the distribution of graphs created by the ECM is controlled by the $\ell_{4/3}$-norm of the degree sequence. Norms of the degree sequence are a measure of the heaviness of the tail, and it is precisely this feature that allows non-trivial speedups of simple triangle enumeration algorithms. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent $α\geq 7/3$, and non-trivial speedup whenever $α\in (2,3)$.
Frugal Streaming for Estimating Quantiles:One (or two) memory suffices
Venue: arXiv cs.DB 2014
Year: 2014

Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one needs to compute such statistical quantities for each of a large number of groups, which additionally restricts the amount of memory available for the stream for any particular group. We address this challenge and introduce frugal streaming, that is algorithms that work with tiny -- typically, sub-streaming -- amount of memory per group. We design a frugal algorithm that uses only one unit of memory per group to compute a quantile for each group. For stochastic streams where data items are drawn from a distribution independently, we analyze and show that the algorithm finds an approximation to the quantile rapidly and remains stably close to it. We also propose an extension of this algorithm that uses two units of memory per group. We show with extensive experiments with real world data from HTTP trace and Twitter that our frugal algorithms are comparable to existing streaming algorithms for estimating any quantile, but these existing algorithms use far more space per group and are unrealistic in frugal applications; further, the two memory frugal algorithm converges significantly faster than the one memory algorithm.
Improving legibility of natural deduction proofs is not trivial
Venue: arXiv cs.LO 2014
Year: 2014

In formal proof checking environments such as Mizar it is not merely the validity of mathematical formulas that is evaluated in the process of adoption to the body of accepted formalizations, but also the readability of the proofs that witness validity. As in case of computer programs, such proof scripts may sometimes be more and sometimes be less readable. To better understand the notion of readability of formal proofs, and to assess and improve their readability, we propose in this paper a method of improving proof readability based on Behaghel's First Law of sentence structure. Our method maximizes the number of local references to the directly preceding statement in a proof linearisation. It is shown that our optimization method is NP-complete.
Usage of Optimal Restructuring Plan in Detection of Code Smells
Venue: arXiv cs.SE 2014
Year: 2014

To remain useful for their users, software systems need to continuously enhance and extend their functionality. Nevertheless, in many object-oriented applications, features are not represented explicitly. The lack of modularization is known to make application features difficult to locate, to comprehend and to modify in isolation from one another. In our work, we implement restructuring using Featureous plug-in where we can change the classes between packages. In the previous literature works, lot of complexities arises while using the tool due to dependencies. Changes to the code without knowing the root cause of the problem leads to further production of new errors. So, we aim in finding the restructuring candidates which have to be rearranged, thereby applying changes to the code on those parts using the tool helps in ordered arrangement of the source code. Applying modularization to the restructuring candidates will lead to decrease in the human effort as well as tool effort in restructuring. Unwanted evolution of new errors will be eliminated
Opportunistic Beamforming using Dumb Basis Patterns in Multiple Access Cognitive Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate multiuser diversity in interference-limited Multiple Access (MAC) underlay cognitive channels with Line-of-Sight interference (LoS) from the secondary to the primary network. It is shown that for $N$ secondary users, and assuming Rician interference channels, the secondary sum capacity scales like $\log\left(\frac{K^{2}+K}{\mathcal{W}\left(\frac{K e^{K}}{N}\right)}\right)$, where $K$ is the $K$-factor of the Rician channels, and $\mathcal{W}(.)$ is the Lambert W function. Thus, LoS interference hinders the achievable multiuser diversity gain experienced in Rayleigh channels, where the sum capacity grows like $\log(N)$. To overcome this problem, we propose the usage of single radio Electronically Steerable Parasitic Array Radiator (ESPAR) antennas at the secondary mobile terminals. Using ESPAR antennas, we induce artificial fluctuations in the interference channels to restore the $\log(N)$ growth rate by assigning random weights to orthogonal {\it basis patterns}. We term this technique as {\it Random Aerial Beamforming} (RAB). While LoS interference is originally a source of capacity hindrance, we show that using RAB, it can actually be exploited to improve multiuser interference diversity by boosting the {\it effective number of users} with minimal hardware complexity.
Decision versions of optimization problems: cardinality constraint (lower bound) as a CNF Horn formula for Maximum Matching
Venue: arXiv cs.LO 2014
Year: 2014

We provide a formula for the lower bound in the form of $|F| \ge K$, in such a way that the decision version of unweighted non-bipartite matching can be solved in polynomial time. ~The parameter $K$ can vary from instance to instance. We assume that the domains, the set of vertices and the set of edges, are ordered. To our knowledge, no polynomially solvable satisfiability expression has been developed for this problem so far, or for that matter, for any decision problem derived from optimization. Hence for such problems, this opens up a new approach to solving them.