OpenRaiser/Intern-Atlas huggingface dataset:
Diameter of Cayley graphs of permutation groups generated by transposition trees
Venue: arXiv cs.DM 2011
Year: 2011

Let $Γ$ be a Cayley graph of the permutation group generated by a transposition tree $T$ on $n$ vertices. In an oft-cited paper \cite{Akers:Krishnamurthy:1989} (see also \cite{Hahn:Sabidussi:1997}), it is shown that the diameter of the Cayley graph $Γ$ is bounded as $$\diam(Γ) \le \max_{π\in S_n}{c(π)-n+\sum_{i=1}^n \dist_T(i,π(i))},$$ where the maximization is over all permutations $π$, $c(π)$ denotes the number of cycles in $π$, and $\dist_T$ is the distance function in $T$. In this work, we first assess the performance (the sharpness and strictness) of this upper bound. We show that the upper bound is sharp for all trees of maximum diameter and also for all trees of minimum diameter, and we exhibit some families of trees for which the bound is strict. We then show that for every $n$, there exists a tree on $n$ vertices, such that the difference between the upper bound and the true diameter value is at least $n-4$. Observe that evaluating this upper bound requires on the order of $n!$ (times a polynomial) computations. We provide an algorithm that obtains an estimate of the diameter, but which requires only on the order of (polynomial in) $n$ computations; furthermore, the value obtained by our algorithm is less than or equal to the previously known diameter upper bound. This result is possible because our algorithm works directly with the transposition tree on $n$ vertices and does not require examining any of the permutations (only the proof requires examining the permutations). For all families of trees examined so far, the value $β$ computed by our algorithm happens to also be an upper bound on the diameter, i.e. $$\diam(Γ) \le β\le \max_{π\in S_n}{c(π)-n+\sum_{i=1}^n \dist_T(i,π(i))}.$$
Tracing the temporal evolution of clusters in a financial stock market
Venue: arXiv cs.CE 2011
Year: 2011

We propose a methodology for clustering financial time series of stocks' returns, and a graphical set-up to quantify and visualise the evolution of these clusters through time. The proposed graphical representation allows for the application of well known algorithms for solving classical combinatorial graph problems, which can be interpreted as problems relevant to portfolio design and investment strategies. We illustrate this graph representation of the evolution of clusters in time and its use on real data from the Madrid Stock Exchange market.
Évaluation de lexiques syntaxiques par leur intégartion dans l'analyseur syntaxiques FRMG
Venue: arXiv cs.CL 2011
Year: 2011

In this paper, we evaluate various French lexica with the parser FRMG: the Lefff, LGLex, the lexicon built from the tables of the French Lexicon-Grammar, the lexicon DICOVALENCE and a new version of the verbal entries of the Lefff, obtained by merging with DICOVALENCE and partial manual validation. For this, all these lexica have been converted to the format of the Lefff, Alexina format. The evaluation was made on the part of the EASy corpus used in the first evaluation campaign Passage.
Construction du lexique LGLex à partir des tables du Lexique-Grammaire des verbes du grec moderne
Venue: arXiv cs.CL 2011
Year: 2011

In this paper, we summerize the work done on the resources of Modern Greek on the Lexicon-Grammar of verbs. We detail the definitional features of each table, and all changes made to the names of features to make them consistent. Through the development of the table of classes, including all the features, we have considered the conversion of tables in a syntactic lexicon: LGLex. The lexicon, in plain text format or XML, is generated by the LGExtract tool (Constant & Tolone, 2010). This format is directly usable in applications of Natural Language Processing (NLP).
Pilotless Recovery of Clipped OFDM Signals by Compressive Sensing over Reliable Data Carriers
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we propose a novel form of clipping mitigation in OFDM using compressive sensing that completely avoids tone reservation and hence rate loss for this purpose. The method builds on selecting the most reliable perturbations from the constellation lattice upon decoding at the receiver, and performs compressive sensing over these observations in order to completely recover the temporally sparse nonlinear distortion. As such, the method provides a unique practical solution to the problem of initial erroneous decoding decisions in iterative ML methods, offering both the ability to augment these techniques and to solely recover the distorted signal in one shot.
(Non-)Equivalence of Universal Priors
Venue: arXiv cs.IT 2011
Year: 2011

Ray Solomonoff invented the notion of universal induction featuring an aptly termed "universal" prior probability function over all possible computable environments. The essential property of this prior was its ability to dominate all other such priors. Later, Levin introduced another construction --- a mixture of all possible priors or `universal mixture'. These priors are well known to be equivalent up to multiplicative constants. Here, we seek to clarify further the relationships between these three characterisations of a universal prior (Solomonoff's, universal mixtures, and universally dominant priors). We see that the the constructions of Solomonoff and Levin define an identical class of priors, while the class of universally dominant priors is strictly larger. We provide some characterisation of the discrepancy.
A Facial Expression Classification System Integrating Canny, Principal Component Analysis and Artificial Neural Network
Venue: arXiv cs.CV 2011
Year: 2011

Facial Expression Classification is an interesting research problem in recent years. There are a lot of methods to solve this problem. In this research, we propose a novel approach using Canny, Principal Component Analysis (PCA) and Artificial Neural Network. Firstly, in preprocessing phase, we use Canny for local region detection of facial images. Then each of local region's features will be presented based on Principal Component Analysis (PCA). Finally, using Artificial Neural Network (ANN)applies for Facial Expression Classification. We apply our proposal method (Canny_PCA_ANN) for recognition of six basic facial expressions on JAFFE database consisting 213 images posed by 10 Japanese female models. The experimental result shows the feasibility of our proposal method.
Control Neuronal por Modelo Inverso de un Servosistema Usando Algoritmos de Aprendizaje Levenberg-Marquardt y Bayesiano
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we present the experimental results of the neural network control of a servo-system in order to control its speed. The control strategy is implemented by using an inverse-model control based on Artificial Neural Networks (ANNs). The network training was performed using two learning algorithms: Levenberg-Marquardt and Bayesian regularization. We evaluate the generalization capability for each method according to both the correct operation of the controller to follow the reference signal, and the control efforts developed by the ANN-based controller.
Battling the Internet Water Army: Detection of Hidden Paid Posters
Venue: arXiv cs.SI 2011
Year: 2011

We initiate a systematic study to help distinguish a special group of online users, called hidden paid posters, or termed "Internet water army" in China, from the legitimate ones. On the Internet, the paid posters represent a new type of online job opportunity. They get paid for posting comments and new threads or articles on different online communities and websites for some hidden purposes, e.g., to influence the opinion of other people towards certain social events or business markets. Though an interesting strategy in business marketing, paid posters may create a significant negative effect on the online communities, since the information from paid posters is usually not trustworthy. When two competitive companies hire paid posters to post fake news or negative comments about each other, normal online users may feel overwhelmed and find it difficult to put any trust in the information they acquire from the Internet. In this paper, we thoroughly investigate the behavioral pattern of online paid posters based on real-world trace data. We design and validate a new detection mechanism, using both non-semantic analysis and semantic analysis, to identify potential online paid posters. Our test results with real-world datasets show a very promising performance.
Energy Aware Node Selection for Cluster-based Data Accuracy Estimation in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

The main objective of this paper is to reduce the number of sensor nodes by estimating a trade off between data accuracy and energy consumption for selecting nodes in probabilistic approach in distributed networks. Design Procedure/Approach: Observed data are highly correlated among sensor nodes in the spatial domain due to deployment of high density of sensor nodes. These sensor nodes form non-overlapping distributed clusters due to high data correlation among them. We develop a probabilistic model for each distributed cluster to perform data accuracy and energy consumption model in the network. Finally we find a trade off between data accuracy and energy consumption model to select an optimal number of sensor nodes in each distributed cluster. We also compare the performance for our data accuracy estimation model with information accuracy model for each distributed cluster in the network. Practical Implementation: Measuring temperature in physical environment and measuring moisture content in agricultural field. Inventive /Novel Idea: Optimal node selection in probabilistic approach using the trade of between data accuracy and energy consumption in cluster-based distributed network.
Practical Top-K Document Retrieval in Reduced Space
Venue: arXiv cs.DS 2011
Year: 2011

Supporting top-k document retrieval queries on general text databases, that is, finding the k documents where a given pattern occurs most frequently, has become a topic of interest with practical applications. While the problem has been solved in optimal time and linear space, the actual space usage is a serious concern. In this paper we study various reduced-space structures that support top-k retrieval and propose new alternatives. Our experimental results show that our novel algorithms and data structures dominate almost all the space/time tradeoff.
Networked estimation under information constraints
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study estimation of potentially unstable linear dynamical systems when the observations are distributed over a network. We are interested in scenarios when the information exchange among the agents is restricted. In particular, we consider that each agent can exchange information with its neighbors only once per dynamical system evolution-step. Existing work with similar information-constraints is restricted to static parameter estimation, whereas, the work on dynamical systems assumes large number of information exchange iterations between every two consecutive system evolution steps. We show that when the agent communication network is sparely-connected, the sparsity of the network plays a key role in the stability and performance of the underlying estimation algorithm. To this end, we introduce the notion of \emph{Network Tracing Capacity} (NTC), which is defined as the largest two-norm of the system matrix that can be estimated with bounded error. Extending this to fully-connected networks or infinite information exchanges (per dynamical system evolution-step), we note that the NTC is infinite, i.e., any dynamical system can be estimated with bounded error. In short, the NTC characterizes the estimation capability of a sparse network by relating it to the evolution of the underlying dynamical system.
An Insight into Spreadsheet User Behaviour through an Analysis of EuSpRIG Website Statistics
Venue: arXiv cs.CY 2011
Year: 2011

The European Spreadsheet Risks Interest Group (EuSpRIG) has maintained a website almost since its inception in 2000. We present here longitudinal and cross-sectional statistics from the website log in order to shed some light upon end-user activity in the EuSpRIG domain.
Solving the TTC 2011 Reengineering Case with VIATRA2
Venue: arXiv cs.SE 2011
Year: 2011

The current paper presents a solution of the Program Understanding: A Reengineering Case for the Transformation Tool Contest using the VIATRA2 model transformation tool.
Solving the TTC 2011 Reengineering Case with GrGen.NET
Venue: arXiv cs.PL 2011
Year: 2011

The challenge of the Reengineering Case is to extract a state machine model out of the abstract syntax graph of a Java program. The extracted state machine offers a reduced view on the full program graph and thus helps to understand the program regarding the question of interest. We tackle this task employing the general purpose graph rewrite system GrGen.NET (www.grgen.net).
Solving the TTC 2011 Reengineering Case with Henshin
Venue: arXiv cs.SE 2011
Year: 2011

This paper presents the Henshin solution to the Model Transformations for Program Understanding case study as part of the Transformation Tool Contest 2011.
Saying Hello World with Edapt - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

This paper gives an overview of the Edapt solution to the hello world case of the Transformation Tool Contest 2011.
Saying Hello World with Henshin - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

This paper gives an overview of the Henshin solution to the Hello World case study of the Transformation Tool Contest 2011, intended to show basic language concepts and constructs.
Enhancement of Image Resolution by Binarization
Venue: arXiv cs.CV 2011
Year: 2011

Image segmentation is one of the principal approaches of image processing. The choice of the most appropriate Binarization algorithm for each case proved to be a very interesting procedure itself. In this paper, we have done the comparison study between the various algorithms based on Binarization algorithms and propose a methodologies for the validation of Binarization algorithms. In this work we have developed two novel algorithms to determine threshold values for the pixels value of the gray scale image. The performance estimation of the algorithm utilizes test images with, the evaluation metrics for Binarization of textual and synthetic images. We have achieved better resolution of the image by using the Binarization method of optimum thresholding techniques.
A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations
Venue: arXiv cs.DS 2011
Year: 2011

A "floorplan" is a rectangle subdivided into smaller rectangular sections by horizontal and vertical line segments. Each section in the floorplan is called a "block". Two floorplans are considered equivalent if and only if there is a one-to-one correspondence between the blocks in the two floorplans such that the relative position relationship of the blocks in one floorplan is the same as the relative position relationship of the corresponding blocks in another floorplan. The objects of "Mosaic floorplans" are the same as floorplans, but an alternative definition of equivalence is used. Two mosaic floorplans are considered equivalent if and only if they can be converted to each other by sliding the line segments that divide the blocks. Mosaic floorplans are widely used in VLSI circuit design. An important problem in this area is to find short binary string representations of the set of n-block mosaic floorplans. The best known representation is the "Quarter-State Sequence" which uses 4n bits. This paper introduces a simple binary representation of n-block mosaic floorplan using 3n-3 bits. It has been shown that any binary representation of n-block mosaic floorplans must use at least (3n-o(n)) bits. Therefore, the representation presented in this paper is optimal (up to an additive lower order term). "Baxter permutations" are a set of permutations defined by prohibited subsequences. Baxter permutations have been shown to have one-to-one correspondences to many interesting objects in the so-called "Baxter combinatorial family". In particular, there exists a simple one-to-one correspondence between mosaic floorplans and Baxter permutations. As a result, the methods introduced in this paper also lead to an optimal binary representation of Baxter permutations and all objects in the Baxter combinatorial family.
Pretty Private Group Management
Venue: arXiv cs.DC 2011
Year: 2011

Group management is a fundamental building block of today's Internet applications. Mailing lists, chat systems, collaborative document edition but also online social networks such as Facebook and Twitter use group management systems. In many cases, group security is required in the sense that access to data is restricted to group members only. Some applications also require privacy by keeping group members anonymous and unlinkable. Group management systems routinely rely on a central authority that manages and controls the infrastructure and data of the system. Personal user data related to groups then becomes de facto accessible to the central authority. In this paper, we propose a completely distributed approach for group management based on distributed hash tables. As there is no enrollment to a central authority, the created groups can be leveraged by various applications. Following this paradigm we describe a protocol for such a system. We consider security and privacy issues inherently introduced by removing the central authority and provide a formal validation of security properties of the system using AVISPA. We demonstrate the feasibility of this protocol by implementing a prototype running on top of Vuze's DHT.
Refinement of Gini-Means Inequalities and Connections with Divergence Measures
Venue: arXiv cs.IT 2011
Year: 2011

In 1938, Gini studied a mean having two parameters. Later, many authors studied properties of this mean. It contains as particular cases the famous means such as harmonic, geometric, arithmetic, etc. Also it contains, the power mean of order r and Lehmer mean as particular cases. In this paper we have considered inequalities arising due to Gini-Mean and Heron's mean, and improved them based on the results recently studied by the author (Taneja, 2011).
Using Scalp Electrical Biosignals to Control an Object by Concentration and Relaxation Tasks: Design and Evaluation
Venue: arXiv cs.OH 2011
Year: 2011

In this paper we explore the use of electrical biosignals measured on scalp and corresponding to mental relaxation and concentration tasks in order to control an object in a video game. To evaluate the requirements of such a system in terms of sensors and signal processing we compare two designs. The first one uses only one scalp electroencephalographic (EEG) electrode and the power in the alpha frequency band. The second one uses sixteen scalp EEG electrodes and machine learning methods. The role of muscular activity is also evaluated using five electrodes positioned on the face and the neck. Results show that the first design enabled 70% of the participants to successfully control the game, whereas 100% of the participants managed to do it with the second design based on machine learning. Subjective questionnaires confirm these results: users globally felt to have control in both designs, with an increased feeling of control in the second one. Offline analysis of face and neck muscle activity shows that this activity could also be used to distinguish between relaxation and concentration tasks. Results suggest that the combination of muscular and brain activity could improve performance of this kind of system. They also suggest that muscular activity has probably been recorded by EEG electrodes.
On the Gaussian Z-Interference Channel with Processing Energy Cost
Venue: arXiv cs.IT 2011
Year: 2011

This work considers a Gaussian interference channel with processing energy cost, which explicitly takes into account the energy expended for processing when each transmitter is on. With processing overhead, bursty transmission at each transmitter generally becomes more advantageous. Assuming on-off states do not carry information, for a two-user Z-interference channel, the new regime of very strong interference is identified and shown to be enlarged compared with the conventional one. With the interfered receiver listening when its own transmitter is silent, for a wide range of cross-link power gains, one can either achieve or get close to the interference-free upper bound on sum rate.
Representations and Ensemble Methods for Dynamic Relational Classification
Venue: arXiv cs.AI 2011
Year: 2011

Temporal networks are ubiquitous and evolve over time by the addition, deletion, and changing of links, nodes, and attributes. Although many relational datasets contain temporal information, the majority of existing techniques in relational learning focus on static snapshots and ignore the temporal dynamics. We propose a framework for discovering temporal representations of relational data to increase the accuracy of statistical relational learning algorithms. The temporal relational representations serve as a basis for classification, ensembles, and pattern mining in evolving domains. The framework includes (1) selecting the time-varying relational components (links, attributes, nodes), (2) selecting the temporal granularity, (3) predicting the temporal influence of each time-varying relational component, and (4) choosing the weighted relational classifier. Additionally, we propose temporal ensemble methods that exploit the temporal-dimension of relational data. These ensembles outperform traditional and more sophisticated relational ensembles while avoiding the issue of learning the most optimal representation. Finally, the space of temporal-relational models are evaluated using a sample of classifiers. In all cases, the proposed temporal-relational classifiers outperform competing models that ignore the temporal information. The results demonstrate the capability and necessity of the temporal-relational representations for classification, ensembles, and for mining temporal datasets.
The Management and Use of Social Network Sites in a Government Department
Venue: arXiv cs.SI 2011
Year: 2011

In this paper we report findings from a study of social network site use in a UK Government department. We have investigated this from a managerial, organisational perspective. We found at the study site that there are already several social network technologies in use, and that these: misalign with and problematize organisational boundaries; blur boundaries between working and social lives; present differing opportunities for control; have different visibilities; have overlapping functionality with each other and with other information technologies; that they evolve and change over time; and that their uptake is conditioned by existing infrastructure and availability. We find the organisational complexity that social technologies are often hoped to cut across is, in reality, something that shapes their uptake and use. We argue the idea of a single, central social network site for supporting cooperative work within an organisation will hit the same problems as any effort of centralisation in organisations. We argue that while there is still plenty of scope for design and innovation in this area, an important challenge now is in supporting organisations in managing what can best be referred to as a social network site 'ecosystem'.
A class of punctured simplex codes which are proper for error detection
Venue: arXiv cs.IT 2011
Year: 2011

Binary linear [n,k] codes that are proper for error detection are known for many combinations of n and k. For the remaining combinations, existence of proper codes is conjectured. In this paper, a particular class of [n,k] codes is studied in detail. In particular, it is shown that these codes are proper for many combinations of n and k which were previously unsettled.