OpenRaiser/Intern-Atlas huggingface dataset:
Sustaining the Internet with Hyperbolic Mapping
Venue: arXiv cs.NI 2010
Year: 2010

The Internet infrastructure is severely stressed. Rapidly growing overheads associated with the primary function of the Internet---routing information packets between any two computers in the world---cause concerns among Internet experts that the existing Internet routing architecture may not sustain even another decade. Here we present a method to map the Internet to a hyperbolic space. Guided with the constructed map, which we release with this paper, Internet routing exhibits scaling properties close to theoretically best possible, thus resolving serious scaling limitations that the Internet faces today. Besides this immediate practical viability, our network mapping method can provide a different perspective on the community structure in complex networks.
Performance Evaluation of an OMPR Algorithm for Route Discovery in Noisy MANETs
Venue: arXiv cs.NI 2010
Year: 2010

It has been revealed in the literature that pure multipoint relaying (MPR) algorithms demonstrate both simplicity and outstanding performance, as compared to other flooding algorithms in wireless networks. One drawback of pure MPR algorithms is that the selected forwarding set may not represent the optimum selection. In addition, little efforts have been carried-out to investigate the performance of such algorithms in noisy mobile ad hoc networks (MANETs) suffering from high packet-loss and node mobility. In this paper, we develop and evaluate the performance of an optimal MPR (OMPR) algorithm for route discovery in noisy MANETs. The main feature of this new algorithm is that it calculates all possible sets of multipoint relays (MPRs) and then selects the set with minimum number of nodes. The algorithm demonstrates an excellent performance when it is compared with other route discovery algorithms as it achieves the highest cost-effective reachability.
Automatic Recommendation for Online Users Using Web Usage Mining
Venue: arXiv cs.IR 2010
Year: 2010

A real world challenging task of the web master of an organization is to match the needs of user and keep their attention in their web site. So, only option is to capture the intuition of the user and provide them with the recommendation list. Most specifically, an online navigation behavior grows with each passing day, thus extracting information intelligently from it is a difficult issue. Web master should use web usage mining method to capture intuition. A WUM is designed to operate on web server logs which contain user's navigation. Hence, recommendation system using WUM can be used to forecast the navigation pattern of user and recommend those to user in a form of recommendation list. In this paper, we propose a two tier architecture for capturing users intuition in the form of recommendation list containing pages visited by user and pages visited by other user's having similar usage profile. The practical implementation of proposed architecture and algorithm shows that accuracy of user intuition capturing is improved.
The Challenge of Believability in Video Games: Definitions, Agents Models and Imitation Learning
Venue: arXiv cs.AI 2010
Year: 2010

In this paper, we address the problem of creating believable agents (virtual characters) in video games. We consider only one meaning of believability, ``giving the feeling of being controlled by a player'', and outline the problem of its evaluation. We present several models for agents in games which can produce believable behaviours, both from industry and research. For high level of believability, learning and especially imitation learning seems to be the way to go. We make a quick overview of different approaches to make video games' agents learn from players. To conclude we propose a two-step method to develop new models for believable agents. First we must find the criteria for believability for our application and define an evaluation method. Then the model and the learning algorithm can be designed.
Lombardi Drawings of Graphs
Venue: arXiv cs.CG 2010
Year: 2010

We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs.
Secured Greedy Perimeter Stateless Routing for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Wireless sensor networks are collections of large number of sensor nodes. The sensor nodes are featured with limited energy, computation and transmission power. Each node in the network coordinates with every other node in forwarding their packets to reach the destination. Since these nodes operate in a physically insecure environment; they are vulnerable to different types of attacks such as selective forwarding and sinkhole. These attacks can inject malicious packets by compromising the node. Geographical routing protocols of wireless sensor networks have been developed without considering the security aspects against these attacks. In this paper, a secure routing protocol named secured greedy perimeter stateless routing protocol (S-GPSR) is proposed for mobile sensor networks by incorporating trust based mechanism in the existing greedy perimeter stateless routing protocol (GPSR). Simulation results prove that S-GPSR outperforms the GPSR by reducing the overhead and improving the delivery ratio of the networks.
Grammar-Based Geodesics in Semantic Networks
Venue: arXiv cs.DS 2010
Year: 2010

A geodesic is the shortest path between two vertices in a connected network. The geodesic is the kernel of various network metrics including radius, diameter, eccentricity, closeness, and betweenness. These metrics are the foundation of much network research and thus, have been studied extensively in the domain of single-relational networks (both in their directed and undirected forms). However, geodesics for single-relational networks do not translate directly to multi-relational, or semantic networks, where vertices are connected to one another by any number of edge labels. Here, a more sophisticated method for calculating a geodesic is necessary. This article presents a technique for calculating geodesics in semantic networks with a focus on semantic networks represented according to the Resource Description Framework (RDF). In this framework, a discrete "walker" utilizes an abstract path description called a grammar to determine which paths to include in its geodesic calculation. The grammar-based model forms a general framework for studying geodesic metrics in semantic networks.
Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
Venue: arXiv cs.DS 2010
Year: 2010

We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h-index of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in O(h) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in O(h^2) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research.
Towards a Property Preserving Transformation from IEC 61131-3 to BIP
Venue: arXiv cs.PL 2010
Year: 2010

We report on a transformation from Sequential Function Charts of the IEC 61131-3 standard to BIP. Our presentation features a description of formal syntax and semantics representation of the involved languages and transformation rules. Furthermore, we present a formalism for describing invariants of IEC 61131-3 systems and establish a notion of invariant preservation between the two languages. For a subset of our transformation rules we sketch a proof showing invariant preservation during the transformation of IEC 61131-3 to BIP and vice versa.
Knowledge Recognition Algorithm enables P = NP
Venue: arXiv cs.CC 2010
Year: 2010

This paper introduces a knowledge recognition algorithm (KRA) that is both a Turing machine algorithm and an Oracle Turing machine algorithm. By definition KRA is a non-deterministic language recognition algorithm. Simultaneously it can be implemented as a deterministic Turing machine algorithm. KRA applies mirrored perceptual-conceptual languages to learn member-class relations between the two languages iteratively and retrieve information through deductive and reductive recognition from one language to another. The novelty of KRA is that the conventional concept of relation is adjusted. The computation therefore becomes efficient bidirectional string mapping.
JIT Spraying and Mitigations
Venue: arXiv cs.CR 2010
Year: 2010

With the discovery of new exploit techniques, novel protection mechanisms are needed as well. Mitigations like DEP (Data Execution Prevention) or ASLR (Address Space Layout Randomization) created a significantly more difficult environment for exploitation. Attackers, however, have recently researched new exploitation methods which are capable of bypassing the operating system's memory mitigations. One of the newest and most popular exploitation techniques to bypass both of the aforementioned security protections is JIT memory spraying, introduced by Dion Blazakis. In this article we will present a short overview of the JIT spraying technique and also novel mitigation methods against this innovative class of attacks. An anti-JIT spraying library was created as part of our shellcode execution prevention system.
Social interaction as a heuristic for combinatorial optimization problems
Venue: arXiv cs.DS 2010
Year: 2010

We investigate the performance of a variant of Axelrod's model for dissemination of culture - the Adaptive Culture Heuristic (ACH) - on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size $F$ by a Boolean Binary Perceptron. In this heuristic, $N$ agents, characterized by binary strings of length $F$ which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable $F/N^{1/4}$ so that the number of agents must increase with the fourth power of the problem size, $N \propto F^ 4$, to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with $F^ 6$ which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean Binary Perceptron, given a fixed probability of success.
Weight Distributions of Multi-Edge type LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

The multi-edge type LDPC codes, introduced by Richardson and Urbanke, present the general class of structured LDPC codes. In this paper, we derive the average weight distributions of the multi-edge type LDPC code ensembles. Furthermore, we investigate the asymptotic exponential growth rate of the average weight distributions and investigate the connection to the stability condition of the density evolution.
A family of sequences with large size and good correlation property arising from $M$-ary Sidelnikov sequences of period $q^d-1$
Venue: arXiv cs.IT 2010
Year: 2010

Let $q$ be any prime power and let $d$ be a positive integer greater than 1. In this paper, we construct a family of $M$-ary sequences of period $q-1$ from a given $M$-ary, with $M|q-1$, Sidelikov sequence of period $q^d-1$. Under mild restrictions on $d$, we show that the maximum correlation magnitude of the family is upper bounded by $(2d -1) \sqrt { q }+1$ and the asymptotic size, as $q\rightarrow \infty$, of that is $\frac{ (M-1)q^{d-1}}{d }$. This extends the pioneering work of Yu and Gong for $d=2$ case.
Approximate Lesion Localization in Dermoscopy Images
Venue: arXiv cs.CV 2010
Year: 2010

Background: Dermoscopy is one of the major imaging modalities used in the diagnosis of melanoma and other pigmented skin lesions. Due to the difficulty and subjectivity of human interpretation, automated analysis of dermoscopy images has become an important research area. Border detection is often the first step in this analysis. Methods: In this article, we present an approximate lesion localization method that serves as a preprocessing step for detecting borders in dermoscopy images. In this method, first the black frame around the image is removed using an iterative algorithm. The approximate location of the lesion is then determined using an ensemble of thresholding algorithms. Results: The method is tested on a set of 428 dermoscopy images. The localization error is quantified by a metric that uses dermatologist determined borders as the ground truth. Conclusion: The results demonstrate that the method presented here achieves both fast and accurate localization of lesions in dermoscopy images.
Generalized Semimagic Squares for Digital Halftoning
Venue: arXiv cs.CG 2010
Year: 2010

Completing Aronov et al.'s study on zero-discrepancy matrices for digital halftoning, we determine all (m, n, k, l) for which it is possible to put mn consecutive integers on an m-by-n board (with wrap-around) so that each k-by-l region holds the same sum. For one of the cases where this is impossible, we give a heuristic method to find a matrix with small discrepancy.
Two-Way Transmission Capacity of Wireless Ad-hoc Networks
Venue: arXiv cs.IT 2010
Year: 2010

The transmission capacity of an ad-hoc network is the maximum density of active transmitters per unit area, given an outage constraint at each receiver for a fixed rate of transmission. Most prior work on finding the transmission capacity of ad-hoc networks has focused only on one-way communication where a source communicates with a destination and no data is sent from the destination to the source. In practice, however, two-way or bidirectional data transmission is required to support control functions like packet acknowledgements and channel feedback. This paper extends the concept of transmission capacity to two-way wireless ad-hoc networks by incorporating the concept of a two-way outage with different rate requirements in both directions. Tight upper and lower bounds on the two-way transmission capacity are derived for frequency division duplexing. The derived bounds are used to derive the optimal solution for bidirectional bandwidth allocation that maximizes the two-way transmission capacity, which is shown to perform better than allocating bandwidth proportional to the desired rate in both directions. Using the proposed two-way transmission capacity framework, a lower bound on the two-way transmission capacity with transmit beamforming using limited feedback is derived as a function of bandwidth, and bits allocated for feedback.
On the Impact of Caching and a Model for Storage-Capacity Measurements for Energy Conservation in Asymmetrical Wireless Devices
Venue: arXiv cs.NI 2010
Year: 2010

Traffic and channel-data rate combined with the stream oriented methodology can provide a scheme for offering optimized and guaranteed QoS. In this work a stream oriented modeled scheme is proposed based on each node's self-scheduling energy management. This scheme is taking into account the overall packet loss in order to form the optimal effective -for the end-to-end connection- throughput response. The scheme also -quantitatively- takes into account the asymmetrical nature of wireless links and the caching activity that is used for data revocation in the ad-hoc based connectivity scenario. Through the designed middleware and the architectural layering and through experimental simulation, the proposed energy-aware management scheme is thoroughly evaluated in order to meet the parameters' values where the optimal throughput response for each device/user is achieved.
Conductance and Eigenvalue
Venue: arXiv cs.DM 2010
Year: 2010

We show the following. \begin{theorem} Let $M$ be an finite-state ergodic time-reversible Markov chain with transition matrix $P$ and conductance $ϕ$. Let $λ\in (0,1)$ be an eigenvalue of $P$. Then, $$ϕ^2 + λ^2 \leq 1$$ \end{theorem} This strengthens the well-known~\cite{HLW,Dod84, AM85, Alo86, JS89} inequality $λ\leq 1- ϕ^2/2$. We obtain our result by a slight variation in the proof method in \cite{JS89, HLW}; the same method was used earlier in \cite{RS06} to obtain the same inequality for random walks on regular undirected graphs.
Aero Fighter - 2D Gaming
Venue: arXiv cs.OH 2010
Year: 2010

Designing and developing quality based computer game is always a challenging task for developers. In this paper I briefly discuss aero fighting war game based on simple 2D gaming concepts and developed in C & C++ programming languages, using old bitmapping concepts. Going into the details of the game development, I discuss the designed strategies, flow of game and implemented prototype version of game, especially for beginners of game programming.
AI 3D Cybug Gaming
Venue: arXiv cs.AI 2010
Year: 2010

In this short paper I briefly discuss 3D war Game based on artificial intelligence concepts called AI WAR. Going in to the details, I present the importance of CAICL language and how this language is used in AI WAR. Moreover I also present a designed and implemented 3D War Cybug for AI WAR using CAICL and discus the implemented strategy to defeat its enemies during the game life.
Delay-Optimal User Scheduling and Inter-Cell Interference Management in Cellular Network via Distributive Stochastic Learning
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a distributive queueaware intra-cell user scheduling and inter-cell interference (ICI) management control design for a delay-optimal celluar downlink system with M base stations (BSs), and K users in each cell. Each BS has K downlink queues for K users respectively with heterogeneous arrivals and delay requirements. The ICI management control is adaptive to joint queue state information (QSI) over a slow time scale, while the user scheduling control is adaptive to both the joint QSI and the joint channel state information (CSI) over a faster time scale. We show that the problem can be modeled as an infinite horizon average cost Partially Observed Markov Decision Problem (POMDP), which is NP-hard in general. By exploiting the special structure of the problem, we shall derive an equivalent Bellman equation to solve the POMDP problem. To address the distributive requirement and the issue of dimensionality and computation complexity, we derive a distributive online stochastic learning algorithm, which only requires local QSI and local CSI at each of the M BSs. We show that the proposed learning algorithm converges almost surely (with probability 1) and has significant gain compared with various baselines. The proposed solution only has linear complexity order O(MK).
One software tool for testing square s-boxes
Venue: arXiv cs.CR 2010
Year: 2010

An encryption technique is widely used to keep data confidential. Most of the block symmetric algorithms use substitution functions. Often this functions use so called S-BOX matrix. In this paper author presents one software tool for testing and measuring square s-boxes. Based of information theory functions for testing static and dynamic criteria are presented. These criteria are mathematically defined for square s-boxes. Two new criteria "private criteria" a proposed and pseudo codes for they creation and testing are presented.
INDECT Advanced Security Requirements
Venue: arXiv cs.CR 2010
Year: 2010

This paper reviews the requirements for the security mechanisms that are currently being developed in the framework of the European research project INDECT. An overview of features for integrated technologies such as Virtual Private Networks (VPNs), Cryptographic Algorithms, Quantum Cryptography, Federated ID Management and Secure Mobile Ad-hoc networking are described together with their expected use in INDECT.
Left-Inverses of Fractional Laplacian and Sparse Stochastic Processes
Venue: arXiv cs.IT 2010
Year: 2010

The fractional Laplacian $(-\triangle)^{γ/2}$ commutes with the primary coordination transformations in the Euclidean space $\RR^d$: dilation, translation and rotation, and has tight link to splines, fractals and stable Levy processes. For $0<γ<d$, its inverse is the classical Riesz potential $I_γ$ which is dilation-invariant and translation-invariant. In this work, we investigate the functional properties (continuity, decay and invertibility) of an extended class of differential operators that share those invariance properties. In particular, we extend the definition of the classical Riesz potential $I_γ$ to any non-integer number $γ$ larger than $d$ and show that it is the unique left-inverse of the fractional Laplacian $(-\triangle)^{γ/2}$ which is dilation-invariant and translation-invariant. We observe that, for any $1\le p\le \infty$ and $γ\ge d(1-1/p)$, there exists a Schwartz function $f$ such that $I_γf$ is not $p$-integrable. We then introduce the new unique left-inverse $I_{γ, p}$ of the fractional Laplacian $(-\triangle)^{γ/2}$ with the property that $I_{γ, p}$ is dilation-invariant (but not translation-invariant) and that $I_{γ, p}f$ is $p$-integrable for any Schwartz function $f$. We finally apply that linear operator $I_{γ, p}$ with $p=1$ to solve the stochastic partial differential equation $(-\triangle)^{γ/2} Φ=w$ with white Poisson noise as its driving term $w$.
Energy-preserving numerical schemes of high accuracy for one-dimensional Hamiltonian systems
Venue: arXiv cs.NA 2010
Year: 2010

We present a class of non-standard numerical schemes which are modifications of the discrete gradient method. They preserve the energy integral exactly (up to the round-off error). The considered class contains locally exact discrete gradient schemes and integrators of arbitrary high order. In numerical experiments we compare our integrators with some other numerical schemes, including the standard discrete gradient method, the leap-frog scheme and a symplectic scheme of 4th order. We study the error accumulation for very long time and the conservation of the energy integral.
The Detection of Human Spreadsheet Errors by Humans versus Inspection (Auditing) Software
Venue: arXiv cs.SE 2010
Year: 2010

Previous spreadsheet inspection experiments have had human subjects look for seeded errors in spreadsheets. In this study, subjects attempted to find errors in human-developed spreadsheets to avoid the potential artifacts created by error seeding. Human subject success rates were compared to the successful rates for error-flagging by spreadsheet static analysis tools (SSATs) applied to the same spreadsheets. The human error detection results were comparable to those of studies using error seeding. However, Excel Error Check and Spreadsheet Professional were almost useless for correctly flagging natural (human) errors in this study.