OpenRaiser/Intern-Atlas huggingface dataset:
Inferring global network properties from egocentric data with applications to epidemics
Venue: arXiv cs.SI 2012
Year: 2012

Social networks are rarely observed in full detail. In many situations properties are known for only a sample of the individuals in the network and it is desirable to induce global properties of the full social network from this "egocentric" network data. In the current paper we study a few different types of egocentric data, and show what global network properties are consistent with those egocentric data. Two global network properties are considered: the size of the largest connected component in the network (the giant), and secondly, the possible size of an epidemic outbreak taking place on the network, in which transmission occurs only between network neighbours, and with probability $p$. The main conclusion is that in most cases, egocentric data allow for a large range of possible sizes of the giant and the outbreak. However, there is an upper bound for the latter. For the case that the network is selected uniformly among networks with prescribed egocentric data (satisfying some conditions), the asymptotic size of the giant and the outbreak is characterised.
Opportunistic Adaptive Relaying in Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

Combining cognitive radio technology with user cooperation could be advantageous to both primary and secondary transmissions. In this paper, we propose a first relaying scheme for cognitive radio networks (called "Adaptive relaying scheme 1"), where one relay node can assist the primary or the secondary transmission with the objective of improving the outage probability of the secondary transmission with respect to a primary outage probability threshold. Upper bound expressions of the secondary outage probability using the proposed scheme are derived over Rayleigh fading channels. Numerical and simulation results show that the secondary outage probability using the proposed scheme is lower than that of other relaying schemes. Then, we extend the proposed scheme to the case where the relay node has the ability to decode both the primary and secondary signals and also can assist simultaneously both transmissions. Simulations show the performance improvement that can be obtained due to this extension in terms of secondary outage probability.
Information algebra system of soft sets
Venue: arXiv cs.IT 2012
Year: 2012

Information algebra is algebraic structure for local computation and inference. Given an initial universe set and a parameter set, we show that a soft set system over them is an information algebra. Moreover, in a soft set system, the family of all soft sets with a finite parameter subset can form a compact information algebra.
G-Lets: Signal Processing Using Transformation Groups
Venue: arXiv cs.CV 2012
Year: 2012

We present an algorithm using transformation groups and their irreducible representations to generate an orthogonal basis for a signal in the vector space of the signal. It is shown that multiresolution analysis can be done with amplitudes using a transformation group. G-lets is thus not a single transform, but a group of linear transformations related by group theory. The algorithm also specifies that a multiresolution and multiscale analysis for each resolution is possible in terms of frequencies. Separation of low and high frequency components of each amplitude resolution is facilitated by G-lets. Using conjugacy classes of the transformation group, more than one set of basis may be generated, giving a different perspective of the signal through each basis. Applications for this algorithm include edge detection, feature extraction, denoising, face recognition, compression, and more. We analyze this algorithm using dihedral groups as an example. We demonstrate the results with an ECG signal and the standard `Lena' image.
DISco: a Distributed Information Store for network Challenges and their Outcome
Venue: arXiv cs.NI 2012
Year: 2012

We present DISco, a storage and communication middleware designed to enable distributed and task-centric autonomic control of networks. DISco is designed to enable multi-agent identification of anomalous situations -- so-called "challenges" -- and assist coordinated remediation that maintains degraded -- but acceptable -- service level, while keeping a track of the challenge evolution in order to enable human-assisted diagnosis of flaws in the network. We propose to use state-of-art peer-to-peer publish/subscribe and distributed storage as core building blocks for the DISco service.
A Bijective String Sorting Transform
Venue: arXiv cs.DS 2012
Year: 2012

Given a string of characters, the Burrows-Wheeler Transform rearranges the characters in it so as to produce another string of the same length which is more amenable to compression techniques such as move to front, run-length encoding, and entropy encoders. We present a variant of the transform which gives rise to similar or better compression value, but, unlike the original, the transform we present is bijective, in that the inverse transformation exists for all strings. Our experiments indicate that using our variant of the transform gives rise to better compression ratio than the original Burrows-Wheeler transform. We also show that both the transform and its inverse can be computed in linear time and consuming linear storage.
On the Properties of Language Classes Defined by Bounded Reaction Automata
Venue: arXiv cs.FL 2012
Year: 2012

Reaction automata are a formal model that has been introduced to investigate the computing powers of interactive behaviors of biochemical reactions([14]). Reaction automata are language acceptors with multiset rewriting mechanism whose basic frameworks are based on reaction systems introduced in [4]. In this paper we continue the investigation of reaction automata with a focus on the formal language theoretic properties of subclasses of reaction automata, called linearbounded reaction automata (LRAs) and exponentially-bounded reaction automata (ERAs). Besides LRAs, we newly introduce an extended model (denoted by lambda-LRAs) by allowing lambda-moves in the accepting process of reaction, and investigate the closure properties of language classes accepted by both LRAs and lambda-LRAs. Further, we establish new relationships of language classes accepted by LRAs and by ERAs with the Chomsky hierarchy. The main results include the following : (i) the class of languages accepted by lambda-LRAs forms an AFL with additional closure properties, (ii) any recursively enumerable language can be expressed as a homomorphic image of a language accepted by an LRA, (iii) the class of languages accepted by ERAs coincides with the class of context-sensitive languages.
An Adaptive Modulation Scheme for Two-user Fading MAC with Quantized Fade State Feedback
Venue: arXiv cs.IT 2012
Year: 2012

With no CSI at the users, transmission over the two-user Gaussian Multiple Access Channel with fading and finite constellation at the input, is not efficient because error rates will be high when the channel conditions are poor. However, perfect CSI at the users is an unrealistic assumption in the wireless scenario, as it would involve massive feedback overheads. In this paper we propose a scheme which uses only quantized knowledge of CSI at the transmitters with the overhead being nominal. The users rotate their constellation without varying their transmit power to adapt to the existing channel conditions, in order to meet certain pre-determined minimum Euclidean distance requirement in the equivalent constellation at the destination. The optimal modulation scheme has been described for the case when both the users use symmetric M-PSK constellations at the input, where $ M=2^λ$, $ λ$ being a positive integer. The strategy has been illustrated by considering examples where both users use QPSK or 8-PSK signal sets at the input. It is shown that the proposed scheme has better throughput and error performance compared to the conventional non-adaptive scheme, at the cost of a feedback overhead of just $\lceil \log_2(\frac{M^2}{8}-\frac{M}{4}+2)\rceil + 1 $ bits, for the M-PSK case.
Simple permutations poset
Venue: arXiv cs.DM 2012
Year: 2012

This article studies the poset of simple permutations with respect to the pattern involvement. We specify results on critically indecomposable posets obtained by Schmerl and Trotter to simple permutations and prove that if $σ, π$ are two simple permutations such that $π< σ$ then there exists a chain of simple permutations $σ^{(0)} = σ, σ^{(1)}, ..., σ^{(k)}=π$ such that $|σ^{(i)}| - |σ^{(i+1)}| = 1$ - or 2 when permutations are exceptional- and $σ^{(i+1)} < σ^{(i)}$. This characterization induces an algorithm polynomial in the size of the output to compute the simple permutations in a wreath-closed permutation class.
Maximum Throughput in Multiple-Antenna Systems
Venue: arXiv cs.IT 2012
Year: 2012

The point-to-point multiple-antenna channel is investigated in uncorrelated block fading environment with Rayleigh distribution. The maximum throughput and maximum expected-rate of this channel are derived under the assumption that the transmitter is oblivious to the channel state information (CSI), however, the receiver has perfect CSI. First, we prove that in multiple-input single-output (MISO) channels, the optimum transmission strategy maximizing the throughput is to use all available antennas and perform equal power allocation with uncorrelated signals. Furthermore, to increase the expected-rate, multi-layer coding is applied. Analogously, we establish that sending uncorrelated signals and performing equal power allocation across all available antennas at each layer is optimum. A closed form expression for the maximum continuous-layer expected-rate of MISO channels is also obtained. Moreover, we investigate multiple-input multiple-output (MIMO) channels, and formulate the maximum throughput in the asymptotically low and high SNR regimes and also asymptotically large number of transmit or receive antennas by obtaining the optimum transmit covariance matrix. Finally, a distributed antenna system, wherein two single-antenna transmitters want to transmit a common message to a single-antenna receiver, is considered. It is shown that this system has the same outage probability and hence, throughput and expected-rate, as a point-to-point $2\times 1$ MISO channel.
Strictness of the Collapsible Pushdown Hierarchy
Venue: arXiv cs.FL 2012
Year: 2012

We present a pumping lemma for each level of the collapsible pushdown graph hierarchy in analogy to the second author's pumping lemma for higher-order pushdown graphs (without collapse). Using this lemma, we give the first known examples that separate the levels of the collapsible pushdown graph hierarchy and of the collapsible pushdown tree hierarchy, i.e., the hierarchy of trees generated by higher-order recursion schemes. This confirms the open conjecture that higher orders allow one to generate more graphs and more trees.
Mining Educational Data to Analyze Students' Performance
Venue: arXiv cs.IR 2012
Year: 2012

The main objective of higher education institutions is to provide quality education to its students. One way to achieve highest level of quality in higher education system is by discovering knowledge for prediction regarding enrolment of students in a particular course, alienation of traditional classroom teaching model, detection of unfair means used in online examination, detection of abnormal values in the result sheets of the students, prediction about students' performance and so on. The knowledge is hidden among the educational data set and it is extractable through data mining techniques. Present paper is designed to justify the capabilities of data mining techniques in context of higher education by offering a data mining model for higher education system in the university. In this research, the classification task is used to evaluate student's performance and as there are many approaches that are used for data classification, the decision tree method is used here. By this task we extract knowledge that describes students' performance in end semester examination. It helps earlier in identifying the dropouts and students who need special attention and allow the teacher to provide appropriate advising/counseling. Keywords-Educational Data Mining (EDM); Classification; Knowledge Discovery in Database (KDD); ID3 Algorithm.
A Genetic Algorithm for the Calibration of a Micro-Simulation Model
Venue: arXiv cs.OH 2012
Year: 2012

This paper describes the process followed to calibrate a micro-simulation model for the Altmark region in Germany and a Derbyshire region in the UK. The calibration process is performed in three main steps: first, a subset of input and output variables to use for the calibration process is selected from the complete parameter space in the model; second, the calibration process is performed using a genetic algorithm calibration approach; finally, a comparison between the real data and the data obtained from the best fit model is done to verify the accuracy of the model.
Simple Numerical Model of Laminated Glass Beams
Venue: arXiv cs.CE 2012
Year: 2012

This contribution presents a simple Finite Element model aimed at efficient simulation of layered glass units. The adopted approach is based on considering independent kinematics of each layer, tied together via Lagrange multipliers. Validation and verification of the resulting model against independent data demonstrate its accuracy, showing its potential for generalization towards more complex problems.
A Synthesis of the Procedural and Declarative Styles of Interactive Theorem Proving
Venue: arXiv cs.LO 2012
Year: 2012

We propose a synthesis of the two proof styles of interactive theorem proving: the procedural style (where proofs are scripts of commands, like in Coq) and the declarative style (where proofs are texts in a controlled natural language, like in Isabelle/Isar). Our approach combines the advantages of the declarative style - the possibility to write formal proofs like normal mathematical text - and the procedural style - strong automation and help with shaping the proofs, including determining the statements of intermediate steps. Our approach is new, and differs significantly from the ways in which the procedural and declarative proof styles have been combined before in the Isabelle, Ssreflect and Matita systems. Our approach is generic and can be implemented on top of any procedural interactive theorem prover, regardless of its architecture and logical foundations. To show the viability of our proposed approach, we fully implemented it as a proof interface called miz3, on top of the HOL Light interactive theorem prover. The declarative language that this interface uses is a slight variant of the language of the Mizar system, and can be used for any interactive theorem prover regardless of its logical foundations. The miz3 interface allows easy access to the full set of tactics and formal libraries of HOL Light, and as such has "industrial strength". Our approach gives a way to automatically convert any procedural proof to a declarative counterpart, where the converted proof is similar in size to the original. As all declarative systems have essentially the same proof language, this gives a straightforward way to port proofs between interactive theorem provers.
Compact Binary Relation Representations with Rich Functionality
Venue: arXiv cs.DS 2012
Year: 2012

Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations, some simple and some quite sophisticated, that not only are space-efficient but also efficiently support a large subset of the desired queries.
Energy Efficient Iterative Waterfilling for the MIMO Broadcasting Channels
Venue: arXiv cs.IT 2012
Year: 2012

Optimizing energy efficiency (EE) for the MIMO broadcasting channels (BC) is considered in this paper, where a practical power model is taken into account. Although the EE of the MIMO BC is non-concave, we reformulate it as a quasiconcave function based on the uplink-downlink duality. After that, an energy efficient iterative waterfilling scheme is proposed based on the block-coordinate ascent algorithm to obtain the optimal transmission policy efficiently, and the solution is proved to be convergent. Through simulations, we validate the efficiency of the proposed scheme and discuss the system parameters' effect on the EE.
Proportional Fair Coding for Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

We consider multi--hop wireless networks carrying unicast flows for multiple users. Each flow has a specified delay deadline, and the lossy wireless links are modelled as binary symmetric channels (BSCs). Since transmission time, also called airtime, on the links is shared amongst flows, increasing the airtime for one flow comes at the cost of reducing the airtime available to other flows sharing the same link. We derive the joint allocation of flow airtimes and coding rates that achieves the proportionally fair throughput allocation. This utility optimisation problem is non--convex, and one of the technical contributions of this paper is to show that the proportional fair utility optimisation can nevertheless be decomposed into a sequence of convex optimisation problems. The solution to this sequence of convex problems is the unique solution to the original non--convex optimisation. Surprisingly, this solution can be written in an explicit form that yields considerable insight into the nature of the proportional fair joint airtime/coding rate allocation. To our knowledge, this is the first time that the utility fair joint allocation of airtime/coding rate has been analysed, and also, one of the first times that utility fairness with delay deadlines has been considered.
Processor Allocation for Optimistic Parallelization of Irregular Programs
Venue: arXiv cs.PL 2012
Year: 2012

Optimistic parallelization is a promising approach for the parallelization of irregular algorithms: potentially interfering tasks are launched dynamically, and the runtime system detects conflicts between concurrent activities, aborting and rolling back conflicting tasks. However, parallelism in irregular algorithms is very complex. In a regular algorithm like dense matrix multiplication, the amount of parallelism can usually be expressed as a function of the problem size, so it is reasonably straightforward to determine how many processors should be allocated to execute a regular algorithm of a certain size (this is called the processor allocation problem). In contrast, parallelism in irregular algorithms can be a function of input parameters, and the amount of parallelism can vary dramatically during the execution of the irregular algorithm. Therefore, the processor allocation problem for irregular algorithms is very difficult. In this paper, we describe the first systematic strategy for addressing this problem. Our approach is based on a construct called the conflict graph, which (i) provides insight into the amount of parallelism that can be extracted from an irregular algorithm, and (ii) can be used to address the processor allocation problem for irregular algorithms. We show that this problem is related to a generalization of the unfriendly seating problem and, by extending Turán's theorem, we obtain a worst-case class of problems for optimistic parallelization, which we use to derive a lower bound on the exploitable parallelism. Finally, using some theoretically derived properties and some experimental facts, we design a quick and stable control strategy for solving the processor allocation problem heuristically.
A Dynamic Model for Sharing Reputation of Sellers among Buyers for Enhancing Trust in Agent Mediated e-market
Venue: arXiv cs.SI 2012
Year: 2012

Reputation systems aim to reduce the risk of loss due to untrustworthy participants. This loss is aggravated by dishonest advisors trying to pollute the e-market environment for their self-interest. A major task of a reputation system is to promote and encourage advisors who repeatedly respond with fair advice and to apply an opinion filtering or honesty checking mechanism to detect and resist dishonest advisors. This paper provides a dynamic approach to compute the aggregated shared reputation component by filtering out unfair advice and then generating the aggregated shared reputation value. The proposed approach is dynamic in nature as it is sensitive to the behaviour of advisors, value of the current transaction and encourages the cooperation among buyers as advisors. It provides incentive to honest advisors in lieu of repeated sharing of honest opinion by increasing the weight of their opinion and by making the increase in the reputation of honest advisors monotonically proportional to the value of a transaction.
Congestion Control and Routing over Challenged Networks
Venue: arXiv cs.NI 2012
Year: 2012

This dissertation is a study on the design and analysis of novel, optimal routing and rate control algorithms in wireless, mobile communication networks. Congestion control and routing algorithms upto now have been designed and optimized for wired or wireless mesh networks. In those networks, optimal algorithms (optimal in the sense that either the throughput is maximized or delay is minimized, or the network operation cost is minimized) can be engineered based on the classic time scale decomposition assumption that the dynamics of the network are either fast enough so that these algorithms essentially see the average or slow enough that any changes can be tracked to allow the algorithms to adapt over time. However, as technological advancements enable integration of ever more mobile nodes into communication networks, any rate control or routing algorithms based, for example, on averaging out the capacity of the wireless mobile link or tracking the instantaneous capacity will perform poorly. The common element in our solution to engineering efficient routing and rate control algorithms for mobile wireless networks is to make the wireless mobile links seem as if they are wired or wireless links to all but few nodes that directly see the mobile links (either the mobiles or nodes that can transmit to or receive from the mobiles) through an appropriate use of queuing structures at these selected nodes. This approach allows us to design end-to-end rate control or routing algorithms for wireless mobile networks so that neither averaging nor instantaneous tracking is necessary.
A Novel Approach to Fast Image Filtering Algorithm of Infrared Images based on Intro Sort Algorithm
Venue: arXiv cs.CV 2012
Year: 2012

In this study we investigate the fast image filtering algorithm based on Intro sort algorithm and fast noise reduction of infrared images. Main feature of the proposed approach is that no prior knowledge of noise required. It is developed based on Stefan- Boltzmann law and the Fourier law. We also investigate the fast noise reduction approach that has advantage of less computation load. In addition, it can retain edges, details, text information even if the size of the window increases. Intro sort algorithm begins with Quick sort and switches to heap sort when the recursion depth exceeds a level based on the number of elements being sorted. This approach has the advantage of fast noise reduction by reducing the comparison time. It also significantly speed up the noise reduction process and can apply to real-time image processing. This approach will extend the Infrared images applications for medicine and video conferencing.