OpenRaiser/Intern-Atlas huggingface dataset:
New hybrid distributed voting algorithm
Venue: arXiv cs.DC 2013
Year: 2013

Increasing data volumes requires additional rating techniques. Reputation systems are the subject of much research. There are various techniques to rate content that facilitate the search of quality content. Page rank, citation index and votes from users are some rating examples. In the article I focus on decentralized vote systems. The article reviews several distributed vote designs. I list the distributed vote requirements. A new hybrid algorithm is proposed which operates in the structured overlay P2P DHT Kademlia network.
A Novel Symmetric Key Cryptographic Technique at Bit Level Based on Spiral Matrix Concept
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we propose a session based bit level symmetric key cryptographic technique and it is termed as Spiral Matrix Based Bit Orientation Technique (SMBBOT). SMBBOT consider the input plain text as binary bit stream. During encryption this stream is chopped into manageable sized blocks with variable lengths. Bits of these blocks are taken from MSB to LSB to fit into a square matrix of suitable order following the concept of Spiral matrix. This square matrix splits into 2x2 sub-matrices. Bits are taken column-wise from all 2x2 sub-matrices to form the encrypted binary string. Cipher text is generated from this encrypted binary string. Combination of values of block length and no. of blocks of a session generates the session key for SMBBOT. For decryption the cipher text is considered as binary bit string. Processing the session key information, this binary string is broken down into predefined blocks. Bits of these blocks are taken from MSB to LSB to fit column-wise into 2x2 square matrices. Using these sub-matrices a single square matrix with suitable order is formed. The decrypted binary string is formed after taking the bits from the square matrix following the reverse concept of Spiral Matrix. The plain text is regenerated from decrypted binary string. A comparison of SMBBOT with existing and industrially accepted TDES and AES has been done.
Characterizing and Evaluation :Temporal properties of real and synthetic datasets for DTN
Venue: arXiv cs.NI 2013
Year: 2013

Nodes movements play a significant role in disseminating messages in the sparse mobile ad-hoc network. In the network scenarios, where traditional end-to-end paths do not exist, mobility creates opportunities for nodes to connect and communicate when they are encountered. A series of encountering opportunities spread a message among many nodes and eventually deliver to the destination. Further improvements to the performance of message delivery can come from exploiting temporal mobility properties. It is modeled as time varying graph, where, moving nodes are considered as vertices and contact opportunity to other nodes as an edge. The paper discusses about characterization and design of the temporal algorithm. Then, evaluating temporal distance, diameter and centrality of real and synthetic mobility data sets.
Primer and Recent Developments on Fountain Codes
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we survey the various erasure codes which had been proposed and patented recently, and along the survey we provide introductory tutorial on many of the essential concepts and readings in erasure and Fountain codes. Packet erasure is a fundamental characteristic inherent in data storage and data transmission system. Traditionally replication/ retransmission based techniques had been employed to deal with packet erasures in such systems. While the Reed-Solomon (RS) erasure codes had been known for quite some time to improve system reliability and reduce data redundancy, the high decoding computation cost of RS codes has offset wider implementation of RS codes. However recent exponential growth in data traffic and demand for larger data storage capacity has simmered interest in erasure codes. Recent results have shown promising results to address the decoding computation complexity and redundancy tradeoff inherent in erasure codes.
Weighted Electoral Control
Venue: arXiv cs.GT 2013
Year: 2013

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.
A Versatile Dependent Model for Heterogeneous Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

We propose a new model for heterogeneous cellular networks that incorporates dependencies between the layers. In particular, it places lower-tier base stations at locations that are poorly covered by the macrocells, and it includes a small-cell model for the case where the goal is to enhance network capacity.
Further improvements on the Feng-Rao bound for dual codes
Venue: arXiv cs.IT 2013
Year: 2013

Salazar, Dunn and Graham in [Salazar et. al., 2006] presented an improved Feng-Rao bound for the minimum distance of dual codes. In this work we take the improvement a step further. Both the original bound by Salazar et. al., as well as our improvement are lifted so that they deal with generalized Hamming weights. We also demonstrate the advantage of working with one-way well-behaving pairs rather than weakly well-behaving or well-behaving pairs.
Efficient computation of trees with minimal atom-bond connectivity index
Venue: arXiv cs.DM 2013
Year: 2013

The {\em atom-bond connectivity (ABC) index} is one of the recently most investigated degree-based molecular structure descriptors, that have applications in chemistry. For a graph $G$, the ABC index is defined as $\sum_{uv\in E(G)}\sqrt{\frac{(d(u) +d(v)-2)}{d(u)d(v)}}$, where $d(u)$ is the degree of vertex $u$ in $G$ and $E(G)$ is the set of edges of $G$. Despite many attempts in the last few years, it is still an open problem to characterize trees with minimal $ABC$ index. In this paper, we present an efficient approach of computing trees with minimal ABC index, by considering the degree sequences of trees and some known properties of the graphs with minimal $ABC$ index. The obtained results disprove some existing conjectures end suggest new ones to be set.
Speckle Noise Reduction in Medical Ultrasound Images
Venue: arXiv cs.CV 2013
Year: 2013

Ultrasound imaging is an incontestable vital tool for diagnosis, it provides in non-invasive manner the internal structure of the body to detect eventually diseases or abnormalities tissues. Unfortunately, the presence of speckle noise in these images affects edges and fine details which limit the contrast resolution and make diagnostic more difficult. In this paper, we propose a denoising approach which combines logarithmic transformation and a non linear diffusion tensor. Since speckle noise is multiplicative and nonwhite process, the logarithmic transformation is a reasonable choice to convert signaldependent or pure multiplicative noise to an additive one. The key idea from using diffusion tensor is to adapt the flow diffusion towards the local orientation by applying anisotropic diffusion along the coherent structure direction of interesting features in the image. To illustrate the effective performance of our algorithm, we present some experimental results on synthetically and real echographic images.
Granular association rules for multi-valued data
Venue: arXiv cs.IR 2013
Year: 2013

Granular association rule is a new approach to reveal patterns hide in many-to-many relationships of relational databases. Different types of data such as nominal, numeric and multi-valued ones should be dealt with in the process of rule mining. In this paper, we study multi-valued data and develop techniques to filter out strong however uninteresting rules. An example of such rule might be "male students rate movies released in 1990s that are NOT thriller." This kind of rules, called negative granular association rules, often overwhelms positive ones which are more useful. To address this issue, we filter out negative granules such as "NOT thriller" in the process of granule generation. In this way, only positive granular association rules are generated and strong ones are mined. Experimental results on the movielens data set indicate that most rules are negative, and our technique is effective to filter them out.
Unique Perfect Phylogeny Characterizations via Uniquely Representable Chordal Graphs
Venue: arXiv cs.DM 2013
Year: 2013

The perfect phylogeny problem is a classic problem in computational biology, where we seek an unrooted phylogeny that is compatible with a set of qualitative characters. Such a tree exists precisely when an intersection graph associated with the character set, called the partition intersection graph, can be triangulated using a restricted set of fill edges. Semple and Steel used the partition intersection graph to characterize when a character set has a unique perfect phylogeny. Bordewich, Huber, and Semple showed how to use the partition intersection graph to find a maximum compatible set of characters. In this paper, we build on these results, characterizing when a unique perfect phylogeny exists for a subset of partial characters. Our characterization is stated in terms of minimal triangulations of the partition intersection graph that are uniquely representable, also known as ur-chordal graphs. Our characterization is motivated by the structure of ur-chordal graphs, and the fact that the block structure of minimal triangulations is mirrored in the graph that has been triangulated.
Generalization of Risch's Algorithm to Special Functions
Venue: arXiv cs.SC 2013
Year: 2013

Symbolic integration deals with the evaluation of integrals in closed form. We present an overview of Risch's algorithm including recent developments. The algorithms discussed are suited for both indefinite and definite integration. They can also be used to compute linear relations among integrals and to find identities for special functions given by parameter integrals. The aim of this presentation is twofold: to introduce the reader to some basic ideas of differential algebra in the context of integration and to raise awareness in the physics community of computer algebra algorithms for indefinite and definite integration.
Abelian Group Codes for Source Coding and Channel Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the asymptotic performance of Abelian group codes for the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources as well as the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels. For the source coding problem, we derive an achievable rate-distortion function that is characterized in a single-letter information-theoretic form using the ensemble of Abelian group codes. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. Similarly, for the channel coding problem, we find an achievable rate characterized in a single-letter information-theoretic form using group codes. This simplifies to the symmetric capacity of the channel when the underlying group is a field. We compute the rate-distortion function and the achievable rate for several examples of sources and channels. Due to the non-symmetric nature of the sources and channels considered, our analysis uses a synergy of information theoretic and group-theoretic tools.
Location sharing without the central server
Venue: arXiv cs.NI 2013
Year: 2013

This paper describes a new model for sharing location info for mobile users. This approach can operate without the need for disclosing identity info to third party servers. It could be described as a safe location sharing model. The proposed approach creates a special form of distributed database that splits location info and identity information. In this distributed data store identity info is always saved locally. It eliminates one of the main concerns with location-based systems - privacy. This paper describes a model itself as well as its implementation in the form of HTML5 mobile web application.
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut
Venue: arXiv cs.DS 2013
Year: 2013

We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for $γ$-stable Max Cut instances with $γ\geq c\sqrt{\log n}\log\log n$ for some absolute constant $c > 0$. Our algorithm is robust: it never returns an incorrect answer; if the instance is $γ$-stable, it finds the maximum cut, otherwise, it either finds the maximum cut or certifies that the instance is not $γ$-stable. We prove that there is no robust polynomial-time algorithm for $γ$-stable instances of Max Cut when $γ< α_{SC}(n/2)$, where $α_{SC}$ is the best approximation factor for Sparsest Cut with non-uniform demands. Our algorithm is based on semidefinite programming. We show that the standard SDP relaxation for Max Cut (with $\ell_2^2$ triangle inequalities) is integral if $γ\geq D_{\ell_2^2\to \ell_1}(n)$, where $D_{\ell_2^2\to \ell_1}(n)$ is the least distortion with which every $n$ point metric space of negative type embeds into $\ell_1$. On the negative side, we show that the SDP relaxation is not integral when $γ< D_{\ell_2^2\to \ell_1}(n/2)$. Moreover, there is no tractable convex relaxation for $γ$-stable instances of Max Cut when $γ< α_{SC}(n/2)$. That suggests that solving $γ$-stable instances with $γ=o(\sqrt{\log n})$ might be difficult or impossible. Our results significantly improve previously known results. The best previously known algorithm for $γ$-stable instances of Max Cut required that $γ\geq c\sqrt{n}$ (for some $c > 0$) [Bilu, Daniely, Linial, and Saks]. No hardness results were known for the problem. Additionally, we present an algorithm for 4-stable instances of Minimum Multiway Cut. We also study a relaxed notion of weak stability.
Evolution of the user's content: An Overview of the state of the art
Venue: arXiv cs.IR 2013
Year: 2013

The evolution of the user's content still remains a problem for an accurate recommendation.This is why the current research aims to design Recommender Systems (RS) able to continually adapt information that matches the user's interests. This paper aims to explain this problematic point in outlining the proposals that have been made in research with their advantages and disadvantages.
A Dataflow Language for Decentralised Orchestration of Web Service Workflows
Venue: arXiv cs.DC 2013
Year: 2013

Orchestrating centralised service-oriented workflows presents significant scalability challenges that include: the consumption of network bandwidth, degradation of performance, and single points of failure. This paper presents a high-level dataflow specification language that attempts to address these scalability challenges. This language provides simple abstractions for orchestrating large-scale web service workflows, and separates between the workflow logic and its execution. It is based on a data-driven model that permits parallelism to improve the workflow performance. We provide a decentralised architecture that allows the computation logic to be moved "closer" to services involved in the workflow. This is achieved through partitioning the workflow specification into smaller fragments that may be sent to remote orchestration services for execution. The orchestration services rely on proxies that exploit connectivity to services in the workflow. These proxies perform service invocations and compositions on behalf of the orchestration services, and carry out data collection, retrieval, and mediation tasks. The evaluation of our architecture implementation concludes that our decentralised approach reduces the execution time of workflows, and scales accordingly with the increasing size of data sets.
Semantic-based Anomalous Pattern Discovery in Moving Object Trajectories
Venue: arXiv cs.AI 2013
Year: 2013

In this work, we investigate a novel semantic approach for pattern discovery in trajectories that, relying on ontologies, enhances object movement information with event semantics. The approach can be applied to the detection of movement patterns and behaviors whenever the semantics of events occurring along the trajectory is, explicitly or implicitly, available. In particular, we tested it against an exacting case scenario in maritime surveillance, i.e., the discovery of suspicious container transportations. The methodology we have developed entails the formalization of the application domain through a domain ontology, extending the Moving Object Ontology (MOO) described in this paper. Afterwards, movement patterns have to be formalized, either as Description Logic (DL) axioms or queries, enabling the retrieval of the trajectories that follow the patterns. In our experimental evaluation, we have considered a real world dataset of 18 Million of container events describing the deed undertaken in a port to accomplish the shipping (e.g., loading on a vessel, export operation). Leveraging events, we have reconstructed almost 300 thousand container trajectories referring to 50 thousand containers travelling along three years. We have formalized the anomalous itinerary patterns as DL axioms, testing different ontology APIs and DL reasoners to retrieve the suspicious transportations. Our experiments demonstrate that the approach is feasible and efficient. In particular, the joint use of Pellet and SPARQL-DL enables to detect the trajectories following a given pattern in a reasonable time with big size datasets.
The Dynamically Extended Mind -- A Minimal Modeling Case Study
Venue: arXiv cs.AI 2013
Year: 2013

The extended mind hypothesis has stimulated much interest in cognitive science. However, its core claim, i.e. that the process of cognition can extend beyond the brain via the body and into the environment, has been heavily criticized. A prominent critique of this claim holds that when some part of the world is coupled to a cognitive system this does not necessarily entail that the part is also constitutive of that cognitive system. This critique is known as the "coupling-constitution fallacy". In this paper we respond to this reductionist challenge by using an evolutionary robotics approach to create a minimal model of two acoustically coupled agents. We demonstrate how the interaction process as a whole has properties that cannot be reduced to the contributions of the isolated agents. We also show that the neural dynamics of the coupled agents has formal properties that are inherently impossible for those neural networks in isolation. By keeping the complexity of the model to an absolute minimum, we are able to illustrate how the coupling-constitution fallacy is in fact based on an inadequate understanding of the constitutive role of nonlinear interactions in dynamical systems theory.
LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation
Venue: arXiv cs.SI 2013
Year: 2013

An increasingly important challenge in network analysis is efficient detection and tracking of communities in dynamic networks for which changes arrive as a stream. There is a need for algorithms that can incrementally update and monitor communities whose evolution generates huge realtime data streams, such as the Internet or on-line social networks. In this paper, we propose LabelRankT, an online distributed algorithm for detection of communities in large-scale dynamic networks through stabilized label propagation. Results of tests on real-world networks demonstrate that LabelRankT has much lower computational costs than other algorithms. It also improves the quality of the detected communities compared to dynamic detection methods and matches the quality achieved by static detection approaches. Unlike most of other algorithms which apply only to binary networks, LabelRankT works on weighted and directed networks, which provides a flexible and promising solution for real-world applications.
On the reduction of the CSP dichotomy conjecture to digraphs
Venue: arXiv cs.CC 2013
Year: 2013

It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.
Characterizing User Behavior and Information Propagation on a Social Multimedia Network
Venue: arXiv cs.SI 2013
Year: 2013

An increasing portion of modern socializing takes place via online social networks. Members of these communities often play distinct roles that can be deduced from observations of users' online activities. One such activity is the sharing of multimedia, the popularity of which can vary dramatically. Here we discuss our initial analysis of anonymized, scraped data from consenting Facebook users, together with associated demographic and psychological profiles. We present five clusters of users with common observed online behaviors, where these users also show correlated profile characteristics. Finally, we identify some common properties of the most popular multimedia content.
Intercept Probability Analysis of Cooperative Wireless Networks with Best Relay Selection in the Presence of Eavesdropping Attack
Venue: arXiv cs.IT 2013
Year: 2013

Due to the broadcast nature of wireless medium, wireless communication is extremely vulnerable to eavesdropping attack. Physical-layer security is emerging as a new paradigm to prevent the eavesdropper from interception by exploiting the physical characteristics of wireless channels, which has recently attracted a lot of research attentions. In this paper, we consider the physical-layer security in cooperative wireless networks with multiple decode-and-forward (DF) relays and investigate the best relay selection in the presence of eavesdropping attack. For the comparison purpose, we also examine the conventional direct transmission without relay and traditional max-min relay selection. We derive closed-form intercept probability expressions of the direct transmission, traditional max-min relay selection, and proposed best relay selection schemes in Rayleigh fading channels. Numerical results show that the proposed best relay selection scheme strictly outperforms the traditional direct transmission and max-min relay selection schemes in terms of intercept probability. In addition, as the number of relays increases, the intercept probabilities of both traditional max-min relay selection and proposed best relay selection schemes decrease significantly, showing the advantage of exploiting multiple relays against eavesdropping attack.
Capacity of a Simple Intercellular Signal Transduction Channel
Venue: arXiv cs.IT 2013
Year: 2013

We model the ligand-receptor molecular communication channel with a discrete-time Markov model, and show how to obtain the capacity of this channel. We show that the capacity-achieving input distribution is iid; further, unusually for a channel with memory, we show that feedback does not increase the capacity of this channel.