OpenRaiser/Intern-Atlas huggingface dataset:
A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --
Venue: arXiv cs.LG 2013
Year: 2013

Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are the first active algorithms for link classification with mistake bounds that hold for arbitrary signed networks.
A Rank-based Convex Hull method for Dense Data Sets
Venue: arXiv cs.CG 2013
Year: 2013

A novel 2-D method for computing the convex hull of a sufficiently dense set of n integer points is introduced. The approach employs a ranking function that avoids sorting the points directly thus reducing the overall time complexity. The ranked points create a simple polygonal chain from which the Convex Hull can be found using a suitable O(n) method. The result is achieved by placing a bound on the density (or ratio) of points to m, where m is the maximum value of the ranking function required to represent the set of points yielding an O(n+m) method. A fast method is then developed based on the bit length, p, of the data set which reduces this time further. The required conditions are easily satisfied by image processing methods which determine the Hulls of polygonal regions where the densities are in the range of 3%. Our experiments on a range problem domains show that this is not atypical. Since the complexity of the method is related to the bit size p for current machines (p=32, p=64) the method is for all practical purposes O(n). A short proof is provided.
The Weight Enumerator of Three Families of Cyclic Codes
Venue: arXiv cs.IT 2013
Year: 2013

Cyclic codes are a subclass of linear codes and have wide applications in consumer electronics, data storage systems, and communication systems due to their efficient encoding and decoding algorithms. Cyclic codes with many zeros and their dual codes have been a subject of study for many years. However, their weight distributions are known only for a very small number of cases. In general the calculation of the weight distribution of cyclic codes is heavily based on the evaluation of some exponential sums over finite fields. Very recently, Li, Hu, Feng and Ge studied a class of $p$-ary cyclic codes of length $p^{2m}-1$, where $p$ is a prime and $m$ is odd. They determined the weight distribution of this class of cyclic codes by establishing a connection between the involved exponential sums with the spectrum of Hermitian forms graphs. In this paper, this class of $p$-ary cyclic codes is generalized and the weight distribution of the generalized cyclic codes is settled for both even $m$ and odd $m$ alone with the idea of Li, Hu, Feng, and Ge. The weight distributions of two related families of cyclic codes are also determined.
A DSL for Mapping Abstract Syntax Models to Concrete Syntax Models in ModelCC
Venue: arXiv cs.PL 2013
Year: 2013

ModelCC is a model-based parser generator that decouples language design from language processing. ModelCC provides two different mechanisms to specify the mapping from an abstract syntax model to a concrete syntax model: metadata annotations defined on top of the abstract syntax model specification and a domain-specific language for defining ASM-CSM mappings. Using a domain-specific language to specify the mapping from abstract to concrete syntax models allows the definition of multiple concrete syntax models for the same abstract syntax model. In this paper, we describe the ModelCC domain-specific language for abstract syntax model to concrete syntax model mappings and we showcase its capabilities by providing a meta-definition of that domain-specific language.
Analyzing the Performance of LRU Caches under Non-Stationary Traffic Patterns
Venue: arXiv cs.NI 2013
Year: 2013

This work presents, to the best of our knowledge of the literature, the first analytic model to address the performance of an LRU (Least Recently Used) implementing cache under non-stationary traffic conditions, i.e., when the popularity of content evolves with time. We validate the accuracy of the model using Monte Carlo simulations. We show that the model is capable of accurately estimating the cache hit probability, when the popularity of content is non-stationary. We find that there exists a dependency between the performance of an LRU implementing cache and i) the lifetime of content in a system, ii) the volume of requests associated with it, iii) the distribution of content request volumes and iv) the shape of the popularity profile over time.
Mapping the network structure of science parks: An exploratory study of cross-sectoral interactions reflected on the web
Venue: arXiv cs.DL 2013
Year: 2013

This study introduces a method based on link analysis to investigate the structure of the R&D support infrastructure associated with science parks in order to determine whether this webometric approach gives plausible results. Three science parks from Yorkshire and the Humber in the UK were analysed with webometric and social network analysis techniques. Interlinking networks were generated through the combination of two different data sets extracted from three sources (Yahoo!, Bing, SocSciBot). These networks suggest that institutional sectors, representing business, universities and public bodies, are primarily tied together by a core formed by research institutions, support structure organisations and business developers. The comparison of the findings with traditional indicators suggests that the web-based networks reflect the offline conditions and policy measures adopted in the region, giving some evidence that the webometric approach is plausible to investigating science park networks. This is the first study that applies a web-based approach to investigate to what extent the science parks facilitate a closer interaction between the heterogeneous organisations that converge in R&D networks. This indicates that link analysis may help to get a first insight into the organisation of the R&D support infrastructure provided by science parks.
Centralized Lifetime Maximizing Tree For Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

To enable data aggregation among the event sources in wireless sensor networks and to reduce the communication cost there is a need to establish a coveraged tree structure inside any given event region to allow data reports to be aggregated at a single processing point prior to transmission to the network. In this paper we propose a novel technique to create one such tree which maximizes the lifetime of the event sources while they are constantly transmitting for data aggregation. We use the term Centralized Lifetime Maximizing Tree (CLMT) to denote this tree. CLMT features with identification of bottleneck node among the given set of nodes. This node collects the data from every other node via routes with the highest branch energy subject to condition loop is not created. By constructing tree in such a way, protocol is able to reduce the frequency of tree reconstruction, minimize the delay and maximize the functional lifetime of source nodes by minimizing the additional energy involved in tree reconstruction.
Downlink MIMO HetNets: Modeling, Ordering Results and Performance Analysis
Venue: arXiv cs.IT 2013
Year: 2013

We develop a general downlink model for multi-antenna heterogeneous cellular networks (HetNets), where base stations (BSs) across tiers may differ in terms of transmit power, target signal-to-interference-ratio (SIR), deployment density, number of transmit antennas and the type of multi-antenna transmission. In particular, we consider and compare space division multiple access (SDMA), single user beamforming (SU-BF), and baseline single-input single-output (SISO) transmission. For this general model, the main contributions are: (i) ordering results for both coverage probability and per user rate in closed form for any BS distribution for the three considered techniques, using novel tools from stochastic orders, (ii) upper bounds on the coverage probability assuming a Poisson BS distribution, and (iii) a comparison of the area spectral efficiency (ASE). The analysis concretely demonstrates, for example, that for a given total number of transmit antennas in the network, it is preferable to spread them across many single-antenna BSs vs. fewer multi-antenna BSs. Another observation is that SU-BF provides higher coverage and per user data rate than SDMA, but SDMA is in some cases better in terms of ASE.
Capacity Region Bounds and Resource Allocation for Two-Way OFDM Relay Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider two-way orthogonal frequency division multiplexing (OFDM) relay channels, where the direct link between the two terminal nodes is too weak to be used for data transmission. The widely known per-subcarrier decode-and-forward (DF) relay strategy, treats each subcarrier as a separate channel, and performs independent channel coding over each subcarrier. We show that this per-subcarrier DF relay strategy is only a suboptimal DF relay strategy, and present a multi-subcarrier DF relay strategy which utilizes cross-subcarrier channel coding to achieve a larger rate region. We then propose an optimal resource allocation algorithm to characterize the achievable rate region of the multi-subcarrier DF relay strategy. The computational complexity of this algorithm is much smaller than that of standard Lagrangian duality optimization algorithms. We further analyze the asymptotic performance of two-way relay strategies including the above two DF relay strategies and an amplify-and-forward (AF) relay strategy. The analysis shows that the multi-subcarrier DF relay strategy tends to achieve the capacity region of the two-way OFDM relay channels in the low signal-to-noise ratio (SNR) regime, while the AF relay strategy tends to achieve the multiplexing gain region of the two-way OFDM relay channels in the high SNR regime. Numerical results are provided to justify all the analytical results and the efficacy of the proposed optimal resource allocation algorithm.
Security in Wireless Sensor Networks
Venue: arXiv cs.CR 2013
Year: 2013

Wireless sensor networks have attracted a lot of interest over the last decade in wireless and mobile computing research community. Applications of these networks are numerous and growing, which range from indoor deployment scenarios in the home and office to outdoor deployment in adversary's territory in a tactical battleground. However, due to distributed nature and their deployment in remote areas, these networks are vulnerable to numerous security threats that can adversely affect their performance. This chapter provides a comprehensive discussion on the state of the art in security technologies for wireless sensor networks. It identifies various possible attacks at different layers of the communication protocol stack in a typical sensor network and their possible countermeasures. A brief discussion on the future direction of research in WSN security is also included.
Broadcasting Algorithm with Per-neighbor Queues
Venue: arXiv cs.NI 2013
Year: 2013

Broadcasting systems such as P2P streaming systems represent important network applications that support up to millions of online users. An efficient broadcasting mechanism is at the core of the system design. Despite substantial efforts on developing efficient broadcasting algorithms, the following important question remains open: How to achieve the maximum broadcast rate in a distributed manner with each user maintaining information queues only for its direct neighbors? In this work, we first derive an innovative formulation of the problem over acyclic overlay networks with arbitrary underlay capacity constraints. Then, based on the formulation, we develop a distributed algorithm to achieve the maximum broadcast rate and every user only maintains one queue per-neighbor. Due to its lightweight nature, our algorithm scales very well with the network size and remains robust against high system dynamics. Finally, by conducting simulations we validate the optimality of our algorithm under different network capacity models. Simulation results further indicate that the convergence time of our algorithm grows linearly with the network size, which suggests an interesting direction for future investigation.
Active Learning on Trees and Graphs
Venue: arXiv cs.LG 2013
Year: 2013

We investigate the problem of active learning on a given tree whose nodes are assigned binary labels in an adversarial way. Inspired by recent results by Guillory and Bilmes, we characterize (up to constant factors) the optimal placement of queries so to minimize the mistakes made on the non-queried nodes. Our query selection algorithm is extremely efficient, and the optimal number of mistakes on the non-queried nodes is achieved by a simple and efficient mincut classifier. Through a simple modification of the query selection algorithm we also show optimality (up to constant factors) with respect to the trade-off between number of queries and number of mistakes on non-queried nodes. By using spanning trees, our algorithms can be efficiently applied to general graphs, although the problem of finding optimal and efficient active learning algorithms for general graphs remains open. Towards this end, we provide a lower bound on the number of mistakes made on arbitrary graphs by any active learning algorithm using a number of queries which is up to a constant fraction of the graph size.
A Rational and Efficient Algorithm for View Revision in Databases
Venue: arXiv cs.LO 2013
Year: 2013

The dynamics of belief and knowledge is one of the major components of any autonomous system that should be able to incorporate new pieces of information. In this paper, we argue that to apply rationality result of belief dynamics theory to various practical problems, it should be generalized in two respects: first of all, it should allow a certain part of belief to be declared as immutable; and second, the belief state need not be deductively closed. Such a generalization of belief dynamics, referred to as base dynamics, is presented, along with the concept of a generalized revision algorithm for Horn knowledge bases. We show that Horn knowledge base dynamics has interesting connection with kernel change and abduction. Finally, we also show that both variants are rational in the sense that they satisfy certain rationality postulates stemming from philosophical works on belief dynamics.
From Two-Way to One-Way Finite State Transducers
Venue: arXiv cs.FL 2013
Year: 2013

Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characterize the class of regular languages. It is also known that this result does not extend to finite string transductions: (deterministic) two-way finite state transducers strictly extend the expressive power of (functional) one-way transducers. In particular deterministic two-way transducers capture exactly the class of MSO-transductions of finite strings. In this paper, we address the following definability problem: given a function defined by a two-way finite state transducer, is it definable by a one-way finite state transducer? By extending Rabin and Scott's proof to transductions, we show that this problem is decidable. Our procedure builds a one-way transducer, which is equivalent to the two-way transducer, whenever one exists.
Approximately counting semismooth integers
Venue: arXiv cs.DS 2013
Year: 2013

An integer $n$ is $(y,z)$-semismooth if $n=pm$ where $m$ is an integer with all prime divisors $\le y$ and $p$ is 1 or a prime $\le z$. arge quantities of semismooth integers are utilized in modern integer factoring algorithms, such as the number field sieve, that incorporate the so-called large prime variant. Thus, it is useful for factoring practitioners to be able to estimate the value of $Ψ(x,y,z)$, the number of $(y,z)$-semismooth integers up to $x$, so that they can better set algorithm parameters and minimize running times, which could be weeks or months on a cluster supercomputer. In this paper, we explore several algorithms to approximate $Ψ(x,y,z)$ using a generalization of Buchstab's identity with numeric integration.
Generalized Cut-Set Bounds for Broadcast Networks
Venue: arXiv cs.IT 2013
Year: 2013

A broadcast network is a classical network with all source messages collocated at a single source node. For broadcast networks, the standard cut-set bounds, which are known to be loose in general, are closely related to union as a specific set operation to combine the basic cuts of the network. This paper provides a new set of network coding bounds for general broadcast networks. These bounds combine the basic cuts of the network via a variety of set operations (not just the union) and are established via only the submodularity of Shannon entropy. The tightness of these bounds are demonstrated via applications to combination networks.
A Single Journal Study : Malaysian Journal of Computer Science
Venue: arXiv cs.DL 2013
Year: 2013

Single journal studies are reviewed and measures used in the studies are highlighted. The following quantitative measures are used to study 272 articles published in Malaysian Journal of Computer Science, (1) the article productivity of the journal from 1985 to 2007, (2) the observed and expected authorship productivity tested using Lotka's Law of author productivity, identification and listing of core authors; (3) the authorship, co-authorship pattern by authors' country of origin and institutional affiliations; (4) the subject areas of research; (5) the citation analysis of resources referenced as well as the age and half-life of citations; the journals referenced and tested for zonal distribution using Bradford's law of journal scattering; the extent of web citations; and (6) the citations received by articles published in MJCS and impact factor of the journal based on information obtained from Google Scholar, the level of author and journal self-citation.
Measuring the influence of a journal using impact and diffusion factors
Venue: arXiv cs.DL 2013
Year: 2013

Presents the result of the calculated IS! equivalent Impact Factor, Relative Diffusion Factor (RDF), and Journal Diffusion Factor (JDF) for articles published in the Medical Journal of Malaysia (MJM) between the years 2004 and 2008 in both their synchronous and diachronous versions. The publication data are collected from MyAis (Malaysian Abstracting & Indexing system) while the citation data are collected from Google Scholar. The values of the synchronous JDF ranges from 0.057 - 0.14 while the diachronous JDF ranges from 0.46 - 1.98. The high diachronous JDF is explained by a relatively high number of different citing journals against the number of publications. This implies that the results of diachronous JDF is influenced by the numbers of publications and a good comparison may be one of which the subject of analysis have similar number of publications and citations period. The yearly values of the synchronous RDF vary in the range of 0.66 - 1.00 while diachronous RDF ranges from 0.62 - 0.88. The result shows that diachronous RDF is negatively correlated with the number of citations, resulting in a low RDF value for highly cited publication years. What this implies in practice is that the diffusion factors can be calculated for every additional year at any journal level of analysis. This study demonstrates that these indicators are valuable tools that help to show development of journals as it changes through time.
Collaborative digital library of historical resources: Evaluation of first users
Venue: arXiv cs.HC 2013
Year: 2013

This paper describes the digital library of historical resources, a research project which involves building a testbed for the purpose of developing and testing new collaborative digital library functionality and presents an initial analysis of the digital library's public use on the web. The digital library is modeled to focus on serving secondary students information needs in conducting history projects. As such, in the implementation of the digital library, the use of online resources would be an integral part of history project based learning activities. Students should be enabled to access digital resources, create and publish their own documents in the digital library and share them with others. As a testbed system, the collaborative digital library known as CoreDev has demonstrated its capabilities in serving an educational community as has been reflected by the positive feedback on the functional requirements from 44 users. Over 75% of the respondents in the user survey considered themselves capable of using the digital library easily. The beta tester demographics (n = 105) indicate that the digital library is reaching its target communities.
The Importance of Continuous Value Based Project Management in the Context of Requirements Engineering
Venue: arXiv cs.SE 2013
Year: 2013

Despite several scientific achievements in the last years, there are still a lot of IT projects that fail. Researchers found that one out of five IT-projects run out of time, budget or value. Major reasons for this failure are unexpected economic risk factors that emerge during the runtime of projects. In order to be able to identify emerging risks early and to counteract reasonably, financial methods for a continuous IT-project-steering are necessary, which as of today to the best of our knowledge are missing within scientific literature.
Requirements Issues in SoC and SoS
Venue: arXiv cs.SE 2013
Year: 2013

This position paper outlines some of the existing issues and challenges concerned with the complexity of the requirements for service-oriented computing and systems-of-systems applications.
Information as Distinctions: New Foundations for Information Theory
Venue: arXiv cs.IT 2013
Year: 2013

The logical basis for information theory is the newly developed logic of partitions that is dual to the usual Boolean logic of subsets. The key concept is a "distinction" of a partition, an ordered pair of elements in distinct blocks of the partition. The logical concept of entropy based on partition logic is the normalized counting measure of the set of distinctions of a partition on a finite set--just as the usual logical notion of probability based on the Boolean logic of subsets is the normalized counting measure of the subsets (events). Thus logical entropy is a measure on the set of ordered pairs, and all the compound notions of entropy (join entropy, conditional entropy, and mutual information) arise in the usual way from the measure (e.g., the inclusion-exclusion principle)--just like the corresponding notions of probability. The usual Shannon entropy of a partition is developed by replacing the normalized count of distinctions (dits) by the average number of binary partitions (bits) necessary to make all the distinctions of the partition.