OpenRaiser/Intern-Atlas huggingface dataset:
Topological Feature Based Classification
Venue: arXiv cs.SI 2011
Year: 2011

There has been a lot of interest in developing algorithms to extract clusters or communities from networks. This work proposes a method, based on blockmodelling, for leveraging communities and other topological features for use in a predictive classification task. Motivated by the issues faced by the field of community detection and inspired by recent advances in Bayesian topic modelling, the presented model automatically discovers topological features relevant to a given classification task. In this way, rather than attempting to identify some universal best set of clusters for an undefined goal, the aim is to find the best set of clusters for a particular purpose. Using this method, topological features can be validated and assessed within a given context by their predictive performance. The proposed model differs from other relational and semi-supervised learning models as it identifies topological features to explain the classification decision. In a demonstration on a number of real networks the predictive capability of the topological features are shown to rival the performance of content based relational learners. Additionally, the model is shown to outperform graph-based semi-supervised methods on directed and approximately bipartite networks.
Taking Roots over High Extensions of Finite Fields
Venue: arXiv cs.DS 2011
Year: 2011

We present a new algorithm for computing $m$-th roots over the finite field $\F_q$, where $q = p^n$, with $p$ a prime, and $m$ any positive integer. In the particular case $m=2$, the cost of the new algorithm is an expected $O(\M(n)\log (p) + \CC(n)\log(n))$ operations in $\F_p$, where $\M(n)$ and $\CC(n)$ are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give $\M(n) = O(n\log (n) \log\log (n))$ and $\CC(n) = O(n^{1.67})$, so our algorithm is subquadratic in $n$.
Improved Grammar-Based Compressed Indexes
Venue: arXiv cs.DS 2011
Year: 2011

We introduce the first grammar-compressed representation of a sequence that supports searches in time that depends only logarithmically on the size of the grammar. Given a text $T[1..u]$ that is represented by a (context-free) grammar of $n$ (terminal and nonterminal) symbols and size $N$ (measured as the sum of the lengths of the right hands of the rules), a basic grammar-based representation of $T$ takes $N\lg n$ bits of space. Our representation requires $2N\lg n + N\lg u + ε\, n\lg n + o(N\lg n)$ bits of space, for any $0<ε\le 1$. It can find the positions of the $occ$ occurrences of a pattern of length $m$ in $T$ in $O((m^2/ε)\lg (\frac{\lg u}{\lg n}) +occ\lg n)$ time, and extract any substring of length $\ell$ of $T$ in time $O(\ell+h\lg(N/h))$, where $h$ is the height of the grammar tree.
Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Full)
Venue: arXiv cs.SI 2011
Year: 2011

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.
Verifying Sierpiński and Riesel Numbers in ACL2
Venue: arXiv cs.DM 2011
Year: 2011

A Sierpinski number is an odd positive integer, k, such that no positive integer of the form k * 2^n + 1 is prime. Similar to a Sierpinski number, a Riesel number is an odd positive integer, k, such that no positive integer of the form k * 2^n + 1 is prime. A cover for such a k is a finite list of positive integers such that each integer j of the appropriate form has a factor, d, in the cover, with 1 < d < j. Given a k and its cover, ACL2 is used to systematically verify that each integer of the given form has a non-trivial factor in the cover.
Proactive Resource Allocation: Harnessing the Diversity and Multicast Gains
Venue: arXiv cs.IT 2011
Year: 2011

This paper introduces the novel concept of proactive resource allocation through which the predictability of user behavior is exploited to balance the wireless traffic over time, and hence, significantly reduce the bandwidth required to achieve a given blocking/outage probability. We start with a simple model in which the smart wireless devices are assumed to predict the arrival of new requests and submit them to the network T time slots in advance. Using tools from large deviation theory, we quantify the resulting prediction diversity gain} to establish that the decay rate of the outage event probabilities increases with the prediction duration T. This model is then generalized to incorporate the effect of the randomness in the prediction look-ahead time T. Remarkably, we also show that, in the cognitive networking scenario, the appropriate use of proactive resource allocation by the primary users improves the diversity gain of the secondary network at no cost in the primary network diversity. We also shed lights on multicasting with predictable demands and show that the proactive multicast networks can achieve a significantly higher diversity gain that scales super-linearly with T. Finally, we conclude by a discussion of the new research questions posed under the umbrella of the proposed proactive (non-causal) wireless networking framework.
Analysis of Differential Phase Shift Quantum Key Distribution
Venue: arXiv cs.CR 2011
Year: 2011

We review the implementation of two QKD protocols (BB84 and B92) keeping in mind that their implementations do not easily satisfy the requirement of use of single photons. We argue that current models do not take into account issues raised by the Uncertainty Principle related to time-location and transmission characteristics of single photons. This indicates that security proofs of current implementations even after the fixes for the recent successful hacks are made will be hard to obtain.
Capturing an Evader in Polygonal Environments: A Complete Information Game
Venue: arXiv cs.GT 2011
Year: 2011

Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well---this accords with the standard worst-case analysis model, but also models a practical situation where the evader has "hacked" into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment. The result should be contrasted with the incomplete information pursuit-evasion where at least Ω(\surd h + log n) pursuers are required just for detecting the evader in an environment with n vertices and h holes.
Analyzing Answers in Threaded Discussions using a Role-Based Information Network
Venue: arXiv cs.SI 2011
Year: 2011

Online discussion boards are an important medium for collaboration. The goal of our work is to understand how messages and individual discussants contribute to Q&A discussions. We present a novel network model for capturing in-formation roles of messages and discussants, and show how we identify useful answers to the initial question. We first classify information seeking or information providing roles of messages, such as question, answer or acknowledgement. We also identify user intent in the discussion as an information seeker or a provider. We capture such role information within a reply-to discussion network, and identify messages that answer seeker questions and how answeres are acknowledged. Message influences are analyzed using B-centrality measures. User influences across different threads are combined with message influences. We use the combined score in identifying the most useful answer in the thread. The resulting ranks correlate with human provided ranks with an MRR score of 0.67.
On the Practicality of `Practical' Byzantine Fault Tolerance
Venue: arXiv cs.DC 2011
Year: 2011

Byzantine Fault Tolerant (BFT) systems are considered by the systems research community to be state of the art with regards to providing reliability in distributed systems. BFT systems provide safety and liveness guarantees with reasonable assumptions, amongst a set of nodes where at most f nodes display arbitrarily incorrect behaviors, known as Byzantine faults. Despite this, BFT systems are still rarely used in practice. In this paper we describe our experience, from an application developer's perspective, trying to leverage the publicly available and highly-tuned PBFT middleware (by Castro and Liskov), to provide provable reliability guarantees for an electronic voting application with high security and robustness needs. We describe several obstacles we encountered and drawbacks we identified in the PBFT approach. These include some that we tackled, such as lack of support for dynamic client management and leaving state management completely up to the application. Others still remaining include the lack of robust handling of non-determinism, lack of support for web-based applications, lack of support for stronger cryptographic primitives, and others. We find that, while many of the obstacles could be overcome with a revised BFT middleware implementation that is tuned specifically for the needs of the particular application, they require significant engineering effort and time and their performance implications for the end-application are unclear. An application developer is thus unlikely to be willing to invest the time and effort to do so to leverage the BFT approach. We conclude that the research community needs to focus on the usability of BFT algorithms for real world applications, from the end-developer perspective, in addition to continuing to improve the BFT middleware performance, robustness and deployment layouts.
Geometry of the 3-user MIMO interference channel
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies vector space interference alignment for the three-user MIMO interference channel with no time or frequency diversity. The main result is a characterization of the feasibility of interference alignment in the symmetric case where all transmitters have M antennas and all receivers have N antennas. If N >= M and all users desire d transmit dimensions, then alignment is feasible if and only if (2r+1)d <= max(rN,(r+1)M) for all nonnegative integers r. The analogous result holds with M and N switched if M >= N. It turns out that, just as for the 3-user parallel interference channel \cite{BT09}, the length of alignment paths captures the essence of the problem. In fact, for each feasible value of M and N the maximum alignment path length dictates both the converse and achievability arguments. One of the implications of our feasibility criterion is that simply counting equations and comparing to the number of variables does not predict feasibility. Instead, a more careful investigation of the geometry of the alignment problem is required. The necessary condition obtained by counting equations is implied by our new feasibility criterion.
Ad Hoc Protocols Via Multi Agent Based Tools
Venue: arXiv cs.SI 2011
Year: 2011

The purpose of this paper is investigating behaviors of Ad Hoc protocols in Agent-based simulation environments. First we bring brief introduction about agents and Ad Hoc networks. We introduce some agent-based simulation tools like NS-2. Then we focus on two protocols, which are Ad Hoc On-demand Multipath Distance Vector (AODV) and Destination Sequenced Distance Vector (DSDV). At the end, we bring simulation results and discuss about their reasons.
A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games
Venue: arXiv cs.GT 2011
Year: 2011

We present a general technique, based on a primal-dual formulation, for analyzing the quality of self-emerging solutions in weighted congestion games. With respect to traditional combinatorial approaches, the primal-dual schema has at least three advantages: first, it provides an analytic tool which can always be used to prove tight upper bounds for all the cases in which we are able to characterize exactly the polyhedron of the solutions under analysis; secondly, in each such a case the complementary slackness conditions give us an hint on how to construct matching lower bounding instances; thirdly, proofs become simpler and easy to check. For the sake of exposition, we first apply our technique to the problems of bounding the prices of anarchy and stability of exact and approximate pure Nash equilibria, as well as the approximation ratio of the solutions achieved after a one-round walk starting from the empty strategy profile, in the case of affine latency functions and we show how all the known upper bounds for these measures (and some of their generalizations) can be easily reobtained under a unified approach. Then, we use the technique to attack the more challenging setting of polynomial latency functions. In particular, we obtain the first known upper bounds on the price of stability of pure Nash equilibria and on the approximation ratio of the solutions achieved after a one-round walk starting from the empty strategy profile for unweighted players in the cases of quadratic and cubic latency functions. We believe that our technique, thanks to its versatility, may prove to be a powerful tool also in several other applications.
WeSSQoS: A Configurable SOA System for Quality-aware Web Service Selection
Venue: arXiv cs.NI 2011
Year: 2011

Web Services (WS) have become one the most used technologies nowadays in software systems. Among the challenges when integrating WS in a given system, requirements-driven selection occupies a prominent place. A comprehensive selection process needs to check compliance of Non-Functional Requirements (NFR), which can be assessed by analysing WS Quality of Service (QoS). In this paper, we describe the WeSSQoS system that aims at ranking available WS based on the comparison of their QoS and the stated NFRs. WeSSQoS is designed as an open service-oriented architecture that hosts a configurable portfolio of normalization and ranking algorithms that can be selected by the engineer when starting a selection process. WS' QoS can be obtained either from a static, WSDL-like description, or computed dynamically through monitoring techniques. WeSSQoS is designed to work over multiple WS repositories and QoS sources. The impact of having a portfolio of different normalization and ranking algorithms is illustrated with an example.
Annotation of Scientific Summaries for Information Retrieval
Venue: arXiv cs.IR 2011
Year: 2011

We present a methodology combining surface NLP and Machine Learning techniques for ranking asbtracts and generating summaries based on annotated corpora. The corpora were annotated with meta-semantic tags indicating the category of information a sentence is bearing (objective, findings, newthing, hypothesis, conclusion, future work, related work). The annotated corpus is fed into an automatic summarizer for query-oriented abstract ranking and multi- abstract summarization. To adapt the summarizer to these two tasks, two novel weighting functions were devised in order to take into account the distribution of the tags in the corpus. Results, although still preliminary, are encouraging us to pursue this line of work and find better ways of building IR systems that can take into account semantic annotations in a corpus.
Swarmrobot.org - Open-hardware Microrobotic Project for Large-scale Artificial Swarms
Venue: arXiv cs.RO 2011
Year: 2011

The purpose of this paper is to give an overview of the open-hardware microrobotic project swarmrobot.org and the platform Jasmine for building large-scale artificial swarms. The project targets an open development of cost-effective hardware and software for a quick implementation of swarm behavior with real robots. Detailed instructions for making the robot, open-source simulator, software libraries and multiple publications about performed experiments are ready for download and intend to facilitate exploration of collective and emergent phenomena, guided self-organization and swarm robotics in experimental way.
A New Similarity Measure for Non-Local Means Filtering of MRI Images
Venue: arXiv cs.CV 2011
Year: 2011

The acquisition of MRI images offers a trade-off in terms of acquisition time, spatial/temporal resolution and signal-to-noise ratio (SNR). Thus, for instance, increasing the time efficiency of MRI often comes at the expense of reduced SNR. This, in turn, necessitates the use of post-processing tools for noise rejection, which makes image de-noising an indispensable component of computer assistance diagnosis. In the field of MRI, a multitude of image de-noising methods have been proposed hitherto. In this paper, the application of a particular class of de-noising algorithms - known as non-local mean (NLM) filters - is investigated. Such filters have been recently applied for MRI data enhancement and they have been shown to provide more accurate results as compared to many alternative de-noising algorithms. Unfortunately, virtually all existing methods for NLM filtering have been derived under the assumption of additive white Gaussian (AWG) noise contamination. Since this assumption is known to fail at low values of SNR, an alternative formulation of NLM filtering is required, which would take into consideration the correct Rician statistics of MRI noise. Accordingly, the contribution of the present paper is two-fold. First, it points out some principal disadvantages of the earlier methods of NLM filtering of MRI images and suggests means to rectify them. Second, the paper introduces a new similarity measure for NLM filtering of MRI Images, which is derived under bona fide statistical assumptions and results in more accurate reconstruction of MR scans as compared to alternative NLM approaches. Finally, the utility and viability of the proposed method is demonstrated through a series of numerical experiments using both in silico and in vivo MRI data.
Provisioning Spot Market Cloud Resources to Create Cost-effective Virtual Clusters
Venue: arXiv cs.DC 2011
Year: 2011

Infrastructure-as-a-Service providers are offering their unused resources in the form of variable-priced virtual machines (VMs), known as "spot instances", at prices significantly lower than their standard fixed-priced resources. To lease spot instances, users specify a maximum price they are willing to pay per hour and VMs will run only when the current price is lower than the user's bid. This paper proposes a resource allocation policy that addresses the problem of running deadline-constrained compute-intensive jobs on a pool of composed solely of spot instances, while exploiting variations in price and performance to run applications in a fast and economical way. Our policy relies on job runtime estimations to decide what are the best types of VMs to run each job and when jobs should run. Several estimation methods are evaluated and compared, using trace-based simulations, which take real price variation traces obtained from Amazon Web Services as input, as well as an application trace from the Parallel Workload Archive. Results demonstrate the effectiveness of running computational jobs on spot instances, at a fraction (up to 60% lower) of the price that would normally cost on fixed priced resources.
Entropy of the Mixture of Sources and Entropy Dimension
Venue: arXiv cs.IT 2011
Year: 2011

We investigate the problem of the entropy of the mixture of sources. There is given an estimation of the entropy and entropy dimension of convex combination of measures. The proof is based on our alternative definition of the entropy based on measures instead of partitions.
Modelling Constraint Solver Architecture Design as a Constraint Problem
Venue: arXiv cs.AI 2011
Year: 2011

Designing component-based constraint solvers is a complex problem. Some components are required, some are optional and there are interdependencies between the components. Because of this, previous approaches to solver design and modification have been ad-hoc and limited. We present a system that transforms a description of the components and the characteristics of the target constraint solver into a constraint problem. Solving this problem yields the description of a valid solver. Our approach represents a significant step towards the automated design and synthesis of constraint solvers that are specialised for individual constraint problem classes or instances.
Iris Codes Classification Using Discriminant and Witness Directions
Venue: arXiv cs.NE 2011
Year: 2011

The main topic discussed in this paper is how to use intelligence for biometric decision defuzzification. A neural training model is proposed and tested here as a possible solution for dealing with natural fuzzification that appears between the intra- and inter-class distribution of scores computed during iris recognition tests. It is shown here that the use of proposed neural network support leads to an improvement in the artificial perception of the separation between the intra- and inter-class score distributions by moving them away from each other.
A Generalized Loss Network Model with Overflow for Capacity Planning of a Perinatal Network
Venue: arXiv cs.PF 2011
Year: 2011

We develop a generalized loss network framework for capacity planning of a perinatal network in the UK. Decomposing the network by hospitals, each unit is analyzed with a GI/G/c/0 overflow loss network model. A two-moment approximation is performed to obtain the steady state solution of the GI/G/c/0 loss systems, and expressions for rejection probability and overflow probability have been derived. Using the model framework, the number of required cots can be estimated based on the rejection probability at each level of care of the neonatal units in a network. The generalization ensures that the model can be applied to any perinatal network for renewal arrival and discharge processes.