OpenRaiser/Intern-Atlas huggingface dataset:
Identification of hybrid node and link communities in complex networks
Venue: arXiv cs.SI 2013
Year: 2013

Identification of communities in complex networks has become an effective means to analysis of complex systems. It has broad applications in diverse areas such as social science, engineering, biology and medicine. Finding communities of nodes and finding communities of links are two popular schemes for network structure analysis. These schemes, however, have inherent drawbacks and are often inadequate to properly capture complex organizational structures in real networks. We introduce a new scheme and effective approach for identifying complex network structures using a mixture of node and link communities, called hybrid node-link communities. A central piece of our approach is a probabilistic model that accommodates node, link and hybrid node-link communities. Our extensive experiments on various real-world networks, including a large protein-protein interaction network and a large semantic association network of commonly used words, illustrated that the scheme for hybrid communities is superior in revealing network characteristics. Moreover, the new approach outperformed the existing methods for finding node or link communities separately.
Fixed-Parameter and Approximation Algorithms: A New Look
Venue: arXiv cs.DS 2013
Year: 2013

A Fixed-Parameter Tractable (\FPT) $ρ$-approximation algorithm for a minimization (resp. maximization) parameterized problem $P$ is an FPT algorithm that, given an instance $(x, k)\in P$ computes a solution of cost at most $k \cdot ρ(k)$ (resp. $k/ρ(k)$) if a solution of cost at most (resp. at least) $k$ exists; otherwise the output can be arbitrary. For well-known intractable problems such as the W[1]-hard {Clique} and W[2]-hard {Set Cover} problems, the natural question is whether we can get any \FPT-approximation. It is widely believed that both {Clique} and {Set-Cover} admit no FPT $ρ$-approximation algorithm, for any increasing function $ρ$. Assuming standard conjectures such as the Exponential Time Hypothesis (ETH) \cite{eth-paturi} and the Projection Games Conjecture (PGC) \cite{r3}, we make the first progress towards proving this conjecture by showing that 1. Under the ETH and PGC, there exist constants $F_1, F_2 >0$ such that the {Set Cover} problem does not admit an FPT approximation algorithm with ratio $k^{F_1}$ in $2^{k^{F_2}}\cdot \text{poly}(N,M)$ time, where $N$ is the size of the universe and $M$ is the number of sets. 2. Unless $\NP\subseteq \SUBEXP$, for every $1> δ> 0$ there exists a constant $F(δ)>0$ such that {Clique} has no FPT cost approximation with ratio $k^{1-δ}$ in $2^{k^{F}}\cdot \text{poly}(n)$ time, where $n$ is the number of vertices in the graph. In the second part of the paper we consider various W[1]-hard problems such as {\dst}, {\dsf}, Directed Steiner Network and {\mec}. For all these problem we give polynomial time $f(\text{OPT})$-approximation algorithms for some small function $f$ (the largest approximation ratio we give is $\text{OPT}^2$).
Euclidean and Hermitian Self-orthogonal Algebraic Geometry Codes and Their Application to Quantum Codes
Venue: arXiv cs.IT 2013
Year: 2013

In the present paper, we show that if the dimension of an arbitrary algebraic geometry code over a finite field of even characters is slightly less than half of its length, then it is equivalent to an Euclidean self-orthogonal code. However, in the literatures, a strong contrition about existence of certain differential is required to obtain such a result. We also show a similar result on Hermitian self-orthogonal algebraic geometry codes. As a consequence, we can apply our result to quantum codes and obtain quantum codes with good asymptotic bounds.
Layered Constructions for Low-Delay Streaming Codes
Venue: arXiv cs.IT 2013
Year: 2013

We propose a new class of error correction codes for low-delay streaming communication. We consider an online setup where a source packet arrives at the encoder every $M$ channel uses, and needs to be decoded with a maximum delay of $T$ packets. We consider a sliding-window erasure channel --- $\cC(N,B,W)$ --- which introduces either up to $N$ erasures in arbitrary positions, or $B$ erasures in a single burst, in any window of length $W$. When $M=1$, the case where source-arrival and channel-transmission rates are equal, we propose a class of codes --- MiDAS codes --- that achieve a near optimal rate. Our construction is based on a {\em layered} approach. We first construct an optimal code for the $\cC(N=1,B,W)$ channel, and then concatenate an additional layer of parity-check symbols to deal with $N>1$. When $M > 1$, the case where source-arrival and channel-transmission rates are unequal, we characterize the capacity when $N=1$ and $W \ge M(T+1),$ and for $N>1$, we propose a construction based on a layered approach. Numerical simulations over Gilbert-Elliott and Fritchman channel models indicate significant gains in the residual loss probability over baseline schemes. We also discuss the connection between the error correction properties of the MiDAS codes and their underlying column distance and column span.
A Variational Principle for Improving 2D Triangle Meshes based on Hyperbolic Volume
Venue: arXiv cs.CG 2013
Year: 2013

In this paper, we consider the problem of improving 2D triangle meshes tessellating planar regions. We propose a new variational principle for improving 2D triangle meshes where the energy functional is a convex function over the angle structures whose maximizer is unique and consists only of equilateral triangles. This energy functional is related to hyperbolic volume of ideal 3-simplex. Even with extra constraints on the angles for embedding the mesh into the plane and preserving the boundary, the energy functional remains well-behaved. We devise an efficient algorithm for maximizing the energy functional over these extra constraints. We apply our algorithm to various datasets and compare its performance with that of CVT. The experimental results show that our algorithm produces the meshes with both the angles and the aspect ratios of triangles lying in tighter intervals.
Alert-BDI: BDI Model with Adaptive Alertness through Situational Awareness
Venue: arXiv cs.MA 2013
Year: 2013

In this paper, we address the problems faced by a group of agents that possess situational awareness, but lack a security mechanism, by the introduction of a adaptive risk management system. The Belief-Desire-Intention (BDI) architecture lacks a framework that would facilitate an adaptive risk management system that uses the situational awareness of the agents. We extend the BDI architecture with the concept of adaptive alertness. Agents can modify their level of alertness by monitoring the risks faced by them and by their peers. Alert-BDI enables the agents to detect and assess the risks faced by them in an efficient manner, thereby increasing operational efficiency and resistance against attacks.
Implementing Constraint Handling Rules as a Domain-Specific Language Embedded in Java
Venue: arXiv cs.PL 2013
Year: 2013

Programming languages and techniques based on logic and constraints, such as the Constraint Handling Rules (CHR), can support many common programming tasks that can be expressed in the form of a search for feasible or optimal solutions. Developing new constraint solvers using CHR is especially interesting in configuration management for large scale, distributed and dynamic cloud applications, where dynamic configuration and component selection is an integral part of the programming environment. Writing CHR-style constraint solvers in a domain-specific language which is a subset of Java -- instead of using a separate language layer -- solves many integration, development cycle disruption, testing and debugging problems that discourage or make difficult the adoption of the CHR-based approach in the mainstream programming environments. Besides, the prototype implementation exposes a well-defined API that supports transactional store behavior, safe termination, and debugging via event notifications.
Why It's Nice to be Quoted: Quasiquoting for Prolog
Venue: arXiv cs.PL 2013
Year: 2013

Prolog's support for dynamic programming, meta programming and text processing using context free grammars make the language highly suitable for defining domain specific languages (DSL) as well as analysing, refactoring or generating expression states in other (programming) languages. Well known DSLs are the DCG (Definite Clause Grammar) notation and constraint languages such as CHR. These extensions use Prolog operator declarations and the {...} notation to realise a good syntax. When external languages, such as HTML, SQL or JavaScript enter the picture, operators no longer satisfy for embedding snippets of these languages into a Prolog source file. In addition, Prolog has poor support for quoting long text fragments. Haskell introduced quasi quotationsto resolve this problem. In this paper we `ported' the Haskell mechanism for quasi quoting to Prolog. We show that this can be done cleanly and that quasi quoting can solve the above mentioned problems.
Optimal Algorithms for Testing Closeness of Discrete Distributions
Venue: arXiv cs.DS 2013
Year: 2013

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions $p$ and $q$ over an $n$-element set, we wish to distinguish whether $p=q$ versus $p$ is at least $\eps$-far from $q$, in either $\ell_1$ or $\ell_2$ distance. Batu et al. gave the first sub-linear time algorithms for these problems, which matched the lower bounds of Valiant up to a logarithmic factor in $n$, and a polynomial factor of $\eps.$ In this work, we present simple (and new) testers for both the $\ell_1$ and $\ell_2$ settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on $n$, and the dependence on $\eps$; for the $\ell_1$ testing problem we establish that the sample complexity is $Θ(\max\{n^{2/3}/\eps^{4/3}, n^{1/2}/\eps^2 \}).$
Iterative Multiuser Detection and Decoding with Spatially Coupled Interleaving
Venue: arXiv cs.IT 2013
Year: 2013

Spatially coupled (SC) interleaving is proposed to improve the performance of iterative multiuser detection and decoding (MUDD) for quasi-static fading multiple-input multiple-output systems. The linear minimum mean-squared error (LMMSE) demodulator is used to reduce the complexity and to avoid error propagation. Furthermore, sliding window MUDD is proposed to circumvent an increase of the decoding latency due to SC interleaving. Theoretical and numerical analyses show that SC interleaving can improve the performance of the iterative LMMSE MUDD for regular low-density parity-check codes.
Reachability Problem for Weak Multi-Pushdown Automata
Venue: arXiv cs.LO 2013
Year: 2013

This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all transitions of an automaton go downwards with respect to the order. We prove decidability of the reachability problem, and computability of the backward reachability set. As the main contribution, we identify relevant subclasses where the reachability problem becomes NP-complete. This matches the complexity of the same problem for communication-free vector addition systems, a special case of stateless multi-pushdown automata.
Gcube Indexing
Venue: arXiv cs.DB 2013
Year: 2013

Spatial Online Analytical Processing System involves the non-categorical attribute information also whereas standard Online Analytical Processing System deals with only categorical attributes. Providing spatial information to the data warehouse (DW); two major challenges faced are;1.Defining and Aggregation of Spatial/Continues values and 2.Representation, indexing, updating and efficient query processing. In this paper, we present GCUBE(Geographical Cube) storage and indexing procedure to aggregate the spatial information/Continuous values. We employed the proposed approach storing and indexing using synthetic and real data sets and evaluated its build, update and Query time. It is observed that the proposed procedure offers significant performance advantage.
List coloring the square of sparse graphs with large degree
Venue: arXiv cs.DM 2013
Year: 2013

We consider the problem of coloring the squares of graphs of bounded maximum average degree, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbour receive different colors. Borodin et al. proved in 2004 and 2008 that the squares of planar graphs of girth at least seven and sufficiently large maximum degree $Δ$ are list $(Δ+1)$-colorable, while the squares of some planar graphs of girth six and arbitrarily large maximum degree are not. By Euler's Formula, planar graphs of girth at least $6$ are of maximum average degree less than $3$, and planar graphs of girth at least $7$ are of maximum average degree less than $14/5<3$. We strengthen their result and prove that there exists a function $f$ such that the square of any graph with maximum average degree $m<3$ and maximum degree $Δ\geq f(m)$ is list $(Δ+1)$-colorable. This bound of $3$ is optimal in the sense that the above-mentioned planar graphs with girth $6$ have maximum average degree less than $3$ and arbitrarily large maximum degree, while their square cannot be $(Δ+1)$-colored. The same holds for list injective $Δ$-coloring.
Private Outsourcing of Polynomial Evaluation and Matrix Multiplication using Multilinear Maps
Venue: arXiv cs.CR 2013
Year: 2013

{\em Verifiable computation} (VC) allows a computationally weak client to outsource the evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of off-line computation and gives an encoding of its function to the server. The server returns both an evaluation of the function on the client's input and a proof such that the client can verify the evaluation using substantially less effort than doing the evaluation on its own. We consider how to privately outsource computations using {\em privacy preserving} VC schemes whose executions reveal no information on the client's input or function to the server. We construct VC schemes with {\em input privacy} for univariate polynomial evaluation and matrix multiplication and then extend them such that the {\em function privacy} is also achieved. Our tool is the recently developed {mutilinear maps}. The proposed VC schemes can be used in outsourcing {private information retrieval (PIR)}.
Compressive Sampling for the Packet Loss Recovery in Audio Multimedia Streaming
Venue: arXiv cs.MM 2013
Year: 2013

The aim of this paper is to introduce a new schema, based on a Compressive Sampling technique, for the recovery of lost data in multimedia streaming. The audio streaming data are encapsuled in different packets by using an interleaving technique. The Compressive Sampling technique is used to recover audio information in case of lost packets. Experimental results are presented on speech and musical audio signals to illustrate the performances and the capabilities of the proposed methodology.
Expanding the Knowledge Horizon in Underwater Robot Swarms
Venue: arXiv cs.RO 2013
Year: 2013

In this paper we study the time delays affecting the diffusion of information in an underwater heterogeneous robot swarm, considering a time-sensitive environment. In many situations each member of the swarm must update its knowledge about the environment as soon as possible, thus every effort to expand the knowledge horizon is useful. Otherwise critical information may not reach nodes far from the source causing dangerous misbehaviour of the swarm. We consider two extreme situations. In the first scenario we have an unique probabilistic delay distribution. In the second scenario, each agent is subject to a different truncated gaussian distribution, meaning local conditions are significantly different from link to link. We study how several swarm topologies react to the two scenarios and how to allocate the more efficient transmission resources in order to expand the horizon. Results show that significant time savings under a gossip-like protocol are possible properly allocating the resources. Moreover, methods to determine the fastest swarm topologies and the most important nodes are suggested.
Simple and Robust Boolean Operations for Triangulated Surfaces
Venue: arXiv cs.CG 2013
Year: 2013

Boolean operations of geometric models is an essential issue in computational geometry. In this paper, we develop a simple and robust approach to perform Boolean operations on closed and open triangulated surfaces. Our method mainly has two stages: (1) We firstly find out candidate intersected-triangles pairs based on Octree and then compute the inter-section lines for all pairs of triangles with parallel algorithm; (2) We form closed or open intersection-loops, sub-surfaces and sub-blocks quite robustly only according to the cleared and updated topology of meshes while without coordinate computations for geometric enti-ties. A novel technique instead of inside/outside classification is also proposed to distinguish the resulting union, subtraction and intersection. Several examples have been given to illus-trate the effectiveness of our approach.
The Wonderful Toy of 20th Century can be a Disaster in 21st Century:Scenario and Policies Regarding Mobile Waste in India
Venue: arXiv cs.CY 2013
Year: 2013

The subscribers base of mobile phones is increasing globally with a rapid rate.The sale of mobile phones has exceeded those of personal computers.India is the second largest telecommunication network in the world in terms of number of wireless connections after China.Telecom companies are ready to tap a large unexplored market in India with lucrative offerings.Smart phones sale are at its peak.3G technology is also ready to play a lead role in mobile revolution.Due to the low average life of the mobile phones,lack of awareness among users and in absence of government policies,mobile waste is accumulating in vast amount in India.Without a proper system of recycling,the unsafe disposal is causing a variety of environmental and health problems.This paper discusses the various issues related to the worldwide growth of mobile phones,the insecure methods of disposal and the regulations and policies in India.We intend to put forward some challenges and advices.
On the Throughput and Energy Efficiency of Cognitive MIMO Transmissions
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, throughput and energy efficiency of cognitive multiple-input multiple-output (MIMO) systems operating under quality-of-service (QoS) constraints, interference limitations, and imperfect channel sensing, are studied. It is assumed that transmission power and covariance of the input signal vectors are varied depending on the sensed activities of primary users (PUs) in the system. Interference constraints are applied on the transmission power levels of cognitive radios (CRs) to provide protection for the PUs whose activities are modeled as a Markov chain. Considering the reliability of the transmissions and channel sensing results, a state-transition model is provided. Throughput is determined by formulating the effective capacity. First derivative of the effective capacity is derived in the low-power regime and the minimum bit energy requirements in the presence of QoS limitations and imperfect sensing results are identified. Minimum energy per bit is shown to be achieved by beamforming in the maximal-eigenvalue eigenspace of certain matrices related to the channel matrix. In a special case, wideband slope is determined for more refined analysis of energy efficiency. Numerical results are provided for the throughput for various levels of buffer constraints and different number of transmit and receive antennas. The impact of interference constraints and benefits of multiple-antenna transmissions are determined. It is shown that increasing the number of antennas when the interference power constraint is stringent is generally beneficial. On the other hand, it is shown that under relatively loose interference constraints, increasing the number of antennas beyond a certain level does not lead to much increase in the throughput.
An Investigation On Fuzzy Logic Controllers (TAKAGI-SUGENO & MAMDANI) In Inverse Pendulum System
Venue: arXiv cs.SY 2013
Year: 2013

The concept of controlling non-linear systems is one the significant fields in scientific researches for the purpose of which intelligent approaches can provide desirable applicability. Fuzzy systems are systems with ambiguous definition and fuzzy control is an especial type of non-linear control. Inverse pendulum system is one the most widely popular non-linear systems which is known for its specific characteristics such as being intrinsically non-linear and unsteady. Therefore, a controller is required for maintaining stability of the system Present study tries to compare the obtained results from designing fuzzy intelligent controllers in similar conditions and also identify the appropriate controller for holding the inverse pendulum in vertical position on the cart.
Strategy For Assessment Of Land And Complex Fields Type Analysis Through GIS In Bangladesh
Venue: arXiv cs.CY 2013
Year: 2013

Bangladesh is an over populated developing country where crisis of food is a major issue, it faces different infrastructure problem in every sector. For Poverty Alleviation from the country we have to confirm cultivable land to increase the crop production for feeding the over population of the country. This paper focuses on the measurement of cultivable land for cultivation. The main purpose of this paper is to briefly describe how the GIS, Digital Mapping, Internet concepts and tools can effectively contribute in the modeling, analysis and visualization phases within an engineering or research project according to the crops by using object detection, object tracking and field mapping in Bangladesh. Through GIS mapping of the agricultural lands, the statistics can be made of how much land is cultivable and each year how much land we are losing. Mapping the cultivation land will tell us how much crop we have to import from other countries. Enabling real-time GIS analysis anytime, anywhere, the implementation of the GIS information to a wider aspect. Automation is the indicator of the modern civilizations. The system will benefit the food stock of the country according to the harvest. For this research we developed a new interactive system. The system will integrate with GIS project data in Google Earth, first finds highly accurate cluster images and partial images, obtains user feedback to merge or correct these digests, and then the supplementary visual analysis complete the partitioning of the data. This study was conducted at the software laboratory, Computer Science and Engineering department, Jahangirnagar University, Dhaka, Bangladesh in 2013.
How to implement Marketing 2.0 Successfully
Venue: arXiv cs.OH 2013
Year: 2013

The purpose of this research is to develop a model that would close the gap between marketing plans and strategies from one side and the advanced online collaboration applications platforms known as WEB 2.0 in order to implement marketing 2.0 smoothly without disrupting the working environment. We started by examining published articles related to marketing, Web 2.0, Customer Relationship Management Systems, CRM, and social media in a step to conduct an extensive review of the available literature. Then, we presented critique of the articles we have examined. After that, we have been able to develop the model we are proposing in this research. As this paper shows, the proposed model will help in transforming marketing plans and strategies from its traditional approach into, what we would like to call, marketing 2.0 approach smoothly. There are some unavoidable limitations due to the given time and scope constrains. The factors included in the proposed model does not cover every related aspect, however, they cover the most important ones.